0
$\begingroup$

Suppose you have two adjacency matrices $A$ and $B$ of cospectral but non-isomorphic graphs. Is there a matrix $Q$ such that $$A=Q^{-1}BQ$$ holds?

Note if $A$ and $B$ are not cospectral we cannot have a $Q$ such that $$A=Q^{-1}BQ$$ holds.

$\endgroup$
1
$\begingroup$

Two real symmetric matrices are similar if and only if they have the same characteristic polynomial. So if two graphs are cospectral, their adjacency matrices must be similar.

$\endgroup$
  • $\begingroup$ what of i interpret adjacencies as in $\Bbb F_p$? $\endgroup$ – T.... Jan 2 '16 at 9:59
  • $\begingroup$ @Turbo: in finite characteristic, having the same characteristic polynomial does not imply similarity. In this case $A$ and $B$ are similar if and only if $tI-A$ and $tI-B$ have the same Smith normal form. $\endgroup$ – Chris Godsil Jan 2 '16 at 18:05
1
$\begingroup$

Since you assume A and B are co-spectral adjacency matrices, they are real symmetric matrices with spectral decompositions $$A= X^{-1} \Lambda X $$ and $$B=Y^{-1} \Lambda Y$$ where $X$ and $Y$ are orthogonal matrices and $\Lambda$ is a diagonal matrix with the eigenvalues on the diagonal.

Then $Q=Y^{-1}X$ is your desired matrix.

$\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.