<p>There are indeed other restrictions on <span class="math-container">$P$</span> that relate this problem to GI. For example, if one requires that <span class="math-container">$P$</span> be a Kronecker (tensor) product <span class="math-container">$P_1 \otimes P_2 \otimes P_3$</span>, then the resulting problem is TI-complete [<a href="https://dx.doi.org/10.4230/LIPIcs.ITCS.2021.31" rel="nofollow noreferrer">G-Qiao</a>], which is at least as hard as Linear Code Equivalence, which in turn is GI-hard (but not known to be equivalent to GI).</p>
<p>Another viewpoint on your question, which may shed some light on the general situation, is as follows. For any group action of <span class="math-container">$G_n$</span> on a set <span class="math-container">$X_n$</span> (one for each <span class="math-container">$n$</span>), one can ask about the complexity of deciding if two given points <span class="math-container">$x,y \in X_n$</span> are in the same <span class="math-container">$G_n$</span>-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 <em>linear</em> action of a group <span class="math-container">$G_n$</span> on a vector space <span class="math-container">$V_n$</span>, consider the orbit problem of the <em>induced</em> action of <span class="math-container">$G_n$</span> (by conjugation) on <span class="math-container">$X_n = V_n \otimes (V_n)^*$</span>.</p>
<p>For graph isomorphism we have <span class="math-container">$G_n = S_n$</span> and <span class="math-container">$V_n = \mathbb{R}^n$</span> with the natural action by permuting coordinates. For matrix conjugation we have <span class="math-container">$G_n = \text{GL}_n(\mathbb{F})$</span> in its natural action on <span class="math-container">$V_n = \mathbb{F}^n$</span>. For the above example we have <span class="math-container">$G_n = \text{GL}_a \times \text{GL}_b \times \text{GL}_c$</span> in its natural action on <span class="math-container">$V_n = \mathbb{F}^{a} \otimes \mathbb{F}^b \otimes \mathbb{F}^c$</span>.</p>

CC BY-SA 4.0
2014-10-07T19:34:06.737Z
2021-11-19T08:15:08.043Z
2021-11-19T08:15:08.043Z
Joshua Grochow
<p>Matrices <i>A</i> and <i>B</i> whose elements are in a field <i>F</i> are similar (in <i>F</i>) if and only if they have the same <a href="http://en.wikipedia.org/wiki/Frobenius_normal_form">Frobenius normal form</a>.  According to a quick search, it seems that the Frobenius normal form of an <i>n</i>×<i>n</i> matrix can be computed with O(<i>n</i><sup>3</sup>) field operations [Sto98], and that this can be improved to something comparable to the complexity of matrix multiplication [Sto01].</p>

<p>[Sto98] Arne Storjohann.  An O(<i>n</i><sup>3</sup>) algorithm for the Frobenius normal form.  In <em>Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation (ISSAC)</em>, pp. 101–105, Aug. 1998.  DOI: <a href="http://dx.doi.org/10.1145/281508.281570">10.1145/281508.281570</a>.</p>

<p>[Sto01] Arne Storjohann.  Deterministic computation of the Frobenius form.  In <em>42nd IEEE Symposium on Foundations of Computer Science (FOCS)</em>, pp. 368–377, Oct. 2001.  DOI: <a href="http://dx.doi.org/10.1109/SFCS.2001.959911">10.1109/SFCS.2001.959911</a>.</p>

CC BY-SA 3.0
2012-09-21T12:14:18.323Z
2012-09-21T12:14:18.323Z
Tsuyoshi Ito
<p>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 <code>GI</code>(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 <code>GI</code> or other hard problems?</p>

CC BY-SA 3.0
2012-09-21T13:29:04.613Z
Maybe I should have asked this before posting an answer, but what did you try before posting this question here?
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-22T08:13:13.600Z
@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
CC BY-SA 3.0
2012-09-22T11:09:12.360Z
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
CC BY-SA 3.0
2012-09-22T15:57:23.207Z
I will be careful next time onwards. Thank you.
DurgaDatta
<ds.algorithms><time-complexity><linear-algebra><matrices><graph-isomorphism>
similar matrices
DurgaDatta
# similar matrices

(Asked by: username_0 on 2012-09-21)

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?

**Tags:** ds.algorithms, time-complexity, linear-algebra, matrices, graph-isomorphism
> **Comments:**
> **username_1**: Maybe I should have asked this before posting an answer, but what did you try before posting this question here?  
> **username_0**: @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.  
> **username_1**: 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.  
> **username_0**: I will be careful next time onwards. Thank you.  

---

## 2 answers

### Answer by username_1 on 2012-09-21. Score: 14 | Accepted answer

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](http://en.wikipedia.org/wiki/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*3) 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*3) 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](http://dx.doi.org/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](http://dx.doi.org/10.1109/SFCS.2001.959911).


---

### Answer by username_2 on 2014-10-07. Score: 6

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](https://dx.doi.org/10.4230/LIPIcs.ITCS.2021.31)], 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$.


---

