# Two cospectral (normal) digraphs which are not orthogonal similar

Preliminaries

A complex matrix $$A$$ is normal when $$A$$ and $$A^*$$ commute. A real matrix $$A$$ is normal when $$A$$ and $$A^t$$ commute.

Two complex matrices $$A$$ and $$B$$ are said to be unitary similar if there exists a unitary matrix $$U$$ such that $$A\cdot U=U\cdot B$$. Two real matrices $$A$$ and $$B$$ are orthogonal similar if there exists a (real) orthogonal matrix $$O$$ such that $$A\cdot O=O\cdot B$$.

When $$A$$ and $$B$$ are complex normal matrices then $$A$$ and $$B$$ are unitary similar if and only if $$A$$ and $$B$$ have the same characteristic polynomial (see e.g., this post).

Let $$A$$ and $$B$$ be real normal matrices. If $$A$$ and $$B$$ are orthogonal similar then $$A$$ and $$B$$ have the same characteristic polynomial. The converse does not hold, however, since $$A$$ and $$B$$ may have complex eigenvalues and unitary rather than orthogonal matrices are needed.

Question I would like to have an graph-based example showing that having the same characteristic polynomial does not suffice for orthogonal similarity.

More precisely, call a directed graph $$G=(V,E)$$ normal if its adjacency matrix $$A_G$$ is normal.

Normal directed graphs are necessarily balanced, i.e., the in-degree of each vertex is equal to its out-degree (see e.g., this post).

So, what are examples of two normal (and thus balanced) graphs $$G$$ and $$H$$ (consisting of the same number of vertices) whose adjacency matrices have the same characteristic polynomial yet are not related by means of an orthogonal similarity?

• The matrices A and B of order 36 here are normal and cospectral. I'm not sure whether they are orthogonal similar. – LeechLattice Aug 29 at 15:11
• How do I know two matrices are {\em not} orthogonal similar? That is, what properties of a matrix are invariant under orthogonal similarity -- besides the characteristic polynomial -- that I could use to separate cospectral graphs? – Ken W. Smith Aug 29 at 19:46
• @KenW.Smith: Orthogonal similarity of two $n\times n$ matrices $A$ and $B$ is equivalent to checking whether $tr(w(A,A^*))=tr(w(B,B^*)$ for all words $w(x,y)$ of length at most $n^2$. (real version of Specht's Theorem). – Sirolf Aug 29 at 20:49
• @Bullet51. Thanks for the example. I need to check for the orthogonal similarity. – Sirolf Aug 29 at 20:54
• @Chris: sure, but for normal complex matrices this implication holds. I am not sure whether it holds for real normal matrices, that's why the question. – Sirolf Aug 29 at 20:57

Let $$A$$ and $$B$$ two real normal matrices. From the comment above, it suffices to check that $$tr(w(A,A^t))=tr(w(B,B^t))$$ holds for all words $$w(x,y)$$. Since $$A$$ and $$A^t$$ commute (because of $$A$$ being norma) we may assume $$w(A,A^*)$$ to be of the form $$(A^t)^k\cdot A^\ell$$ for some $$k$$ and $$\ell$$. We can further diagonalize $$A$$ (again using normality) by means of a unitary matrix $$U$$, i.e., $$A=U\cdot \Delta_A\cdot U^*$$ where $$\Delta_A$$ is a diagonal matrix with $$A$$'s (possibly complex) eigenvalues $$\lambda_1,\ldots,\lambda_n$$ on its diagonal. Note also that $$A^t=U\cdot\Delta_A\cdot U^*$$ (for normal matrices, an eigenvector of $$A$$ is an eigenvector of $$A^t$$ for the same eigenvalue and $$U$$ may be assumed to consist of eigenvectors). Using properties of trace and $$U\cdot U^*=I=U^*\cdot U$$: \begin{align*} tr((A^t)^k\cdot A^\ell)&=tr(I\cdot (A^t)^k\cdot I\cdot A^\ell)\\ &=tr(U\cdot U^*\cdot (A^t)^k\cdot U\cdot U^*\cdot A^k)\\ &=tr(U^*\cdot (A^t)^k\cdot U\cdot U^*\cdot A^k\cdot U)\\ &=tr((\Delta_A)^k\cdot\Delta_A^\ell)\\ &=\sum_{i=1}^n \lambda_i^{k+\ell}. \end{align*} Since $$A$$ and $$B$$ are assumed to have the same characteristic polynomial, $$tr((B^t)^k\cdot B^\ell)=\sum_{i=1}^n \lambda_i^{k+\ell}$$ as well. Hence, repeating this for every word $$w(x,y)$$, $$tr(w(A,A^t))=tr(w(B,B^t))$$ holds for all words $$w(x,y)$$.