How can you show that 2 (adjacency) matrices are isomorphic?

Question

Would you do it by showing that elementary matrix operations can be used to get from one matrix to the other? If not, how would you show that 2 adjacency matrices are isomorphic?

Answer 1

Adjacency matrices $A$ and $B$ are isomorphic graphs iff there exists a permutation matrix $S$ such that $A = SBS^{-1}$. This doesn't necessarily help you decide if the two are isomorphic, since you still would have to check all $n!$ permutations. However, it gives lots of easy ways to detect when $A$ and $B$ are not isomorphic, because this implies that they are similar by a unitary matrix. For example:

• If $\det A \ne \det B$ then they are not isomorphic.

• If $\text{Tr } A^m \ne \text{Tr } B^m$ then they are not isomorphic.

• Any other property that depends only on $A, B$ being linear maps on an inner product space of dimension $n$, and not on the specific orthonormal basis chosen.

---

Computationally speaking, deciding when two adjacency matrix are isomorphic is equivalent to showing two graphs are isomorphic, and is a famous problem since it is not known to be either in $P$ or be $NP$-complete. However, there is currently a potential breakthrough showing that it can be solved in "quasipolynomial time", that is to say, in time equal to $2^{P(\log n)}$ where $P$ is a polynomial.