signs of eigenvalues

Question

Let $\Gamma$ be a multiple edge free (di)graph (with or without loop). Let $A$ be its adjacency matrix. It is clear that if $\lambda^2$ is an eigenvalue of $A^2$, then $\lambda$ or $-\lambda$ is an eigenvalue of $A$. What can we say about sign of $\lambda$ in general? I mean that can we exactly determine sign of eigenvalues of $A$ from eigenvalues of $A^2$?

Answer 1

Just to build on the answer which Chris gave, one can replace two disjoint copies $K_3$ with two disjoint copies of any graph $G$ (which is not bipartite, just to keep things simple). Let the vertices of $G$ be numbered $0,1,\cdots,v-1.$ Now make two graphs $G_1$ (not bipartite) and $G_2$ (bipartite) with vertex sets $0,1,\cdots,2v-1$ and matrices $A_1$ and $A_2$. For each edge $(i,j)$ of $G$ add edges $(i,j)$ and $(i+v,j+v)$ to $G_1$ and also edges $(i,j+v)$ and $(i+v,j)$ to $G_2.$ With this numbering we have $A_1^2=A_2^2$ so even knowing the exact matrix $A^2$ does not tell you the eigenvalues of $A$.

If the largest eigenvalue of $A^2$ is $\alpha$ with multiplicity $m$ then $A$ has eigenvalue $+\sqrt{\alpha}$ with multiplicity at least $\frac{m}2.$

If we do not allow loops then we do know that the sum (with multiplicities) of the eigenvalues is $0$.

Here are a couple of explicit variations of the example above which easily generalize (in case you don't want disconnected graphs or don't want a purely bipartite graph). If numbered correctly, they also preserve the $A_1^2=A_2^2$ feature (or $A_1^2=A_2^2=A_3^2$ in the second.)

• Add a seventh vertex connected to each of the six others. Then the eigenvalues are $[1+\sqrt{7},1-\sqrt{7},2,-1,-1,-1,-1]$ for two copies of $K_3$ but $[1+\sqrt{7},1-\sqrt{7},-2,1,1,-1,-1]$ for $K_6$

• Here are three different graphs each with $12$ vertices and every one of the first $6$ connected to every one of the second $6$: For the first and second sets of $6$ vertices put in edges to make two copies of $K_3$ in each OR $K_6$ in each OR $K_6$ for one and two copies of $K_3$ for the other. Then the eigenvalues are $[ 8,-4,2,2,-1^{8}]$ OR $[8,-4,-2,-2,1^4,-1^4 ]$ OR $[8,-4,2,-2,1^4,-1^4]$

Even this second example can be further generalized to give huge sets of graphs all with distinct spectrums but all having the same $A^2$: Take any graph you like, say $H$ with $w$ vertices, Make (lots of) new graphs with $2vw$ vertices by replacing some vertices by $G_1$ from above and others by $G_2$. Replace each edge of $H$ by $(2v)^2$ edges constituting all possible edges between corresponding copies of $G_i$.

Answer 2

The eigenvalues of $C_6$ are 2, 1,$-1$ and $-2$ with respective multiplicities 1, 2, 2, 1. The eigenvalues of two disjoint copies of $K_3$ are $2$ and $-1$ with multiplicities 2 and 4. In this case the squares of the adjacency matrices have the same spectrum. As Carlo has stated, this shows that we cannot recover the eigenvalue signs of the adjacency matrix from the spectrum of its square.