Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
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
Email: tao@math.ucla.edu

Van Vu
Affiliation: Department of Mathematics, Rutgers University, Piscataway, New Jersey 08854-8019
Email: vanvu@ucsd.edu

DOI: http://dx.doi.org/10.1090/S0894-0347-07-00555-3
PII: S 0894-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.