Two cospectral (normal) digraphs which are not orthogonal similar

Question

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?

Answer 1

Two normal digraphs with the same characteristic polynomial are orthogonally similar. So no counter example can exist.

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