Singularity of random Bernoulli matrices

330 views · Published 6 September 2016 · 1:26:16 · Indexed 12 November 2026

Channel: Microsoft Research · 2016 · Science & Technology

Watch on YouTube

Let M_n be an n by n random matrix, whose entries are i.i.d. Bernoulli random variables (taking  value 1 and -1 with probability half). Let p_n be the probability that M_n is singular. It has been conjectured for sometime that p_n= (1/2+o(1))^n (basically the probability that there are two equal rows).    Komlos showed, back in the 60s, that p_n=o(1). Later he proved that p_n=O(n^{-1/2}).  A breakthrough result of Kahn, Komlos and Szemeredi in early 90s gives p_n= O(.999^n). In this talk, we present a new result which improves the bound to (3/4+o(1))^n. The new main ingredient in this work is the so-called inverse technique from additive number theory.    Joint work with T. Tao (UCLA)

More from this channel