pith. sign in

arxiv: 2604.10446 · v1 · submitted 2026-04-12 · 🧮 math.PR

The circular law for sparse random combinatorial matrices

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

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

classification 🧮 math.PR
keywords circular lawsparse random matricesempirical spectral distributionsingular value boundscombinatorial matrices0-1 matricesrandom matrices with fixed row sums
0
0 comments X

The pith

The empirical spectral distribution of rescaled sparse random 0-1 matrices with exactly d ones per row converges in probability to the circular law when d=o(n).

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

The paper proves that an n by n random matrix with each row independently chosen as a uniform random vector with exactly d ones has its eigenvalues, after appropriate rescaling, distributed according to the circular law in the limit as n grows, provided d=o(n) and d is at least polylogarithmic in n. This means the eigenvalues fill a disk in the complex plane uniformly at random. The result requires new bounds showing that the smallest singular value of the matrix shifted by z times the identity stays bounded away from zero for z inside a disk of radius roughly sqrt(d) times log log d. If this holds, it means the circular law applies even under the combinatorial constraint of fixed row sums and in the sparse regime.

Core claim

We show that the empirical spectral distribution of the appropriately rescaled matrix M_n converges in probability to the circular law provided that d=o(n). As a crucial element of the proof, we obtain quantitative lower bounds on the smallest singular value of the shifted matrices M_n - z I_n whenever |z| ≤ sqrt(d) log log d and C log n ≤ d ≤ n/2 for some absolute positive constant C.

What carries the argument

Quantitative lower bounds on the smallest singular value of the shifted matrices M_n - z I_n for |z| up to sqrt(d) log log d.

If this is right

  • The circular law holds with high probability for these matrices across the stated range of d.
  • The smallest singular values of shifted versions remain controlled inside a slowly growing disk.
  • Convergence in probability of the empirical measure to the circular law follows from the singular value bounds.
  • The result applies specifically to the uniform sampling over fixed-weight vectors.

Where Pith is reading between the lines

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

  • The circular law may extend to even smaller d if improved singular value estimates are found.
  • Similar techniques could apply to adjacency matrices of random d-regular graphs by symmetrization.
  • Numerical checks for moderate n and varying d could measure the rate at which the distribution approaches the circle.

Load-bearing premise

Each row must be sampled independently and uniformly from all vectors with exactly d ones, with d at least on the order of log squared n.

What would settle it

A computation or construction for some sequence of d = o(n) with d at least polylog n where the smallest singular value of M_n - z I_n falls below the claimed threshold for some |z| near sqrt(d), causing the empirical spectral distribution to deviate from the circular law.

Figures

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

Figure 1
Figure 1. Figure 1: Empirical spectra of four independently generated 5000 × 5000 random com￾binatorial matrices where each row has exactly d ∈ {2, 5, 8, 72} ones. In each panel, the plotted points are the eigenvalues of the normalized matrix Mn = Mn/ p d(1 − d/n). The red dashed circle is the unit circle {z ∈ C : |z| = 1}. For d = 2, the empirical spectral dis￾tribution is visibly inconsistent with the circular law. However,… view at source ↗
Figure 2
Figure 2. Figure 2: An illustration of the classification of steep vectors into the sets T1, T2, and T3. The vertical axis represents the magnitude of the sorted components (x ∗ k ) and the horizontal axis represents the component index k. The picture is drawn for the regime ℓ0 < n1, so that T10 is represented by the jump condition x ∗ 1 > 6d x∗ ℓ0 . A vector is classified based on the location and the size of the first jump.… view at source ↗
read the original abstract

Let $\log^{2+\varepsilon} n \le d \le n/2$ for some fixed $\varepsilon \in (0,1)$, and let $M_n$ 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. We show that the empirical spectral distribution of the appropriately rescaled matrix $M_n$ converges in probability to the circular law provided that $d=o(n)$. As a crucial element of the proof, we obtain quantitative lower bounds on the smallest singular value of the shifted matrices $M_n-zI_n$ whenever $|z|\le \sqrt d \log\log d$ and $C\log n \le d \le n/2$ for some absolute positive constant $C$.

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 paper claims that the empirical spectral distribution of the rescaled n×n random matrix M_n, with each row independently and uniformly selected from the set of 0-1 vectors with exactly d ones, converges in probability to the circular law when log^{2+ε} n ≤ d ≤ n/2 and d = o(n). A key part of the proof is the derivation of quantitative lower bounds for the smallest singular value of M_n − zI_n for |z| ≤ √d log log d under a slightly weaker lower bound on d.

Significance. This is a significant result in random matrix theory, extending the circular law to sparse matrices with a strict combinatorial constraint on the number of non-zero entries per row. Such models arise in the study of random regular graphs and combinatorial designs. The explicit singular value bounds provided are a strength, as they can be of independent interest. The proof builds on existing techniques without introducing circularity or ad-hoc parameters.

