The singularity probability conjecture for random Bernoulli matrices

Let AnA_n be an nn by nn random matrix with iid Bernoulli entries taking values ±1\pm 1 with probability 1/21/2, and let pnp_n be the probability that AnA_n is singular.

Singularity probability conjecture. The singularity probability satisfies

pn=(12+o(1))n.p_n=\left(\frac{1}{2}+o(1)\right)^n.

This conjecture asserts that the elementary lower bound arising from pairs of equal or opposite rows or columns is asymptotically best possible. At the time of the paper, the best known upper bound was exponential, namely pn=O((1/2)n)p_n=O((1/\sqrt{2})^n), so the conjectured asymptotic remained open.

Sources & referencesView supporting material

Primary source

Hoi H. Nguyen, “Inverse Littlewood-Offord problems and The Singularity of Random Symmetric Matrices”, arXiv:1101.3074 (2012).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.