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.**Yuri Bilu,*Structure of sets with small sumset*, Astérisque**258**(1999), xi, 77–108 (English, with English and French summaries). Structure theory of set addition. MR**1701189****2.**Y. F. Bilu, V. F. Lev, and I. Z. Ruzsa,*Rectification principles in additive number theory*, Discrete Comput. Geom.**19**(1998), no. 3, Special Issue, 343–353. Dedicated to the memory of Paul Erdős. MR**1608875**, https://doi.org/10.1007/PL00009351**3.**J. W. S. Cassels,*An introduction to the geometry of numbers*, Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen mit besonderer Berücksichtigung der Anwendungsgebiete, Bd. 99 Springer-Verlag, Berlin-Göttingen-Heidelberg, 1959. MR**0157947****4.**Mei-Chu Chang,*A polynomial bound in Freiman’s theorem*, Duke Math. J.**113**(2002), no. 3, 399–419. MR**1909605**, https://doi.org/10.1215/S0012-7094-02-11331-3**5.**P. Erdös,*On a lemma of Littlewood and Offord*, Bull. Amer. Math. Soc.**51**(1945), 898–902. MR**0014608**, https://doi.org/10.1090/S0002-9904-1945-08454-7**6.**G. A. Freĭman,*Foundations of a structural theory of set addition*, American Mathematical Society, Providence, R. I., 1973. Translated from the Russian; Translations of Mathematical Monographs, Vol 37. MR**0360496****7.**Ben Green and Imre Z. Ruzsa,*Sets with small sumset and rectification*, Bull. London Math. Soc.**38**(2006), no. 1, 43–52. MR**2201602**, https://doi.org/10.1112/S0024609305018102**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**, https://doi.org/10.1007/BF02018403**10.**Fritz John,*Extremum problems with inequalities as subsidiary conditions*, Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948, Interscience Publishers, Inc., New York, N. Y., 1948, pp. 187–204. MR**0030135****11.**Jeff Kahn, János Komlós, and Endre Szemerédi,*On the probability that a random ±1-matrix is singular*, J. Amer. Math. Soc.**8**(1995), no. 1, 223–240. MR**1260107**, https://doi.org/10.1090/S0894-0347-1995-1260107-2**12.**J. Komlós,*On the determinant of (0,1) matrices*, Studia Sci. Math. Hungar**2**(1967), 7–21. MR**0221962****13.**J. Komlós,*On the determinant of random matrices*, Studia Sci. Math. Hungar.**3**(1968), 387–399. MR**0238371****14.**A. M. Odlyzko,*On subspaces spanned by random selections of ±1 vectors*, J. Combin. Theory Ser. A**47**(1988), no. 1, 124–133. MR**924455**, https://doi.org/10.1016/0097-3165(88)90046-5**15.**I. Z. Ruzsa,*Generalized arithmetical progressions and sumsets*, Acta Math. Hungar.**65**(1994), no. 4, 379–388. MR**1281447**, https://doi.org/10.1007/BF01876039**16.**Imre Z. Ruzsa,*An analog of Freiman’s theorem in groups*, Astérisque**258**(1999), xv, 323–326 (English, with English and French summaries). Structure theory of set addition. MR**1701207****17.**Terence Tao and Van Vu,*On random ±1 matrices: singularity and determinant*, Random Structures Algorithms**28**(2006), no. 1, 1–23. MR**2187480**, https://doi.org/10.1002/rsa.20109

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.