# Showing two graphs isomorphic using their adjacency matrices

I don't know how to solve the following problem:

Show that two simple graphs $G$ and $H$ are isomorphic if and only if there exists a permutation matrix $P$ such that $A_G=PA_HP^t$.

Here $A$ is the adjacency matrix. I have a feeling this shouldn't be very difficult, but my linear algebra is not very good, am I missing something obvious?

-
Multiplying by $P$ on the left permutes the rows of the matrix. Multiplying by $P^t$ on the right permutes the columns. The important thing here is that the two permutations are the same if you think of them as acting on indices. There is hardly any linear algebra needed, just chasing definitions. –  Harald Hanche-Olsen Mar 15 '13 at 14:17
You probably mean $A_G=PA_HP^t$. –  Brian M. Scott Mar 15 '13 at 14:18
@BrianM.Scott Yes of course, thank you. –  hannahh Mar 16 '13 at 6:56

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)$.

-