# Why isn't an adjacency matrix a graph invariant?

When working out if two graphs are isomorphic, why can't you use an adjacency matrix and match each pattern of row or column to the other graph's matrix?

The patterns seem to match up and everything works but obviously the answer is wrong; can you not do this?

-
The adjacency matrix is different depending on how you order the nodes. Obviously, if your graphs are isomorphic and you order the nodes properly, you'll get the same matrix, but if you don't know whether they are isomorphic, different orders of nodes give different matrices. – Thomas Andrews Dec 28 '11 at 17:58
if you consider the adjacency matrix up to conjugation by a permutation, it is an invariant (ie relabeling of vertices). – yoyo Dec 28 '11 at 17:58
There is nothing wrong with the approach in principle. But one has to test all permutations. However, easily computed matrix invariants can be used to rule out isomorphism in many cases. – André Nicolas Dec 28 '11 at 18:01
Is there a easy way to work out if they are isomorphic? Can you show me or link me to the "easily computed matrix invariants"? I'm studying for my exams and am having troubling identifying which vertex is which when they are isomorphic. – orange Dec 28 '11 at 18:05
There are plenty of matrix invariants, but they don't do a good job of proving isomorphism, just ruling out isomorphism. For example, the characteristic polynomial of the adjacency matrix is an invariant, but it isn't "faithful." That is, if $G$ and $G'$ are graphs, then the characteristic polynomial of their adjacencies will be the same if they are isomorphic, but if the polynomials are the same, they are not necessarily isomorphic. – Thomas Andrews Dec 28 '11 at 18:14

The matrices:

$$\left(\begin{matrix} 0&0&1&1 \\ 0&0&1&1 \\ 1&1&0&0 \\ 1&1&0&0\end{matrix}\right)$$

and:

$$\left(\begin{matrix} 0&1&0&1 \\ 1&0&1&0 \\ 0&1&0&1 \\ 1&0&1&0\end{matrix}\right)$$

Are incidence matrices for isomorphic graphs.

[As commenter Chris Godsil below has noted, these are adjacency matrices, not incidence matrices, but the same thing applies for incidence matrices.]

-
Can you explain more please? So for these two graphs how can you use the incidence matrices to show they are isomorphic? - cl.ly/3s2Y2F231X0X3I174628 – orange Dec 28 '11 at 18:13
My point is that the incidence matrices are not the same for isomorphic graphs - which means that it is not an invariant. – Thomas Andrews Dec 28 '11 at 18:16
I see, is there an easy way to work out if they are isomorphic and easy way to state which vertex on graph G belongs to vertex on graph H? – orange Dec 28 '11 at 18:18
Surprisingly, that's an open question. Graph isomorphism is in NP, but nobody knows whether it's P or whether it's NP-complete. – Lopsy Dec 28 '11 at 18:24
These are not incidence matrices, they are adjacency matrices. (The incidence matrix has rows indexed by vertices and columns indexed by edges, so usually it is not square. – Chris Godsil Dec 29 '11 at 0:39

The adjacency matrix itself is not a graph invariant, because it is not invariant under relabeling of the nodes of the graph. Let $B_{n}$ be the set of symmetric, zero-diagonal, $n\times n$ binary matrices. Then the simple graphs on $[n]=\{1,2,...,n\}$ are in a one-to-one correspondence with the elements of $B_n$: take the adjacency matrix of the graph to get its representative in $B_n$. Permutations of the node labels act as follows: for $\pi\in S_{n}$ and $X=(X_{ij})\in B_{n}$, we have $(\pi\cdot X)_{ij}=X_{\pi^{-1}(i),\pi^{-1}(j)}$. The operations $\langle S_{n},\cdot \rangle$ define an equivalence relation on $B_{n}$; and the elements $[X]$ of the quotient $B_{n}/\langle S_{n},\cdot \rangle$ are the desired graph invariants: $G$ and $H$ are isomorphic if and only if their adjacency matrices satisfy $[A(G)]=[A(H)]$.

The problem becomes one of finding a canonical representative for each element of $B_{n}$, or otherwise testing whether any two elements of $B_{n}$ are in the same equivalence class. For instance, one could choose the lexicographically smallest element of the orbit $S_{n}\cdot X$ as the representative of $[X]$ for each equivalence class. The problem with this approach is that the orbit can have size $n!$. Clearly it can be done; but the open question is whether it can be done efficiently. The equivalence-testing problem is not currently known to be NP-hard (and hence NP-complete, since clearly it is in NP); but neither is any polynomial-time algorithm known.

-