Let Q_n be a random matrix whose independent rows are chosen uniformly from the vectors in 0,1^n having sum exactly lfloor n/2 rfloor. Nguyen's conjecture. P[Q_n emph is singular]=(frac12+o_n(1))^n. This model is a dependent-entry analogue of random adjacency matrices of regular directed graphs and serves as a test bed for inverse Littlewood–Offord questions. The source states that the paper resolves Nguyen’s conjecture.

Nguyen's singularity conjecture for random matrices with fixed row sums

Let $Q_n$ be a random matrix whose independent rows are chosen uniformly from the vectors in $\{0,1\}^n$ having sum exactly $\lfloor n/2\rfloor$ . Nguyen's conjecture.

\mathbb{P}[Q_n\emph{ is singular}]=\left(\frac{1}{2}+o_n(1)\right)^n.

This model is a dependent-entry analogue of random adjacency matrices of regular directed graphs and serves as a test bed for inverse Littlewood–Offord questions. The source states that the paper resolves Nguyen’s conjecture.

Sources & referencesView supporting material

Primary source

Vishesh Jain, Ashwin Sah and Mehtaab Sawhney, “Sharp invertibility of random Bernoulli matrices”, arXiv:2010.06553 (2021).

Additional references

2 papers in this index state this conjecture (2020). The statement above is taken from the most recent of them; the others are arXiv:2007.06318.

1 week ago

Progress summary

Refreshed 6 days ago

Open

The conjecture remains open: known work shows singular matrices are very rare, but not the precise exponential rate predicted.

Nguyen conjectured that for the fixed-row-sum random matrix model, the singularity probability is asymptotic to $(1/2)^n$ . The conjecture was posed in Nguyen’s work after identifying equal rows as the apparent dominant source of singularity.

Known results

Nguyen proved, for even $n$ , that $\mathbb{P}(Q_n\text{ is singular})=O(n^{-C})$ for every $C>0$ .
Equal rows give the lower bound $\mathbb{P}(Q_n\text{ is singular})\geq (1/2+o(1))^n$ .
Subsequent work proved exponential upper bounds, including $\mathbb{P}(Q_n\text{ is singular})\leq 2e^{-cn}$ , but not the conjectured asymptotic.

Current status (as of August 2026): The conjectured asymptotic remains unproved; only polynomial and exponential-scale nonsingularity estimates are established.

Sources

No solutions have been posted yet.