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 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
- Terence Tao
- Affiliation: Department of Mathematics, UCLA, Los Angeles, California 90095-1555
- MR Author ID: 361755
- ORCID: 0000-0002-0140-7641
- Email: email@example.com
- Van Vu
- Affiliation: Department of Mathematics, Rutgers University, Piscataway, New Jersey 08854-8019
- Email: firstname.lastname@example.org
- 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