The singularity probability of a random symmetric matrix is exponentially small

Campos, Marcelo; Jenssen, Matthew; Michelen, Marcus; Sahasrabudhe, Julian

doi:10.1090/jams/1042

The singularity probability of a random symmetric matrix is exponentially small
HTML articles powered by AMS MathViewer

by Marcelo Campos, Matthew Jenssen, Marcus Michelen and Julian Sahasrabudhe

J. Amer. Math. Soc.

DOI: https://doi.org/10.1090/jams/1042

Published electronically: January 19, 2024

HTML | PDF | Request permission

Abstract:

Let $A$ be drawn uniformly at random from the set of all $n\times n$ symmetric matrices with entries in $\{-1,1\}$. We show that \[ \mathbb {P}( \det (A) = 0 ) \leqslant e^{-cn}, \] where $c>0$ is an absolute constant, thereby resolving a long-standing conjecture.

References

Z. D. Bai and Y. Q. Yin, Necessary and sufficient conditions for almost sure convergence of the largest eigenvalue of a Wigner matrix, Ann. Probab. 16 (1988), no. 4, 1729–1741. MR 958213
József Balogh, Robert Morris, and Wojciech Samotij, Independent sets in hypergraphs, J. Amer. Math. Soc. 28 (2015), no. 3, 669–709. MR 3327533, DOI 10.1090/S0894-0347-2014-00816-X
Béla Bollobás, Random graphs, Springer, 1998.
Christer Borell, Inequalities of the Brunn-Minkowski type for Gaussian measures, Probab. Theory Related Fields 140 (2008), no. 1-2, 195–205. MR 2357675, DOI 10.1007/s00440-007-0062-5
Jean Bourgain, Van H. Vu, and Philip Matchett Wood, On the singularity probability of discrete random matrices, J. Funct. Anal. 258 (2010), no. 2, 559–603. MR 2557947, DOI 10.1016/j.jfa.2009.04.016
Marcelo Campos, Matthew Jenssen, Marcus Michelen, and Julian Sahasrabudhe, Singularity of random symmetric matrices revisited, Proc. Amer. Math. Soc. 150 (2022), no. 7, 3147–3159. MR 4428895, DOI 10.1090/proc/15807
Marcelo Campos, Matthew Jenssen, Marcus Michelen, and Julian Sahasrabudhe, The singularity probability of a random symmetric matrix is exponentially small, arXiv:2105.11384 (2021).
Marcelo Campos, Letícia Mattos, Robert Morris, and Natasha Morrison, On the singularity of random symmetric matrices, Duke Math. J. 170 (2021), no. 5, 881–907. MR 4255046, DOI 10.1215/00127094-2020-0054
Kevin P. Costello, Terence Tao, and Van Vu, Random symmetric matrices are almost surely nonsingular, Duke Math. J. 135 (2006), no. 2, 395–413. MR 2267289, DOI 10.1215/S0012-7094-06-13527-5
P. Erdös, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. 51 (1945), 898–902. MR 14608, DOI 10.1090/S0002-9904-1945-08454-7
Asaf Ferber and Vishesh Jain, Singularity of random symmetric matrices—a combinatorial approach to improved bounds, Forum Math. Sigma 7 (2019), Paper No. e22, 29. MR 3993806, DOI 10.1017/fms.2019.21
Asaf Ferber, Vishesh Jain, Kyle Luh, and Wojciech Samotij, On the counting problem in inverse Littlewood-Offord theory, J. Lond. Math. Soc. (2) 103 (2021), no. 4, 1333–1362. MR 4273471, DOI 10.1112/jlms.12409
Asaf Ferber, Vishesh Jain, and Yufei Zhao, On the number of Hadamard matrices via anti-concentration, Combin. Probab. Comput. 31 (2022), no. 3, 455–477. MR 4410720, DOI 10.1017/s0963548321000377
P. Frankl and Z. Füredi, Solution of the Littlewood-Offord problem in high dimensions, Ann. of Math. (2) 128 (1988), no. 2, 259–270. MR 960947, DOI 10.2307/1971442
Jerrold R. Griggs, Jeffrey C. Lagarias, Andrew M. Odlyzko, and James B. Shearer, On the tightest packing of sums of vectors, European J. Combin. 4 (1983), no. 3, 231–236. MR 725071, DOI 10.1016/S0195-6698(83)80017-1
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
Vishesh Jain, Ashwin Sah, and Mehtaab Sawhney, Singularity of discrete random matrices, Geom. Funct. Anal. 31 (2021), no. 5, 1160–1218. MR 4356701, DOI 10.1007/s00039-021-00580-6
Vishesh Jain, Ashwin Sah, and Mehtaab Sawhney, On the smallest singular value of symmetric random matrices, Combin. Probab. Comput. 31 (2022), no. 4, 662–683. MR 4439776, DOI 10.1017/s0963548321000511
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
Gy. Katona, On a conjecture of Erdős and a stronger form of Sperner’s theorem, Studia Sci. Math. Hungar. 1 (1966), 59–63. MR 205864
Daniel J. Kleitman, On a lemma of Littlewood and Offord on the distributions of linear combinations of vectors, Advances in Math. 5 (1970), 155–157 (1970). MR 265923, DOI 10.1016/0001-8708(70)90038-1
J. Komlós, On the determinant of $(0,\,1)$ matrices, Studia Sci. Math. Hungar. 2 (1967), 7–21. MR 221962
J. Komlós, On the determinant of random matrices, Studia Sci. Math. Hungar. 3 (1968), 387–399. MR 238371
J. E. Littlewood and A. C. Offord, On the Number of Real Roots of a Random Algebraic Equation, J. London Math. Soc. 13 (1938), no. 4, 288–295. MR 1574980, DOI 10.1112/jlms/s1-13.4.288
M. Kac, On the average number of real roots of a random algebraic equation, Bull. Amer. Math. Soc. 49 (1943), 314–320. MR 7812, DOI 10.1090/S0002-9904-1943-07912-8
Alexander E. Litvak and Konstantin E. Tikhomirov, Singularity of sparse Bernoulli matrices, Duke Math. J. 171 (2022), no. 5, 1135–1233. MR 4402560, DOI 10.1215/00127094-2021-0056
Galyna V. Livshyts, The smallest singular value of heavy-tailed not necessarily i.i.d. random matrices via random rounding, J. Anal. Math. 145 (2021), no. 1, 257–306. MR 4361906, DOI 10.1007/s11854-021-0183-2
Galyna V. Livshyts, Konstantin Tikhomirov, and Roman Vershynin, The smallest singular value of inhomogeneous square random matrices, Ann. Probab. 49 (2021), no. 3, 1286–1309. MR 4255145, DOI 10.1214/20-aop1481
Mark W. Meckes, Concentration of norms and eigenvalues of random matrices, J. Funct. Anal. 211 (2004), no. 2, 508–524. MR 2057479, DOI 10.1016/S0022-1236(03)00198-8
Hoi Nguyen and Van Vu, Optimal inverse Littlewood-Offord theorems, Adv. Math. 226 (2011), no. 6, 5298–5319. MR 2775902, DOI 10.1016/j.aim.2011.01.005
Hoi H. Nguyen, Inverse Littlewood-Offord problems and the singularity of random symmetric matrices, Duke Math. J. 161 (2012), no. 4, 545–586. MR 2891529, DOI 10.1215/00127094-1548344
Hoi H. Nguyen and Van H. Vu, Small ball probability, inverse theorems, and applications, Erdös centennial, Bolyai Soc. Math. Stud., vol. 25, János Bolyai Math. Soc., Budapest, 2013, pp. 409–463. MR 3203607, DOI 10.1007/978-3-642-39286-3_{1}6
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
Emmanuel Rio, On McDiarmid’s concentration inequality, Electron. Commun. Probab. 18 (2013), no. 44, 11. MR 3070910, DOI 10.1214/ECP.v18-2659
Emmanuel Rio, Small ball probabilities for linear images of high-dimensional distributions, Int. Math. Res. 2015 (2015), no. 19, 9594–9617.
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
A. Sali, Stronger form of an $M$-part Sperner theorem, European J. Combin. 4 (1983), no. 2, 179–183. MR 705971, DOI 10.1016/S0195-6698(83)80048-1
A. Sárközi and E. Szemerédi, Über ein Problem von Erdős und Moser, Acta Arith. 11 (1965), 205–208 (German). MR 182619, DOI 10.4064/aa-11-2-205-208
David Saxton and Andrew Thomason, Hypergraph containers, Invent. Math. 201 (2015), no. 3, 925–992. MR 3385638, DOI 10.1007/s00222-014-0562-8
Richard P. Stanley, Weyl groups, the hard Lefschetz theorem, and the Sperner property, SIAM J. Algebraic Discrete Methods 1 (1980), no. 2, 168–184. MR 578321, DOI 10.1137/0601021
Michel Talagrand, A new look at independence, Ann. Probab. 24 (1996), no. 1, 1–34. MR 1387624, DOI 10.1214/aop/1042644705
Terence Tao, Topics in random matrix theory, Graduate Studies in Mathematics, vol. 132, American Mathematical Society, Providence, RI, 2012. MR 2906465, DOI 10.1090/gsm/132
Terence Tao and Van Vu, On random $\pm 1$ matrices: singularity and determinant, Random Structures Algorithms 28 (2006), no. 1, 1–23. MR 2187480, DOI 10.1002/rsa.20109
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, A sharp inverse Littlewood-Offord theorem, Random Structures Algorithms 37 (2010), no. 4, 525–539. MR 2760363, DOI 10.1002/rsa.20327
Terence Tao and Van Vu, The Littlewood-Offord problem in high dimensions and a conjecture of Frankl and Füredi, Combinatorica 32 (2012), no. 3, 363–372. MR 2965282, DOI 10.1007/s00493-012-2716-x
Terence Tao and Van Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2006. MR 2289012, DOI 10.1017/CBO9780511755149
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
Konstantin Tikhomirov, Singularity of random Bernoulli matrices, Ann. of Math. (2) 191 (2020), no. 2, 593–634. MR 4076632, DOI 10.4007/annals.2020.191.2.6
Roman Vershynin, Invertibility of symmetric random matrices, Random Structures Algorithms 44 (2014), no. 2, 135–182. MR 3158627, DOI 10.1002/rsa.20429
Van Vu, Random discrete matrices, Horizons of combinatorics, Bolyai Soc. Math. Stud., vol. 17, Springer, Berlin, 2008, pp. 257–280. MR 2432537, DOI 10.1007/978-3-540-77200-2_{1}3
Van H. Vu, Recent progress in combinatorial random matrix theory, Probab. Surv. 18 (2021), 179–200. MR 4260513, DOI 10.1214/20-ps346