## 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