SINGULARITY OF SPARSE BERNOULLI MATRICES

Let M-n be an n x n random matrix with independent and identically distributed Bernoulli(p) entries. We show that there is a universal constant C >= 1 such that, whenever p and n satisfy C log n/n <= p <= C-1, P{M-n is singular} = (1 + o(n)(1))P{M-n contains a zero row or column} = (2 + o(n)(1))n(1-p)(n); where o(n)(1) denotes a quantity which converges to zero as n -> infinity. We provide the corresponding upper and lower bounds on the smallest singular value of M-n as well.