2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Sal Apr 24 '18 at 14:26
1
$\begingroup$

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."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.