betaFeedback

WorksMathematics

A second eigenvalue lower bound for the directed configuration model

Abstract

We prove a high-probability lower bound for the second eigenvalue in modulus of the transition matrix of the simple random walk on a directed configuration model with minimal out-degree at least two and maximal degree not too large. The lower bound matches the upper bound found by Coste (2021) on the same model. Our proof bypasses the need to establish convergence of the empirical eigenvalue distribution. Instead, it reduces the spectral lower bound to a central limit theorem for the trace of the transition matrix at powers much larger than the logarithmic scale, a range that previous results failed to reach. Both the general strategy and the central limit theorem might be of independent interest.

Introduction

Motivation from random matrix theory

Consider a sequence of possibly random matrices A∈Mn(C)A \in M_n(\mathbb{C}) of growing dimension n→∞n \to\infty. In many situations, we are interested in the asymptotics as n→∞n \to\infty of the spectral radius of AA defined as

ϱ(A)=max⁡{∣λ∣:λ∈σ(A)}.\varrho(A) = \max\{|\lambda| : \lambda\in\sigma(A)\}.

The spectral radius is upper bounded by the operator norm:

ϱ(A)≤∥A∥op=sup⁡x≠0∥Ax∥2∥x∥2.\varrho(A) \le\lVert A\rVert_{\mathrm{op}} = \sup_{x \ne0} \frac{\lVert Ax\rVert_2}{\lVert x\rVert_2}.

In particular, for any integer k≥1k \ge1, we have ϱ(A)k=ϱ(Ak)≤∥Ak∥op\varrho(A)^k = \varrho(A^k) \le\lVert A^k\rVert_{\mathrm{op}}. Gelfand’s theorem asserts that this upper bound is asymptotically sharp in the sense that

ϱ(A)=lim⁡k→∞∥Ak∥op1/k.\varrho(A) = \lim_{k \to\infty} \lVert A^k\rVert_{\mathrm{op}}^{1/k}.

This limit is, however, not uniform over the dimension nn, and this formula may not be very useful in high dimensions.

The trace method is a classical general strategy to upper bound the spectral radius of random matrices; see the monographs [1, 2, 38]. A foundational application to the extreme eigenvalues of symmetric random matrices is due to Füredi and Komlós [21]. It starts with the following chain of inequalities:

ϱ(A)2k=ϱ(Ak)2≤∥Ak∥op2=∥Ak(Ak)∗∥op≤tr⁡(Ak(Ak)∗).\varrho(A)^{2k} = \varrho(A^k)^2 \le\lVert A^k\rVert_{\mathrm{op}}^2 = \lVert A^k(A^k)^*\rVert_{\mathrm{op}} \le\operatorname{tr}\left(A^k(A^k)^*\right).

Then, we may expand the trace as a sum of products of matrix entries and, for many sequences of random matrices AA, we may derive a probabilistic upper bound on the growth rate of trace powers of the form: tr⁡(Ak(Ak)∗)≤n(1+ϵk)2kρ+2k\operatorname{tr}\left(A^k(A^k)^*\right) \le n(1+\epsilon_k)^{2k}\rho_+^{2k} for some ρ+>0\rho_+ > 0 and where ϵk\epsilon_k goes to 00 as k→∞k \to\infty. Therefore, we find that ϱ(A)≤n1/2k(1+ϵk)ρ+\varrho(A) \le n^{1/2k}(1+\epsilon_k)\rho_+. If this holds for k≫log⁡nk \gg\log n, we then deduce that ϱ(A)≤(1+O(max⁡(ϵk,log⁡n/k)))ρ+\varrho(A) \le(1+O(\max(\epsilon_k,\log n/k)))\rho_+.

For example, if A=X/nA = X/\sqrt{n} with (Xij)(X_{ij}) independent, centered, variance 11 and uniformly bounded support, it follows from Geman [23], one of the earliest appearances of this method, that for some c1>0c_1 > 0, Etr⁡(Ak(Ak)∗)≤nkc1\mathbb{E}\operatorname{tr}(A^k(A^k)^*) \le n k^{c_1} for k≤n1/c1k \le n^{1/c_1}, leading to ϱ(A)≤1+O(n−c2)\varrho(A) \le1 + O(n^{-c_2}) with high probability for some c2>0c_2 > 0. Since then, there have been numerous improvements and further examples of such successful computations in random matrix theory; see, for example [37, 40, 3, 5]. If AA is a normal matrix (that is if AA∗=A∗AAA^* = A^*A), then the same strategy gives also a lower bound. Indeed, for normal matrices, we have ρ(A)=∥A∥op\rho(A) = \|A\|_{\mathrm{op}} and thus

