Resilience conjecture for nonsingularity of Bernoulli matrices

At least 19 years old · documented by

For a {−1,1}\{-1,1\} matrix MM, let Res⁡(M)\operatorname{Res}(M) be the minimum number of entries that must be switched from 11 to −1-1 or vice versa in order to make MM singular. Let MnM_n be a random n×nn\times n Bernoulli matrix. Resilience conjecture. Almost surely,

Res⁡(Mn)=(1/2+o(1))n.\operatorname{Res}(M_n)=(1/2+o(1))n.

The conjecture predicts that making two rows equal is asymptotically the cheapest way to destroy nonsingularity. The source gives no resolution.

References

Primary source

V. Vu, “Random Discrete Matrices”, arXiv:math/0611321 (2006).

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.