pith. sign in

arxiv: 2604.11761 · v1 · submitted 2026-04-13 · 🧮 math.PR · math.CO

The smallest singular value of signed random combinatorial matrices

Kexin Yu This is my paper

Pith reviewed 2026-05-10 15:56 UTC · model grok-4.3

classification 🧮 math.PR math.CO
keywords random matricessmallest singular valuecombinatorial matricesanti-concentrationCLCDsingularity probabilitysigned vectors
0
0 comments X

The pith

Signed random combinatorial matrices with half-zero rows have smallest singular value at least order n^{-1/2} except with probability Cε + e^{-cn}.

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

The paper proves a bound showing that the smallest singular value of these n by n matrices is unlikely to be very small. Each row is chosen independently and uniformly from all vectors with entries in {-1, 0, 1} that have exactly n/2 zeros. The probability that this smallest singular value falls below ε times n to the power -1/2 is at most Cε plus a term that decays exponentially in n. As a direct consequence, the chance that the matrix has a zero singular value, making it singular, is exponentially small in n. The argument adapts an existing anti-concentration tool called the combinatorial least common denominator to the setting where each row has a fixed number of zeros.

Core claim

Let M_n be an n×n signed random combinatorial matrix whose rows are independent and uniformly distributed over the set of {-1,0,1}-vectors with exactly n/2 zero coordinates. We prove that there exist constants C,c > 0 such that for any ε≥0, P(s_n(M_n) ≤ ε n^{-1/2}) ≤ Cε + e^{-cn}. In particular, the probability that M_n is singular is exponentially small. Our approach builds on the Combinatorial Least Common Denominator (CLCD) introduced by Tran and develops the method in the present constrained setting.

What carries the argument

The Combinatorial Least Common Denominator (CLCD), which is extended here to control anti-concentration of linear forms when the rows are restricted to vectors with a fixed number of zero entries.

If this is right

  • The matrix M_n is singular with probability at most e^{-c n}.
  • The row-wise combinatorial constraints do not destroy the anti-concentration properties needed for the singularity bound.
  • The CLCD method continues to work after the adaptation to fixed-support rows.
  • The smallest singular value is of order at least n^{-1/2} except on a set of probability O(ε) + exponentially small.

Where Pith is reading between the lines

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

  • The same CLCD adaptation might yield analogous bounds when the number of zeros per row is any fixed fraction of n instead of exactly n/2.
  • Numerical experiments on moderate n could estimate the constants C and c by plotting the empirical distribution of the smallest singular value.
  • The result suggests that other models with linear constraints on each row may still enjoy exponentially small singularity probability.

Load-bearing premise

The rows of M_n are independent and each is uniformly distributed over the set of {-1,0,1}-vectors with exactly n/2 zero coordinates.

What would settle it

For large n, sample many independent copies of M_n and count how often s_n(M_n) is smaller than 0.01 n^{-1/2}; if this frequency stays bounded away from zero instead of being at most roughly 0.01 C plus e^{-c n}, the bound fails.

read the original abstract

Let $M_n$ be an $n\times n$ signed random combinatorial matrix whose rows are independent and uniformly distributed over the set of $\{-1,0,1\}$-vectors with exactly $n/2$ zero coordinates. Despite the dependence induced by the row constraints, we prove that there exist constants $C,c > 0$ such that for any $\varepsilon\ge0$, \begin{align*} \textbf{P}\left(s_{n}(M_n)\le {\varepsilon}{n^{-1/2}}\right)\le C\varepsilon+e^{-cn}. \end{align*} In particular, the probability that $M_n$ is singular is exponentially small. Our approach builds on the Combinatorial Least Common Denominator (CLCD) introduced by Tran and develops the method in the present constrained setting.

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 / 0 minor

Summary. The paper proves that for the n×n signed random combinatorial matrix M_n with independent rows each uniformly chosen from the set of vectors in {-1,0,1}^n with exactly n/2 zeros, there exist constants C, c > 0 such that for any ε ≥ 0, P(s_n(M_n) ≤ ε n^{-1/2}) ≤ Cε + exp(-c n). This implies that the probability that M_n is singular is exponentially small in n. The proof adapts the Combinatorial Least Common Denominator (CLCD) method introduced by Tran to this setting with intra-row dependencies.

