Singularity of sparse Bernoulli matrices

Abstract

Let $M_n$ be an $n\times n$ random matrix with i.i.d. Bernoulli(p) entries. We show that there is a universal constant $C\ge 1$ such that, whenever $p$ and $n$ satisfy $C\log n/n\le p\le C^{-1}$, \begin{align*} {\mathbb P}\big\{\mbox{$M_n$ is singular}\big\}&=(1+o_n(1)){\mathbb P}\big\{\mbox{$M_n$ contains a zero row or column}\big\}\\ &=(2+o_n(1))n\,(1-p)^n, \end{align*} where $o_n(1)$ denotes a quantity which converges to zero as $n\to \infty$. We provide the corresponding upper and lower bounds on the smallest singular value of $M_n$ as well.