**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](https://math.stackexchange.com/q/2002020) 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](https://mathoverflow.net/q/151853) 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?



Two cospectral (normal) digraphs which are not orthogonal similar
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)$.


