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?
 A: 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.]
A: 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.
A: You cannot make a conclusion by matching just rows or just columns of two graph's adjacency independently. What you need to do is to match both rows and columns after some permutation. So the conclusion is whether or not there is a permutation matrix $P$ which meets $A=PBP^{T}$ where $A$ and $B$ is the adjacency of two graphs, $P$ is the permutation matrix where it has just a single 1 on each row's and columns, rest of them is zero. So the complexity by brutal force is $n!$ which is ridiculously high. What all literature on graph isomorphism is to decrease this complexity to the linear if it is possible.
