# Similar adjacency matrices of the same graph

I am able to represent a simple graph on $n$ vertices by at most $n!$ different adjacency matrices. Do all of the adjacency matrices corresponding to the same graph have the same spectrum or are they similar?

Adjacency matrices $A$ and $B$ represent isomorphic graphs if and only if there is a permutation matrix $P$ such that $B=P^TAP$. Since permutation matrices are orthogonal, $P^T=P^{-1}$ and so the matrices $A$ and $B$ are similar.
• In my case,among the $n!$ adjacency matrices representing the same simple graph ,take $A$ and $B$ e.g., how are we sure that we can find a permutation matrix st $B$=$P^T$$A$$P$? – Sal Apr 24 '18 at 14:26