Singularity probability conjecture for random fixed-row-sum matrices

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(nC)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.

Sources & referencesView supporting material

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.