## On the singularity probability of random Bernoulli matrices

HTML articles powered by AMS MathViewer

- by Terence Tao and Van Vu PDF
- J. Amer. Math. Soc.
**20**(2007), 603-628 Request permission

## 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.## References

- 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 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**, DOI 10.1007/978-3-642-62035-5 - Mei-Chu Chang,
*A polynomial bound in Freiman’s theorem*, Duke Math. J.**113**(2002), no. 3, 399–419. MR**1909605**, DOI 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 10.1090/S0002-9904-1945-08454-7 - G. A. Freĭman,
*Foundations of a structural theory of set addition*, Translations of Mathematical Monographs, Vol 37, American Mathematical Society, Providence, R.I., 1973. Translated from the Russian. 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 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 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 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 10.1016/0097-3165(88)90046-5 - I. Z. Ruzsa,
*Generalized arithmetical progressions and sumsets*, Acta Math. Hungar.**65**(1994), no. 4, 379–388. MR**1281447**, DOI 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 10.1002/rsa.20109

## 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. - © Copyright 2007
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: J. Amer. Math. Soc.
**20**(2007), 603-628 - MSC (2000): Primary 15A52
- DOI: https://doi.org/10.1090/S0894-0347-07-00555-3
- MathSciNet review: 2291914