ρ(A)2k=∥(AA∗)k∥op≥1ntr⁡((AA∗)k).\rho(A)^{2k} = \|(AA^*)^k\|_{\mathrm{op}} \ge\frac{1}{n}\operatorname{tr}\left((AA^*)^k\right).

In particular, any lower bound of the form tr⁡((AA∗)k)≥n(1−ϵk)2kρ−2k\operatorname{tr}\left((AA^*)^k\right) \ge n(1-\epsilon_k)^{2k}\rho_-^{2k} now gives ρ(A)≥(1−ϵk)ρ−\rho(A) \ge(1-\epsilon_k)\rho_-. Note that for the lower bound, there is no need to let k→∞k \to\infty jointly with n→∞n \to\infty. If ρ+=ρ−\rho_+ = \rho_-, then we have obtained an asymptotic equivalent to ρ(A)\rho(A) with a controlled error.

In the non-normal case, however, it is not straightforward to extend this strategy to get a lower bound. The usual route takes the following detour. We first prove that the empirical distribution of the eigenvalues of AA converges weakly to a compactly supported measure μ\mu on C\mathbb{C}. Then, we observe that it implies that lim inf⁡n→∞ρ(A)≥ρ−\liminf_{n\to\infty}\rho(A) \ge\rho_- with ρ−=sup⁡{∣λ∣:λ∈supp⁡(μ)}\rho_- = \sup\{|\lambda| : \lambda\in\operatorname{supp}(\mu)\}.

For example, if A=X/nA = X/\sqrt{n} with (Xij)(X_{ij}) iid centered entries of variance 11, then, in probability, the empirical distribution of eigenvalues converges weakly to the uniform measure on the unit disc; see [8] for a survey. Together with the upper bound ρ(A)≤1+o(1)\rho(A) \le1 + o(1) from [9], we thus get in probability, lim⁡nρ(A)=1\lim_{n}\rho(A) = 1 in this case.

Proving the weak convergence of the empirical distribution of eigenvalues is usually not an easy task, and one might wonder if a more direct and quantitative approach exists. One goal of this work is to illustrate one such possible approach. It still relies on the trace powers, but now it exploits its trace fluctuations for large powers. More precisely, we write:

ρ(A)≥1n∑i=1n∣λi(A)∣≥∣1n∑i=1nλi(A)∣=∣1ntr⁡(A)∣.\rho(A) \ge\frac{1}{n}\sum_{i=1}^{n}|\lambda_i(A)| \ge\left|\frac{1}{n}\sum_{i=1}^{n}\lambda_i(A)\right| = \left|\frac{1}{n}\operatorname{tr}(A)\right|.

Hence for any integer k≥1k \ge1,

ρ(A)≥∣1ntr⁡(Ak)∣1/k.(1)\rho(A) \ge\left|\frac{1}{n}\operatorname{tr}(A^k)\right|^{1/k}. \tag*{(1)}

For fixed kk, at first order in nn, this lower bound may be crude. For example, if ρ(A)=O(1)\rho(A) = O(1) and if the empirical distribution of eigenvalues of AA converges to a radial measure μ\mu on C\mathbb{C} then for any integer k≥1k \ge1,

lim⁡n→∞1ntr⁡(Ak)=∫Cλk dμ(λ)=0.\lim_{n\to\infty}\frac{1}{n}\operatorname{tr}(A^k) = \int_{\mathbb{C}}\lambda^k\,\mathrm{d}\mu(\lambda) = 0.

As we discussed above, this case notably happens if A=X/nA = X/\sqrt{n} with (Xij)(X_{ij}) i.i.d. centered entries of variance 11. On the other hand, for this random matrix, under a proper moment condition on XijX_{ij}, for any fixed k≥1k \ge1, it is well-known [35, 32] that, as n→∞n \to\infty,

tr⁡(Ak)k⟹Z,\frac{\operatorname{tr}(A^k)}{\sqrt{k}} \Longrightarrow Z,

where ZZ is a Gaussian variable of unit variance. Moreover, central limit theorems for linear eigenvalue statistics have been established for analytic test functions in real elliptic ensembles [33], and for sufficiently smooth test functions in non-Hermitian matrices with i.i.d. entries [13, 12].

More quantitatively, for any random matrix model AA, assume that we can prove that weakly, along a sequence k=knk = k_n with k≫log⁡nk \gg\log n,

tr⁡(Ak)(1+ϵk)kρ−k⟹Z,\frac{\operatorname{tr}(A^k)}{(1+\epsilon_k)^k\rho_-^k} \Longrightarrow Z,

where ρ−>0\rho_- > 0 and ZZ is a random variable such that P(Z=0)=0\mathbb{P}(Z=0)=0. Then, ∣Z∣1/k≥1−O(log⁡n/k)|Z|^{1/k} \ge1 - O(\log n/k) with high probability. We thus get from (1) that, with high probability,

