2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The matrices A and B of order 36 here are normal and cospectral. I'm not sure whether they are orthogonal similar. $\endgroup$ – LeechLattice Aug 29 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$ – Ken W. Smith Aug 29 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 at 20:49
  • $\begingroup$ @Bullet51. Thanks for the example. I need to check for the orthogonal similarity. $\endgroup$ – Sirolf Aug 29 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 at 20:57
4
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.