Skip to Main Content

Journal of the American Mathematical Society

Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of mathematics.

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

The 2024 MCQ for Journal of the American Mathematical Society is 4.83.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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

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