# similar matrices

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?

• Maybe I should have asked this before posting an answer, but what did you try before posting this question here? – Tsuyoshi Ito Sep 21 '12 at 13:29
• @TsuyoshiIto I tried in wikipdia and mathworld, also tried some search query in google, is this question too elementary to be asked here? I was more interested if some variant of this problem would give some insights for GI. – DurgaDatta Sep 22 '12 at 8:13
• Thanks. I think that the level of the question is fine, but I just wondered why you did not reach the same conclusion as me. What I did to write the answer is just looking up “matrix similarity” in Wikipedia to find a normal form which can be computed easily (unlike Jordan normal form, which requires algebraically closed field). I think that you could have found the same information if you had looked at Wikipedia more carefully. – Tsuyoshi Ito Sep 22 '12 at 11:09
• I will be careful next time onwards. Thank you. – DurgaDatta Sep 22 '12 at 15:57

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 as hard as equivalence of 3-valent tensors, which is roughly the same complexity as Linear Code Equivalence, which in turn is known to be 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$.