8
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ A graph which is essentially undirected, i.e. each edge appears in both directions, will have a symmetric Laplacian and all eigenvalues will be real. Why isn't that a counterexample to your conjecture? Also what you call "strongly regular" to me looks like "strongly connected". Is there a difference? $\endgroup$ – Sasho Nikolov Oct 5 '16 at 21:20
  • $\begingroup$ Sorry - fixed the typo in the conjecture. The strongly regular graph is not undirected - there is a directed PATH between every two vertices, not a directed EDGE. $\endgroup$ – Lior Eldar Oct 5 '16 at 21:24
  • $\begingroup$ I do not get your explanation. Isn't an edge a path of length 1? Why isn't a graph that contains every edge in both directions strongly regular? Do you require the graph to have no cycles of length 2? $\endgroup$ – Sasho Nikolov Oct 9 '16 at 11:42
  • $\begingroup$ Ah - I see - I've corrected the conjecture to reflect your example. I want to consider only strongly connected directed graphs that are not essentially "undirected". Thanks. $\endgroup$ – Lior Eldar Oct 10 '16 at 18:04
  • 1
    $\begingroup$ Can a directed graph have an eigenvalue with an exponentially small imaginary component? I’m pretty sure it can. However, this does not preclude the existence of another eigenvalue with polynomially small imaginary component, so I don’t see how it relates to the conjecture. Are you sure you didn’t mix up the existential and universal quantifiers? $\endgroup$ – Emil Jeřábek supports Monica Oct 18 '16 at 13:41
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Also, $G_1$ is strongly connected if it matters. $\endgroup$ – Emil Jeřábek supports Monica Oct 26 '16 at 20:29
  • $\begingroup$ Thank you. This is very informative. Though this is not strictly a directed graph but rather a weighted graph with arbitrary weights. So it answers a generalization of the above, correct?? Surely it is easy to produce graphs with arbitrarily small eigenvalues if you allow arbitrary weights (say, a single vertex with a 2^{-n} weight self-loop), but the conjecture tries to capture whether you can get exponentially small eigenvalues even with {0,1} elements. Still, I think that showing this with O(1) weights qualifies as progress. $\endgroup$ – Lior Eldar Oct 27 '16 at 13:19
  • $\begingroup$ You missed the point. $G_1$ is not a weighted graph. It is a perfectly normal directed graph. $\endgroup$ – Emil Jeřábek supports Monica Oct 27 '16 at 14:06
  • $\begingroup$ What is the easiest way to make sure that the spectrum of $G_1$ is contained in that of $G_0$? $\endgroup$ – Lior Eldar Oct 27 '16 at 14:26
  • $\begingroup$ I don't think that's reasonably possible. The characteristic polynomial always has $n$ roots with multiplicity, so under normal circumstances, enlarging the graph creates new eigenvalues. I can't imagine an eigenvalue-preserving transformation of weighted to unweighted graphs that would either leave the number of vertices the same, or make the char poly of the new graph a power of the original char poly. $\endgroup$ – Emil Jeřábek supports Monica Oct 27 '16 at 15:30
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you. This is an important example. Actually it seems that even a much sparser non-symmetric graph on 4 vertices has a real spectrum: consider vertices v1,v2,v3,v4: have bi-directed edges between vi and v_{i+1} for $i\in \{1,2,3\}$ and a single directed edge from $v_4$ to $v_1$. Perhaps it is then the case that if you have a subgraph whose induced directed graph is essentially undirected, then in the context of eigenvalues you can "contract" that subgraph. Anyway, I have modified the conjecture to contain this example. $\endgroup$ – Lior Eldar Oct 18 '16 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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