Konstantin Tikhomirov: The Probability that a Bernoulli Matrix is Singular

Posted on February 2, 2019 by Gil Kalai

Konstantin Tikhomirov

An old problem in combinatorial random matrix theory is cracked!

Singularity of random Bernoulli matrices by Konstantin Tikhomirov

Abstract: For each n, let M_n be an n×n random matrix with independent ±1 entries. We show that

P(M_n is singular}=(1/2+o_n(1))^n,

which settles an old problem. Some generalizations are considered.

János Komlós

Background and discussion

What is the probability s(n) that a random n by n matrix with \pm 1 entries is singular? Well, it can be singular if either two rows are identical, or if two columns are identical. This happens with probability

n(n-1)(1+0(1)) \cdot 2^{-n}.

Are there other more dominant reasons for singularity? Are most \pm 1 matrices nonsingular as n tends to infinity? The first results in this direction are by Janos Komlos who first proved in 1968 that s(n)=o(1) and later that s(n)=O(1/\sqrt n). A major breakthrough came in 1995 when  Kahn , Komlos, and Szemeredi proved that s(n) \le 0.999^n. Terry Tao and Van Vu improved in 2006 the constant to 0.939 and then to (3/4+o(1)) and the, now broken, world record from 2010 was (1/\sqrt 2)+o(1))^n  by Jean Bourgain, Van Vu and Philip Wood. Congratulations Konstantin!

If you want to tease the Gods of Mathematics you can try to prove that s(n) =n(n-1)(1+o(1)) \cdot 2^{-n}? and, as suggested in the Kahn-Komlós-Szemerédi paper,  even prove an expansion  s(n) = 2{{n} \choose {2}}(\frac{1}{2})^{n}+2{{n}\choose {4}} (\frac{3}{8})^n\cdots based on dependencies between k-tuples of rows and columns.

Let me mention that  Kevin Costello, Tao, and Vu, proved in 2005 that  random symmetric matrices are almost surely non-singular.  This is related to beautiful mathematics.  Tao and Vu also proved that the probability for vanishing of the permanent of a Bernoulli matrix is o(1). I am not sure what the proven behavior for permanents is and one may expect that vanishing of the permanent occurs in probability which is super exponentially small. (Perhaps C/\sqrt {n!}.)

Here are related posts on Tao’s blog What’s New. A post on Tao’s Milliman’s lecture on the additive combinatorics and random matrices; On the permanent of random Bernoulli matrix;

Determinants and the guaranteed cancellation phenomenon

The value of the determinant of a Bernoulli matrix is the sum of n! ±1 terms. So we can guess that the expected value will be around \sqrt {n!}, and with high probability it is near the expected value. There is something special about the determinant which we can call the Guaranteed Cancellation Phenomenon (GCP). The value of the determinant of a Bernoulli  matrix is at most n^{n/2} which is not that much larger than \sqrt {n!}. (GCP applies to matrices with real or complex variables with rows with prescribed  \ell_2 norms.)  Guaranteed cancellation is a very interesting mathematical phenomenon in various contexts. (For example, the prime number theorem and the Riemann hypothesis are about guaranteed cancellation.) The determinant itself is a polynomial of degree n with n^2 variables , and GCP for determinants was one of the starting points in a paper that I wrote with Leonard Schulman on quasi-random multilinear polynomials. (For other examples of GCP see also this MO question and various posts  on Mobius randomness.) Maybe it is time to ask on MathOverflow for a list of places were GCP  is expected or proven.)

Sperner, the Littlewood-Offord problem, and additive combinatorics

The determinant of a \pm 1 matrix is the signed sum of n minors. It follows from Sperner’s theorem that if m of these minors are non-zero then the probability that the sum vanishes is O(1/\sqrt m). This is the idea behind Komlos’ second proof. The relevant general question (backward Littlewood Offord  problem) which is of much independent interest is “Under which conditions on a sequence a_1,a_2, \dots, a_n we can guarantee that the probability that a signed sum of the sequence vanished (or has a small absolute value) is small.” The famous Erdos-Moser conjecture (solved on the nose by Stanley using the Hard Lefschetz theorem, sharpening a result by Sárközy and Szemerédi) asserts that if the elements of the sequence are distinct then the larger vanishing probability is attained by the sequence of integers between -[n/2] and +[n/2]. In this case (like for any arithmetic progression) the vanishing probability is n^{-3/2}.  Kahn, Komlos and Szemeredi relied on (and extended)  a theory by  Gábor Halász for guaranteeing that the vanishing probability is small (exponentially small) and, of course, much work is needed to prove that Halász-type conditions are satisfied.

I was excited by the 2005 solution for symmetric matrices also because it involved a quadratic version of Littlewood-Offord type results which are of much independent interest. I think that there are many interesting remaining open problems.

 

This entry was posted in Combinatorics, Probability and tagged . Bookmark the permalink.

4 Responses to Konstantin Tikhomirov: The Probability that a Bernoulli Matrix is Singular

  1. Clement Canonne says:
    February 2, 2019 at 11:14 pm

    “and later that $s(n) = O(\sqrt{n})$”

    Shouldn’t that be 1/\sqrt{n}?

    GK:Thanks, corrected.

    Reply
  2. Misha says:
    March 28, 2019 at 11:19 am

    This old problem was cracked by VlADIMIR BLINOVSKY three years before!
    See https://arxiv.org/abs/1511.05283

    Reply

  3. Pingback: Hoi Neguyen and Melanie Wood: Remarkable Formulas for the Probability that Projections of Lattices are Surjective | Combinatorics and more

  4. Pingback: Greatest Hits 2015-2022, Part II | Combinatorics and more

Leave a comment