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

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

American Mathematical Society