Random symmetric matrices are almost surely nonsingular

By Kevin P. Costello, Terence Tao, Van H. Vu. 2005

126 citations recorded by the source corpus.

Let $Q_n$ denote a random symmetric $n$ by $n$ matrix, whose upper diagonal entries are i.i.d. Bernoulli random variables (which take values 0 and 1 with probability 1/2). We prove that $Q_n$ is non-singular with probability $1-O(n^{-1/8+\delta})$ for any fixed $\delta > 0$. The proof uses a quadratic version of Littlewood-Offord type results concerning the concentration functions of random variables and can be extended for more general models of random matrices.

Subfields: Applied Mathematics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/f0f8041f69eabbe09f115757d6e2e7d61a1c8d99

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

The distribution of sandpile groups of random graphs (2014, background): “case of independent entries. In the case of singularity probability of symmetric matrices over R with independent entries on and above the diagonal, Costello, Tao, and Vu obtained the ﬁrst good bound [CTV06], with improvements by Costello [Cos13] and Nguyen [Ngu12], and the current best bound due to”
Inverse Littlewood-Offord problems and The Singularity of Random Symmetric Matrices (2011, methodology): “Roughly speaking, the main approach of [4] is to show that with high probability (with respect to Mn−1) most of the aij are nonzero.”
Graphs with integral spectrum (2009, unknown): “We note that despite a recent series of very strong results [2, 9, 23, 24, 25, 26] treating various counting questions for 0, 1-matrices, no upper bounds on I(n) have been known prior to our work, which derives the following result:”
From the Littlewood-Offord problem to the Circular Law: universality of the spectral distribution of random matrices (2008, background): “In [6], it was shown that for a quadratic form Q := ∑ 1≤i,j≤n cijξiξj with non-zero coefficients, P(Q = z) is O(n−1/8).”
Adjacency matrices of random digraphs: singularity and anti-concentration (2015, background): “The corresponding problem for symmetric Bernoulli matrices was considered in [11], [27], [36].”
Anti-concentration for Polynomials of Independent Random Variables (2015, background): “829v4 [math.PR] 7 Aug 2015 2 RAGHU MEKA, OANH NGUYEN, AND VAN VU P(x 1;:::;x n) := X Sˆf1;:::;ng;jSjd a S Y j2S x j: (1) The rst result in this direction, due to Costello, Tao, and the third author, [9], is Theorem 1.2. There is a constant Bsuch that the following holds for all d;n. If there are mnd”
Small Ball Probability, Inverse Theorems, and Applications (2012, methodology): “This was proved by Costello, Tao, and the second author [8].”