Random symmetric matrices are almost surely nonsingular. (Q854582)

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\).