On the singularity probability of random Bernoulli matrices

Authors:
Terence Tao and Van Vu

Journal:
J. Amer. Math. Soc. **20** (2007), 603-628

MSC (2000):
Primary 15A52

DOI:
https://doi.org/10.1090/S0894-0347-07-00555-3

Published electronically:
February 6, 2007

MathSciNet review:
2291914

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let be a large integer and let be a random matrix whose entries are i.i.d. Bernoulli random variables (each entry is with probability ). We show that the probability that is singular is at most , improving an earlier estimate of Kahn, Komlós and Szemerédi, as well as earlier work by the authors. The key new ingredient is the applications of Freiman-type inverse theorems and other tools from additive combinatorics.

**1.**Y. Bilu, Structure of sets with small sumset. Structure theory of set addition.*Astérisque*, No. 258 (1999), xi, 77-108. MR**1701189 (2000h:11109)****2.**Y. Bilu, V. Lev, I. Ruzsa, Rectification principles in additive number theory,*Discrete Comput. Geom.***19**(1998), 343-353. MR**1608875 (2000a:11018)****3.**J. W. S. Cassels, An introduction to the geometry of numbers, Springer, Berlin, 1959. MR**0157947 (28:1175)****4.**M. Chang, A polynomial bound in Freiman's theorem,*Duke Math. J.***113**(2002), no. 3, 399-419. MR**1909605 (2003d:11151)****5.**P. Erdös, On a lemma of Littlewood and Offord,*Bull. Amer. Math. Soc.***51**(1945), 898-902. MR**0014608 (7:309j)****6.**G. Freiman, Foundations of a structural theory of set addition. Translated from the Russian.*Translations of Mathematical Monographs,*Vol 37. American Mathematical Society, Providence, R. I., 1973. vii+108 pp. MR**0360496 (50:12944)****7.**B. Green, I. Ruzsa, Sets with small sumset and rectification,*Bull. London Math. Soc.***38**(2006), 43-52. MR**2201602 (2006i:11027)****8.**B. Green, I. Ruzsa, Freiman's theorem in an arbitrary abelian group, preprint.**9.**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**0494478 (58:13338)****10.**F. John, Extremum problems with inequalities as subsidiary conditions,*Studies and essays presented to R. Courant on his 60th birthday, Jan 8. 1948*, Interscience Publishers Inc., New York, NY, 1948, 187-204. MR**0030135 (10:719b)****11.**J. Kahn, J. Komlós, E. Szemerédi, On the probability that a random matrix is singular,*J. Amer. Math. Soc.***8**(1995), 223-240. MR**1260107 (95c:15047)****12.**J. Komlós, On the determinant of matrices,*Studia Sci. Math. Hungar.***2**(1967), 7-22. MR**0221962 (36:5014)****13.**J. Komlós, On the determinant of random matrices,*Studia Sci. Math. Hungar.***3**(1968), 387-399. MR**0238371 (38:6647)****14.**A. Odlyzko, On subspaces spanned by random selections of vectors,*J. Combin. Theory Ser. A***47**(1988), no. 1, 124-133. MR**924455 (89h:05012)****15.**I. Ruzsa, Generalized arithmetical progressions and sumsets,*Acta Math. Hungar.*65 (1994), no. 4, 379-388. MR**1281447 (95k:11011)****16.**I. Ruzsa, An analog of Freiman's theorem in groups,*Structure theory of set addition*, Astérisque, No. 258 (1999), 323-326. MR**1701207 (2000h:11111)****17.**T. Tao and V. Vu, On random matrices: Singularity and Determinant,*Random Structures and Algorithms*28 (2006), no 1, 1-23. MR**2187480 (2006g:15048)**

Retrieve articles in *Journal of the American Mathematical Society*
with MSC (2000):
15A52

Retrieve articles in all journals with MSC (2000): 15A52

Additional Information

**Terence Tao**

Affiliation:
Department of Mathematics, UCLA, Los Angeles, California 90095-1555

Email:
tao@math.ucla.edu

**Van Vu**

Affiliation:
Department of Mathematics, Rutgers University, Piscataway, New Jersey 08854-8019

Email:
vanvu@ucsd.edu

DOI:
https://doi.org/10.1090/S0894-0347-07-00555-3

Received by editor(s):
November 5, 2004

Published electronically:
February 6, 2007

Additional Notes:
The first author is a Clay Prize Fellow and is supported by a grant from the Packard Foundation.

The second author is an A. Sloan Fellow and is supported by an NSF Career Grant.

Article copyright:
© Copyright 2007
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.