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

<p>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 <em>not</em> as readily found as I expected, so I decided to write it as a proper answer for the record.</p>

<p>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 <em>real</em> roots near $1/c$ in distance $&lt;2/c^{1+n/2}$, whereas we need a pair of <em>complex</em> 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&amp;-1\\
&amp;x&amp;-1\\
&amp;&amp;x&amp;-1\\
&amp;&amp;&amp;\ddots\\
&amp;&amp;&amp;&amp;x&amp;-1\\
1&amp;-4&amp;4&amp;&amp;&amp;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$.</p>

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

<p><strong>References:</strong></p>

<p>[1] A. Schönhage, <em>Polynomial root separation examples</em>, Journal of Symbolic Computation 41 (2006), no. 10, pp. 1080–1090, <a href="http://dx.doi.org/10.1016/j.jsc.2006.06.003">doi:10.1016/j.jsc.2006.06.003</a>.</p>

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

CC BY-SA 3.0
2016-10-26T20:29:38.833Z
Also, $G_1$ is strongly connected if it matters.
Emil Jeřábek
CC BY-SA 3.0
2016-10-27T13:19:22.840Z
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.
Lior Eldar
CC BY-SA 3.0
2016-10-27T14:06:55.960Z
You missed the point. $G_1$ is *not* a weighted graph. It is a perfectly normal directed graph.
Emil Jeřábek
CC BY-SA 3.0
2016-10-27T14:26:49.670Z
What is the easiest way to make sure that the spectrum of $G_1$ is contained in that of $G_0$?
Lior Eldar
CC BY-SA 3.0
2016-10-27T15:30:24.353Z
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.
Emil Jeřábek
CC BY-SA 3.0
2016-10-28T23:55:15.783Z
In case it matters, you can explicitly list out the extra eigenvalues arising from the construction of $G_1$ from $G_0$. If $|G_0|$ is the matrix formed by taking absolute values entry-wise, then any (generalized) eigenvector of $|G_0|$ can be extended to an eigenvector of $G_1$. There are some other easy-to-find eigenvectors with eigenvalue zero, and this is all of them. For this particular $G_0$, the eigenvalues of $|G_0|$ are the roots of $|f|(x)=x^n+4x^2+4x+1=x^n+(2x+1)^2$, which are situated the same relative to $-1/2$ as the roots of $f$ are to $+1/2$ (at least, when $n$ is even).
Andrew Morgan
CC BY-SA 3.0
2016-10-31T12:17:38.890Z
@AndrewMorgan That’s not quite correct. The $n$ non-zero eigenvalues of $G_1$ are indeed eigenvalues of the weighted graph $|G_0|$ obtained from $G_0$ by taking absolute values of all weights, or of the corresponding matrix with non-negative entries. However, the characteristic polynomial of this matrix is not your $|f|$, but the polynomial $g(x)=x^n-(2x+1)^2$ obtained by making all non-leading coefficients *non-positive*.
Emil Jeřábek
CC BY-SA 3.0
2016-10-31T12:20:05.503Z
On a related note: if $n$ is odd, the polynomial $g(x)=-f(-x)$ also has roots with exponentially small imaginary part, hence I could have used it directly in place of $f$, replacing $G_0$ with $|G_0|$, and $G_1$ with the corresponding unweighted graph on $n+3$ vertices. This somewhat simplifies the construction.
Emil Jeřábek
CC BY-SA 3.0
2016-10-26T19:36:43.400Z
2016-10-26T19:36:43.400Z
Emil Jeřábek
<p>I feel like the bounds will very strongly depend on the particular connectivity structure of the graph. </p>

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

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

<p>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.</p>

CC BY-SA 3.0
2016-10-18T12:47:53.550Z
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.
Lior Eldar
CC BY-SA 3.0
2016-10-18T00:13:51.327Z
2016-10-18T00:13:51.327Z
Lagerbaer
<p>Compared to spectra of undirected graphs, which correspond to symmetric matrices, the spectra of directed graphs is not very well known:</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

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

<p>$\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)$.</p>

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