minor comments (2)
  1. [Abstract] The phrase 'appropriately rescaled' in the abstract should be replaced with the explicit scaling factor (likely M_n / sqrt(d) or equivalent) to make the main theorem statement self-contained.
  2. [Introduction] The introduction would benefit from a short paragraph comparing the result to prior circular-law theorems for sparse matrices (e.g., those relying on i.i.d. Bernoulli entries or different sparsity regimes) to clarify the novelty of the combinatorial row-sampling model.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, accurate summary of the main result, and recommendation of minor revision. The significance noted regarding extensions to sparse combinatorial matrices and independent interest of the singular value bounds is appreciated. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper establishes the circular law convergence for the rescaled sparse combinatorial matrix M_n via a direct proof that obtains quantitative lower bounds on σ_min(M_n - z I_n) for |z| ≤ √d log log d under the stated range on d. This step uses the row-independence and exact-d-ones sampling model to derive concentration and invertibility bounds, which are then fed into standard circular-law machinery (e.g., logarithmic potential or Girko-type arguments). No equation or claim reduces by construction to a fitted parameter, self-definition, or prior result by the same authors; the derivation remains self-contained against external benchmarks and does not invoke load-bearing self-citations whose validity depends on the present work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard tools from probability theory, linear algebra, and random matrix theory for handling empirical spectral distributions and singular values; no free parameters are fitted, no new entities postulated.

axioms (1)
  • standard math Standard results on convergence of empirical spectral distributions for non-Hermitian matrices and lower bounds on smallest singular values
    Invoked to establish the circular law and the key invertibility estimates for M_n - z I_n.

pith-pipeline@v0.9.0 · 5446 in / 1260 out tokens · 33085 ms · 2026-05-10T16:30:14.411471+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

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

    math.PR 2026-04 unverdicted novelty 6.0

    Dense random combinatorial matrices have smallest singular value typically of order n^{-1/2}.

Reference graph

Works this paper leans on

57 extracted references · 57 canonical work pages · cited by 1 Pith paper

  1. [1]

    Adamczak and D

    R. Adamczak and D. Chafa¨ ı. Circular law for random matrices with unconditional log- concave distribution.Commun. Contemp. Math., 17(4):1550020, 22, 2015

    work page 2015

  2. [2]

    Adamczak, D

    R. Adamczak, D. Chafa¨ ı, and P. Wolff. Circular law for random matrices with exchangeable entries.Random Structures & Algorithms, 48(3):454–479, 2016

    work page 2016

  3. [3]

    Adhikari and A

    A. Adhikari and A. Dembo. Spectral measure for uniformd-regular digraphs. arXiv:2310.14132, 2023

    work page arXiv 2023

  4. [4]

    Aigner-Horev and Y

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

    work page 2022

  5. [5]

    G. W. Anderson, A. Guionnet, and O. Zeitouni.An introduction to random matrices, volume 118 ofCambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2010

    work page 2010

  6. [6]

    Bai and J

    Z. Bai and J. W. Silverstein.Spectral analysis of large dimensional random matrices. Springer Series in Statistics. Springer, New York, second edition, 2010

    work page 2010

  7. [7]

    Z. D. Bai. Circular law.Ann. Probab., 25(1):494–529, 1997

    work page 1997

  8. [8]

    Basak and M

    A. Basak and M. Rudelson. The circular law for sparse non-Hermitian matrices.Ann. Probab., 47(4):2359–2416, 2019

    work page 2019

  9. [9]

    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

  10. [10]

    Bauerschmidt, J

    R. Bauerschmidt, J. Huang, and H.-T. Yau. Local Kesten-McKay law for random regular graphs.Comm. Math. Phys., 369(2):523–636, 2019

    work page 2019

  11. [11]

    A. Beker. Limiting spectral laws for sparse random circulant matrices.arXiv:2504.13833, 2025

    work page arXiv 2025

  12. [12]

    Bordenave, P

    C. Bordenave, P. Caputo, and D. Chafa¨ ı. Spectrum of Markov generators on sparse random graphs.Comm. Pure Appl. Math., 67(4):621–669, 2014

    work page 2014

  13. [13]

    Bordenave and D

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

    work page 2012

  14. [14]

    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

  15. [15]

    N. Cook. The circular law for random regular digraphs.Ann. Inst. Henri Poincar´ e Probab. Stat., 55(4):2111–2167, 2019

    work page 2019

  16. [16]

    N. Cook, L. Goldstein, and T. Johnson. Size biased couplings and the spectral gap for random regular graphs.Ann. Probab., 46(1):72–125, 2018

    work page 2018

  17. [17]

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

    work page 2017

  18. [18]

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

    work page 2009

  19. [19]

    A. Edelman. Eigenvalues and condition numbers of random matrices.SIAM J. Matrix Anal. Appl., 9(4):543–560, 1988

    work page 1988

  20. [20]

    C.-G. Esseen. On the concentration function of a sum of independent random variables. Zeitschrift f¨ ur Wahrscheinlichkeitstheorie und Verwandte Gebiete, 9(4):290–308, 1968

    work page 1968

  21. [21]

    Ferber, V

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

    work page 2021

  22. [22]

    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

  23. [23]

    Friedman, J

    J. Friedman, J. Kahn, and E. Szemeredi. On the second eigenvalue of random regular graphs. InProceedings of the twenty-first annual ACM symposium on Theory of computing, pages 587–598, 1989

    work page 1989

  24. [24]

    V. L. Girko. The circular law.Teor. Veroyatnost. i Primenen., 29(4):669–679, 1984

    work page 1984

  25. [25]

    G¨ otze and A

    F. G¨ otze and A. Tikhomirov. The circular law for random matrices.Ann. Probab., 38(4):1444–1491, 2010

    work page 2010

  26. [26]

    H. Huang. Rank of sparse Bernoulli matrices.Pure Appl. Funct. Anal., 10(6):1365–1441, 2025

    work page 2025

  27. [27]

    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

  28. [28]

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

    work page arXiv 2010

  29. [29]

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

    work page 2021

  30. [30]

    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

    work page 2022

  31. [31]

    Joag-Dev and F

    K. Joag-Dev and F. Proschan. Negative association of random variables with applications. The Annals of Statistics, pages 286–295, 1983

    work page 1983

  32. [32]

    H. Kesten. Symmetric random walks on groups.Trans. Amer. Math. Soc., 92:336–354, 1959

    work page 1959

  33. [33]

    D. Li, A. E. Litvak, and T. Yu. An upper bound on the smallest singular value of dense random combinatorial matrices.Journal of Complexity, 95:102031, 2026

    work page 2026

  34. [34]

    Litvak, A

    A. Litvak, A. Lytova, K. Tikhomirov, N. Tomczak-Jaegermann, and P. Youssef. Structure of eigenvectors of random regular digraphs.Transactions of the American Mathematical Society, 371(11):8097–8172, 2019

    work page 2019

  35. [35]

    Litvak, A

    A. Litvak, A. Pajor, M. Rudelson, N. Tomczak-Jaegermann, and R. Vershynin. Random Euclidean embeddings in spaces of bounded volume ratio.C. R. Math. Acad. Sci. Paris, 339(1):33–38, 2004

    work page 2004

  36. [36]

    A. E. Litvak, A. Lytova, K. Tikhomirov, N. Tomczak-Jaegermann, and P. Youssef. Adja- cency matrices of random digraphs: singularity and anti-concentration.Journal of Mathe- matical Analysis and Applications, 445(2):1447–1491, 2017

    work page 2017

  37. [37]

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

    work page 2019

  38. [38]

    A. E. Litvak, A. Lytova, K. Tikhomirov, N. Tomczak-Jaegermann, and P. Youssef. Circular law for sparse random regular digraphs.J. Eur. Math. Soc. (JEMS), 23(2):467–501, 2021

    work page 2021

  39. [39]

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

    work page 2005

  40. [40]

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

    work page 2022

  41. [41]

    B. D. McKay. The expected eigenvalue distribution of a large regular graph.Linear Algebra Appl., 40:203–216, 1981

    work page 1981

  42. [42]

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

    work page 2013

  43. [43]

    H. H. Nguyen. Random doubly stochastic matrices: the circular law.Ann. Probab., 42(3):1161–1196, 2014

    work page 2014

  44. [44]

    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

  45. [45]

    Pan and W

    G. Pan and W. Zhou. Circular law, extreme singular values and potential theory.J. Multivariate Anal., 101(3):645–656, 2010

    work page 2010

  46. [46]

    Pastur and M

    L. Pastur and M. Shcherbina.Eigenvalue distribution of large random matrices, volume 171 ofMathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2011

    work page 2011

  47. [47]

    Rudelson and K

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

    work page 2019

  48. [48]

    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

    work page 2008

  49. [49]

    A. Sah, J. Sahasrabudhe, and M. Sawhney. The limiting spectral law for sparse iid matrices. arXiv preprint arXiv:2310.17635, Forum of Math Pi, to appear, 2023

    work page arXiv 2023

  50. [50]

    A. Sah, J. Sahasrabudhe, and M. Sawhney. The sparse circular law, revisited.Bull. Lond. Math. Soc., 57(2):330–358, 2025

    work page 2025

  51. [51]

    Tao.Topics in random matrix theory, volume 132

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

    work page 2012

  52. [52]

    Tao and V

    T. Tao and V. Vu. Random matrices: the circular law.Commun. Contemp. Math., 10(2):261–307, 2008

    work page 2008

  53. [53]

    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

  54. [54]

    Tikhomirov

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

    work page 2020

  55. [55]

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

    work page arXiv 2007

  56. [56]

    P. M. Wood. Universality and the circular law for sparse random matrices.Ann. Appl. Probab., 22(3):1266–1300, 2012

    work page 2012

  57. [57]

    Y. Zhu. On the second eigenvalue of random bipartite biregular graphs.Journal of Theo- retical Probability, 36(2):1269–1303, 2023. Dongbin Li Email address:dongbinli@snnu.edu.cn School of Mathematics and Statistics, Shaanxi Normal University, Xi’an, 710119, China. Alexander E. Litvak Email address:alitvak@ualberta.ca Dept. of Math. and Stat. Sciences, Uni...

    work page 2023