Inverse Littlewood-Offord problems and the singularity of random symmetric matrices. (English) Zbl 1276.15019

Nguyen, Hoi H.

Duke Math. J. 161, No. 4, 545-586 (2012).

Let \(M_n\) denote a random symmetric (\(n\times n\))-matrix whose upper diagonal entries are independent and identically distributed Bernoulli random variables (which take values \(-1\) and \(1\) with probability \(1\over 2\)). Improving the earlier result by K. P. Costello, T. Tao and V. Vu [Duke Math. J. 135, No. 2, 395–413 (2006; Zbl 1110.15020)], the author shows that \(M_n\) is nonsingular with probability \(1-O(n^{-C})\) for any positive constant \(C\). The proof uses an inverse Littlewood-Offord result for quadratic forms, which is of interest of its own.

Reviewer: Costică Moroşanu (Iaşi)

MSC:

15B52	Random matrices (algebraic aspects)
11B30	Arithmetic combinatorics; higher degree uniformity
11M50	Relations with random matrices
60B20	Random matrices (probabilistic aspects)
15A63	Quadratic and bilinear forms, inner products

Keywords:

random matrices; arithmetic combinatorics; relations with random matrices; random matrices (probabilistic aspects); inverse Littlewood-Offord problems; singularity; symmetric matrices; Bernoulli random variables; quadratic forms

Citations:

Zbl 1110.15020

References:

[1]	B. Bollobás, Random Graphs , Academic Press, London, 1985.
[2]	J. Bourgain, V. Vu, and P. M. Wood, On the singularity probability of discrete random matrices , J. Funct. Anal. 258 (2010), 559-603. · Zbl 1186.60003 · doi:10.1016/j.jfa.2009.04.016
[3]	K. Costello, Bilinear and quadratic variants on the Littlewood-Offord problem , preprint, [math.PR] 0902.1538v1 · Zbl 1317.60051
[4]	K. Costello, T. Tao, and V. Vu, Random symmetric matrices are almost surely nonsingular , Duke Math. J. 135 (2006), 395-413. · Zbl 1110.15020 · doi:10.1215/S0012-7094-06-13527-5
[5]	P. Erdős, On a lemma of Littlewood and Offord , Bull. Amer. Math. Soc. 51 (1945), 898-902. · Zbl 0063.01270 · doi:10.1090/S0002-9904-1945-08454-7
[6]	P. Erdős and L. Moser, Elementary problems and solutions: Solutions, E736 , Amer. Math. Monthly 54 (1947), 229-230. · doi:10.2307/2304711
[7]	C. G. Esseen, On the Kolmogorov-Rogozin inequality for the concentration function , Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 5 (1966), 210-216. · Zbl 0142.14702 · doi:10.1007/BF00533057
[8]	G. Halász, Estimates for the concentration function of combinatorial number theory and probability , Period. Math. Hungar. 8 (1977), 197-211. · Zbl 0336.10050 · doi:10.1007/BF02018403
[9]	J. Kahn, J. Komlós, and E. Szemerédi, On the probability that a random \pm 1 matrix is singular , J. Amer. Math. Soc. 8 (1995), 223-240. · Zbl 0829.15018 · doi:10.2307/2152887
[10]	M. Kanter, Probability inequalities for convex sets and multidimensional concentration functions , J. Multivariate Anal. 6 (1976), 222-236. · Zbl 0347.60043 · doi:10.1016/0047-259X(76)90032-4
[11]	G. Katona, On a conjecture of Erdős and a stronger form of Sperner’s theorem , Studia Sci. Math. Hungar. 1 (1966), 59-63. · Zbl 0143.02403
[12]	D. Kleitman, On a lemma of Littlewood and Offord on the distributions of linear combinations of vectors , Adv. Math. 5 (1970), 155-157. · Zbl 0195.40703 · doi:10.1016/0001-8708(70)90038-1
[13]	A. Kolmogorov, Two uniform limit theorems for sums of independent random variables , Theory Probab. Appl. 1 (1956), 384-394. · Zbl 0079.34502 · doi:10.1137/1101030
[14]	J. Komlós, On the determinant of (0, 1) matrices , Studia Sci. Math. Hungar. 2 (1967), 7-22.
[15]	J. E. Littlewood and A. C. Offord, On the number of real roots of a random algebraic equation, III , Rec. Math. [Mat. Sbornik] N.S. 12 (1943), 277-286. · Zbl 0061.01801
[16]	H. Nguyen and V. Vu, Optimal Littlewood-Offord theorems , Adv. Math. 226 (2011), 5298-5319. · Zbl 1268.11020 · doi:10.1016/j.aim.2011.01.005
[17]	A. Odlyzko, On subspaces spanned by random selections of \pm 1 vectors , J. Combin. Theory Ser. A 47 (1988), 124-133. · Zbl 0664.05004 · doi:10.1016/0097-3165(88)90046-5
[18]	B. A. Rogozin, An estimate for concentration functions , Theory Probab. Appl. 6 (1961), 94-97. · Zbl 0106.34002 · doi:10.1137/1106009
[19]	J. Rosiński and G. Samorodnitsky, Symmetrization and concentration inequality for multilinear forms with applications to zero-one laws for Lévy chaos , Ann. Probab. 24 (1996), 422-437. · Zbl 0854.60017 · doi:10.1214/aop/1042644724
[20]	A. Sárközy and E. Szemerédi, Über ein Problem von Erdős und Moser , Acta Arith. 11 (1965), 205-208. · Zbl 0134.27801
[21]	R. Stanley, Weyl groups, the hard Lefschetz theorem, and the Sperner property , SIAM J. Algebraic Discrete Methods 1 (1980), 168-184. · Zbl 0502.05004 · doi:10.1137/0601021
[22]	T. Tao and V. Vu, Additive Combinatorics , Cambridge Stud. Adv. Math. 105 , Cambridge Univ. Press, Cambridge, 2006. · Zbl 1127.11002
[23]	T. Tao and V. Vu, On the singularity probability of random Bernoulli matrices , J. Amer. Math. Soc. 20 (2007), 603-628. · Zbl 1116.15021 · doi:10.1090/S0894-0347-07-00555-3
[24]	T. Tao and V. Vu, Inverse Littlewood-Offord theorems and the condition number of random matrices , Ann. of Math. (2) 169 (2009), 595-632. · Zbl 1250.60023 · doi:10.4007/annals.2009.169.595
[25]	T. Tao and V. Vu, A sharp inverse Littlewood-Offord theorem , Random Structures Algorithms 37 (2010), 525-539. · Zbl 1205.60091
[26]	V. Vu, “Random discrete matrices” in Horizons of Combinatorics , Bolyai Soc. Math. Stud. 17 , Springer, Berlin, 2008, 257-280. · Zbl 1154.15024 · doi:10.1007/978-3-540-77200-2_13