On the singularity probability of discrete random matrices

Let n be a large integer and Mn be an n by n complex matrix whose entries are independent (but not necessarily identically distributed) discrete random variables. The main goal of this paper is to prove a general upper bound for the probability that Mn is singular. For a constant 0< p <1 and a constant positive integer r, we will define a property p-bounded of exponent r. Our main result shows that if the entries ofMn satisfy this property, then the probability that Mn is singular is at most (p1/r + o(1))n. All of the results in this paper hold for any characteristic zero integral domain replacing the complex numbers. In the special case where the entries of Mn are “fair coin flips” (taking the values +1,−1 each with probability 1/2), our general bound implies that the probability that Mn is singular is at most ( 1 √2 + o(1))n, improving on the previous best upper bound of (34 + o(1))n, proved by Tao and Vu [Terence Tao, Van Vu, On the singularity probability of random Bernoulli matrices, J. Amer. Math. Soc. 20 (2007) 603–628]. In the special case where the entries of Mn are “lazy coin flips” (taking values +1,−1 each with probability 1/4 and value 0 with probability 1/2), our general bound implies that the probability that Mn is singular is at most (12 + o(1))n, which is asymptotically sharp. Our method is a refinement of those from [Jeff Kahn, János Komlós, Endre Szemerédi, On the probability that a random ±1-matrix is singular, J. Amer. Math. Soc. 8 (1) (1995) 223–240; Terence Tao, Van Vu, On the singularity probability of random Bernoulli matrices, J. Amer. Math. Soc. 20 (2007) 603–628]. In particular, we make a critical use of the structure theorem from [Terence Tao, Van Vu, On the singularity probability of random Bernoulli matrices, J. Amer. Math. Soc. 20 (2007) 603–628], which was obtained using tools from additive combinatorics. © 2009 Elsevier Inc. All rights reserved.