On the probability that a random $\pm 1$-matrix is singular
Authors:
Jeff Kahn, János Komlós and Endre Szemerédi
Journal:
J. Amer. Math. Soc. 8 (1995), 223-240
MSC:
Primary 15A52; Secondary 11K99, 60C05
DOI:
https://doi.org/10.1090/S0894-0347-1995-1260107-2
MathSciNet review:
1260107
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
Abstract: We report some progress on the old problem of estimating the probability, ${P_n}$, that a random $n \times n \pm 1$-matrix is singular: Theorem. There is a positive constant $\varepsilon$ for which ${P_n} < {(1 - \varepsilon )^n}$. This is a considerable improvement on the best previous bound, ${P_n} = O(1/\sqrt n )$, given by Komlós in 1977, but still falls short of the often-conjectured asymptotical formula ${P_n} = (1 + o(1)){n^2}{2^{1 - n}}$. The proof combines ideas from combinatorial number theory, Fourier analysis and combinatorics, and some probabilistic constructions. A key ingredient, based on a Fourier-analytic idea of Halász, is an inequality (Theorem 2) relating the probability that $\underline a \in {{\mathbf {R}}^n}$ is orthogonal to a random $\underline \varepsilon \in {\{ \pm 1\} ^n}$ to the corresponding probability when $\underline \varepsilon$ is random from ${\{ - 1,0,1\} ^n}$ with $Pr({\varepsilon _i} = - 1) = Pr({\varepsilon _i} = 1) = p$ and ${\varepsilon _i}$’s chosen independently.
- Béla Bollobás, Random graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1985. MR 809996
- P. Erdös, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. 51 (1945), 898–902. MR 14608, DOI https://doi.org/10.1090/S0002-9904-1945-08454-7
- C. G. Esseen, On the Kolmogorov-Rogozin inequality for the concentration function, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 5 (1966), 210–216. MR 205297, DOI https://doi.org/10.1007/BF00533057
- Z. Füredi, Random polytopes in the $d$-dimensional cube, Discrete Comput. Geom. 1 (1986), no. 4, 315–319. MR 866367, DOI https://doi.org/10.1007/BF02187704
- Zoltán Füredi, Matchings and covers in hypergraphs, Graphs Combin. 4 (1988), no. 2, 115–206. MR 943753, DOI https://doi.org/10.1007/BF01864160
- V. L. Girko, Theory of random determinants, Mathematics and its Applications (Soviet Series), vol. 45, Kluwer Academic Publishers Group, Dordrecht, 1990. Translated from the Russian. MR 1080966
- Curtis Greene and Daniel J. Kleitman, Proof techniques in the theory of finite sets, Studies in combinatorics, MAA Stud. Math., vol. 17, Math. Assoc. America, Washington, D.C., 1978, pp. 22–79. MR 513002
- Gábor Halász, On the distribution of additive arithmetic functions, Acta Arith. 27 (1975), 143–152. MR 369292, DOI https://doi.org/10.4064/aa-27-1-143-152
- 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 https://doi.org/10.1007/BF02018403
- H. Halberstam and K. F. Roth, Sequences. Vol. I, Clarendon Press, Oxford, 1966. MR 0210679 I. Kanter and H. Sompolinsky, Associative recall of memory without errors, Phys. Rev. (A) (3) 35 (1987), 380-392. János Komlós, On the determinant of $(0,1)$ matrices, Studia Sci. Math. Hungar. 2 (1967), 7-21.
- J. Komlós, On the determinant of random matrices, Studia Sci. Math. Hungar. 3 (1968), 387–399. MR 238371 ---, Circulated manuscript, 1977.
- L. Lovász, On the ratio of optimal integral and fractional covers, Discrete Math. 13 (1975), no. 4, 383–390. MR 384578, DOI https://doi.org/10.1016/0012-365X%2875%2990058-8
- Madan Lal Mehta, Random matrices, 2nd ed., Academic Press, Inc., Boston, MA, 1991. MR 1083764
- N. Metropolis and P. R. Stein, On a class of $(0,\,1)$ matrices with vanishing determinants, J. Combinatorial Theory 3 (1967), 191–198. MR 211889
- Saburo Muroga, Threshold logic and its applications, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1971. MR 0439441
- A. M. Odlyzko, On the ranks of some $(0,\,1)$-matrices with constant row sums, J. Austral. Math. Soc. Ser. A 31 (1981), no. 2, 193–201. MR 629173
- 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 https://doi.org/10.1016/0097-3165%2888%2990046-5
- G. W. Peck, Erdős conjecture on sums of distinct numbers, Stud. Appl. Math. 63 (1980), no. 1, 87–92. MR 578458, DOI https://doi.org/10.1002/sapm198063187 Imre Ruzsa, Private communication. András Sárközy and Endre Szemerédi, Über ein Problem von Erdős und Moser, Acta. Arith. 11 (1965), 205-208.
- Emanuel Sperner, Ein Satz über Untermengen einer endlichen Menge, Math. Z. 27 (1928), no. 1, 544–548 (German). MR 1544925, DOI https://doi.org/10.1007/BF01171114
- Richard P. Stanley, Weyl groups, the hard Lefschetz theorem, and the Sperner property, SIAM J. Algebraic Discrete Methods 1 (1980), no. 2, 168–184. MR 578321, DOI https://doi.org/10.1137/0601021
- Thomas Zaslavsky, Facing up to arrangements: face-count formulas for partitions of space by hyperplanes, Mem. Amer. Math. Soc. 1 (1975), no. issue 1, 154, vii+102. MR 357135, DOI https://doi.org/10.1090/memo/0154
- Yu. A. Zuev, Combinatorial-probability and geometric methods in threshold logic, Diskret. Mat. 3 (1991), no. 2, 47–57 (Russian); English transl., Discrete Math. Appl. 2 (1992), no. 4, 427–438. MR 1134280, DOI https://doi.org/10.1515/dma.1992.2.4.427
Retrieve articles in Journal of the American Mathematical Society with MSC: 15A52, 11K99, 60C05
Retrieve articles in all journals with MSC: 15A52, 11K99, 60C05
Additional Information
Keywords:
Random matrices,
exponential sums,
Littlewood-Offord Problem
Article copyright:
© Copyright 1995
American Mathematical Society