CC BY-SA 3.0
2016-10-05T21:20:53.733Z
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?
Sasho Nikolov
CC BY-SA 3.0
2016-10-05T21:24:43.093Z
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.
Lior Eldar
CC BY-SA 3.0
2016-10-09T11:42:32.323Z
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?
Sasho Nikolov
CC BY-SA 3.0
2016-10-10T18:04:28.607Z
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.
Lior Eldar
CC BY-SA 3.0
2016-10-10T19:17:15.060Z
One more question: the Laplacian (normalized or not) is usually not a 0-1 matrix even for undirected. Do you mean the adjacency matrix?
Sasho Nikolov
CC BY-SA 3.0
2016-10-10T19:38:39.337Z
Indeed !  Modified.
Lior Eldar
CC BY-SA 3.0
2016-10-18T13:41:31.233Z
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?
Emil Jeřábek
CC BY-SA 3.0
2016-10-19T13:40:09.770Z
Well, so far I pose the conjecture with the quantifiers as they are.  Should I swap them?  What is an example of a directed graph on n vertices with an eigenvalue with exponentially small imaginary component?
Lior Eldar
CC BY-SA 3.0
2016-10-24T07:00:46.017Z
Still I don't see why you say strongly regular to strongly connected digraps? Is there any text book which calls them strongly regular or do I miss something?
Saeed
CC BY-SA 3.0
2016-10-24T18:37:28.107Z
Well, with a bit of perseverance, it is easy to show that if $f$ is a monic integer polynomial of degree $n$ and $L_1$-norm $m$, there is a strongly connected graph on $O(n+m)$ vertices whose eigenvalues include the roots of $f$.
Emil Jeřábek
CC BY-SA 3.0
2016-10-24T18:40:49.540Z
Is this an answer to the conjecture?  If so, can you please write it in more detail as a separate answer?
Lior Eldar
<graph-theory><graph-algorithms><linear-algebra><spectral-graph-theory>
Dichotomy of the spectra of directed graphs
Lior Eldar
# Dichotomy of the spectra of directed graphs

(Asked by: username_0 on 2016-10-05)

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?

**Tags:** graph-theory, graph-algorithms, linear-algebra, spectral-graph-theory

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  
> **username_1**: 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?  
> **username_0**: 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.  
> **username_1**: One more question: the Laplacian (normalized or not) is usually not a 0-1 matrix even for undirected. Do you mean the adjacency matrix?  
> **username_0**: Indeed !  Modified.  
> **username_2**: 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?  
> **username_0**: Well, so far I pose the conjecture with the quantifiers as they are.  Should I swap them?  What is an example of a directed graph on n vertices with an eigenvalue with exponentially small imaginary component?  
> **username_3**: Still I don't see why you say strongly regular to strongly connected digraps? Is there any text book which calls them strongly regular or do I miss something?  
> **username_2**: Well, with a bit of perseverance, it is easy to show that if $f$ is a monic integer polynomial of degree $n$ and $L_1$-norm $m$, there is a strongly connected graph on $O(n+m)$ vertices whose eigenvalues include the roots of $f$.  
> **username_0**: Is this an answer to the conjecture?  If so, can you please write it in more detail as a separate answer?  

---

## 2 answers

### Answer by username_2 on 2016-10-26. Score: 6 | Accepted answer

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](http://dx.doi.org/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](http://dx.doi.org/10.1007/978-3-7091-7551-4_16).

> **Comments:**
> **username_2**: Also, $G_1$ is strongly connected if it matters.  
> **username_0**: 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.  
> **username_2**: You missed the point. $G_1$ is *not* a weighted graph. It is a perfectly normal directed graph.  
> **username_0**: What is the easiest way to make sure that the spectrum of $G_1$ is contained in that of $G_0$?  
> **username_2**: 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.  
> **username_4**: In case it matters, you can explicitly list out the extra eigenvalues arising from the construction of $G_1$ from $G_0$. If $|G_0|$ is the matrix formed by taking absolute values entry-wise, then any (generalized) eigenvector of $|G_0|$ can be extended to an eigenvector of $G_1$. There are some other easy-to-find eigenvectors with eigenvalue zero, and this is all of them. For this particular $G_0$, the eigenvalues of $|G_0|$ are the roots of $|f|(x)=x^n+4x^2+4x+1=x^n+(2x+1)^2$, which are situated the same relative to $-1/2$ as the roots of $f$ are to $+1/2$ (at least, when $n$ is even).  
> **username_2**: @AndrewMorgan That’s not quite correct. The $n$ non-zero eigenvalues of $G_1$ are indeed eigenvalues of the weighted graph $|G_0|$ obtained from $G_0$ by taking absolute values of all weights, or of the corresponding matrix with non-negative entries. However, the characteristic polynomial of this matrix is not your $|f|$, but the polynomial $g(x)=x^n-(2x+1)^2$ obtained by making all non-leading coefficients *non-positive*.  
> **username_2**: On a related note: if $n$ is odd, the polynomial $g(x)=-f(-x)$ also has roots with exponentially small imaginary part, hence I could have used it directly in place of $f$, replacing $G_0$ with $|G_0|$, and $G_1$ with the corresponding unweighted graph on $n+3$ vertices. This somewhat simplifies the construction.  

---

### Answer by username_5 on 2016-10-18. Score: 1

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.

> **Comments:**
> **username_0**: 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.  

---

