<s>[INST] 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?
 [/INST] 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)$.
</s>