The optimal singularity-probability conjecture for random symmetric Bernoulli matrices

Let MnM_n be a random n×nn\times n symmetric matrix whose upper-diagonal entries are independent Bernoulli random variables taking the values 11 and 1-1 with probability 1/21/2 each, and let qn=P(Mn is singular)q_n=\mathbb{P}(M_n\text{ is singular}). The event that the first and last rows are equal up to a sign gives the lower bound qn(2+o(1))nq_n\geq(2+o(1))^{-n}. Optimal singularity-probability conjecture. One has

qn=(2+o(1))n.q_n=(2+o(1))^{-n}.

This conjecture asserts that the elementary row-dependence construction gives the correct asymptotic order. Before this work, the best known upper bound was only qn=O(2nc)q_n=O(2^{-n^c}) for some unspecified constant c>0c>0, while the matching lower bound was known.

Sources & referencesView supporting material

Primary source

Asaf Ferber and Vishesh Jain, “Singularity of random symmetric matrices – a combinatorial approach to improved bounds”, arXiv:1809.04718 (2019).

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.