similar matrices

Question

Given two $n \times n$ matrices $A$ and $B$, the problem of deciding if there exist a permutation matrix $P$ such that $B = P^{-1}AP$ is equivalent to GI(Graph Isomorphism). But if we relax $P$ to be just an invertible matrix, then what is the complexity? Are there any other restrictions on an invertible matrix $P$, apart from being a permutation, that relate this problem to GI or other hard problems?

Answer 1

Matrices A and B whose elements are in a field F are similar (in F) if and only if they have the same Frobenius normal form. According to a quick search, it seems that the Frobenius normal form of an n×n matrix can be computed with O(n³) field operations [Sto98], and that this can be improved to something comparable to the complexity of matrix multiplication [Sto01].

[Sto98] Arne Storjohann. An O(n³) algorithm for the Frobenius normal form. In Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 101–105, Aug. 1998. DOI: 10.1145/281508.281570.

[Sto01] Arne Storjohann. Deterministic computation of the Frobenius form. In 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 368–377, Oct. 2001. DOI: 10.1109/SFCS.2001.959911.

Answer 2

There are indeed other restrictions on $P$ that relate this problem to GI. For example, if one requires that $P$ be a Kronecker (tensor) product $P_1 \otimes P_2 \otimes P_3$, then the resulting problem is TI-complete [G-Qiao], which is at least as hard as Linear Code Equivalence, which in turn is GI-hard (but not known to be equivalent to GI).

Another viewpoint on your question, which may shed some light on the general situation, is as follows. For any group action of $G_n$ on a set $X_n$ (one for each $n$), one can ask about the complexity of deciding if two given points $x,y \in X_n$ are in the same $G_n$-orbit; call this the orbit problem for that (family of) action(s). Your question is then essentially about the complexity of the orbit problems that can be phrased as follows: given a linear action of a group $G_n$ on a vector space $V_n$, consider the orbit problem of the induced action of $G_n$ (by conjugation) on $X_n = V_n \otimes (V_n)^*$.

For graph isomorphism we have $G_n = S_n$ and $V_n = \mathbb{R}^n$ with the natural action by permuting coordinates. For matrix conjugation we have $G_n = \text{GL}_n(\mathbb{F})$ in its natural action on $V_n = \mathbb{F}^n$. For the above example we have $G_n = \text{GL}_a \times \text{GL}_b \times \text{GL}_c$ in its natural action on $V_n = \mathbb{F}^{a} \otimes \mathbb{F}^b \otimes \mathbb{F}^c$.