← All problems

The optimal singularity-probability conjecture for random symmetric Bernoulli matrices

8 years old · traced to

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(2−nc)q_n=O(2^{-n^c}) for some unspecified constant c>0c>0, while the matching lower bound was known.

References

Status

  • Solved: Marcelo Campos, Matthew Jenssen, Marcus Michelen, and Julian Sah. The singularity probability of a random symmetric matrix (arXiv, 2021) https://arxiv.org/abs/2105.11384

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 2

Claimed by OpenAI. Claims that a symmetric n-by-n matrix with independent uniformly random sign entries on and above the diagonal has singularity probability (1/2 + o(1))^n.See full solutionHide full solution

The symmetric independent equiprobable sign-entry model agrees with the target; (1/2+o(1))^n is the same exponential-rate formulation as (2+o(1))^(-n). Source independence includes the diagonal.

GitHub repository: https://github.com/openai/math

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/The-sharp-exponential-rate-of-singularity-for-symmetric-Bernoulli-matrices-October-3-2026/symmetric-bernoulli-singularity.pdf

  • OpenAI-239-01-The-sharp-exponential-rate-of-singularity-for-symmetric-Bernoulli-matrices.pdf644,716 bytesOpen
Claimed by OpenAI. For a symmetric n-by-n random matrix with independent signs on and above the diagonal, equal to 1 with fixed probability p in (0,1) except 1/2, claims lim as n tends to infinity of P(det A_n=0)^(1/n)=p^2+(1-p)^2. Equivalently, its singularity probability is (p^2+(1-p)^2+o(1))^n.See full solutionHide full solution

This is a biased-sign extension of the target model for fixed p in (0,1) distinct from1/2. It claims rate p^2+(1-p)^2 for independent on-and-above-diagonal signs; it does not itself supply the p=1/2 case requested here.

GitHub repository: https://github.com/openai/math

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/The-sharp-singularity-rate-for-biased-symmetric-sign-matrices-October-4-2026/biased-symmetric-sign-singularity.pdf

  • OpenAI-239-02-The-sharp-singularity-rate-for-biased-symmetric-sign-matrices.pdf560,671 bytesOpen