Sharp singularity asymptotics for discrete random matrices

Abstract

We resolve the Rademacher singularity conjecture: an $n\times n$ matrix with independent uniform $\{-1,1\}$ entries is singular with probability $(2+o(1))n^2{2}^{-n}$. More generally, for an $n\times n$ matrix $M_n$ with independent entries uniform on a fixed set $S\subset \mathbb{R}$ of cardinality $q\ge 2$, we prove $\mathbb{P}(s_n(M_n)\le z/\sqrt{n})\le Cz+a_n(S)+C^{\prime }{n}^{1+\epsilon }{q}^{-n}$ for all $n\ge 1$, $z\ge 0$, and $\epsilon >0$, with $C=C(S)$ and $C^{\prime }=C^{\prime }(S,\epsilon )$. Here $s_n$ denotes the least singular value, and $a_n(S)$ is the sum of the probabilities of the events involving zero rows or columns and equal or opposite pairs of rows or columns.