Similar adjacency matrices of the same graph

Question

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?

Answer 1

They should have the same spectrum. I quote from the following book [Machine Learning in Complex Networks, By Thiago Christiano Silva, Liang Zhao]; "While the adjacency matrix depends on the vertex labeling or ordering, its spectrum is graph invariant."

Answer 2

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.