Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)



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

References [Enhancements On Off] (What's this?)

Similar Articles

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