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 Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $n$ be a large integer and let $M_n$ be a random $n \times n$ matrix whose entries are i.i.d. Bernoulli random variables (each entry is $\pm 1$ with probability $1/2$). We show that the probability that $M_n$ is singular is at most $(3/4 +o(1))^n$, 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.

- 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** - 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**, DOI https://doi.org/10.1007/PL00009351 - 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** - Mei-Chu Chang,
*A polynomial bound in Freiman’s theorem*, Duke Math. J.**113**(2002), no. 3, 399–419. MR**1909605**, DOI https://doi.org/10.1215/S0012-7094-02-11331-3 - P. Erdös,
*On a lemma of Littlewood and Offord*, Bull. Amer. Math. Soc.**51**(1945), 898–902. MR**14608**, DOI https://doi.org/10.1090/S0002-9904-1945-08454-7 - 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** - Ben Green and Imre Z. Ruzsa,
*Sets with small sumset and rectification*, Bull. London Math. Soc.**38**(2006), no. 1, 43–52. MR**2201602**, DOI https://doi.org/10.1112/S0024609305018102
green-ruzsa4 B. Green, I. Ruzsa, Freiman’s theorem in an arbitrary abelian group, preprint.
- 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**494478**, DOI https://doi.org/10.1007/BF02018403 - 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** - 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 https://doi.org/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** - J. Komlós,
*On the determinant of random matrices*, Studia Sci. Math. Hungar.**3**(1968), 387–399. MR**238371** - A. M. Odlyzko,
*On subspaces spanned by random selections of $\pm 1$ vectors*, J. Combin. Theory Ser. A**47**(1988), no. 1, 124–133. MR**924455**, DOI https://doi.org/10.1016/0097-3165%2888%2990046-5 - I. Z. Ruzsa,
*Generalized arithmetical progressions and sumsets*, Acta Math. Hungar.**65**(1994), no. 4, 379–388. MR**1281447**, DOI https://doi.org/10.1007/BF01876039 - 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** - 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 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

MR Author ID:
361755

ORCID:
0000-0002-0140-7641

Email:
tao@math.ucla.edu

**Van Vu**

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

Email:
vanvu@ucsd.edu

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.