On the singularity probability of random Bernoulli matrices

By Terence Tao, Van H. Vu. 2005

212 citations recorded by the source corpus.

Let $n$ be a large integer and $M_n$ be a random $n$ by $n$ matrix whose entries are i.i.d. Bernoulli random variables (each entry is $\pm 1$ with probability 1/2). We show that the probability that $M_n$ is singular is at most $(3/4 +o(1))^n$, improving an earlier estimate of Kahn, Koml\'os and Szemer\'edi, as well as earlier work by the authors. The key new ingredient is the applications of Freiman type inverse theorems and other tools from additive combinatorics.

Subfields: Geometry and Topology, Mathematical Physics, Statistics and Probability

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

How researchers see this paper

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

In Geometry and Topology

In Mathematical Physics

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].”
On the singularity probability of discrete random matrices (2009, methodology): “2] (which was called the Structure Theorem in [11]), which gives a complete characterization of a set with certain additive properties.”
Random integral matrices: universality of surjectivity and the cokernel (2018, methodology): “r medium primes, analogous to the proof of Theorem 5.1. Now we give a proof of Theorem 8.2. Our overall approach is similar to the proof of [21, Theorems A.1 and A.4] (which is built on approaches in [19, 30]), but for the Laplacian we cannot apply these results because the column vectors, as well a”
Inverse Littlewood-Offord problems and The Singularity of Random Symmetric Matrices (2011, background): “One may hope to combine our approach and the ”replacement technique” from [9] and [24] to improve the bound further to exponential decay.”
Non-asymptotic theory of random matrices: extreme singular values (2010, background): “The base c was gradually improved in [78, 81], with the latest record of p n = (1 / √ 2+ o (1)) n obtained in [12].”
Random Matrices: the Distribution of the Smallest Singular Values (2009, background): “For more recent developments along this line we refer to [20, 46, 6].”
Singularity of random Bernoulli matrices (2018, background): “939n in [15] and (3/4+on(1)) n in [16] by T.”
On the singularity of adjacency matrices for random regular digraphs (2014, methodology): “999 was obtained by Kahn, Komlós and Szemerédi in [18], and was lowered to c = 3/4 + o(1) by Tao and Vu [40], and to c = 1/ √ 2 + o(1) by Bourgain, Vu and Wood [7].”
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].”
Inverse Littlewood-Offord theorems and the condition number of random discrete matrices (2005, background): “Finally we perform some additional arguments to eliminate the 1τ dilations in Theorem 2.4 and obtain our final inverse Littlewood-Offord theorem.”
On the hyperplane conjecture for random convex sets (2006, unknown): “See [14, 25].”
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].”
From the Littlewood-Offord problem to the Circular Law: universality of the spectral distribution of random matrices (2008, methodology): “Motivated by inverse theorems from additive combinatorics, in particular Freiman’s theorem (see [15], [48, Chapter 5]) and a variant for random sums in [ 53, Theorem 5.2 ] (inspired by earlier work in [26]), the authors [49] brought a different view to the problem.”
Small Ball Probability, Inverse Theorems, and Applications (2012, methodology): “This method was first used in studies of random matrices [57, 60, 45], but it is simpler to illustrate the idea by the following more recent result of Conlon, Fox, and Sudakov [6].”
Graphs with integral spectrum (2009, unknown): “We note that despite a recent series of very strong results [2, 9, 23, 24, 25, 26] treating various counting questions for 0, 1-matrices, no upper bounds on I(n) have been known prior to our work, which derives the following result:”