1
$\begingroup$

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$?

$\endgroup$
5
  • 1
    $\begingroup$ If $\Gamma$ is bipartite then both $\lambda$ and $-\lambda$ are eigenvalues of $\Gamma$. $\endgroup$ Apr 21, 2013 at 18:41
  • $\begingroup$ how would $A^2$ contain that information? $\endgroup$ Apr 21, 2013 at 18:43
  • $\begingroup$ Ok. But I want a general result. Not for speciall graphs. Indeed I am looking for any result or paper concerning this problem. $\endgroup$ Apr 21, 2013 at 18:44
  • $\begingroup$ We can suppose that the eigenspaces of eigenvalues of $A^2$ are available. $\endgroup$ Apr 21, 2013 at 18:46
  • 1
    $\begingroup$ the information is just not there, no amount of math can help you. $\endgroup$ Apr 21, 2013 at 19:29

2 Answers 2

0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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