ρ(A)≥(1+ϵk)(1−O(log⁡nk))ρ−.\rho(A) \ge(1+\epsilon_k)\left(1-O\left(\frac{\log n}{k}\right)\right)\rho_-.

Therefore, the fluctuations of trace powers provide a lower bound on the spectral radius. To our knowledge, this strategy has not been used so far. In the present work, we follow this strategy for the study of the spectral gap of the simple random walk on a random directed graph sampled according to the configuration model, which we define below.

Model and motivation from spectral theory of Markov chains

For integer n≥1n \ge1, prescribe non-negative integers (di+,di−)i=1n(d_i^+,d_i^-)_{i=1}^n such that

References

  1. [1]Greg W. Anderson, Alice Guionnet, and Ofer Zeitouni. An Introduction to Random Matrices, volume 118 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2010.DOI
  2. [2]Zhidong Bai and Jack W. Silverstein. Spectral Analysis of Large Dimensional Random Matrices. Springer Series in Statistics. Springer, New York, second edition, 2010.DOI
  3. [3]Afonso S. Bandeira and Ramon van Handel. Sharp nonasymptotic bounds on the norm of random matrices with independent entries. Ann. Probab., 44(4):2479–2506, 2016.DOI
  4. [4]Anirban Basak, Nicholas Cook, and Ofer Zeitouni. Circular law for the sum of random permutation matrices. Electronic Journal of Probability, 23:Paper No. 33, 51 pp., 2018.arxiv.org/abs/1705.09053
  5. [5]Florent Benaych-Georges, Charles Bordenave, and Antti Knowles. Spectral radii of sparse random matrices. Ann. Inst. Henri Poincaré Probab. Stat., 56(3):2141–2161, 2020.
  6. [6]Charles Bordenave. A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts. Annales Scientifiques de l’École Normale Supérieure, 53(6):1393–1439, 2020.arxiv.org/abs/1502.04482
  7. [7]Charles Bordenave, Pietro Caputo, and Justin Salez. Random walk on sparse random digraphs. Probability Theory and Related Fields, 170(3–4):933–960, 2018.arxiv.org/abs/1508.06600
  8. [8]Charles Bordenave and Djalil Chafaï. Lecture notes on the circular law. In Van H. Vu, editor, Modern Aspects of Random Matrix Theory, volume 72 of Proceedings of Symposia in Applied Mathematics, pages 1–34. Providence, RI: American Mathematical Society (AMS), 2014.DOI
  9. [9]Charles Bordenave, Djalil Chafaï, and David García-Zelada. Convergence of the spectral radius of a random matrix through its characteristic polynomial. Probability Theory and Related Fields, 182(3):1163–1181, 2022.DOI
  10. [10]Charles Bordenave and Benoît Collins. Eigenvalues of random lifts and polynomials of random permutation matrices. Annals of Mathematics, 190(3):811–875, 2019.DOI
  11. [11]Charles Bordenave, Yanqi Qiu, and Yiwei Zhang. Spectral gap of sparse bistochastic matrices with exchangeable rows. Annales de l’Institut Henri Poincaré Probabilités et Statistiques, 56(4):2971–2995, 2020.DOI
  12. [12]Giorgio Cipolloni, László Erdős, and Dominik Schröder. Fluctuation around the circular law for random matrices with real entries. Electron. J. Probab., 26:Paper No. 24, 61, 2021.arxiv.org/abs/2002.02438
  13. [13]Giorgio Cipolloni, László Erdős, and Dominik Schröder. Central limit theorem for linear eigenvalue statistics of non-Hermitian random matrices. Comm. Pure Appl. Math., 76(5):946–1034, 2023.
  14. [14]Benoît Collins and Manasa Nagatsu. Weingarten calculus for centered random permutation matrices. Algebraic Combinatorics, 9(2):465–479, 2026.DOI
  15. [15]Simon Coste. The spectral gap of sparse random digraphs. Annales de l’Institut Henri Poincaré Probabilités et Statistiques, 57(2):644–684, 2021.arxiv.org/abs/1708.00530
  16. [16]Simon Coste, Gaëlium Lambert, and Yizhe Zhu. The characteristic polynomial of sums of random permutations and regular digraphs. International Mathematics Research Notices, 2024(3):2461–2510, 2024.arxiv.org/abs/2204.00524
  17. [17]Simon Coste and Yizhe Zhu. The spectral edge of sparse directed Erdős–Rényi graphs. arXiv preprint arXiv:2609.18369, 2026.
  18. [18]Charles Delorme and Jean-Pierre Tillich. The spectrum of de Bruijn and Kautz graphs. European Journal of Combinatorics, 19(3):307–319, 1998.DOI
  19. [19]Ioana Dumitriu, Tobias Johnson, Soumik Pal, and Elliot Paquette. Functional limit theorems for random regular graphs. Probab. Theory Relat. Fields, 156(3–4):921–975, 2013.DOI
  20. [20]Joel Friedman. A proof of Alon’s second eigenvalue conjecture and related problems. Memoirs of the American Mathematical Society, 195(910):viii+100 pp., 2008.DOI
  21. [21]Zoltán Füredi and János Komlós. The eigenvalues of random symmetric matrices. Combinatorica, 1(3):233–241, 1981.DOI
  22. [22]Hans Garmo. The asymptotic distribution of long cycles in random regular graphs. Random Structures & Algorithms, 15(1):43–92, 1999.doi.org/10.1002/(sici)1098-2418(199908)15:1<43::aid-rsa3>3.0.co;2-s
  23. [23]Stuart Geman. The spectral radius of large random matrices. Ann. Probab., 14(4):1318–1328, 1986.DOI
  24. [24]Godfrey Harold Hardy and Edward Maitland Wright. An introduction to the theory of numbers. Oxford University Press, fifth edition, 1979.
  25. [25]Yukun He and Jiaoyang Huang. The oriented kesten–mckay law for random regular digraphs. arXiv preprint arXiv:2609.05297, 2026.arxiv.org/abs/2609.05297
  26. [26]Tobias Johnson. Exchangeable pairs, switchings, and random regular graphs. Electronic Journal of Combinatorics, 22(1):Paper P1.33, 2015.DOI
  27. [27]David A. Levin and Yuval Peres. Markov chains and mixing times. American Mathematical Society, Providence, RI, second edition, 2017. With contributions by Elizabeth L. Wilmer; with a chapter on “Coupling from the past” by James G. Propp and David B. Wilson.
  28. [28]Alexander E Litvak, Anna Lytova, Konstantin Tikhomirov, Nicole Tomczak-Jaegermann, and Pierre Youssef. Circular law for sparse random regular digraphs. Journal of the European Mathematical Society, 23(2):467–501, 2021.arxiv.org/abs/1801.05576
  29. [29]Theo McKenzie. An Alon-Boppana bound for the non-backtracking operator. arXiv preprint arXiv:2609.17529, 2026.arxiv.org/abs/2609.17529
  30. [30]Jensih C. Mehta and Leonard J. Schulman. Edge expansion and spectral gap of nonnegative matrices. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1200–1213. SIAM, 2020.arxiv.org/abs/1909.12497
  31. [31]James R. Norris. Markov Chains, volume 2 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 1997.
  32. [32]Ivan Nourdin and Giovanni Peccati. Universal Gaussian fluctuations of non-Hermitian matrix ensembles: from weak convergence to almost sure CLTs. ALEA Lat. Am. J. Probab. Math. Stat., 7:341–375, 2010.arxiv.org/abs/1002.1212
  33. [33]Sean O’Rourke and David Renfrew. Central limit theorem for linear eigenvalue statistics of elliptic random matrices. J. Theoret. Probab., 29(3):1121–1191, 2016.arxiv.org/abs/1410.4586
  34. [34]Ori Parzanchevski. Ramanujan graphs and digraphs. In Matthias Keller, Daniel Lenz, and Radoslaw K. Wojciechowski, editors, Analysis and Geometry on Graphs and Manifolds, volume 461 of London Mathematical Society Lecture Note Series, pages 344–367. Cambridge University Press, 2020.DOI
  35. [35]Brian Rider and Jack W. Silverstein. Gaussian fluctuations for non-Hermitian random matrix ensembles. Ann. Probab., 34(6):2118–2143, 2006.DOI
  36. [36]Ashwin Sah, Julian Sahasrabudhe, and Mehtaab Sawhney. The limiting spectral law for sparse iid matrices. arXiv preprint arXiv:2310.17635, 2023. To appear in Forum of Mathematics, Pi.arxiv.org/abs/2310.17635
  37. [37]Alexander Soshnikov. Universality at the edge of the spectrum in Wigner random matrices. Comm. Math. Phys., 207(3):697–733, 1999.
  38. [38]Terence Tao. Topics in Random Matrix Theory, volume 132 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2012.DOI
  39. [39]Sarah Timhadjelt. Spectral gap of a convex combination of a random permutation and a deterministic matrix. Electronic Journal of Probability, 31:1–47, 2026.DOI
  40. [40]Van H. Vu. Spectral norm of random matrices. Combinatorica, 27(6):721–736, 2007.

Paper details

vlnc:W_366yc4ny
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 16

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents