Structure of eigenvectors of random regular digraphs
HTML articles powered by AMS MathViewer
- by Alexander E. Litvak, Anna Lytova, Konstantin Tikhomirov, Nicole Tomczak-Jaegermann and Pierre Youssef PDF
- Trans. Amer. Math. Soc. 371 (2019), 8097-8172 Request permission
Abstract:
Let $d$ and $n$ be integers satisfying $C\leq d\leq \exp (c\sqrt {\ln n})$ for some universal constants $c, C>0$, and let $z\in \mathbb {C}$. Denote by $M$ the adjacency matrix of a random $d$-regular directed graph on $n$ vertices. In this paper, we study the structure of the kernel of submatrices of $M-z \textrm {Id}$, formed by removing a subset of rows. We show that with large probability the kernel consists of two nonintersecting types of vectors, which we call very steep and gradual with many levels. As a corollary, we show, in particular, that every eigenvector of $M$, except for constant multiples of $(1,1,\dots ,1)$, possesses a weak delocalization property: its level sets have cardinality less than $Cn\ln ^2 d/\ln n$. For a large constant $d$, this provides principally new structural information on eigenvectors, implying that the number of their level sets grows to infinity with $n$. As a key technical ingredient of our proofs, we introduce a decomposition of $\mathbb {C}^n$ into vectors of different degrees of “structuredness”, which is an alternative to the decomposition based on the least common denominator in the regime when the underlying random matrix is very sparse.References
- N. Alon and V. D. Milman, $\lambda _1,$ isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B 38 (1985), no. 1, 73–88. MR 782626, DOI 10.1016/0095-8956(85)90092-9
- Nalini Anantharaman and Etienne Le Masson, Quantum ergodicity on large regular graphs, Duke Math. J. 164 (2015), no. 4, 723–765. MR 3322309, DOI 10.1215/00127094-2881592
- Á. Backhausz and B. Szegedy, On the almost eigenvectors of random regular graphs, arXiv:1607.04785 (2016).
- Zhidong Bai and Jack W. Silverstein, Spectral analysis of large dimensional random matrices, 2nd ed., Springer Series in Statistics, Springer, New York, 2010. MR 2567175, DOI 10.1007/978-1-4419-0661-8
- Anirban Basak, Nicholas Cook, and Ofer Zeitouni, Circular law for the sum of random permutation matrices, Electron. J. Probab. 23 (2018), Paper No. 33, 51. MR 3798243, DOI 10.1214/18-EJP162
- Anirban Basak and Mark Rudelson, Invertibility of sparse non-Hermitian matrices, Adv. Math. 310 (2017), 426–483. MR 3620692, DOI 10.1016/j.aim.2017.02.009
- A. Basak and M. Rudelson, The circular law for sparse non-Hermitian matrices, arXiv:1707.03675 (2017).
- R. Bauerschmidt, J. Huang, and H.-T. Yau, Local Kesten–McKay law for random regular graphs, arXiv:1609.09052 (2016).
- Roland Bauerschmidt, Antti Knowles, and Horng-Tzer Yau, Local semicircle law for random regular graphs, Comm. Pure Appl. Math. 70 (2017), no. 10, 1898–1960. MR 3688032, DOI 10.1002/cpa.21709
- C. Bordenave, A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts, arXiv:1502.04482 (2015).
- Charles Bordenave and Djalil Chafaï, Around the circular law, Probab. Surv. 9 (2012), 1–89. MR 2908617, DOI 10.1214/11-PS183
- Paul Bourgade, Jiaoyang Huang, and Horng-Tzer Yau, Eigenvector statistics of sparse random matrices, Electron. J. Probab. 22 (2017), Paper No. 64, 38. MR 3690289, DOI 10.1214/17-EJP81
- Andrei Z. Broder, Alan M. Frieze, Stephen Suen, and Eli Upfal, Optimal construction of edge-disjoint paths in random graphs, SIAM J. Comput. 28 (1999), no. 2, 541–573. MR 1634360, DOI 10.1137/S0097539795290805
- Nicholas A. Cook, Discrepancy properties for random regular digraphs, Random Structures Algorithms 50 (2017), no. 1, 23–58. MR 3583025, DOI 10.1002/rsa.20643
- Nicholas A. Cook, On the singularity of adjacency matrices for random regular digraphs, Probab. Theory Related Fields 167 (2017), no. 1-2, 143–200. MR 3602844, DOI 10.1007/s00440-015-0679-8
- N. Cook, The circular law for random regular digraphs, arXiv:1703.05839 (2017). Ann. Inst. Henri Poincaré Probab. Stat. (to appear).
- Nicholas Cook, Larry Goldstein, and Tobias Johnson, Size biased couplings and the spectral gap for random regular graphs, Ann. Probab. 46 (2018), no. 1, 72–125. MR 3758727, DOI 10.1214/17-AOP1180
- Leander Geisinger, Convergence of the density of states and delocalization of eigenvectors on random regular graphs, J. Spectr. Theory 5 (2015), no. 4, 783–827. MR 3433288, DOI 10.4171/JST/114
- Jozef Dodziuk, Difference equations, isoperimetric inequality and transience of certain random walks, Trans. Amer. Math. Soc. 284 (1984), no. 2, 787–794. MR 743744, DOI 10.1090/S0002-9947-1984-0743744-X
- Ioana Dumitriu and Soumik Pal, Sparse regular random graphs: spectral density and eigenvectors, Ann. Probab. 40 (2012), no. 5, 2197–2235. MR 3025715, DOI 10.1214/11-AOP673
- Ioana Dumitriu, Tobias Johnson, Soumik Pal, and Elliot Paquette, Functional limit theorems for random regular graphs, Probab. Theory Related Fields 156 (2013), no. 3-4, 921–975. MR 3078290, DOI 10.1007/s00440-012-0447-y
- C. G. Esseen, On the Kolmogorov-Rogozin inequality for the concentration function, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 5 (1966), 210–216. MR 205297, DOI 10.1007/BF00533057
- C. G. Esseen, On the concentration function of a sum of independent random variables, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 9 (1968), 290–308. MR 231419, DOI 10.1007/BF00531753
- Joel Friedman, A proof of Alon’s second eigenvalue conjecture and related problems, Mem. Amer. Math. Soc. 195 (2008), no. 910, viii+100. MR 2437174, DOI 10.1090/memo/0910
- J. Friedman, J. Kahn, and E. Szemerédi, On the second eigenvalue of random regular graphs, in Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing, ACM, New York, 1989, pp. 587–598.
- V. L. Girko, The circular law, Teor. Veroyatnost. i Primenen. 29 (1984), no. 4, 669–679 (Russian). MR 773436
- Friedrich Götze and Alexander Tikhomirov, The circular law for random matrices, Ann. Probab. 38 (2010), no. 4, 1444–1491. MR 2663633, DOI 10.1214/09-AOP522
- Catherine Greenhill, Brendan D. McKay, and Xiaoji Wang, Asymptotic enumeration of sparse 0-1 matrices with irregular row and column sums, J. Combin. Theory Ser. A 113 (2006), no. 2, 291–324. MR 2199276, DOI 10.1016/j.jcta.2005.03.005
- Gábor Halász, On the distribution of additive arithmetic functions, Acta Arith. 27 (1975), 143–152. MR 369292, DOI 10.4064/aa-27-1-143-152
- G. Halász, Estimates for the concentration function of combinatorial number theory and probability, Period. Math. Hungar. 8 (1977), no. 3-4, 197–211. MR 494478, DOI 10.1007/BF02018403
- Wassily Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), 13–30. MR 144363
- Shlomo Hoory, Nathan Linial, and Avi Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439–561. MR 2247919, DOI 10.1090/S0273-0979-06-01126-8
- Jeff Kahn, János Komlós, and Endre Szemerédi, On the probability that a random $\pm 1$-matrix is singular, J. Amer. Math. Soc. 8 (1995), no. 1, 223–240. MR 1260107, DOI 10.1090/S0894-0347-1995-1260107-2
- Harry Kesten, Symmetric random walks on groups, Trans. Amer. Math. Soc. 92 (1959), 336–354. MR 109367, DOI 10.1090/S0002-9947-1959-0109367-6
- Harry Kesten, A sharper form of the Doeblin-Lévy-Kolmogorov-Rogozin inequality for concentration functions, Math. Scand. 25 (1969), 133–144. MR 258095, DOI 10.7146/math.scand.a-10950
- Alexander E. Litvak, Anna Lytova, Konstantin Tikhomirov, Nicole Tomczak-Jaegermann, and Pierre Youssef, Anti-concentration property for random digraphs and invertibility of their adjacency matrices, C. R. Math. Acad. Sci. Paris 354 (2016), no. 2, 121–124 (English, with English and French summaries). MR 3456885, DOI 10.1016/j.crma.2015.12.002
- Alexander E. Litvak, Anna Lytova, Konstantin Tikhomirov, Nicole Tomczak-Jaegermann, and Pierre Youssef, Adjacency matrices of random digraphs: singularity and anti-concentration, J. Math. Anal. Appl. 445 (2017), no. 2, 1447–1491. MR 3545253, DOI 10.1016/j.jmaa.2016.08.020
- A. E. Litvak, A. Lytova, K. Tikhomirov, N. Tomczak-Jaegermann, and P. Youssef, The smallest singular value of a shifted $d$-regular random square matrix, Probab. Theory Related Fields (to appear).
- A. E. Litvak, A. Lytova, K. Tikhomirov, N. Tomczak-Jaegermann, and P. Youssef, The circular law for sparse random regular digraphs, arXiv:1801.05576 (2018).
- Alexander E. Litvak, Anna Lytova, Konstantin Tikhomirov, Nicole Tomczak-Jaegermann, and Pierre Youssef, The rank of random regular digraphs of constant degree, J. Complexity 48 (2018), 103–110. MR 3828839, DOI 10.1016/j.jco.2018.05.004
- A. E. Litvak, A. Pajor, M. Rudelson, and N. Tomczak-Jaegermann, Smallest singular value of random matrices and geometry of random polytopes, Adv. Math. 195 (2005), no. 2, 491–523. MR 2146352, DOI 10.1016/j.aim.2004.08.004
- Alexander E. Litvak and Omar Rivasplata, Smallest singular value of sparse random matrices, Studia Math. 212 (2012), no. 3, 195–218. MR 3009072, DOI 10.4064/sm212-3-1
- Brendan D. McKay, The expected eigenvalue distribution of a large regular graph, Linear Algebra Appl. 40 (1981), 203–216. MR 629617, DOI 10.1016/0024-3795(81)90150-6
- Brendan D. McKay, Asymptotics for $0$-$1$ matrices with prescribed line sums, Enumeration and design (Waterloo, Ont., 1982) Academic Press, Toronto, ON, 1984, pp. 225–238. MR 782316
- A. L. Miroshnikov, Estimates for a multidimensional Lévy concentration function, Teor. Veroyatnost. i Primenen. 34 (1989), no. 3, 593–598 (Russian); English transl., Theory Probab. Appl. 34 (1989), no. 3, 535–540 (1990). MR 1022646, DOI 10.1137/1134064
- Doron Puder, Expansion of random graphs: new proofs, new results, Invent. Math. 201 (2015), no. 3, 845–908. MR 3385636, DOI 10.1007/s00222-014-0560-x
- Elizaveta Rebrova and Konstantin Tikhomirov, Coverings of random ellipsoids, and invertibility of matrices with i.i.d. heavy-tailed entries, Israel J. Math. 227 (2018), no. 2, 507–544. MR 3846333, DOI 10.1007/s11856-018-1732-y
- Mark Rudelson, Invertibility of random matrices: norm of the inverse, Ann. of Math. (2) 168 (2008), no. 2, 575–600. MR 2434885, DOI 10.4007/annals.2008.168.575
- Mark Rudelson and Roman Vershynin, The Littlewood-Offord problem and invertibility of random matrices, Adv. Math. 218 (2008), no. 2, 600–633. MR 2407948, DOI 10.1016/j.aim.2008.01.010
- Mark Rudelson and Roman Vershynin, Smallest singular value of a random rectangular matrix, Comm. Pure Appl. Math. 62 (2009), no. 12, 1707–1739. MR 2569075, DOI 10.1002/cpa.20294
- Mark Rudelson and Roman Vershynin, Non-asymptotic theory of random matrices: extreme singular values, Proceedings of the International Congress of Mathematicians. Volume III, Hindustan Book Agency, New Delhi, 2010, pp. 1576–1602. MR 2827856
- Mark Rudelson and Roman Vershynin, Delocalization of eigenvectors of random matrices with independent entries, Duke Math. J. 164 (2015), no. 13, 2507–2538. MR 3405592, DOI 10.1215/00127094-3129809
- Mark Rudelson and Roman Vershynin, No-gaps delocalization for general random matrices, Geom. Funct. Anal. 26 (2016), no. 6, 1716–1776. MR 3579707, DOI 10.1007/s00039-016-0389-0
- Terence Tao and Van Vu, On the singularity probability of random Bernoulli matrices, J. Amer. Math. Soc. 20 (2007), no. 3, 603–628. MR 2291914, DOI 10.1090/S0894-0347-07-00555-3
- Terence Tao and Van Vu, Random matrices: the circular law, Commun. Contemp. Math. 10 (2008), no. 2, 261–307. MR 2409368, DOI 10.1142/S0219199708002788
- Terence Tao and Van H. Vu, Inverse Littlewood-Offord theorems and the condition number of random discrete matrices, Ann. of Math. (2) 169 (2009), no. 2, 595–632. MR 2480613, DOI 10.4007/annals.2009.169.595
- K. Tikhomirov and P. Youssef, The spectral gap of dense random regular graphs, arXiv:1610.01765 (2016). Ann. Probab. (to appear).
- Linh V. Tran, Van H. Vu, and Ke Wang, Sparse random graphs: eigenvalues and eigenvectors, Random Structures Algorithms 42 (2013), no. 1, 110–134. MR 2999215, DOI 10.1002/rsa.20406
- Roman Vershynin, Introduction to the non-asymptotic analysis of random matrices, Compressed sensing, Cambridge Univ. Press, Cambridge, 2012, pp. 210–268. MR 2963170
Additional Information
- Alexander E. Litvak
- Affiliation: Department of Mathematics and Statistical Sciences, University of Alberta, Edmonton, Alberta T6G 2G1, Canada
- MR Author ID: 367520
- Email: aelitvak@gmail.com
- Anna Lytova
- Affiliation: Faculty of Mathematics, Physics, and Computer Science, University of Opole, plac Kopernika 11A, 45-040 Opole, Poland
- MR Author ID: 631572
- Email: alytova@uni.opole.pl
- Konstantin Tikhomirov
- Affiliation: Department of Mathematics, Princeton University, Fine Hall, Washington road, Princeton, New Jersey 08544
- MR Author ID: 806060
- Email: kt12@math.princeton.edu
- Nicole Tomczak-Jaegermann
- Affiliation: Department of Mathematics and Statistical Sciences, University of Alberta, Edmonton, Alberta T6G 2G1, Canada
- MR Author ID: 173265
- Email: nicole.tomczak@ualberta.ca
- Pierre Youssef
- Affiliation: Université Paris Diderot, Laboratoire de Probabilités, Statistiques et Modélisation, 75013 Paris, France
- MR Author ID: 1051458
- Email: youssef@lpsm.paris
- Received by editor(s): May 8, 2018
- Received by editor(s) in revised form: October 16, 2018
- Published electronically: January 16, 2019
- Additional Notes: The first two authors visited the Mathematical Sciences Research Institute (MSRI) in Berkeley, California.
A significant part of this work was completed while the last three authors were in residence at the MSRI, supported by NSF grant DMS-1440140. The hospitality of MSRI and of the organizers of the program Geometric Functional Analysis and Applications is gratefully acknowledged.
The research of the last author was partially supported by grant ANR-16-CE40-0024-01. - © Copyright 2019 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 371 (2019), 8097-8172
- MSC (2010): Primary 60B20, 15B52, 46B06, 05C80; Secondary 46B09, 60C05
- DOI: https://doi.org/10.1090/tran/7742
- MathSciNet review: 3955544