Inverse Littlewood-Offord problems and The Singularity of Random Symmetric Matrices

Abstract

Let $M_n$ denote a random symmetric $n$ by $n$ matrix, whose upper diagonal entries are iid Bernoulli random variables (which take value -1 and 1 with probability 1/2). Improving the earlier result by Costello, Tao and Vu, we show that $M_n$ is non-singular 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.

arXiv commentSome minor corrections in Section 10 of v1

Cited by in corpus (5)

• Random doubly stochastic matrices: The circular law
• Anticoncentration for subgraph statistics
• Singularity of random symmetric matrices -- a combinatorial approach to improved bounds
• Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjecture
• Small ball estimates for quasi-norms