On the Singular Probability of Random Discrete Matrices

Let $n$ be a large integer and $M_n$ be an $n$ by $n$ random matrix
whose entries are independent (but not necessarily identically
distributed) random variables. The main goal of this paper is to prove
a general upper bound for the probability that $M_{n}$ is singular.

For a constant $0< p< 1$ and a constant positive integer $r$, we will
define a property called $p$-bounded of exponent $r$. Our main result
shows that if the entries of $M_n$ satisfy this property, then the
probability that $M_n$ is singular is at most $(p^{1/r} + o(1))^n$.
Here are a few sample corollaries of this theorem:

(1) If the distribution of each entry has mass at most p on a single
point, then the singular probability is at most  $(p+o(1))^{n/2}$. In
the special case of random Bernoulli matrices, this improves the
previous bound $(3/4+o(1))^n$ due to Tao and Vu.

(2) If the entries are iid with distribution which puts mass 1/2 on 0
and 1/4 on -1 and 1, then the singular probability is at most
$(1/2+o(1))^n$. This bounds is sharp, as the probability of having a
zero row is (1/2+o(1))^n.

The proof refines the approach from Kahn-Komlos-Szemeredi and Tao-Vu
and makes a critical use of Tao-Vu inverse theorem.

(Joint work with J. Bourgain and V. Vu).