Significance. This result is significant in random matrix theory as it demonstrates that the combinatorial constraint of a fixed number of zeros per row does not prevent the matrix from being well-invertible with high probability. The exponential smallness of the singularity probability is a robust conclusion. The development of CLCD for this dependent case is a methodological advance that could apply to other constrained random models. The bound is parameter-free in the sense that C and c are absolute constants.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, recognition of the significance of the result, and recommendation for minor revision. No specific major comments were listed in the report, so we have no points to address point-by-point. We will make the minor revisions requested by the editor or any additional suggestions that arise during the process.

Circularity Check

0 steps flagged

No circularity; proof adapts external CLCD to constrained model without reduction to inputs

full rationale

The derivation claims a small-ball probability bound for the smallest singular value by extending Tran's CLCD anti-concentration to rows uniform on the exact n/2-zero support. No equation reduces the target inequality to a fitted parameter, self-definition, or self-citation chain; the linear term Cε arises from the combinatorial discrepancy control developed in the paper rather than being presupposed. The cited CLCD is external (Tran), and the adaptation is presented as a technical extension rather than a renaming or tautology. The result is therefore self-contained against the external benchmark.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the probabilistic model definition and standard tools of probability theory; no free parameters or new entities are introduced.

axioms (1)
  • domain assumption Rows are independent and uniformly distributed over {-1,0,1}^n vectors with exactly n/2 zeros.
    This is the explicit definition of the random matrix M_n in the abstract.

pith-pipeline@v0.9.0 · 5422 in / 1298 out tokens · 52575 ms · 2026-05-10T15:56:04.689339+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

