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 pure and applied mathematics.

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

The 2020 MCQ for Journal of the American Mathematical Society is 4.79.

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