Sparse matrices: convergence of the characteristic polynomial seen from infinity. (English) Zbl 1508.60005

Coste, Simon

Electron. J. Probab. 28, Paper No. 8, 40 p. (2023).

Summary: We prove that the reverse characteristic polynomial \(\det ({I_n}-z{A_n})\) of a random \(n\times n\) matrix \({A_n}\) with iid Bernoulli\((d/ n)\) entries converges in distribution towards the random infinite product \[\prod \limits_{\ell =1}^\infty(1-{z^\ell})^{Y_\ell}\] where \({Y_{\ell }}\) are independent Poisson\(({d^{\ell }}/ \ell )\) random variables. We show that this random function is a Poisson analog of more classical Gaussian objects such as the Gaussian holomorphic chaos. As a byproduct, we obtain new simple proofs of previous results on the asymptotic behaviour of extremal eigenvalues of sparse Erdős-Rényi digraphs: for every \(d > 1\), the greatest eigenvalue of \({A_n}\) is close to \(d\) and the second greatest is smaller than \(\sqrt{d} \), a Ramanujan-like property for irregular digraphs. For \(d > 1\), the only non-zero eigenvalues of \({A_n}\) converge to a Poisson multipoint process on the unit circle.
Our results also extend to the semi-sparse regime where \(d\) is allowed to grow to \(\infty\) with \(n\), slower than \({n^{o(1)}}\). We show that the reverse characteristic polynomial converges towards a more classical object written in terms of the exponential of a log-correlated real Gaussian field. In the semi-sparse regime, the empirical spectral distribution of \({A_n}/ \sqrt{{d_n}}\) converges to the circle distribution; as a consequence of our results, the second eigenvalue sticks to the edge of the circle.

MSC:

60B20	Random matrices (probabilistic aspects)
15B52	Random matrices (algebraic aspects)
05C20	Directed graphs (digraphs), tournaments

Keywords:

eigenvalues; random directed graphs; random matrices; sparse matrices

References:

