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 PDF
- J. Amer. Math. Soc. 8 (1995), 223-240 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, New York, 1985.
Pál Erdős, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. 51 (1945), 898-902.
C. G. Esséen, On the Kolmogorov-Rogozin inequality for the concentration function, Z. Wahrsch. Verw. Gebiete 5 (1966), 210-216.
Zoltán Füredi, Random polytopes in the $d$-dimensional cube, Discrete Comput. Geom. 1 (1986), 315-319.
—, Matchings and covers in hypergraphs, Graphs Combin. 4 (1988), 115-206.
V. L. Girko, Theory of random determinants, Math. Appl. (Soviet Ser.), vol. 45, Kluwer Acad. Publ., Dordrecht, 1990.
C. Greene and D. J. Kleitman, Proof techniques in the theory of finite sets, Studies in Combinatorics (G.-C. Rota, ed.), Math. Assoc. Amer., Washington, D.C., 1978.
Gábor Halász, On the distribution of additive arithmetic functions, Acta Arith. 27 (1975), 143-152.
—, Estimates for the concentration function of combinatorial number theory and probability, Period. Math. Hungar. 8 (1977), 197-211.
H. Halberstam and K. F. Roth, Sequences, Vol. 1, Oxford Univ. Press, London and New York, 1966.
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.
—, On the determinants of random matrices, Studia Sci. Math. Hungar. 3 (1968), 387-399.
—, Circulated manuscript, 1977.
László Lovász, On the ratio of optimal integral and fractional covers, Discrete Math. 13 (1975), 383-390.
Madan Lal Mehta, Random matrices, second ed., Academic Press, New York, 1991.
N. Metropolis and P. R. Stein, A class of $(0,1)$-matrices with vanishing determinants, J. Combin. Theory 3 (1967), 191-198.
Saburo Muroga, Threshold logic and its applications, Wiley, New York, 1971.
A. M. Odlyzko, On the ranks of some $(0,1)$-matrices with constant row-sums, J. Austral. Math. Soc. Ser. A 31 (1981), 193-201.
—, On subspaces spanned by random selections of $\pm 1$ vectors, J. Combin. Theory Ser. A 47 (1988), 124-133.
G. W. Peck, Erdős conjecture on sums of distinct numbers, Studies Appl. Math. 63 (1980), 87-92.
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.
E. Sperner, Ein Satz über Untermenge einer endliche Menge, Math. Z. 27 (1928), 544-548.
Richard P. Stanley, Weyl groups, the hard Lefschetz theorem, and the Sperner property, SIAM J. Alg. Discrete Math. 1 (1980), 168-184.
Thomas Zaslavsky, Facing up to arrangements: Face-count formulas for partitions of space by hyperplanes, Mem. Amer. Math. Soc., vol. 154, Amer. Math. Soc., Providence, RI, 1975.
Yu. A. Zuev, Methods of geometry and probabilistic combinatorics in threshold logic, Discrete Math. Appl. 2 (1992), 427-438.
Additional 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