Random symmetric matrices are almost surely nonsingular. (English) Zbl 1110.15020

The authors consider random symmetric \(n \times n\) matrices \(Q_n\) whose upper-diagonal entries are independent, identically distributed, and take values \(0\) and \(1\) with probabilities \(1/2\). Asymptotical relations are obtained presenting upper estimates of the probability \(p_n\) that \(Q_n\) is non-singular.
Theorem 1 states that for any \(\delta > 0\) for sufficiently large \(n\) the probability \(p_n \leq {an}^{-1/8 +\delta},\) where \(a = a (\delta)\) does not depend on \(n\).
This assertion is generalized as follows. A random variable \(\xi\) is said to have \(\rho\)-property if \[ \max_ {c \in \mathbb R}{\mathbf P}(\xi = c ) \leq \rho. \] Theorem 2 states the following. Let some \(\rho > 0\) exist such that in the sequence of matrices \(Q_n = \{\xi_{ij}\}\) all entries \(\xi_{ij}\) have \(\rho\)-property. Then for any \(\delta > 0\) for sufficiently large \(n\), we have \(p_{n} \leq bn^{-1/8 + \delta},\) where \(b = b (\rho, \delta)\) is independent of \(n\).
One more theorem presents a quadratic generalization of the Littlewood-Offord inequality. Let \(z_1,z_2, \dots, z_n\) be independent identically distributed random variables that are equal to \(0\) or \(1\) with the probabilities \(1/2\). Consider quadratic forms \[ Q = \sum^{n}_{i,j=1} c_{ij}z_i z_j, \] in which sufficiently many coeficients are larger \(1\) in absolute value. The authors obtain an asymptotical upper estimate for the probability \({\mathbf P}(Q \in I)\) as \(n \rightarrow \infty\), where \(I\) is an arbitrary non-random interval of length \(1\).


15B52 Random matrices (algebraic aspects)
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
60E15 Inequalities; stochastic orderings
Full Text: DOI arXiv


[1] B. BollobáS, Random Graphs , Academic Press, New York, 1985.
[2] K. Costello and V. Vu, Rank of random graphs , preprint, 2006.
[3] P. ErdöS, On a lemma of Littlewood and Offord , Bull. Amer. Math. Soc. 51 (1945), 898–902. · Zbl 0063.01270
[4] G. HaláSz, Estimates for the concentration function of combinatorial number theory and probability , Period. Math. Hungar. 8 (1977), 197–211. · Zbl 0336.10050
[5] 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. JSTOR: · Zbl 0829.15018
[6] J. KomlóS, On the determinant of \((0,1)\) matrices , Studia Sci. Math. Hungar. 2 (1967), 7–21. · Zbl 0153.05002
[7] -, On the determinant of random matrices , Studia Sci. Math. Hungar. 3 (1968), 387–399. · Zbl 0226.60048
[8] 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 (54) (1943), 277–286. · Zbl 0061.01801
[9] M. Rudelson, Invertibility of random matrices: Norm of the inverse , · Zbl 1175.15030
[10] T. Tao and V. Vu, On random \(\pm 1\) matrices: Singularity and determinant , Random Structures Algorithms 28 (2006), 1–23. · Zbl 1086.60008
[11] -, Inverse Littlewood-Offord theorems and the condition number of random discrete matrices , · Zbl 1250.60023
[12] -, On the singularity probability of random Bernoulli matrices , to appear in J. Amer. Math. Soc., · Zbl 1116.15021
[13] -, Additive Combinatorics , in preparation.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.