5
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Sep 7, 2011 at 13:22
  • 1
    $\begingroup$ 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? $\endgroup$
    – ARupinski
    Commented Sep 8, 2011 at 1:57

2 Answers 2

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ True, but I would think you would have to wake up pretty early in the morning to have things so reducible... $\endgroup$
    – Igor Rivin
    Commented Sep 7, 2011 at 14:39
  • 1
    $\begingroup$ @igor: Actually it is so early in the morning (12:50am) that I don't understand your comment. $\endgroup$
    – Brendan McKay
    Commented Sep 7, 2011 at 14:49
  • $\begingroup$ 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. $\endgroup$
    – Douglas Zare
    Commented Sep 8, 2011 at 4:05
  • $\begingroup$ Yes you are right. I had in mind $k+i$, which is an eigenvalue of a digraph for any positive integer $k$. $\endgroup$
    – Brendan McKay
    Commented Sep 8, 2011 at 4:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .