Singularity of random symmetric matrices -- a combinatorial approach to improved bounds

Abstract

Let $M_n$ denote a random symmetric $n\times n$ matrix whose upper diagonal entries are independent and identically distributed Bernoulli random variables (which take values $1$ and $-1$ with probability $1/2$ each). It is widely conjectured that $M_n$ is singular with probability at most $(2+o(1){)}^{-n}$. On the other hand, the best known upper bound on the singularity probability of $M_n$, due to Vershynin (2011), is $2^{-n^c}$, for some unspecified small constant $c>0$. This improves on a polynomial singularity bound due to Costello, Tao, and Vu (2005), and a bound of Nguyen (2011) showing that the singularity probability decays faster than any polynomial. In this paper, improving on all previous results, we show that the probability of singularity of $M_n$ is at most $2^{-n^{1/4}\sqrt{\log n}/1000}$ for all sufficiently large $n$. The proof utilizes and extends a novel combinatorial approach to discrete random matrix theory, which has been recently introduced by the authors together with Luh and Samotij.

Final version incorporating referee comments

References in corpus (2)

• Quantitative invertibility of random matrices: a combinatorial perspective
• Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices

Cited by in corpus (6)

• The characteristic polynomial of a random matrix
• An ensemble of high rank matrices arising from tournaments
• Quantitative invertibility of random matrices: a combinatorial perspective
• Resilience of the Rank of Random Matrices
• Sparse recovery properties of discrete random matrices
• On the permanent of a random symmetric matrix