Singularity of random Bernoulli matrices

Let Mn 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 pn be the probability that Mn is singular. It has been conjectured for sometime that pn= (1/2+o(1))n (basically the probability that there are two equal rows).

Komlos showed, back in the 60s, that pn=o(1). Later he proved that pn=O(n-1/2).
A breakthrough result of Kahn, Komlos and Szemeredi in early 90s gives pn= O(.999n). 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)

Speaker Details

Van Vu is a professor at the mathematics department at UCSD. His interest includes combinatorics, discrete probability and additive number theory.

Date:
Speakers:
Van Vu
Affiliation:
University of California, San Diego

    • Portrait of Jeff Running

      Jeff Running