# Are cospectral/non-cospectral non-isomorphic graphs similar?

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.

• what of i interpret adjacencies as in $\Bbb F_p$? – T.... Jan 2 '16 at 9:59
• @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. – Chris Godsil Jan 2 '16 at 18:05
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.