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

I have been computing eigenvalues of adjacency matrices for several directed (not necessarily strongly connected) graphs and one remarkable property seemed to hold (each graph that I have examined contained at least one cycle, but this need not to be a necessary condition):

"If $\lambda$ is an eigenvalue of an adjacency matrix $A$, then it can be expressed as $r\cdot z$, where $r$ is some real number and z is $n$-th root of unity for some $n \in \mathbb{N}$. Moreover, if some eigenvalue $\lambda$ can be expressed in this form, then for all $n$-th roots of unity $z'$, $r \cdot z'$ is an eigenvalue of $A$. As a consequence, if $\lambda$ is eigenvalue of $A$, then also $|\lambda|$ (absolute value) is an eigenvalue of $A$."

Since I am not an expert in the field of spectral graph theory, I was unable to proof or disproof the property by myself. Is it known if this property or any similar property holds? Has anyone proved any similar property (it is possible, that the property does not hold exactly in the form I had written it down, but it may hold for instance for some special class of digraphs)? Any reference would be welcomed.

Thank you in advance.

share|improve this question
2  
Eigenvalues = roots of the characteristic polynomial, which in this case is an integer polynomial. Thus, all eigenvalues are algebraic numbers, and if $\lambda$ is an eigenvalue, then all its algebraic conjugates are also eigenvalues. In particular, if $\lambda=rz$ where $r$ is rational and $z$ is a primitive $n$th root of unity, then $rz'$ is also an eigenvalue whenever $z'$ is another primitive $n$th root of unity. –  Emil Jeřábek Sep 7 '11 at 13:22
    
As Chris' answer below shows, the property that the eigenvalues always have polar angle equal to a rational multiple of $\pi$ does not hold for arbitrary digraphs. However, this property may hold for certain classes of digraphs; are there any particular constraints on the digraphs you are interested in? –  ARupinski Sep 8 '11 at 1:57
add comment

2 Answers

up vote 8 down vote accepted

Let $D$ be the Paley tournament on seven vertices. Its vertices are the integers mod seven and there is an arc from $i$ to $j$ is $j-i$ is a non-zero square mod seven. The characteristic polynomial of the adjacency matrix is $(x-3)(x^2+x+2)^3$. The only real eigenvalue is 3, the remaining eigenvalues are equal to $(-1\pm\sqrt{-7})/2$, with absolute value $\sqrt{2}$. This can be generalized to Paley tournaments on $q$ vertices, where $q\equiv3$ mod 4.

According to my computations (in sage) random directed graphs with seven vertices and arc probability 0.5 do well as counterexamples too.

share|improve this answer
add comment

If $k$ is the greatest common divisor of the cycle lengths of the digraph, then the spectrum is invariant under rotation around the origin by $2\pi/k$. This is an application of the Perron-Frobenius theorem (see the Wikipedia article of that name).

On the other hand, the set of eigenvalues of digraphs is closed under addition, since the eigenvalues of the cartesian product of two digraphs consist of an eigenvalue of one plus an eigenvalue of the other, but the set of complex numbers of the form real times root of unity are not closed under addition. So there is some digraph with no eigenvalues of that form, probably you just need to try larger examples.

share|improve this answer
    
True, but I would think you would have to wake up pretty early in the morning to have things so reducible... –  Igor Rivin Sep 7 '11 at 14:39
1  
@igor: Actually it is so early in the morning (12:50am) that I don't understand your comment. –  Brendan McKay Sep 7 '11 at 14:49
    
That conclusion doesn't follow directly from the failure of closure of the reals times roots of unity since not all such numbers are eigenvalues of digraphs, but that is a good method for constructing counterexamples. –  Douglas Zare Sep 8 '11 at 4:05
    
Yes you are right. I had in mind $k+i$, which is an eigenvalue of a digraph for any positive integer $k$. –  Brendan McKay Sep 8 '11 at 4:28
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.