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.
-
[AK]
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.
@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]
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.
@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]
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.
@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]
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.
@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]
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.
@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.
@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.
@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]
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.
@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.
@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]
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.
@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]
B. A. Rogozin, "On the increase of dispersion of sums of independent random variables," Teor. Verojatnost. i Primenen, vol. 6, pp. 106-108, 1961.
@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]
M. Rudelson, "Invertibility of random matrices: norm of the inverse," Ann. of Math. (2), vol. 168, iss. 2, pp. 575-600, 2008.
@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]
M. Rudelson and R. Vershynin, "The Littlewood-Offord problem and invertibility of random matrices," Adv. Math., vol. 218, iss. 2, pp. 600-633, 2008.
@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]
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.
@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]
T. Tao and V. Vu, "On random $\pm1$ matrices: singularity and determinant," Random Structures Algorithms, vol. 28, iss. 1, pp. 1-23, 2006.
@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]
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.
@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]
T. Tao and V. Vu, "Random matrices: the circular law," Commun. Contemp. Math., vol. 10, iss. 2, pp. 261-307, 2008.
@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]
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.
@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]
R. Vershynin, "Introduction to the non-asymptotic analysis of random matrices," in Compressed Sensing, Cambridge Univ. Press, Cambridge, 2012, pp. 210-268.
@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]
V. Vu, "Random discrete matrices," in Horizons of Combinatorics, Springer, Berlin, 2008, vol. 17, pp. 257-280.
@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]
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.
@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},
}