On the Maximum Spread of Directed Graphs
Susie Lu, John Urschel · 2025
Read On the Maximum Spread of Directed Graphs by Susie Lu, John Urschel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-05760.txt.
Introduction
Lu and Urschel settled how large the eigenvalue spread of a non-negative matrix can be in twenty twenty-five. The spread of a matrix, or of a directed graph's adjacency matrix, is the largest distance between any two of its eigenvalues in the complex plane. A twenty twenty-two question asked which directed graph on n vertices maximizes spread, and whether it must be undirected.
The authors prove the more general matrix result. For any n by n non-negative matrix whose entries are at most one, the spread is at most two n over the square root of three. The bound is tight up to an additive factor and exact when n is a multiple of three. Moreover, the maximizing matrix is always symmetric, answering the graph question's spirit: the extremal example is effectively undirected.
Catalog record
| CREATOR | Susie Lu, John Urschel |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 18 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-05760
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Maximum Spread of Directed Graphs Susie Lu, John Urschel Abstract . Given a directed graph G G , the spread of G G is the largest distance between any two eigenvalues of its adjacency matrix. In 2022, Breen, Riasanovsky, Tait, and Urschel asked what n n -vertex directed graph maximizes spread, and whether this graph is undirected. We prove the more general result that the spread of any n × n n\times n non-negative matrix A A with ‖ A ‖ max ≤ 1 \|A\|_{\max}\leq 1 is at most 2 n / 3 2n/\sqrt{3} , which is tight up to an additive factor and exact when n n is a multiple of three. Furthermore, our results show that the matrix with maximum spread is always symmetric. 2020 Mathematics Subject Classification Primary 05C50 The spread of an n\times n complex matrix M is the diameter of its spectrum \Lambda(M) : that is, \mathrm{diam}(\Lambda(M))=\max_{\lambda,\lambda^{\prime}\in\Lambda(M)}|\lambda-\lambda^{\prime}|. General upper and lower bounds on s(M) have been established by Mirsky [ 24 , Theorem 2] and by Johnson, Kumar, and Wolkowicz [ 14 , Theorem 2.1] . Consider a (possibly directed) graph G=(V,E) of order n . The adjacency matrix A of G is the n\times n matrix whose rows and columns are indexed by the vertices of G , with entries satisfying A_{i,j}=1 if (i,j)\in E and A_{i,j}=0 otherwise. The spread of the adjacency matrix of a graph G is \mathrm{diam}(\Lambda(A))=\max_{\lambda,\lambda^{\prime}\in\Lambda(A)}|\lambda-\lambda^{\prime}|, which is called the spread of the graph G . In the special case when the graph G is undirected, the adjacency matrix is symmetric, so its eigenvalues are real and can be ordered \lambda_{1}(A)\geq\lambda_{2}(A)\geq\dots\geq\lambda_{n}(A) . Then, \mathrm{diam}(\Lambda(A))=\lambda_{1}(A)-\lambda_{n}(A) . In 2001, Gregory, Hershkowitz, and Kirkland initiated a detailed analysis of the spread of a graph [ 13 ] , leading to a large literature on the subject under various conditions and matrix representations. See, for instance, [ 1 , 2 , 3 , 7 , 9 , 10 , 15 , 17 , 18 , 19 , 20 , 22 , 25 , 27 , 28 ] and the references therein. In 2022, Breen, Riasanovsky, Tait, and Urschel characterized the graphs with maximum spread among all n -vertex undirected graphs, both allowing and not allowing loops [ 5 ] , which solved a main conjecture of Gregory, Hershkowitz, and Kirkland for n sufficiently large. To state their results, we let \|A\|_{\max} denote the largest magnitude entry in a matrix A , and A\otimes B denote the Kronecker product of two matrices A and B . Theorem 1 ( [ 5 , Theorem 1.1 & 1.3, Corollary 1.4] ) . Let A be an n\times n symmetric non-negative matrix. Then \lambda_{1}(A)-\lambda_{n}(A)\leq\frac{2\,n}{\sqrt{3}}\,\|A\|_{\max}, with equality if and only if n=0\bmod 3 and A=P_{\pi}\left(\begin{pmatrix}1&1&1\\ 1&1&1\\ 1&1&0\end{pmatrix}\otimes J_{\frac{n}{3}}\right)P_{\pi} , where J_{k} is the k\times k all-ones matrix and P_{\pi} is a permutation matrix. Furthermore: (1) Any matrix A that maximizes \big(\lambda_{1}(A)-\lambda_{n}(A)\big) over all n\times n symmetric non-negative matrices with \|A\|_{\max}=1 is a 0-1 matrix and has spread at least 2n/\sqrt{3}-1/(2\sqrt{3}n) . (2) The matrix A that maximizes \big(\lambda_{1}(A)-\lambda_{n}(A)\big) over all n\times n zero-diagonal symmetric non-negative matrices with \|A\|_{\max}=1 is exactly the adjacency matrix of the join of a clique on \lfloor 2n/3\rfloor vertices and an independent set on \lceil n/3\rceil vertices for all n sufficiently large. This matrix always has spread at least (2n-1)/\sqrt{3} for n>1 . In the same paper, the authors detailed a number of open problems, beginning with the following: “What digraph of order n maximizes the spread of its adjacency matrix … Is this more general problem also maximized by the same set of graphs as in the undirected case?” [ 5 , Sec. 8] While many refinements and related results have been produced recently [ 6 , 12 , 16 , 21 , 26 ] , the above question remains open. Here, we answer this question in the affirmative, generalizing Theorem 1 to all non-negative matrices: Theorem 2 (Directed Spread Theorem) . Let A be an n\times n non-negative matrix. Then \mathrm{diam}\big(\Lambda(A)\big)\leq\frac{2\,n}{\sqrt{3}}\,\|A\|_{\max}, with equality if and only if n=0\bmod 3 and A=P_{\pi}\left(\begin{pmatrix}1&1&1\\ 1&1&1\\ 1&1&0\end{pmatrix}\otimes J_{\frac{n}{3}}\right)P_{\pi} , where J_{k} is the k\times k all-ones matrix and P_{\pi} is a permutation matrix. Furthermore, (1) the matrix A that maximizes \mathrm{diam}\big(\Lambda(A)\big)/\|A\|_{\max} over all n\times n non-negative matrices is symmetric for all n , and (2) the matrix A that maximizes \mathrm{diam}\big(\Lambda(A)\big)/\|A\|_{\max} over all n\times n zero-diagonal non-negative matrices is exactly the adjacency matrix of the join of a clique on \lfloor 2n/3\rfloor vertices and an independent set on \lceil n/3\rceil vertices for all n sufficiently large. In contrast to Breen, Riasanovsky, Tait, and Urschel’s proof of Theorem 1 (which involves nearly 70 pages of complicated mathematics and computation), the proof of Theorem 2 (given Theorem 1 ) is incredibly simple and intuitive. The main idea is that, while the use of the complex plane allows for larger distances in theory, complex eigenvalues come in pairs, making them slightly too “expensive” for maximizing the spread of eigenvalues. The key ingredient in our proof is the following lemma regarding the maximum magnitude and real part of non-real eigenvalues of non-negative matrices, which may be of independent interest. Lemma 3 . Let A be an n\times n non-negative matrix with \|A\|_{\max}\leq 1 . Any eigenvalue \mu of A with \mathrm{Im}(\mu)\neq 0 satisfies (1) |\mu|^{2}\leq\min\left\{\frac{n^{2}+n\lambda_{\max}-2\lambda_{\max}^{2}-\gamma}{4},\;\lambda_{\max}^{2}\right\} and (2) \mathrm{Re}(\mu)^{2}\leq\min\left\{\frac{n^{2}+3n\lambda_{\max}-4\lambda_{\max}^{2}-\gamma}{8},\;\lambda_{\max}^{2}\right\}, where \lambda_{\max} is the Perron eigenvalue of A and \gamma:=n\lambda_{\max}-\sum_{i,j=1}^{n}\min\{A_{ij},A_{ji}\}+\sum_{i,j=1}^{n}\left(1+\min\{A_{ij},A_{ji}\}-A_{ij}^{2}-A_{ji}^{2}\right)\geq 0. Proof of Lemma 3 . First, we note that, by Perron-Frobenius, \mathrm{Re}(\mu)^{2}\leq|\mu|^{2}\leq\lambda_{\max}^{2} , immediately handling half of Inequalities 1 and 2 . Next, we verify that \gamma\geq 0 and prove Inequality 1 . Consider the matrix \hat{A}\in\mathbb{R}^{n\times n} with \hat{A}_{ij}=\min\{A_{ij},A_{ji}\} for all i,j\in[n] . We may express \|A\|_{F}^{2} in terms of n , \lambda_{\max} , and \gamma : \displaystyle\sum_{i,j=1}^{n}A_{ij}^{2} \displaystyle=\frac{1}{2}\left(n^{2}+n\lambda_{\max}-\sum_{i,j=1}^{n}(1+\min\{A_{ij},A_{ji}\}-A_{ij}^{2}-A_{ji}^{2})-(n\lambda_{\max}-\bm{1}^{T}\hat{A}\bm{1})\right) (3) \displaystyle=\frac{1}{2}(n^{2}+n\lambda_{\max}-\gamma). The quantity \gamma is the sum of the two addends n\lambda_{\max}-\bm{1}^{T}\hat{A}\bm{1} and \sum_{i,j=1}^{n}(1+\min\{A_{ij},A_{ji}\}-A_{ij}^{2}-A_{ji}^{2}) . The former is non-negative by the non-decreasing property of the spectral radius [ 23 , Corollary 2.1] and the Courant-Fischer theorem: \lambda_{\max}(A)\geq\lambda_{\max}(\hat{A})\geq\frac{\textbf{1}^{T}\hat{A}\textbf{1}}{\textbf{1}^{T}\textbf{1}}=\frac{\textbf{1}^{T}\hat{A}\textbf{1}}{n}, and the latter is non-negative because \|A\|_{\max}\leq 1 . The lower bound \|A\|_{F}^{2}\geq\sum_{i=1}^{n}|\lambda_{i}|^{2}=\lambda_{\max}^{2}+2|\mu|^{2}+\sum_{\lambda\in\Lambda(A)\setminus\{\lambda_{\max},\mu,\overline{\mu}\}}|\lambda|^{2} combined with Equation 3 produces the remainder of Inequality 1 : |\mu|^{2}\leq\frac{\|A\|_{F}^{2}-\lambda_{\max}^{2}}{2}\leq\frac{n^{2}+n\lambda_{\max}-2\lambda_{\max}^{2}-\gamma}{4}. Furthermore, we may also bound the sum of the squared moduli of the remaining eigenvalues: \displaystyle\sum_{\lambda\in\Lambda(A)\setminus\{\lambda_{\max},\mu,\overline{\mu}\}}|\lambda|^{2} \displaystyle\leq\|A\|_{F}^{2}-\lambda_{\max}^{2}-2|\mu|^{2} \displaystyle\leq\frac{n^{2}+n\lambda_{\max}-\gamma}{2}-\lambda_{\max}^{2}-2|\mu|^{2} (4) \displaystyle=\frac{n^{2}+n\lambda_{\max}-2\lambda_{\max}^{2}-\gamma}{2}-2|\mu|^{2}. Finally, using the trace of A^{2} , we prove the remainder of Inequality 2 . We have \mathrm{trace}(A^{2})=\sum_{i,j=1}^{n}A_{ij}A_{ji}\leq\sum_{i,j=1}^{n}\min\{A_{ij},A_{ji}\}\leq n\lambda_{\max}. On the other hand, the trace of A^{2} can also be written in terms of eigenvalues, giving the lower bound \displaystyle\mathrm{trace}(A^{2}) \displaystyle=\lambda_{\max}^{2}+\mu^{2}+\overline{\mu}^{2}+\sum_{\lambda\in\Lambda(A)\setminus\{\lambda_{\max},\mu,\overline{\mu}\}}\lambda^{2} \displaystyle\geq\lambda_{\max}^{2}+\mu^{2}+\overline{\mu}^{2}-\sum_{\lambda\in\Lambda(A)\setminus\{\lambda_{\max},\mu,\overline{\mu}\}}|\lambda|^{2} \displaystyle\geq\lambda_{\max}^{2}+\mu^{2}+\overline{\mu}^{2}+2|\mu|^{2}-\frac{n^{2}+n\lambda_{\max}-2\lambda_{\max}^{2}-\gamma}{2}\qquad\text{by Inequality \ref{ineq:other-eig}} \displaystyle=4\mathrm{Re}(\mu)^{2}-\frac{n^{2}+n\lambda_{\max}-4\lambda_{\max}^{2}-\gamma}{2}. Combining the lower and upper bounds for \mathrm{trace}(A^{2}) yields our desired result \displaystyle 4\mathrm{Re}(\mu)^{2}-\frac{n^{2}+n\lambda_{\max}-4\lambda_{\max}^{2}-\gamma}{2}\leq n\lambda_{\max} \displaystyle\implies \displaystyle 4\mathrm{Re}(\mu)^{2}\leq n\lambda_{\max}+\frac{n^{2}+n\lambda_{\max}-4\lambda_{\max}^{2}-\gamma}{2} \displaystyle\implies \displaystyle\mathrm{Re}(\mu)^{2}\leq\frac{n^{2}+3n\lambda_{\max}-4\lambda_{\max}^{2}-\gamma}{8}. ∎ Lemma 3 immediately implies that for any eigenvalue \mu with \mathrm{Im}(\mu)\neq 0 , its modulus and real part are bounded by constant multiples of n . Corollary 4 . Let A be an n\times n non-negative matrix with \|A\|_{\max}\leq 1 . Any eigenvalue \mu of A with \mathrm{Im}(\mu)\neq 0 satisfies |\mu|\leq\frac{n}{2}\qquad\text{and}\qquad|\mathrm{Re}(\mu)|\leq\frac{3+\sqrt{57}}{24}n. Proof. The desired result follows immediately from Lemma 3 and the observations that \max_{x\in[0,1]}\min\left\{\frac{1+x-2x^{2}}{4},x^{2}\right\}=\frac{1}{4}\qquad\text{and}\qquad\max_{x\in[0,1]}\min\left\{\frac{1+3x-4x^{2}}{8},x^{2}\right\}=\left(\frac{3+\sqrt{57}}{24}\right)^{2}, achieved at x=1/2 and x=(3+\sqrt{57})/24 , respectively. ∎ For the proof of Theorem 2 , we also require the following four lemmas. Lemma