Singularity of random Bernoulli matrices

Опубликовано 6 сентября 2016, 5:41

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)