Showing two graphs isomorphic using their adjacency matrices

Solution 1:

Here’s an example that may get you thinking in the right direction. Consider $PAP^t$, where $P$ is the permutation matrix

$$\begin{bmatrix} 0&0&0&1\\ 1&0&0&0\\ 0&0&1&0\\ 0&1&0&0 \end{bmatrix}$$

and, as an illustrative example,

$$A=\begin{bmatrix} 1&2&3&4\\ 2&3&4&5\\ 0&1&2&3\\ 3&2&1&0 \end{bmatrix}\;.$$

We have

$$PA=\begin{bmatrix} 0&0&0&1\\ 1&0&0&0\\ 0&0&1&0\\ 0&1&0&0 \end{bmatrix} \begin{bmatrix} 1&2&3&4\\ 2&3&4&5\\ 0&1&2&3\\ 3&2&1&0 \end{bmatrix}= \begin{bmatrix} 3&2&1&0\\ 1&2&3&4\\ 0&1&2&3\\ 2&3&4&5 \end{bmatrix}\;, $$

and then

$$ PAP^t=\begin{bmatrix} 3&2&1&0\\ 1&2&3&4\\ 0&1&2&3\\ 2&3&4&5 \end{bmatrix} \begin{bmatrix} 0&1&0&0\\ 0&0&0&1\\ 0&0&1&0\\ 1&0&0&0 \end{bmatrix}= \begin{bmatrix} 0&3&1&2\\ 4&1&3&2\\ 3&0&2&1\\ 5&2&4&3 \end{bmatrix}\;. $$

The first row of $A$ is the second row of $PAP^t$, and the first column of $A$ is the second column of $PAP^t$. The second row and second column of $A$ are the fourth row and column of $PAP^t$. The fourth row and column of $A$ are the first row and column of $PAP^t$. And the third row and column of $A$ are still the third row and column of $PAP^t$. In other words, both the rows and columns have been permuted by the permutation $(1,2,4)$ in cycle notation or

$$\pmatrix{1&2&3&4\\2&4&3&1}\tag{1}$$

in two-line notation. If $A$ is the adjacency matrix of a graph, $PAP^t$ is just the adjacency matrix of the same graph after the vertices have been renumbered according to the permutation $(1)$.