Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
If $\Gamma$ is bipartite then both $\lambda$ and $-\lambda$ are eigenvalues of $\Gamma$. –  Alireza Abdollahi Apr 21 '13 at 18:41
    
how would $A^2$ contain that information? –  Carlo Beenakker Apr 21 '13 at 18:43
    
Ok. But I want a general result. Not for speciall graphs. Indeed I am looking for any result or paper concerning this problem. –  majid arezoomand Apr 21 '13 at 18:44
    
We can suppose that the eigenspaces of eigenvalues of $A^2$ are available. –  majid arezoomand Apr 21 '13 at 18:46
1  
the information is just not there, no amount of math can help you. –  Carlo Beenakker Apr 21 '13 at 19:29
add comment

2 Answers

up vote 0 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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