Journal of the American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6834(e) ISSN 0894-0347(p)

On the singularity probability of random Bernoulli matrices

Author(s): Terence Tao; Van Vu
Journal: J. Amer. Math. Soc. 20 (2007), 603-628.
MSC (2000): Primary 15A52
Posted: February 6, 2007
MathSciNet review: 2291914
Retrieve article in: PDF

Abstract | References | Similar articles | Additional information

Abstract: Let be a large integer and let be a random $n \times n$ matrix whose entries are i.i.d. Bernoulli random variables (each entry is $\pm 1$ 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.

References:

1.: Y. Bilu, Structure of sets with small sumset. Structure theory of set addition. Astérisque, No. 258 (1999), xi, 77-108. MR 1701189 (2000h:11109)
2.: Y. Bilu, V. Lev, I. Ruzsa, Rectification principles in additive number theory, Discrete Comput. Geom. 19 (1998), 343-353. MR 1608875 (2000a:11018)
3.: J. W. S. Cassels, An introduction to the geometry of numbers, Springer, Berlin, 1959. MR 0157947 (28:1175)
4.: M. Chang, A polynomial bound in Freiman's theorem, Duke Math. J. 113 (2002), no. 3, 399-419. MR 1909605 (2003d:11151)
5.: P. Erdös, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. 51 (1945), 898-902. MR 0014608 (7:309j)
6.: G. Freiman, Foundations of a structural theory of set addition. Translated from the Russian. Translations of Mathematical Monographs, Vol 37. American Mathematical Society, Providence, R. I., 1973. vii+108 pp. MR 0360496 (50:12944)
7.: B. Green, I. Ruzsa, Sets with small sumset and rectification, Bull. London Math. Soc. 38 (2006), 43-52. MR 2201602 (2006i:11027)
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 (58:13338)
10.: F. John, Extremum problems with inequalities as subsidiary conditions, Studies and essays presented to R. Courant on his 60th birthday, Jan 8. 1948, Interscience Publishers Inc., New York, NY, 1948, 187-204. MR 0030135 (10:719b)
11.: J. Kahn, J. Komlós, E. Szemerédi, On the probability that a random $\pm 1$ matrix is singular, J. Amer. Math. Soc. 8 (1995), 223-240. MR 1260107 (95c:15047)
12.: J. Komlós, On the determinant of matrices, Studia Sci. Math. Hungar. 2 (1967), 7-22. MR 0221962 (36:5014)
13.: J. Komlós, On the determinant of random matrices, Studia Sci. Math. Hungar. 3 (1968), 387-399. MR 0238371 (38:6647)
14.: A. Odlyzko, On subspaces spanned by random selections of $\pm 1$ vectors, J. Combin. Theory Ser. A 47 (1988), no. 1, 124-133. MR 924455 (89h:05012)
15.: I. Ruzsa, Generalized arithmetical progressions and sumsets, Acta Math. Hungar. 65 (1994), no. 4, 379-388. MR 1281447 (95k:11011)
16.: I. Ruzsa, An analog of Freiman's theorem in groups, Structure theory of set addition, Astérisque, No. 258 (1999), 323-326. MR 1701207 (2000h:11111)
17.: T. Tao and V. Vu, On random $\pm 1$ matrices: Singularity and Determinant, Random Structures and Algorithms 28 (2006), no 1, 1-23. MR 2187480 (2006g:15048)

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: 10.1090/S0894-0347-07-00555-3
PII: S 0894-0347(07)00555-3
Received by editor(s): November 5, 2004
Posted: 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 of article: Copyright 2007, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

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