[1]	Martin Aigner, A course in enumeration, vol. 238, Springer Science & Business Media, 2007. · Zbl 1123.05001
[2]	Anirban Basak, Mark Rudelson, et al., The circular law for sparse non-hermitian matrices, Annals of Probability 47 (2019), no. 4, 2359-2416. · Zbl 1472.60006
[3]	Anirban Basak and Ofer Zeitouni, Outliers of random perturbations of toeplitz matrices with finite symbols, Probability Theory and Related Fields 178 (2020), no. 3, 771-826. · Zbl 1451.60014
[4]	Edward A. Bender, Partitions of multisets, Discrete Mathematics 9 (1974), no. 4, 301-311. · Zbl 0289.05014
[5]	Charles Bordenave, A new proof of friedman’s second eigenvalue theorem and its extension to random lifts, arXiv preprint 1502.04482 (2015).
[6]	Charles Bordenave, Pietro Caputo, Djalil Chafaï, Konstantin Tikhomirov, et al., On the spectral radius of a random matrix: An upper bound without fourth moment, Annals of Probability 46 (2018), no. 4, 2268-2286. · Zbl 1393.05130
[7]	Charles Bordenave, Djalil Chafaï, and David García-Zelada, Convergence of the spectral radius of a random matrix through its characteristic polynomial, 2020.
[8]	Charles Bordenave and Benoît Collins, Eigenvalues of random lifts and polynomials of random permutation matrices, Ann. of Math. (2) 190 (2019), no. 3, 811-875. · Zbl 1446.60004
[9]	Charles Bordenave, Simon Coste, and Raj Rao Nadakuditi, Detection thresholds in very sparse matrix completion, arXiv preprint 2005.06062 (2020).
[10]	Charles Bordenave, Marc Lelarge, and Laurent Massoulié, Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, IEEE, 2015, pp. 1347-1357.
[11]	Stéphane Boucheron, Gábor Lugosi, and Pascal Massart, Concentration inequalities: A nonasymptotic theory of independence, Oxford University Press, 2013. · Zbl 1279.60005
[12]	Gerandy Brito, Ioana Dumitriu, and Kameron Decker Harris, Spectral gap in random bipartite biregular graphs and applications, 2020.
[13]	Simon Coste, The spectral gap of sparse random digraphs, Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, vol. 57, Institut Henri Poincaré, 2021, pp. 644-684. · Zbl 1468.05093
[14]	Simon Coste, Gaultier Lambert, and Yizhe Zhu, The characteristic polynomial of sums of random permutations and regular digraphs, 2022.
[15]	Simon Coste and Ludovic Stephan, A simpler spectral approach for clustering in directed networks, 2021.
[16]	Persi Diaconis and Alex Gamburd, Random matrices, magic squares and matching polynomials, Electron. J. Combin. 11 (2004/06), no. 2, Research Paper 2, 26. · Zbl 1050.05011
[17]	Persi Diaconis and Mehrdad Shahshahani, On the eigenvalues of random matrices, vol. 31A, 1994, Studies in applied probability, pp. 49-62. · Zbl 0807.15015
[18]	Ioana Dumitriu, Tobias Johnson, Soumik Pal, and Elliot Paquette, Functional limit theorems for random regular graphs, Probability Theory and Related Fields 156 (2013), no. 3-4, 921-975. · Zbl 1271.05088
[19]	Joel Friedman, A proof of alon’s second eigenvalue conjecture and related problems, American Mathematical Soc., 2008. · Zbl 1177.05070
[20]	Z. Füredi and J. Komlós, The eigenvalues of random symmetric matrices, Combinatorica 1 (1981), no. 3, 233-241. · Zbl 0494.15010
[21]	Yan V Fyodorov and Jonathan P Keating, Freezing transitions and extreme values: random matrix theory, and disordered landscapes, Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 372 (2014), no. 2007, 20120503. · Zbl 1330.82028
[22]	Svante Janson, Tomasz Luczak, and Andrzej Rucinski, Random graphs, vol. 45, John Wiley & Sons, 2011.
[23]	Tiefeng Jiang and Sho Matsumoto, Moments of traces of circular beta-ensembles, The Annals of Probability 43 (2015), no. 6, 3279-3336. · Zbl 1388.60029
[24]	Jean-Pierre Kahane, Some random series of functions, vol. 5, Cambridge University Press, 1993. · Zbl 0805.60007
[25]	Fernando Lucas Metz, Izaak Neri, and Tim Rogers, Spectral theory of sparse non-hermitian random matrices, Journal of Physics A: Mathematical and Theoretical 52 (2019), no. 43, 434003. · Zbl 1509.15025
[26]	Joseph Najnudel, Elliot Paquette, and Nick Simm, Secular coefficients and the holomorphic multiplicative chaos, 2020.
[27]	Alon Nilli, On the second eigenvalue of a graph, Discrete Mathematics 91 (1991), no. 2, 207-210. · Zbl 0771.05064
[28]	Guillaume Remy et al., The fyodorov-bouchaud formula and liouville conformal field theory, Duke Mathematical Journal 169 (2020), no. 1, 177-211. · Zbl 1465.60032
[29]	Rémi Rhodes and Vincent Vargas, Gaussian multiplicative chaos and applications: a review, 2013.
[30]	Mark Rudelson and Konstantin Tikhomirov, The sparse circular law under minimal assumptions, Geometric and Functional Analysis 29 (2019), no. 2, 561-637. · Zbl 1442.15058
[31]	Tomoyuki Shirai, Limit theorems for random analytic functions and their zeros: Dedicated to the late professor yasunori okabe (functions in number theory and their probabilistic aspects), RIMS Kokyuroku Bessatsu 34 (2012), 335-359. · Zbl 1276.60040
[32]	Barry Simon et al., A comprehensive course in analysis, American Mathematical Society Providence, Rhode Island, 2015. · Zbl 1331.00001
[33]	Yizhe Zhu, On the second eigenvalue of random bipartite biregular graphs, arXiv preprint 2005.08103 (2020).