If the the adjacency matrix of a graph uniquely determines it up to isomorphism, then why is the isomorphism famous?

Question

I hear about "The Graph Isomorphism Problem", and am a bit confused as to where the issue is. Isn't the adjacency matrix ( up to permutation ) unique for a graph up to isomorphism? Can't the problem be solved as easily as checking if two graphs have the same matrix up to permutations?

Answer 1

The problem is equivalent to check if two graphs have the same adjacency matrix up to permutations (that is, if $A_1 = P^{-1}A_2 P$ for some permutation matrix $P$). But that's not easy.

To start with, maybe you should look at an example: $$ \begin{bmatrix} 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ \end{bmatrix} \qquad \begin{bmatrix} 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ \end{bmatrix} $$ Can you turn one matrix into the other? How do you tell? You probably shouldn't try all $8!$ permutation matrices, one at a time. But you also can't notice any useful features just by looking. (For small examples like this one, the representation as a graph diagram is probably more useful than the adjacency matrix.)

This is not to say that adjacency matrices aren't helpful to look at. For example, we can look at their eigenvalues; the first matrix has eigenvalues $$3,\frac{1}{2} \left(-\sqrt{17}-1\right),\frac{1}{2} \left(-\sqrt{5}-1\right),\frac{1}{2} \left(-\sqrt{5}-1\right),\frac{1}{2} \left(\sqrt{17}-1\right),\frac{1}{2} \left(\sqrt{5}-1\right),\frac{1}{2} \left(\sqrt{5}-1\right),0$$ and the second has eigenvalues $$3,-\sqrt{2}-1,-\sqrt{3},\sqrt{3},-1,-1,1,\sqrt{2}-1$$ so they are not isomorphic. But this is not a foolproof method; it works most of the time, but the graph isomorphism problem was already easy most of the time, it's just hard in highly symmetric cases. Non-isomorphic graphs do exist whose adjacency matrices have the same eigenvalues.