Suppose two graphs have adjacency matrix representations $A_1$ and $A_2$ and we want to see if they are isomorphic (assume all graphs here are not directed, so adjacency matrices are symmetric).
It is a well know result that two graphs are isomorphic if and only if there exists some permutation matrix $P$ such that
$$
PA_1P^{-1} = A_2.
$$
I am trying to gain intuition into why this is the case and what the implications are. Specifically my question is, suppose we had two graphs represented through adjacency matrices $B_1, B_2$ (and are hence binary, symmetric matrices), and these two graphs were not isomorphic. Then as by the above stated result, we know there does not exist a permutation matrix $P$ such that $PB_1P^{-1} = B_2$, but could there exists permutation matrices $P_1, P_2$ where $P_2 \not=P_1^{-1}$ such that $P_1B_1P_2 = B_2$?
My intuition tells me "no" because permuting $B_1$ by two different permutations matrices in such a way will not in general leave the resulting matrix symmetric, but I could be wrong.
Best Answer
Suppose $P_1 B_1 P_2 = B_2$. Then $B' = P_1 B_1 P_1^{-1}$ is the adjacency matrix of a graph isomorphic to the first graph, and $P' = P_1 P_2$ is another permutation matrix; we have $B' P' = (P_1 B_1 P_1^{-1}) (P_1 P_2) = B_2$.
The matrix multiplication $B' P'$ permutes only the columns of $B'$. So the question is: when does permuting the columns of an adjacency matrix give the adjacency matrix of a different, non-isomorphic graph?
To understand this deeply unnatural operation, it helps to think of our graphs as directed graphs that merely happen to be symmetric: whenever there is an arc $u \to v$, there is also an arc $v \to u$. The directed adjacency matrix $A$ (which coincides with the undirected adjacency matrix, under this interpretation of all graphs as directed graphs) has $A_{ij} = 1$ whenever there is an arc $i \to j$. Permuting the columns of the matrix is a directed graph operation: we pick a permutation $\sigma$ of the vertices, and permute the ends of every arc in the graph according to $\sigma$, leaving the starts where they are.
It is rare for this to produce another undirected graph (because in general, permuting the columns of a symmetric matrix does not leave it symmetric). But there are examples where it happens.
One nice place to look for these examples is in circulant graphs. An $n$-vertex circulant graph is specified by several values $a_1, a_2, \dots, a_k$ between $1$ and $\frac n2$. The vertices $1, 2, \dots, n$ are arranged in a circle, and two vertices are adjacent if they are $a_i$ steps apart around the circle for some $i$.
Here, if $n$ is even and $\frac n2$ is not one of the $a_i$, let $\sigma$ be the permutation that swaps opposite vertices, and permute the columns of the adjacency matrix according to $\sigma$. We turn a circulant graph with parameters $a_1, a_2, \dots, a_k$ into another undirected graph: a circulant graph with parameters $\frac n2 - a_1, \frac n2 - a_2, \dots, \frac n2 - a_k$. Sometimes this is an isomorphic graph to the original, but usually it's not. For example, the cycle graph $C_6$, a circulant graph with $k=1$ and $a_1 = 1$, turns into a circulant graph with $k=2$ and $a_1 = 2$, which is the disjoint union of two $C_3$'s.