# Blog

Back to main | List of entries |

## Jain–Sah–Sawhney: Singularity of discrete random matrices

October 13, 2020

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!

Back to main | List of entries |

More posts:

- 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