Singularity of random symmetric matrices revisited

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

doi:10.1090/proc/15807

Singularity of random symmetric matrices revisited
HTML articles powered by AMS MathViewer

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

Proc. Amer. Math. Soc. 150 (2022), 3147-3159

DOI: https://doi.org/10.1090/proc/15807

Published electronically: March 24, 2022

PDF

Abstract:

Let $M_n$ be drawn uniformly from all $\pm 1$ symmetric $n \times n$ matrices. We show that the probability that $M_n$ is singular is at most $\exp (-c(n\log n)^{1/2})$, which represents a natural barrier in recent approaches to this problem. In addition to improving on the best-known previous bound of Campos, Mattos, Morris and Morrison of $\exp (-c n^{1/2})$ on the singularity probability, our method is different and considerably simpler: we prove a “rough” inverse Littlewood-Offord theorem by a simple combinatorial iteration.

References

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, 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
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
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
V. Jain, A. Sah, and M. Sawhney, On the smallest singular value of symmetric random matrices, preprint arXiv:2011.02344, 2020.
V. Jain, A. Sah, and M. Sawhney, Singularity of discrete random matrices ii, preprint arXiv:2010.06554, 2020.
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
J. Komlós, On the determinant of $(0,\,1)$ matrices, Studia Sci. Math. Hungar. 2 (1967), 7–21. MR 221962
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
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, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2006. MR 2289012, DOI 10.1017/CBO9780511755149
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