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?

  • $\begingroup$ Maybe I should have asked this before posting an answer, but what did you try before posting this question here? $\endgroup$ Sep 21, 2012 at 13:29
  • $\begingroup$ @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. $\endgroup$
    – DurgaDatta
    Sep 22, 2012 at 8:13
  • $\begingroup$ 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. $\endgroup$ Sep 22, 2012 at 11:09
  • $\begingroup$ I will be careful next time onwards. Thank you. $\endgroup$
    – DurgaDatta
    Sep 22, 2012 at 15:57

2 Answers 2


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(n3) field operations [Sto98], and that this can be improved to something comparable to the complexity of matrix multiplication [Sto01].

[Sto98] Arne Storjohann. An O(n3) 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.


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.