## 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$$.

### MSC:

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

### Keywords:

  B. BollobáS, Random Graphs , Academic Press, New York, 1985.  K. Costello and V. Vu, Rank of random graphs , preprint, 2006.  P. ErdöS, On a lemma of Littlewood and Offord , Bull. Amer. Math. Soc. 51 (1945), 898–902. · Zbl 0063.01270  G. HaláSz, Estimates for the concentration function of combinatorial number theory and probability , Period. Math. Hungar. 8 (1977), 197–211. · Zbl 0336.10050  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  J. KomlóS, On the determinant of $$(0,1)$$ matrices , Studia Sci. Math. Hungar. 2 (1967), 7–21. · Zbl 0153.05002  -, On the determinant of random matrices , Studia Sci. Math. Hungar. 3 (1968), 387–399. · Zbl 0226.60048  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  M. Rudelson, Invertibility of random matrices: Norm of the inverse , · Zbl 1175.15030  T. Tao and V. Vu, On random $$\pm 1$$ matrices: Singularity and determinant , Random Structures Algorithms 28 (2006), 1–23. · Zbl 1086.60008  -, Inverse Littlewood-Offord theorems and the condition number of random discrete matrices , · Zbl 1250.60023  -, On the singularity probability of random Bernoulli matrices , to appear in J. Amer. Math. Soc., · Zbl 1116.15021  -, Additive Combinatorics , in preparation.