Let $\xi$ be a non-constant real-valued random variable with finite support, and let $M_{ n}(\xi)$ denote an $n\times n$ random matrix with entries that are independent copies of $\xi$. For $\xi$ which is not uniform on its support, we show that \begin{ align*} \mathbb{ P}[M_{ n}(\xi)\text{ is singular}] &= \mathbb{ P}[\text{ zero row or column}] + (1+o_n(1))\mathbb{ P}[\text{ two equal (up to sign) rows or columns}], \end{ align*} thereby confirming a folklore conjecture. As special cases, we obtain: (1) For $\xi = \text{ Bernoulli}(p)$ with fixed $p \in (0,1/2)$, \[\mathbb{ P}[M_{ n}(\xi)\text{ is singular}] = 2n(1-p)^{ n} + (1+o_n(1))n(n-1)(p^2 + (1-p)^2)^{ n},\] which determines the singularity probability to two asymptotic terms. Previously, no result of such precision was available in the study of the singularity of random matrices. (2) For $\xi = \text{ Bernoulli}(p)$ with fixed $p \in (1/2,1)$, \[\mathbb{ P}[M_{ n}(\xi)\text{ is singular}] = (1+o_n(1))n(n-1)(p^2 + (1-p)^2)^{ n}.\] Previously, only the much weaker upper bound of $(\sqrt{ p} + o_n(1))^{ n}$ was known due to the work of Bourgain-Vu-Wood. For $\xi$ which is uniform on its support: (1) We show that \begin{ align*} \mathbb{ P}[M_{ n}(\xi)\text{ is singular}] &= (1+o_n(1))^{ n}\mathbb{ P}[\text{ two rows or columns are equal}]. \end{ align*} (2) Perhaps more importantly, we provide a sharp analysis of the contribution of the `compressible' part of the unit sphere to the lower tail of the smallest singular value of $M_{ n}(\xi)$.
Categories: math.PR math.CO