16
$\begingroup$

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?

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

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.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

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.