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

At least 5 years old · documented by 2020

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.

References

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.

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A 2020 paper claims to settle the conjecture by showing that two identical rows determine the correct exponential scale of singularity.

Nguyen posed the conjecture in work from 2011, predicting that singularity is asymptotically caused by coincident rows in the fixed-row-sum model.

Known results

Nguyen, 2011: proved $\mathbb{P}(Q_n\text{ is singular})=O_C(n^{-C})$ for every $C>0$ in the even- $n$ case.
Coincident rows give the lower-bound scale $\left(\frac{1}{2}+o(1)\right)^n$ .
Before the sharp result, later work obtained only weaker exponential-type upper bounds.

2020 claimed resolution

Jain, Sah, and Sawhney state that their paper settles Nguyen’s conjecture. They prove, for every $\epsilon>0$ , an upper bound of the form $\mathbb{P}[s_n(Q_n)\le t/\sqrt n]\le C_\epsilon t+\left(\frac12+\epsilon\right)^n$ , matching the coincident-row lower-bound scale and implying the claimed asymptotic. A related 2020 paper records the same resolution.

Current status (as of August 2026): Nguyen’s conjecture is claimed solved by Jain, Sah, and Sawhney, but the retrieved evidence does not independently verify the proof.

Sources

No solutions have been posted yet.