On the probability that a random $\pm 1$-matrix is singular
HTML articles powered by AMS MathViewer
- by Jeff Kahn, János Komlós and Endre Szemerédi
- J. Amer. Math. Soc. 8 (1995), 223-240
- DOI: https://doi.org/10.1090/S0894-0347-1995-1260107-2
- PDF | Request permission
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.References
- 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 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 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 10.1007/BF02187704
- Zoltán Füredi, Matchings and covers in hypergraphs, Graphs Combin. 4 (1988), no. 2, 115–206. MR 943753, DOI 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, DOI 10.1007/978-94-009-1858-0
- 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 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 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 10.1016/0012-365X(75)90058-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, DOI 10.1016/S0021-9800(67)80006-1
- 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, DOI 10.1017/S1446788700033474
- 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
- G. W. Peck, Erdős conjecture on sums of distinct numbers, Stud. Appl. Math. 63 (1980), no. 1, 87–92. MR 578458, DOI 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 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 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 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 10.1515/dma.1992.2.4.427
Bibliographic Information
- © Copyright 1995 American Mathematical Society
- 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