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
DOI: https://doi.org/10.1090/S0894-0347-1995-1260107-2
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?)

  • [1] Béla Bollobás, Random graphs, Academic Press, New York, 1985. MR 809996 (87f:05152)
  • [2] Pál Erdős, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. 51 (1945), 898-902. MR 0014608 (7:309j)
  • [3] C. G. Esséen, On the Kolmogorov-Rogozin inequality for the concentration function, Z. Wahrsch. Verw. Gebiete 5 (1966), 210-216. MR 0205297 (34:5128)
  • [4] Zoltán Füredi, Random polytopes in the $ d$-dimensional cube, Discrete Comput. Geom. 1 (1986), 315-319. MR 866367 (88d:52003)
  • [5] -, Matchings and covers in hypergraphs, Graphs Combin. 4 (1988), 115-206. MR 943753 (89i:05214)
  • [6] V. L. Girko, Theory of random determinants, Math. Appl. (Soviet Ser.), vol. 45, Kluwer Acad. Publ., Dordrecht, 1990. MR 1080966 (91k:60001)
  • [7] 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. MR 513002 (80a:05006)
  • [8] Gábor Halász, On the distribution of additive arithmetic functions, Acta Arith. 27 (1975), 143-152. MR 0369292 (51:5527)
  • [9] -, Estimates for the concentration function of combinatorial number theory and probability, Period. Math. Hungar. 8 (1977), 197-211. MR 0494478 (58:13338)
  • [10] H. Halberstam and K. F. Roth, Sequences, Vol. 1, Oxford Univ. Press, London and New York, 1966. MR 0210679 (35:1565)
  • [11] I. Kanter and H. Sompolinsky, Associative recall of memory without errors, Phys. Rev. (A) (3) 35 (1987), 380-392.
  • [12] János Komlós, On the determinant of $ (0,1)$ matrices, Studia Sci. Math. Hungar. 2 (1967), 7-21.
  • [13] -, On the determinants of random matrices, Studia Sci. Math. Hungar. 3 (1968), 387-399. MR 0238371 (38:6647)
  • [14] -, Circulated manuscript, 1977.
  • [15] László Lovász, On the ratio of optimal integral and fractional covers, Discrete Math. 13 (1975), 383-390. MR 0384578 (52:5452)
  • [16] Madan Lal Mehta, Random matrices, second ed., Academic Press, New York, 1991. MR 1083764 (92f:82002)
  • [17] N. Metropolis and P. R. Stein, A class of $ (0,1)$-matrices with vanishing determinants, J. Combin. Theory 3 (1967), 191-198. MR 0211889 (35:2764)
  • [18] Saburo Muroga, Threshold logic and its applications, Wiley, New York, 1971. MR 0439441 (55:12334)
  • [19] 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. MR 629173 (82j:05032)
  • [20] -, On subspaces spanned by random selections of $ \pm 1$ vectors, J. Combin. Theory Ser. A 47 (1988), 124-133. MR 924455 (89h:05012)
  • [21] G. W. Peck, Erdős conjecture on sums of distinct numbers, Studies Appl. Math. 63 (1980), 87-92. MR 578458 (82e:10096)
  • [22] Imre Ruzsa, Private communication.
  • [23] András Sárközy and Endre Szemerédi, Über ein Problem von Erdős und Moser, Acta. Arith. 11 (1965), 205-208.
  • [24] E. Sperner, Ein Satz über Untermenge einer endliche Menge, Math. Z. 27 (1928), 544-548. MR 1544925
  • [25] Richard P. Stanley, Weyl groups, the hard Lefschetz theorem, and the Sperner property, SIAM J. Alg. Discrete Math. 1 (1980), 168-184. MR 578321 (82j:20083)
  • [26] 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. MR 0357135 (50:9603)
  • [27] Yu. A. Zuev, Methods of geometry and probabilistic combinatorics in threshold logic, Discrete Math. Appl. 2 (1992), 427-438. MR 1134280 (93d:94031)

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

DOI: https://doi.org/10.1090/S0894-0347-1995-1260107-2
Keywords: Random matrices, exponential sums, Littlewood-Offord Problem
Article copyright: © Copyright 1995 American Mathematical Society

American Mathematical Society