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

-
Hi @Brian M. Scott I am also working on this question. I am confused on how to proceed from here. I am trying to prove the if direction and so I have the isomorphism, but how do I build the permutation matrix out of that? I think my teacher actually wants us to construct the matrix. – H_B May 31 '15 at 20:55
@H_B: If you have the isomorphism, then you have the permutation of the vertices corresponding to $(1)$ in my answer. Apply that permutation to the rows of the $n\times n$ identity matrix (where $n$ is the number of vertices), and you’ll have the permutation matrix $P$. – Brian M. Scott May 31 '15 at 21:07
I am sorry but I am still confused. Say I have drawn the house graph in two different ways $G_1$ and $G_2$, and I label the vertices $1,2,3,4,5$ and $a,b,c,d,e$ and I have the isomorphism $\{(1,d),(2,a),(3,c),(4,b),(5,e)\}$. How would I then do what you explained? – H_B May 31 '15 at 21:21
@H_B: Replace $a,b,c,d,e$ with $1,2,3,4,5$, respectively, so that you’re using the same set of labels for both graphs. Now your permutation analogous to $(1)$ is $$\pmatrix{1&2&3&4&5\\4&1&3&2&5}\;,$$ since $dacbe$ is now $41325$. – Brian M. Scott May 31 '15 at 21:26
I see I see! The renaming was my hangup. Ok so now I understand how could I formally prove it? I am confused on how I should even get started. – H_B May 31 '15 at 21:33