Dichotomy of the spectra of directed graphs

Question

Compared to spectra of undirected graphs, which correspond to symmetric matrices, the spectra of directed graphs is not very well known:

It is known that a directed graph $G = (V,E)$ has an adjacency matrix $A(G)$ whose eigenvalues are binary $\{0,1\}$ if $G$ is a-cyclic. This follows by sorting the vertices into strongly connected components: this fixes an enumeration of the vertices $v_1,.., v_n$ such that the permuted Laplacian according to this ordering is upper-triangular with $0/1$ entries.

But what is known if $G$ is the other extreme end - i.e. $G$ is a strongly-connected graph on $n$ vertices - meaning that there is a directed path between any pair of vertices.

Generally, one would need to compute the characteristic polynomial of $A(G)$ and compute its roots. Despite $A(G)$ being a $\{0,1\}$ matrix this seems like a daunting task. In particular, the roots of this polynomial are in general complex numbers.

The Perron-Frobenius theorem implies that at least the top eigenvalue is real and simple, but does not reveal information about the rest of the eigenvalues.

However, what if we're interested only in very weak bounds of the following form:

$\textbf{Conjecture: Dichotomy of eigenvalues}$: Let $G$ be a directed graph on $n$ vertices. Then either all eigenvalues of $A_G$ are real, or there exists at least one eigenvalue $\lambda$ such that $im(\lambda)\geq 1/poly(n)$.

Do such bounds follow trivially from known theorems? Alternatively, can a directed graph have an eigenvalue with an exponentially small imaginary component?

Answer 1

The answer to “alternatively, can a directed graph have an eigenvalue with an exponentially small imaginary component” is YES (though I don’t understand what is “alternative” about this statement, as it does not in any way disprove the conjecture).

As I already wrote in a comment, it is a not very difficult exercise to show that if $f\in\mathbb Z[x]$ is a monic polynomial, there exists a directed graph $G$ on $O(\deg(f)+\|f\|_1)$ vertices whose eigenvalues include all roots of $f$. This implies the statement above modulo the fact that such polynomials may have roots with exponentially small imaginary part, which I assumed to be easy to find in the literature on minimal root separation. However, I realized that such bounds are actually not as readily found as I expected, so I decided to write it as a proper answer for the record.

Several examples of polynomials with exponentially small root separation are listed by Schönhage [1], in particular the family of polynomials $$x^n-2(cx-1)^2\qquad(n\ge3,c\ge2)$$ attributed to Mignotte [2] (which I cannot verify as I have no access to it at the moment). Now, these polynomials have each a pair of real roots near $1/c$ in distance $<2/c^{1+n/2}$, whereas we need a pair of complex roots. This is, however, easily accomplished by modifying the polynomial slightly: let $$f(x)=x^n\mathbin{\color{red}+}(2x-1)^2=x^n+4x^2-4x+1.$$ Clearly, this polynomial has no positive real root (and no negative real root either if $n$ is even). Moreover, it is easy to show that it still has a pair of (necessarily non-real) roots in exponentially small distance to $1/2$; if I didn’t mess up the computation, these roots are approximately $$z_\pm=\frac12\pm i2^{-1-\frac n2}+O(n2^{-n}).$$ Now, $f(x)$ can be written as the determinant of e.g. the $n\times n$ matrix $$\begin{pmatrix} x&-1\\ &x&-1\\ &&x&-1\\ &&&\ddots\\ &&&&x&-1\\ 1&-4&4&&&x \end{pmatrix}$$ and therefore as the characteristic polynomial of the adjacency matrix of the weighted directed graph $G_0$ on $n$ vertices $\{0,\dots,n-1\}$ with edges $i\to i+1$ of weight $1$ for $i=0,\dots,n-2$; $n-1\to0$ of weight $-1$; $n-1\to1$ of weight $4$; and $n-1\to2$ of weight $-4$. The eigenvalues of $G_0$ are thus exactly the roots of $f$, including $z_\pm$.

Finally, the eigenvalues of $G_0$ are included among eigenvalues of the unweighted directed graph $G_1$ on $2n+6$ vertices $$0_+,0_-,\dots,(n-2)_+,(n-2)_-,(n-1)_+^0,\dots,(n-1)_+^3,(n-1)_-^0,\dots,(n-1)_-^3$$ with edges $i_+\to(i+1)_+$ and $i_-\to(i+1)_-$ for $i=0,\dots,n-3$; $(n-2)_+\to(n-1)_+^j$ and $(n-2)_-\to(n-1)_-^j$ for $j=0,\dots,3$; $(n-1)_+^0\to0_-$, $(n-1)_-^0\to0_+$; and $(n-1)_+^j\to1_+$, $(n-1)_+^j\to2_-$, $(n-1)_-^j\to1_-$, $(n-1)_-^j\to2_+$ for $j=0,\dots,3$.

References:

[1] A. Schönhage, Polynomial root separation examples, Journal of Symbolic Computation 41 (2006), no. 10, pp. 1080–1090, doi:10.1016/j.jsc.2006.06.003.

[2] M. Mignotte, Some useful bounds, in: Buchberger, Collins, Loos (eds.), Computer Algebra: Symbolic and Algebraic Computation, 2nd ed., Springer-Verlag, 1983, pp. 259­–263, doi:10.1007/978-3-7091-7551-4_16.

Answer 2

I feel like the bounds will very strongly depend on the particular connectivity structure of the graph.

One example would be a one-way cycle of length $N$. With the correct ordering, it's not hard to see that $A(G)^N - I = 0$, so the eigenvalues are all the $N$-th roots of unity, i.e. $e^{2\pi i n/N}$ with $n$ going from $0$ to $N-1$.

For even $N$, you're guaranteed some purely imaginary eigenvalues $i$ and $-i$.

Now on the other hand, I went to Wolframalpha and plugged in the complete graph of size 4, then removed a single edge. The resulting graph has purely real eigenvalues (despite not having a symmetric adjacency matrix; yes, that can happen). Which tells me that there is no general statement.