On the probability that a random ±1-matrix is singular

Kahn, Jeff ; Komlós, János ; Szemerédi, Endre

Journal of the American Mathematical Society, Tome 08 (1995) no. 1, pp. 223-240

Résumé

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.

Détail

DOI : 10.1090/S0894-0347-1995-1260107-2

Bibliographie

[1] Bollobã¡S, Bã©La Random graphs 1985

[2] Erdã¶S, P. On a lemma of Littlewood and Offord Bull. Amer. Math. Soc. 1945 898 902

[3] Esseen, C. G. On the Kolmogorov-Rogozin inequality for the concentration function Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 1966 210 216

[4] Fã¼Redi, Z. Random polytopes in the 𝑑-dimensional cube Discrete Comput. Geom. 1986 315 319

[5] Fã¼Redi, Zoltã¡N Matchings and covers in hypergraphs Graphs Combin. 1988 115 206

[6] Girko, V. L. Theory of random determinants 1990

[7] Greene, Curtis, Kleitman, Daniel J. Proof techniques in the theory of finite sets 1978 22 79

[8] Halã¡Sz, Gã¡Bor On the distribution of additive arithmetic functions Acta Arith. 1975 143 152

[9] Halã¡Sz, G. Estimates for the concentration function of combinatorial number theory and probability Period. Math. Hungar. 1977 197 211

[10] Halberstam, H., Roth, K. F. Sequences. Vol. I 1966

[11] Komlã³S, J. On the determinant of random matrices Studia Sci. Math. Hungar. 1968 387 399

[12] Lovã¡Sz, L. On the ratio of optimal integral and fractional covers Discrete Math. 1975 383 390

[13] Mehta, Madan Lal Random matrices 1991

[14] Metropolis, N., Stein, P. R. On a class of (0,1) matrices with vanishing determinants J. Combinatorial Theory 1967 191 198

[15] Muroga, Saburo Threshold logic and its applications 1971

[16] Odlyzko, A. M. On the ranks of some (0,1)-matrices with constant row sums J. Austral. Math. Soc. Ser. A 1981 193 201

[17] Odlyzko, A. M. On subspaces spanned by random selections of ±1 vectors J. Combin. Theory Ser. A 1988 124 133

[18] Peck, G. W. Erdős conjecture on sums of distinct numbers Stud. Appl. Math. 1980 87 92

[19] Sperner, Emanuel Ein Satz über Untermengen einer endlichen Menge Math. Z. 1928 544 548

[20] Stanley, Richard P. Weyl groups, the hard Lefschetz theorem, and the Sperner property SIAM J. Algebraic Discrete Methods 1980 168 184

[21] Zaslavsky, Thomas Facing up to arrangements: face-count formulas for partitions of space by hyperplanes Mem. Amer. Math. Soc. 1975

[22] Zuev, Yu. A. Combinatorial-probability and geometric methods in threshold logic Diskret. Mat. 1991 47 57