20 extracted references · 20 canonical work pages

  1. [1]

    Campos, M. et al. The singularity probability of a random symmetric matrix is exponentially small. J. Amer. Math. Soc.38(1) (2025), 179–224.doi:10.1090/jams/1042

    work page doi:10.1090/jams/1042 2025

  2. [2]

    On the singularity of adjacency matrices for random regular digraphs.Probab

    Cook, N.A. On the singularity of adjacency matrices for random regular digraphs.Probab. Theory Related Fields167(1-2) (2017), 143–200.doi:10.1007/s00440-015-0679-8

    work page doi:10.1007/s00440-015-0679-8 2017

  3. [3]

    Eigenvalues and Condition Numbers of Random Matrices.SIAM Journal on Matrix Analysis and Applications9(4) (1988), 543–560.doi:10.1137/0609045

    Edelman, A. Eigenvalues and Condition Numbers of Random Matrices.SIAM Journal on Matrix Analysis and Applications9(4) (1988), 543–560.doi:10.1137/0609045

    work page doi:10.1137/0609045 1988

  4. [4]

    Permutation, parametric and bootstrap tests of hypotheses

    Good, P. Permutation, parametric and bootstrap tests of hypotheses. Third. Springer Series in Statis- tics. Springer-Verlag, New York, 2005, xx+315.isbn: 0-387-20279-X

    work page 2005

  5. [5]

    Estimates for the concentration function of combinatorial number theory and probability

    Hal´ asz, G. Estimates for the concentration function of combinatorial number theory and probability. Period. Math. Hungar.8(3-4) (1977), 197–211.doi:10.1007/BF02018403

    work page doi:10.1007/bf02018403 1977

  6. [6]

    Singularity of discrete random matrices.Geom

    Jain, V., Sah, A., and Sawhney, M. Singularity of discrete random matrices.Geom. Funct. Anal.31(5) (2021), 1160–1218.doi:10.1007/s00039-021-00580-6

    work page doi:10.1007/s00039-021-00580-6 2021

  7. [7]

    The smallest singular value of dense random regular digraphs.Int

    Jain, V., Sah, A., and Sawhney, M. The smallest singular value of dense random regular digraphs.Int. Math. Res. Not. IMRN(24) (2022), 19300–19334.doi:10.1093/imrn/rnab247

    work page doi:10.1093/imrn/rnab247 2022

  8. [8]

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

    Li, D., Litvak, A.E., and Yu, T. An upper bound on the smallest singular value of dense random combinatorial matrices.J. Complexity95(2026), Paper No. 102031.doi:10 . 1016 / j . jco . 2026 . 102031

    work page 2026

  9. [9]

    Litvak, A.E. et al. Smallest singular value of random matrices and geometry of random polytopes.Adv. Math.195(2) (2005), 491–523.doi:10.1016/j.aim.2004.08.004

    work page doi:10.1016/j.aim.2004.08.004 2005

  10. [10]

    The smallest singular value of heavy-tailed not necessarily i.i.d

    Livshyts, G.V. The smallest singular value of heavy-tailed not necessarily i.i.d. random matrices via random rounding.J. Anal. Math.145(1) (2021), 257–306.doi:10.1007/s11854-021-0183-2. 25

    work page doi:10.1007/s11854-021-0183-2 2021

  11. [11]

    and Schechtman, G

    Milman, V.D. and Schechtman, G. Asymptotic theory of finite dimensional normed spaces. Springer, 1986

    work page 1986

  12. [12]

    Neumann, J. von. Collected works. Vol. V: Design of computers, theory of automata and numerical analysis. General editor: A. H. Taub. The Macmillan Company, New York, 1963, ix+784 pp. (1 plate)

    work page 1963

  13. [13]

    Linear and Multilinear Algebra0(0), 1–11 (2024)

    Roos, B. New inequalities for permanents and hafnians and some generalizations.Linear Multilinear Algebra73(8) (2025), 1634–1667.doi:10.1080/03081087.2024.2436061

    work page doi:10.1080/03081087.2024.2436061 2025

  14. [14]

    Invertibility of random matrices: norm of the inverse.Ann

    Rudelson, M. Invertibility of random matrices: norm of the inverse.Ann. of Math. (2)168(2) (2008), 575–600.doi:10.4007/annals.2008.168.575

    work page doi:10.4007/annals.2008.168.575 2008

  15. [15]

    and Vershynin, R

    Rudelson, M. and Vershynin, R. The Littlewood-Offord problem and invertibility of random matrices. Adv. Math.218(2) (2008), 600–633.doi:10.1016/j.aim.2008.01.010

    work page doi:10.1016/j.aim.2008.01.010 2008

  16. [16]

    and Vu, V.H

    Tao, T. and Vu, V.H. Inverse Littlewood-Offord theorems and the condition number of random discrete matrices.Ann. of Math. (2)169(2) (2009), 595–632.doi:10.4007/annals.2009.169.595

    work page doi:10.4007/annals.2009.169.595 2009

  17. [17]

    Singularity of random Bernoulli matrices.Ann

    Tikhomirov, K. Singularity of random Bernoulli matrices.Ann. of Math. (2)191(2) (2020), 593–634. doi:10.4007/annals.2020.191.2.6

    work page doi:10.4007/annals.2020.191.2.6 2020

  18. [18]

    The smallest singular value of random combinatorial matrices

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

    work page 2020

  19. [19]

    High-dimensional probability

    Vershynin, R. High-dimensional probability. Vol. 47. Cambridge Series in Statistical and Probabilistic Mathematics. An introduction with applications in data science, With a foreword by Sara van de Geer. Cambridge University Press, Cambridge, 2018, xiv+284.isbn: 978-1-108-41519-4.doi:10.1017/ 9781108231596

    work page 2018

  20. [20]

    On the limit of the largest eigenvalue of the large-dimensional sample covariance matrix.Probab

    Yin, Y.Q., Bai, Z.D., and Krishnaiah, P.R. On the limit of the largest eigenvalue of the large-dimensional sample covariance matrix.Probab. Theory Related Fields78(4) (1988), 509–521.doi:10 . 1007 / BF00353874. 26

    work page 1988