On the singularity probability of discrete random matrices

By Jean Bourgain, Van H. Vu, Philip Matchett Wood. 2009

179 citations recorded by the source corpus.

Abstract Let n be a large integer and M n 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 M n 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 of M n satisfy this property, then the probability that M n is singular is at most ( p 1 / 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 M n are “fair coin flips” (taking the values + 1 , − 1 each with probability 1/2), our general bound implies that the probability that M n is singular is at most ( 1 2 + o ( 1 ) ) n , improving on the previous best upper bound of ( 3 4 + 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 M n 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 M n is singular is at most ( 1 2 + o ( 1 ) ) n , which is asymptotically sharp. Our method is a refinement of those from [Jeff Kahn, Janos Komlos, Endre Szemeredi, 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.

Subfields: Applied Mathematics, Electrical and Electronic Engineering, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/fc9f640402acc7cb98d755479a5016e450971ab5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Electrical and Electronic Engineering

In Statistics and Probability

Citations in the corpus

Random matrices: Law of the determinant (2011, background): “Following [12], the upper bound on the probability that det An = 0 has been improved in [11, 20, 21, 3].”
Random integral matrices and the Cohen-Lenstra heuristics (2015, background): “ich are captured by our notion of depth. Inverse Littlewood-Oﬀord Theorems are a key component in the most recent work on singularity probability of discrete random matrices in characteristic 0, both [BVW10] mentioned above and the earlier work of Tao and Vu [TV07]. 3 (See the papers of Tao and Vu [”
The smallest singular value of inhomogeneous square random matrices (2019, background): “The behavior of the smallest singular values of random matrices have been extensively studied [2, 4, 5, 11, 15, 16, 17, 20, 22, 24, 25, 26, 33, 34, 35, 36, 37, 38, 39, 40, 41, 43].”
Singularity of random Bernoulli matrices (2018, methodology): “The proof of upper bounds on the probability of singularity of random discrete matrices developed in work [5] and later in [15, 16, 2], uses, as a starting point, the relation”
Adjacency matrices of random digraphs: singularity and anti-concentration (2015, background): “Upper bounds for the singular probability of random Bernoulli matrices were successively improved to c (for some c ∈ (0, 1)) in [18]; to ( 3/4 + o(1) )n in [34]; and to ( 1/ √ 2 + o(1) )n in [6].”
Small Ball Probability, Inverse Theorems, and Applications (2012, background): “The best current bound is (1/ √ 2 + o(1))n by Bourgain, Vu and Wood [3].”
Inverse Littlewood-Offord problems and The Singularity of Random Symmetric Matrices (2011, background): “The most recent record is due to Bourgain, Vu and Wood [2], who improved it to pn = O((1/ √ 2)n).”
On the singularity of adjacency matrices for random regular digraphs (2014, methodology): “s machinery. Specifically, the base c= :999 was obtained by Kahn, Komlos and Szemeredi in [16], and was lowered to c= 3=4 + o(1) by Tao and Vu [30], and to c= 1= p 2 + o(1) by Bourgain, Vu and Wood [6]. The latter two works relied on the inverse Littlewood-Oord theory developed in [30]. These bounds”
Around the circular law (2011, background): “It can be derived form a representation of stable laws, see e.g. LePage, Woodroofe, and Zinn [101] and also Panchenko and Talagrand [117, Lemma 2.1].”