Singularity probability conjecture for random fixed-row-sum matrices

About 21 years old · traced to

Let nn be even, and let QnQ_n be a random nn by nn (0,1)(0,1) matrix whose rows are independent vectors with exactly n/2n/2 zero components. Fixed-row-sum singularity probability conjecture. The probability that QnQ_n is singular satisfies

P(Qn is singular)=(12+o(1))n.{\bf P}(Q_n\text{ is singular})=\left(\frac{1}{2}+o(1)\right)^n.

The theorem in the source proves only the bound O(n−C)O(n^{-C}) for every C>0C>0, while equal rows give the displayed lower bound. Thus the conjecture predicts that this elementary obstruction has the correct asymptotic order.

References

Primary source

Hoi H. Nguyen, “On the singularity of random combinatorial matrices”, arXiv:1112.0753 (2011).

Additional references

2 papers in this index state this conjecture (2005–2011). The statement above is taken from the most recent of them; the others are arXiv:math/0505156.

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.