Singularity of random Bernoulli matrices

Konstantin Tikhomirov

doi:https://doi.org/10.4007/annals.2020.191.2.6

Abstract

For each $n$, let $M_n$ be an $n\times n$ random matrix with independent $\pm 1$ entries. We show that
$\mathbb{P}\{M_n$ is singular $\}=(1/2+o_n(1))^n$, which settles an old problem. Some generalizations are considered.

Show/hide bibliography for this article

[AK] $Go to document$ N. Alon and B. Klartag, "Optimal compression of approximate inner products and dimension reduction," in 58th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2017, IEEE Computer Soc., Los Alamitos, CA, 2017, pp. 639-650.

Show bibtex

@INCOLLECTION{AK, author = {Alon, Noga and Klartag, Bo'az}, title = {Optimal compression of approximate inner products and dimension reduction}, booktitle = {58th {A}nnual {IEEE} {S}ymposium on {F}oundations of {C}omputer {S}cience---{FOCS} 2017}, pages = {639--650}, publisher = {IEEE Computer Soc., Los Alamitos, CA}, year = {2017}, mrclass = {68U05 (68Q87)}, mrnumber = {3734268}, zblnumber = {}, doi = {10.1109/FOCS.2017.65}, url = {https://doi.org/10.1109/FOCS.2017.65}, }
[Arratia] $Go to document$ R. Arratia and S. DeSalvo, "On the singularity of random Bernoulli matrices—novel integer partitions and lower bound expansions," Ann. Comb., vol. 17, iss. 2, pp. 251-274, 2013.

Show bibtex

@ARTICLE{Arratia, author = {Arratia, Richard and DeSalvo, Stephen}, title = {On the singularity of random {B}ernoulli matrices---novel integer partitions and lower bound expansions}, journal = {Ann. Comb.}, fjournal = {Annals of Combinatorics}, volume = {17}, year = {2013}, number = {2}, pages = {251--274}, issn = {0218-0006}, mrclass = {60B20 (15B52)}, mrnumber = {3056767}, mrreviewer = {Manan Vyas}, doi = {10.1007/s00026-013-0176-7}, url = {https://doi.org/10.1007/s00026-013-0176-7}, zblnumber = {1320.60020}, }
[BVW] $Go to document$ J. Bourgain, V. H. Vu, and P. M. Wood, "On the singularity probability of discrete random matrices," J. Funct. Anal., vol. 258, iss. 2, pp. 559-603, 2010.

Show bibtex

@ARTICLE{BVW, author = {Bourgain, Jean and Vu, Van H. and Wood, Philip Matchett}, title = {On the singularity probability of discrete random matrices}, journal = {J. Funct. Anal.}, fjournal = {Journal of Functional Analysis}, volume = {258}, year = {2010}, number = {2}, pages = {559--603}, issn = {0022-1236}, mrclass = {60B20}, mrnumber = {2557947}, mrreviewer = {Guangyu Yang}, doi = {10.1016/j.jfa.2009.04.016}, url = {https://doi.org/10.1016/j.jfa.2009.04.016}, zblnumber = {1186.60003}, }
[CT] $Go to document$ D. Chafa"i and K. Tikhomirov, "On the convergence of the extremal eigenvalues of empirical covariance matrices with dependence," Probab. Theory Related Fields, vol. 170, iss. 3-4, pp. 847-889, 2018.

Show bibtex

@ARTICLE{CT, author = {Chafaï, Djalil and Tikhomirov, Konstantin}, title = {On the convergence of the extremal eigenvalues of empirical covariance matrices with dependence}, journal = {Probab. Theory Related Fields}, fjournal = {Probability Theory and Related Fields}, volume = {170}, year = {2018}, number = {3-4}, pages = {847--889}, issn = {0178-8051}, mrclass = {60B20 (15B52 52A23 62J10)}, mrnumber = {3773802}, mrreviewer = {Florent Benaych-Georges}, doi = {10.1007/s00440-017-0778-9}, url = {https://doi.org/10.1007/s00440-017-0778-9}, zblnumber = {1384.15008}, }
[KKS] $Go to document$ J. Kahn, J. Komlós, and E. Szemerédi, "On the probability that a random $\pm 1$-matrix is singular," J. Amer. Math. Soc., vol. 8, iss. 1, pp. 223-240, 1995.

Show bibtex

@ARTICLE{KKS, author = {Kahn, Jeff and Komlós, J\'{a}nos and Szemerédi, Endre}, title = {On the probability that a random {$\pm 1$}-matrix is singular}, journal = {J. Amer. Math. Soc.}, fjournal = {Journal of the American Mathematical Society}, volume = {8}, year = {1995}, number = {1}, pages = {223--240}, issn = {0894-0347}, mrclass = {15A52 (11K99 60C05)}, mrnumber = {1260107}, doi = {10.2307/2152887}, url = {https://doi.org/10.2307/2152887}, zblnumber = {0829.15018}, }
[KlLiv] B. Klartag and G. V. Livshyts, The lower bound for Koldobsky’s slicing inequality via random rounding, 2018.

Show bibtex

@MISC{KlLiv, author = {Klartag, B. and Livshyts, G. V.}, title = {The lower bound for {K}oldobsky's slicing inequality via random rounding}, arxiv = {1810.06189}, year = {2018}, zblnumber = {}, }
[Komlos] J. Komlós, "On the determinant of $(0,\,1)$ matrices," Studia Sci. Math. Hungar., vol. 2, pp. 7-21, 1967.

Show bibtex

@ARTICLE{Komlos, author = {Komlós, J.}, title = {On the determinant of {$(0,\,1)$} matrices}, journal = {Studia Sci. Math. Hungar.}, fjournal = {Studia Scientiarum Mathematicarum Hungarica. A Quarterly of the Hungarian Academy of Sciences}, volume = {2}, year = {1967}, pages = {7--21}, issn = {0081-6906}, mrclass = {05.25 (15.00)}, mrnumber = {0221962}, mrreviewer = {N. J. Pullman}, zblnumber = {0153.05002}, }
[LPRT] $Go to document$ A. E. Litvak, A. Pajor, M. Rudelson, and N. Tomczak-Jaegermann, "Smallest singular value of random matrices and geometry of random polytopes," Adv. Math., vol. 195, iss. 2, pp. 491-523, 2005.

Show bibtex

@ARTICLE{LPRT, author = {Litvak, A. E. and Pajor, A. and Rudelson, M. and Tomczak-Jaegermann, N.}, title = {Smallest singular value of random matrices and geometry of random polytopes}, journal = {Adv. Math.}, fjournal = {Advances in Mathematics}, volume = {195}, year = {2005}, number = {2}, pages = {491--523}, issn = {0001-8708}, mrclass = {52A22 (15A52 46B09 60D05)}, mrnumber = {2146352}, mrreviewer = {Béla Uhrin}, doi = {10.1016/j.aim.2004.08.004}, url = {https://doi.org/10.1016/j.aim.2004.08.004}, zblnumber = {1077.15021}, }
[Livshyts] G. V. Livshyts, The smallest singular value of heavy-tailed not necessarily i.i.d. random matrices via random rounding.

Show bibtex

@MISC{Livshyts, author = {Livshyts, G. V.}, title = {The smallest singular value of heavy-tailed not necessarily i.i.d. random matrices via random rounding}, zblnumber = {}, arxiv = {1811.07038}, note = {{\em . J. Anal. Math.}, to appear}, }
[RRounding] $Go to document$ P. Raghavan and C. D. Thompson, "Randomized rounding: A technique for provably good algorithms and algorithmic proofs," Combinatorica, vol. 7, iss. 4, pp. 365-374, 1987.

Show bibtex

@ARTICLE{RRounding, author = {Raghavan, P. and Thompson, C. D.}, title = {Randomized rounding: {A} technique for provably good algorithms and algorithmic proofs}, journal = {Combinatorica}, fjournal = {Combinatorica. An International Journal of the J\'{a}nos Bolyai Mathematical Society}, volume = {7}, year = {1987}, number = {4}, pages = {365--374}, issn = {0209-9683}, mrclass = {65K05 (90C09)}, mrnumber = {0931194}, mrreviewer = {V. V. Kolbin}, doi = {10.1007/BF02579324}, url = {https://doi.org/10.1007/BF02579324}, zblnumber = {0651.90052}, }
[Rogozin] $Go to document$ B. A. Rogozin, "On the increase of dispersion of sums of independent random variables," Teor. Verojatnost. i Primenen, vol. 6, pp. 106-108, 1961.

Show bibtex

@ARTICLE{Rogozin, author = {Rogozin, B. A.}, title = {On the increase of dispersion of sums of independent random variables }, journal = {Teor. Verojatnost. i Primenen}, fjournal = {Akademija Nauk SSSR. Teorija Verojatnosteĭ i ee Primenenija}, volume = {6}, year = {1961}, pages = {106--108}, issn = {0040-361x}, mrclass = {60.30}, mrnumber = {0131894}, mrreviewer = {G. Maruyama}, zblnumber = {0106.34003}, doi = {10.1137/1106010}, url = {https://doi.org/10.1137/1106010}, }
[Rudelsonannmath] $Go to document$ M. Rudelson, "Invertibility of random matrices: norm of the inverse," Ann. of Math. (2), vol. 168, iss. 2, pp. 575-600, 2008.

Show bibtex

@ARTICLE{Rudelsonannmath, author = {Rudelson, Mark}, title = {Invertibility of random matrices: norm of the inverse}, journal = {Ann. of Math. (2)}, fjournal = {Annals of Mathematics. Second Series}, volume = {168}, year = {2008}, number = {2}, pages = {575--600}, issn = {0003-486X}, mrclass = {46B09 (15B52 60D05 60E15 60F10)}, mrnumber = {2434885}, mrreviewer = {Sasha Sodin}, doi = {10.4007/annals.2008.168.575}, url = {https://doi.org/10.4007/annals.2008.168.575}, zblnumber = {1175.15030}, }
[RVadv] $Go to document$ M. Rudelson and R. Vershynin, "The Littlewood-Offord problem and invertibility of random matrices," Adv. Math., vol. 218, iss. 2, pp. 600-633, 2008.

Show bibtex

@ARTICLE{RVadv, author = {Rudelson, Mark and Vershynin, Roman}, title = {The {L}ittlewood-{O}fford problem and invertibility of random matrices}, journal = {Adv. Math.}, fjournal = {Advances in Mathematics}, volume = {218}, year = {2008}, number = {2}, pages = {600--633}, issn = {0001-8708}, mrclass = {60E15 (60B20)}, mrnumber = {2407948}, mrreviewer = {Ben Joseph Green}, doi = {10.1016/j.aim.2008.01.010}, url = {https://doi.org/10.1016/j.aim.2008.01.010}, zblnumber = {1139.15015}, }
[RVrect] $Go to document$ M. Rudelson and R. Vershynin, "Smallest singular value of a random rectangular matrix," Comm. Pure Appl. Math., vol. 62, iss. 12, pp. 1707-1739, 2009.

Show bibtex

@ARTICLE{RVrect, author = {Rudelson, Mark and Vershynin, Roman}, title = {Smallest singular value of a random rectangular matrix}, journal = {Comm. Pure Appl. Math.}, fjournal = {Communications on Pure and Applied Mathematics}, volume = {62}, year = {2009}, number = {12}, pages = {1707--1739}, issn = {0010-3640}, mrclass = {60B20 (15A42 15B52 60E15)}, mrnumber = {2569075}, mrreviewer = {Mark W. Meckes}, doi = {10.1002/cpa.20294}, url = {https://doi.org/10.1002/cpa.20294}, zblnumber = {1183.15031}, }
[TVdisc1] $Go to document$ T. Tao and V. Vu, "On random $\pm1$ matrices: singularity and determinant," Random Structures Algorithms, vol. 28, iss. 1, pp. 1-23, 2006.

Show bibtex

@ARTICLE{TVdisc1, author = {Tao, Terence and Vu, Van}, title = {On random {$\pm1$} matrices: singularity and determinant}, journal = {Random Structures Algorithms}, fjournal = {Random Structures \& Algorithms}, volume = {28}, year = {2006}, number = {1}, pages = {1--23}, issn = {1042-9832}, mrclass = {15A52 (60C05)}, mrnumber = {2187480}, mrreviewer = {Hsien-Kuei Hwang}, doi = {10.1002/rsa.20109}, url = {https://doi.org/10.1002/rsa.20109}, zblnumber = {1086.60008}, }
[TVdisc2] $Go to document$ T. Tao and V. Vu, "On the singularity probability of random Bernoulli matrices," J. Amer. Math. Soc., vol. 20, iss. 3, pp. 603-628, 2007.

Show bibtex

@ARTICLE{TVdisc2, author = {Tao, Terence and Vu, Van}, title = {On the singularity probability of random {B}ernoulli matrices}, journal = {J. Amer. Math. Soc.}, fjournal = {Journal of the American Mathematical Society}, volume = {20}, year = {2007}, number = {3}, pages = {603--628}, issn = {0894-0347}, mrclass = {60C05 (15A52)}, mrnumber = {2291914}, mrreviewer = {Ben Joseph Green}, doi = {10.1090/S0894-0347-07-00555-3}, url = {https://doi.org/10.1090/S0894-0347-07-00555-3}, zblnumber = {1116.15021}, }
[TVcircular] $Go to document$ T. Tao and V. Vu, "Random matrices: the circular law," Commun. Contemp. Math., vol. 10, iss. 2, pp. 261-307, 2008.

Show bibtex

@ARTICLE{TVcircular, author = {Tao, Terence and Vu, Van}, title = {Random matrices: the circular law}, journal = {Commun. Contemp. Math.}, fjournal = {Communications in Contemporary Mathematics}, volume = {10}, year = {2008}, number = {2}, pages = {261--307}, issn = {0219-1997}, mrclass = {60F15 (11P70 15A52 60F05)}, mrnumber = {2409368}, mrreviewer = {Ben Joseph Green}, doi = {10.1142/S0219199708002788}, url = {https://doi.org/10.1142/S0219199708002788}, zblnumber = {1156.15010}, }
[TVannmath] $Go to document$ T. Tao and V. H. Vu, "Inverse Littlewood-Offord theorems and the condition number of random discrete matrices," Ann. of Math. (2), vol. 169, iss. 2, pp. 595-632, 2009.

Show bibtex

@ARTICLE{TVannmath, author = {Tao, Terence and Vu, Van H.}, title = {Inverse {L}ittlewood-{O}fford theorems and the condition number of random discrete matrices}, journal = {Ann. of Math. (2)}, fjournal = {Annals of Mathematics. Second Series}, volume = {169}, year = {2009}, number = {2}, pages = {595--632}, issn = {0003-486X}, mrclass = {60G50 (15B52 60E15 60F05)}, mrnumber = {2480613}, mrreviewer = {Michael Stolz}, doi = {10.4007/annals.2009.169.595}, url = {https://doi.org/10.4007/annals.2009.169.595}, zblnumber = {1250.60023}, }
[V12] $Go to document$ R. Vershynin, "Introduction to the non-asymptotic analysis of random matrices," in Compressed Sensing, Cambridge Univ. Press, Cambridge, 2012, pp. 210-268.

Show bibtex

@INCOLLECTION{V12, author = {Vershynin, Roman}, title = {Introduction to the non-asymptotic analysis of random matrices}, booktitle = {Compressed Sensing}, pages = {210--268}, publisher = {Cambridge Univ. Press, Cambridge}, year = {2012}, mrclass = {60B20 (15B52 62H12)}, mrnumber = {2963170}, zblnumber = {}, doi = {10.1017/CBO9780511794308.006}, url = {https://doi.org/10.1017/CBO9780511794308.006}, }
[Vusurvey] $Go to document$ V. Vu, "Random discrete matrices," in Horizons of Combinatorics, Springer, Berlin, 2008, vol. 17, pp. 257-280.

Show bibtex

@INCOLLECTION{Vusurvey, author = {Vu, Van}, title = {Random discrete matrices}, booktitle = {Horizons of Combinatorics}, series = {Bolyai Soc. Math. Stud.}, volume = {17}, pages = {257--280}, publisher = {Springer, Berlin}, year = {2008}, mrclass = {15A52 (60F15 60F99)}, mrnumber = {2432537}, mrreviewer = {Michael Stolz}, doi = {10.1007/978-3-540-77200-2_13}, url = {https://doi.org/10.1007/978-3-540-77200-2_13}, zblnumber = {1154.15024}, }
[VuICM2014] $Go to document$ V. H. Vu, "Combinatorial problems in random matrix theory," in Proceedings of the International Congress of Mathematicians—Seoul 2014. Vol. IV, 2014, pp. 489-508.

Show bibtex

@INPROCEEDINGS{VuICM2014, author = {Vu, Van H.}, title = {Combinatorial problems in random matrix theory}, booktitle = {Proceedings of the {I}nternational {C}ongress of {M}athematicians---{S}eoul 2014. {V}ol. {IV}}, pages = {489--508}, publisher = {Kyung Moon Sa, Seoul}, year = {2014}, mrclass = {05D40 (15B52 60B20 60C05)}, mrnumber = {3727622}, zblnumber = {1373.05201}, url = {http://www.icm2014.org/download/Proceedings_Volume_IV.pdf}, }

Singularity of random Bernoulli matrices

Abstract

Authors