Blog

Vishesh Jain, Ashwin Sah, and Mehtaab Sawhney just posted two amazing papers: Singularity of discrete random matrices Part I and Part II.

The singularity problem for random matrices: what is the probability that a random $n\times n$ matrix with independent 0/1 entries is singular?

The first non-trivial bound on this problem was by Komlós in 1967. After a long series of works by many mathematicians including Kahn, Komlós, Szemerédi, Tao, Vu, Bourgain, Wood, Rudelson, and Vershynin, a breakthrough was recently achieved by Tikhomirov, who showed that, when the matrix entries are iid uniform from \(\{0,1\}\), the probability of singularity if $(1/2 + o(1))^n$, which is tight since with probability $2^{-n}$ the first row is zero.

The new papers of Jain–Sah–Sawhney consider a natural extension of the singularity problem where each entry of the $n\times n$ matrix is iid: 1 with probability $p$ and 0 with probability $1-p$, for some value of $p$ other than 1/2.

A folklore conjecture in this area states that the main reason for the singularity of such random matrices is the presence of two equal rows/columns or some zero row/column:

Conjecture. For a fixed $0 < p < 1$, the probability that a random $n\times n$ matrix with iid Bernoulli(p) entries is singular is $1+o(1)$ times the probability that the matrix has one of the following: (a) two equal rows, (b) two equal columns, (c) a zero row, (d) a zero column.

Note that even Tikhomirov’s breakthrough result does not give precise enough results to answer this conjecture. However, we now have the following incredible result.

Theorem. (Jain–Sah–Sawhney) The above conjecture is true for all $p \ne 1/2$.

(The case $p = 1/2$ remains open.)

In fact, they prove something much more general: namely that the above result remains true if the random matrix entries are iid discrete random variables that are non-uniform on its support. Furthermore, they prove nearly tight bounds on the probability of these matrices having small least singular values. Very impressive!

• Mehtaab Sawhney wins Clay Research Fellowship 1/25/2024
• Papers by MIT combinatorialists—Fall 2023 12/22/2023
• Schildkraut: Equiangular lines and large multiplicity of fixed second eigenvalue 3/6/2023
• Nearly all k-SAT functions are unate 9/19/2022
• Kwan–Sah–Sawhney–Simkin: High-girth Steiner triple systems 1/13/2022
• Graphs with high second eigenvalue multiplicity 9/28/2021
• Enumerating k-SAT functions 7/21/2021
• Mathematical tools for large graphs 7/12/2021
• How I manage my BibTeX references, and why I prefer not initializing first names 7/4/2021
• The cylindrical width of transitive sets 1/28/2021
• Ashwin Sah and Mehtaab Sawhney win the Morgan Prize 10/29/2020
• Jain–Sah–Sawhney: Singularity of discrete random matrices 10/13/2020
• Gunby: Upper tails for random regular graphs 10/5/2020
• Joints of varieties 9/12/2020
• Ashwin Sah's new diagonal Ramsey number upper bound 5/20/2020
• Joints tightened 11/21/2019
• Equiangular lines with a fixed angle 7/30/2019
• Impartial digraphs 6/27/2019
• A reverse Sidorenko inequality 9/26/2018
• The number of independent sets in an irregular graph 5/12/2018