Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)



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

References [Enhancements On Off] (What's this?)

Similar Articles

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

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

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.