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?

  • $\begingroup$ The matrices A and B of order 36 here are normal and cospectral. I'm not sure whether they are orthogonal similar. $\endgroup$ Aug 29, 2019 at 15:11
  • $\begingroup$ 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? $\endgroup$ Aug 29, 2019 at 19:46
  • 3
    $\begingroup$ @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). $\endgroup$
    – Sirolf
    Aug 29, 2019 at 20:49
  • $\begingroup$ @Bullet51. Thanks for the example. I need to check for the orthogonal similarity. $\endgroup$
    – Sirolf
    Aug 29, 2019 at 20:54
  • $\begingroup$ @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. $\endgroup$
    – Sirolf
    Aug 29, 2019 at 20:57

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

  • 1
    $\begingroup$ This seems correct, should have spotted this myself. Thanks! $\endgroup$
    – Sirolf
    Aug 30, 2019 at 8:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .