pith. sign in

arxiv: 2604.12233 · v1 · submitted 2026-04-14 · 🧮 math.PR

An upper bound on the smallest singular value of dense random combinatorial matrices

Dongbin Li , Alexander E. Litvak , Tingzhou Yu This is my paper

Pith reviewed 2026-05-10 16:07 UTC · model grok-4.3

classification 🧮 math.PR
keywords random matricessmallest singular valuecombinatorial matrices0-1 matricesfixed row sumssingular value boundsrandom regular matrices
0
0 comments X

The pith

Dense random 0-1 matrices with fixed row sums have smallest singular value of order n to the power of minus one-half with high probability.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a probabilistic upper bound on the smallest singular value of an n by n random matrix whose rows are chosen independently and uniformly from the 0-1 vectors with exactly d = p n ones. For every positive ε the probability that this singular value falls below sqrt(d) over ε squared n is at least 1 minus C_p times (ε plus 1 over sqrt(d)). This bound complements an earlier lower bound of order 1 over sqrt(n) and shows that the smallest singular value is typically of order n to the minus one-half. Readers care because the size of the smallest singular value governs how well-conditioned the matrix is and how accurately linear systems involving it can be solved.

Core claim

For an n by n matrix M with rows drawn independently and uniformly from all vectors in {0,1}^n having exactly d ones where d = p n and p fixed in (0, 1/2], the smallest singular value s_n(M) satisfies that for every ε > 0 the probability it is at most sqrt(d) / (ε² n) is at least 1 minus C_p (ε + 1/sqrt(d)), with C_p depending only on p. This confirms s_n(M) is typically of order n^{-1/2}.

What carries the argument

The smallest singular value s_n(M) of the random matrix M with fixed row sums, controlled through a direct probability estimate that bounds the chance M x stays small for unit vectors x.

If this is right

  • The condition number of M is typically of order sqrt(n) since the largest singular value is order sqrt(d).
  • Linear systems Mx = b with such random matrices are solvable to accuracy roughly 1/sqrt(n) in the presence of noise.
  • The matrix M is invertible with probability tending to 1 as n grows.
  • The result applies uniformly for any fixed density p in (0,1/2].

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The upper and lower bounds together imply that s_n(M) concentrates on the scale n^{-1/2} rather than merely being bounded above and below separately.
  • Similar upper bounds may hold for other models with constant row sums, such as adjacency matrices of random regular bipartite graphs.
  • The probability bound suggests that the smallest singular value does not fluctuate too wildly once the row-sum constraint is fixed.

Load-bearing premise

The rows are chosen independently and uniformly at random from the set of all 0-1 vectors with exactly d ones.

What would settle it

Generate many independent realizations of such a matrix for increasing n and observe whether the empirical distribution of s_n(M) sqrt(n) stays bounded away from zero or instead concentrates near a positive constant.

Figures

Figures reproduced from arXiv: 2604.12233 by Alexander E. Litvak, Dongbin Li, Tingzhou Yu.

Figure 1
Figure 1. Figure 1: Log-log plots of the mean smallest singular value E[sn(M)] versus n. Points show simulation results (mean ± standard error). The dashed lines represent reference slopes proportional to √ d/n. (a) Case d = ⌊n 1/3 ⌋. (b) Case d = 5⌊log n⌋. Organization of the paper. This paper is structured as follows. In Section 2, we introduce essential preliminaries, including key concepts such as biorthogonal systems, al… view at source ↗
read the original abstract

Let $M$ be an $n\times n$ random matrix with entries in $\{0, 1\}$, where each row is independently and uniformly sampled from the set of all vectors in $\{0, 1\}^n$ containing exactly $d$ ones, with $d=pn$ for some fixed constant $p\in (0,1/2]$. A recent result of Tran states that the smallest singular value $s_n(M)$ is bounded below by $c_p n^{-1/2}$ with high probability. In this note, we establish a complementary upper bound for $s_n(M)$, proving that \[ \forall \varepsilon >0 \qquad \mathbb{P}\left(s_n(M)\le \frac{\sqrt{d}}{\varepsilon^2 n}\right)\ge 1-C_p\left(\varepsilon+\frac{1}{\sqrt{d}}\right), \]where $C_p$ is a positive constant depending only on $p$. This result confirms that the least singular value $s_n(M)$ of dense random combinatorial matrices is typically of the order $n^{-1/2}$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript proves a complementary upper bound on the smallest singular value s_n(M) for an n×n random combinatorial matrix M whose rows are chosen independently and uniformly from the set of all {0,1}^n vectors with exactly d=pn ones, p fixed in (0,1/2]. It shows that ∀ε>0, P(s_n(M) ≤ √d/(ε² n)) ≥ 1−C_p(ε + 1/√d) with C_p depending only on p. This pairs with Tran's lower bound to conclude that s_n(M) is typically of order n^{-1/2}.

Significance. If the result holds, it supplies the matching upper bound needed to establish that the smallest singular value of these dense random combinatorial matrices is typically Θ(n^{-1/2}) with high probability. This strengthens the spectral picture for a standard model in combinatorial probability and random matrix theory, confirming well-conditioned behavior at the natural scale. The ε-tradeoff is the usual device for obtaining 'typically' statements and the reduction to the Bernoulli case (as noted in the stress-test) appears free of circularity or hidden parameters.

minor comments (2)
  1. Abstract and §1: the factor 1/ε² in the threshold could be compared explicitly to the constant in Tran's lower bound to make the 'typically Θ(n^{-1/2})' statement sharper.
  2. The dependence of C_p on p is stated but not quantified; a brief remark on its growth as p→0 or p→1/2 would aid readers applying the bound.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and the recommendation for minor revision. The referee's summary accurately captures the main result: a complementary upper bound showing that the smallest singular value of dense random combinatorial matrices is typically of order n^{-1/2}.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper derives a probabilistic upper bound on the smallest singular value s_n(M) for random combinatorial matrices with fixed row sparsity p, using standard concentration and matrix analysis techniques. It explicitly complements an external result by Tran (cited as prior independent work) without any self-referential definitions, fitted parameters renamed as predictions, or load-bearing self-citations. The claimed inequality is obtained directly from the model assumptions and does not reduce to its inputs by construction. No ansatz smuggling, uniqueness theorems from the authors, or renaming of known results occurs in the derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, no free parameters, invented entities, or non-standard axioms are identifiable. The result relies on background facts from probability and linear algebra.

axioms (1)
  • standard math Standard facts about singular values and concentration inequalities for random matrices
    Invoked implicitly to derive the probability bound on s_n(M).

pith-pipeline@v0.9.0 · 5496 in / 1119 out tokens · 91661 ms · 2026-05-10T16:07:14.333099+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

45 extracted references · 45 canonical work pages · 1 internal anchor

  1. [1]

    Addario-Berry and L

    L. Addario-Berry and L. Eslava. Hitting time theorems for random matrices. Combinatorics, Probability and Computing, 23(5):635–669, 2014

    work page 2014

  2. [2]

    Aigner-Horev and Y

    E. Aigner-Horev and Y. Person. On sparse random combinatorial matrices.Dis- crete Math., 345(11):Paper No. 113017, 11, 2022

    work page 2022

  3. [3]

    Basak and M

    A. Basak and M. Rudelson. Sharp transition of the invertibility of the adjacency matrices of sparse random graphs.Probability Theory and Related Fields, 180:233– 308, 2021

    work page 2021

  4. [4]

    Bordenave and D

    C. Bordenave and D. Chafai. Around the circular law.Probability Surveys, 9:1–89, 2012

    work page 2012

  5. [5]

    Campos, M

    M. Campos, M. Jenssen, M. Michelen, and J. Sahasrabudhe. The least singular value of a random symmetric matrix. InForum of Mathematics, Pi, volume 12, page e3. Cambridge University Press, 2024

    work page 2024

  6. [6]

    N. A. Cook. On the singularity of adjacency matrices for random regular digraphs. Probability Theory and Related Fields, 167(1-2):143–200, 2017

    work page 2017

  7. [7]

    D. P. Dubhashi and A. Panconesi.Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009

    work page 2009

  8. [8]

    A. Edelman. Eigenvalues and condition numbers of random matrices.SIAM journal on matrix analysis and applications, 9(4):543–560, 1988

    work page 1988

  9. [9]

    Ferber, V

    A. Ferber, V. Jain, K. Luh, and W. Samotij. On the counting problem in in- verse Littlewood–Offord theory.Journal of the London Mathematical Society, 103(4):1333–1362, 2021

    work page 2021

  10. [10]

    Ferber, M

    A. Ferber, M. Kwan, and L. Sauermann. Singularity of sparse random matrices: simple proofs.Combinatorics, Probability and Computing, 31(1):21–28, 2022

    work page 2022

  11. [11]

    Fernandez V

    M. Fernandez V. A distance theorem for inhomogenous random rectangular ma- trices.arXiv:2408.06309, 2024

    work page arXiv 2024

  12. [12]

    G. H. Golub and C. F. Van Loan.Matrix computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, fourth edition, 2013

    work page 2013

  13. [13]

    V. Jain. Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices.Israel Journal of Mathematics, 242(1):461–500, 2021

    work page 2021

  14. [14]

    V. Jain, A. Sah, and M. Sawhney. Sharp invertibility of random Bernoulli matrices. arXiv:2010.06553, 2020

    work page arXiv 2010

  15. [15]

    V. Jain, A. Sah, and M. Sawhney. Singularity of discrete random matrices.Geom. Funct. Anal., 31(5):1160–1218, 2021

    work page 2021

  16. [16]

    V. Jain, A. Sah, and M. Sawhney. The smallest singular value of dense random regular digraphs.International Mathematics Research Notices, 2022(24):19300– 19334, 2022. 19

    work page 2022

  17. [17]

    J. Kahn, J. Koml´ os, and E. Szemer´ edi. On the probability that a random±1 matrix is singular.Journal of the American Mathematical Society, 8(1):223–240, 1995

    work page 1995

  18. [18]

    M. Kwan, B. Sudakov, and T. Tran. Anticoncentration for subgraph statistics.J. Lond. Math. Soc. (2), 99(3):757–777, 2019

    work page 2019

  19. [19]

    D. Li, A. E. Litvak, and T. Yu. The circular law for sparse random combinatorial matrices.arXiv:2604.10446, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  20. [20]

    A. E. Litvak, A. Lytova, K. Tikhomirov, N. Tomczak-Jaegermann, and P. Youssef. Adjacency matrices of random digraphs: singularity and anti-concentration.Jour- nal of Mathematical Analysis and Applications, 445(2):1447–1491, 2017

    work page 2017

  21. [21]

    A. E. Litvak, A. Lytova, K. Tikhomirov, N. Tomczak-Jaegermann, and P. Youssef. The smallest singular value of a shiftedd-regular random square matrix.Proba- bility Theory and Related Fields, 173:1301–1347, 2019

    work page 2019

  22. [22]

    A. E. Litvak, A. Pajor, M. Rudelson, and N. Tomczak-Jaegermann. Smallest singular value of random matrices and geometry of random polytopes.Advances in Mathematics, 195(2):491–523, 2005

    work page 2005

  23. [23]

    A. E. Litvak and K. E. Tikhomirov. Singularity of sparse Bernoulli matrices.Duke Mathematical Journal, 171(5):1135–1233, 2022

    work page 2022

  24. [24]

    G. V. Livshyts. The smallest singular value of heavy-tailed not necessarily i.i.d. random matrices via random rounding.Journal d’Analyse Math´ ematique, 145(1):257–306, 2021

    work page 2021

  25. [25]

    G. V. Livshyts, K. Tikhomirov, and R. Vershynin. The smallest singular value of inhomogeneous square random matrices.The Annals of Probability, 49(3):1286– 1309, 2021

    work page 2021

  26. [26]

    Mendelson and G

    S. Mendelson and G. Paouris. On the singular values of random matrices.Journal of the European Mathematical Society (EMS Publishing), 16(4), 2014

    work page 2014

  27. [27]

    H. H. Nguyen. On the singularity of random combinatorial matrices.SIAM Journal on Discrete Mathematics, 27(1):447–458, 2013

    work page 2013

  28. [28]

    H. H. Nguyen and V. H. Vu. Circular law for random discrete matrices of given row sum.Journal of Combinatorics, 4(1):1–30, 2013

    work page 2013

  29. [29]

    Rebrova and K

    E. Rebrova and K. Tikhomirov. Coverings of random ellipsoids, and invertibility of matrices with iid heavy-tailed entries.Israel Journal of Mathematics, 227:507– 544, 2018

    work page 2018

  30. [30]

    Rudelson and K

    M. Rudelson and K. Tikhomirov. The sparse circular law under minimal assump- tions.Geom. Funct. Anal., 29(2):561–637, 2019

    work page 2019

  31. [31]

    Rudelson and R

    M. Rudelson and R. Vershynin. The least singular value of a random square matrix isO(n −1/2).Comptes Rendus Mathematique, 346(15-16):893–896, 2008

    work page 2008

  32. [32]

    Rudelson and R

    M. Rudelson and R. Vershynin. The Littlewood–Offord problem and invertibility of random matrices.Advances in Mathematics, 218(2):600–633, 2008. 20

    work page 2008

  33. [33]

    Rudelson and R

    M. Rudelson and R. Vershynin. Smallest singular value of a random rectangular matrix.Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 62(12):1707–1739, 2009

    work page 2009

  34. [34]

    Spielman and S.-H

    D. Spielman and S.-H. Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time.Journal of the ACM (JACM), 51(3):385– 463, 2004

    work page 2004

  35. [35]

    S. J. Szarek. Condition numbers of random matrices.Journal of Complexity, 7(2):131–149, 1991

    work page 1991

  36. [36]

    Tao.Topics in random matrix theory, volume 132

    T. Tao.Topics in random matrix theory, volume 132. American Mathematical Soc., 2012

    work page 2012

  37. [37]

    Tao and V

    T. Tao and V. Vu. Inverse Littlewood-Offord theorems and the condition number of random discrete matrices.Annals of Mathematics, pages 595–632, 2009

    work page 2009

  38. [38]

    Tao and V

    T. Tao and V. Vu. Random matrices: The distribution of the smallest singular values.Geometric And Functional Analysis, 20:260–297, 2010

    work page 2010

  39. [39]

    Tao and V

    T. Tao and V. Vu. Random matrices: universality of ESDs and the circular law.The Annals of Probability, 38(5):2023–2065, 2010. With an appendix by Manjunath Krishnapur

    work page 2023

  40. [40]

    K. Tatarko. An upper bound on the smallest singular value of a square random matrix.Journal of Complexity, 48:119–128, 2018

    work page 2018

  41. [41]

    Tikhomirov

    K. Tikhomirov. Singularity of random Bernoulli matrices.Annals of Mathematics, 191(2):593–634, 2020

    work page 2020

  42. [42]

    Tikhomirov

    K. Tikhomirov. Quantitative invertibility of non-Hermitian random matrices.to appear in the ICM 2022 proceedings, arXiv:2206.00601, 2022

    work page arXiv 2022

  43. [43]

    T. Tran. The smallest singular value of random combinatorial matrices. arXiv:2007.06318, 2020

    work page arXiv 2007

  44. [44]

    von Neumann.Collected works

    J. von Neumann.Collected works. Vol. V: Design of computers, theory of automata and numerical analysis. The Macmillan Company, New York, 1963. General editor: A. H. Taub

    work page 1963

  45. [45]

    von Neumann and H

    J. von Neumann and H. H. Goldstine. Numerical inverting of matrices of high order.Bulletin of the American Mathematical Society, 53(11):1021 – 1099, 1947. Alexander E. Litvak Email address:alitvak@ualberta.ca Dongbin Li Email address:dongbin@ualberta.ca Tingzhou Yu Email address:tingzho1@ualberta.ca Department of Mathematical and Statistical Sciences, Uni...

    work page 1947