pith. sign in

arxiv: 2503.08139 · v4 · submitted 2025-03-11 · 🧮 math.PR

The eigenvalue gap of inhomogeneous symmetric discrete random matrix

Zeyan Song , Hanchao Wang This is my paper

Pith reviewed 2026-05-23 01:04 UTC · model grok-4.3

classification 🧮 math.PR
keywords eigenvalue gapsrandom matricessubgaussian entriesinhomogeneous matricessingular valueseigenvector delocalizationprobability boundssymmetric matrices
0
0 comments X

The pith

For inhomogeneous symmetric subgaussian random matrices, the probability that k consecutive eigenvalues differ by at most ε n^{-1/2} is at most (C ε)^{(k^2 + k)/2} plus an exponentially small term, when k ≤ n / log n.

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

The paper proves a quantitative upper bound on the probability of unusually small gaps among any k+1 consecutive eigenvalues of a symmetric random matrix whose upper-triangular entries are independent and subgaussian, though the subgaussian parameters may differ across entries. The bound takes the form of a power of ε whose exponent grows quadratically with k, plus a term that decays exponentially in n. The same distance-based approach yields a comparable tail bound on small singular values for a wider range of k and a quantitative estimate on the chance that an eigenvector fails to exhibit gap delocalization. A reader would care because these controls on spectral spacing and eigenvector behavior apply directly to models in which the entries are not required to share the same distribution.

Core claim

The central claim is that if A is an n × n symmetric random matrix whose upper-triangular entries are independent and subgaussian (possibly with distinct parameters), then for every k ≤ n / log n, every 1 ≤ i ≤ n − k, and every ε ≥ 0, the probability that λ_{i+k} − λ_i ≤ ε n^{-1/2} is at most (C ε)^{(k^2 + k)/2} + exp(−c n), where the eigenvalues are ordered increasingly. Combining this gap estimate with an earlier result of Yi Han produces a tail bound on the (n − k + 1)-th smallest singular value for c log n ≤ k ≤ √n. The distance framework developed to prove the eigenvalue gap also supplies a quantitative bound on the probability that some eigenvector of A exhibits no-gap delocalization,,

What carries the argument

distance analytical framework that converts tail bounds and decoupling arguments into control on the distance from an eigenvalue to the span of the remaining eigenvectors

If this is right

  • The same distance framework produces a tail bound on the (n − k + 1)-th smallest singular value of the form (C ε)^{c k^2} + exp(−c k n) when c log n ≤ k ≤ √n.
  • A quantitative upper bound follows for the probability that an eigenvector exhibits no-gap delocalization.
  • All stated probability bounds remain valid when the subgaussian parameters of the entries are allowed to vary arbitrarily.
  • The eigenvalue-gap result directly implies control on the stability of the spectrum under small perturbations of the matrix entries.

Where Pith is reading between the lines

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

  • The bounds could be used to study the spectrum of adjacency matrices of inhomogeneous random graphs whose edge probabilities produce subgaussian entries of differing scales.
  • The delocalization estimate may combine with existing rigidity results to give almost-sure statements on eigenvector behavior once the probability is summed over a net of ε values.
  • Numerical sampling of matrices with deliberately varying subgaussian norms could test whether the exponent (k^2 + k)/2 is sharp.

Load-bearing premise

The upper-triangular entries are independent and each is subgaussian, possibly with different parameters.

What would settle it

Construct or simulate an n × n inhomogeneous symmetric subgaussian matrix for moderate n and k ≈ n / log n such that the empirical frequency of gaps smaller than ε n^{-1/2} exceeds (C ε)^{(k^2 + k)/2} by more than a constant factor for a sequence of ε that tends to zero.

read the original abstract

Let A be an n x n symmetric random matrix whose upper-triangular entries are independent and follow possibly non-identical subgaussian distributions. This paper investigates the spectral properties of A, including its eigenvalues and eigenvectors. Firstly, we prove that for k <= n / log n, 1 <= i <= n - k and epsilon >= 0, P(the gap between the (i+k)-th and i-th eigenvalues is at most epsilon n^(-1/2)) <= (C epsilon)^((k^2 + k)/2) + exp(-c n), where the eigenvalues are ordered increasingly. Secondly, combining the recent result of Yi Han, we give a quantitative estimate of the singular values of A. For c log n <= k <= sqrt(n) and epsilon >= 0, we have P(the (n-k+1)-th smallest singular value of A is at most k epsilon n^(-1/2)) <= (C epsilon)^(c k^2) + exp(-c k n), where the singular values are ordered increasingly. Finally, based on the distance analytical framework developed for the eigenvalue gap, we further derive quantitative bounds for singular values and delocalization of eigenvectors. In particular, we establish a quantitative bound for the probability that some eigenvector of A exhibits no-gap delocalization, which improves the result of Rudelson and Vershynin.

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

2 major / 2 minor

Summary. The manuscript proves a small-gap probability bound for the eigenvalues of an n×n inhomogeneous symmetric sub-Gaussian random matrix A: for k ≤ n/log n, 1 ≤ i ≤ n−k and ε ≥ 0, P(λ_{i+k} − λ_i ≤ ε n^{-1/2}) ≤ (C ε)^{(k^2 + k)/2} + exp(−c n). It also derives quantitative bounds on the (n−k+1)th smallest singular value for c log n ≤ k ≤ √n by combining with a result of Yi Han, and obtains quantitative delocalization estimates for eigenvectors that improve on Rudelson–Vershynin.

Significance. If the proofs hold with constants uniform in the (possibly distinct) sub-Gaussian parameters, the eigenvalue-gap bound extends classical spacing results to the inhomogeneous setting, which is relevant for non-i.i.d. models arising in statistics. The exponent (k^2 + k)/2 matches the dimension of the space of symmetric k×k matrices, and the additive exp(−c n) term is standard. The delocalization improvement is a concrete technical advance.

major comments (2)
  1. [Abstract and §1] Abstract and opening definition of A: the constants C and c are not stated to be independent of the individual sub-Gaussian norms; because the modeling premise explicitly allows non-identical parameters, the proof must track whether the tail and decoupling constants remain uniform (or at worst depend only on a global bound on the ψ2-norms).
  2. [Singular-value section (after the eigenvalue-gap theorem)] The singular-value statement (c log n ≤ k ≤ √n): the reduction to Yi Han’s result must be checked for compatibility with the inhomogeneous sub-Gaussian assumption; if Yi Han’s theorem requires identical distributions or a uniform bound stronger than the paper’s premise, the claimed range and probability bound may not follow directly.
minor comments (2)
  1. [Notation and statements of theorems] The phrase “ordered increasingly” for eigenvalues and singular values should appear once in the introduction and be used consistently thereafter.
  2. [References] The reference to Yi Han’s result should include an arXiv number or full bibliographic details.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment. We address the two major comments below and will make the indicated clarifications in the revised manuscript.

read point-by-point responses

  1. Referee: [Abstract and §1] Abstract and opening definition of A: the constants C and c are not stated to be independent of the individual sub-Gaussian norms; because the modeling premise explicitly allows non-identical parameters, the proof must track whether the tail and decoupling constants remain uniform (or at worst depend only on a global bound on the ψ2-norms).

    Authors: We agree that explicit uniformity must be stated. In all proofs the constants C and c depend only on a global upper bound K on the sub-Gaussian ψ₂-norms of the entries (i.e., ||A_{ij}||_ψ₂ ≤ K for every i,j). The sub-Gaussian tail estimates, moment comparisons, and decoupling arguments are applied uniformly under this single K; no individual-norm dependence appears. We will add this dependence explicitly to the abstract, the definition of A in §1, and the statements of the main theorems. revision: yes

  2. Referee: [Singular-value section (after the eigenvalue-gap theorem)] The singular-value statement (c log n ≤ k ≤ √n): the reduction to Yi Han’s result must be checked for compatibility with the inhomogeneous sub-Gaussian assumption; if Yi Han’s theorem requires identical distributions or a uniform bound stronger than the paper’s premise, the claimed range and probability bound may not follow directly.

    Authors: Yi Han’s theorem applies to symmetric matrices whose upper-triangular entries are independent and sub-Gaussian with a uniform bound on the ψ₂-norms; this is exactly the setting of the present paper. Our eigenvalue-gap bound is likewise uniform under the same global K, so the combination yields the stated probability bound without additional restrictions. We will insert a short paragraph in the singular-value section confirming that the hypotheses of Yi Han’s result are satisfied under our inhomogeneous sub-Gaussian assumption. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper states its modeling premise (independent sub-Gaussian upper-triangular entries) at the outset and derives the eigenvalue-gap probability bound directly from tail inequalities and a geometric distance argument whose dimension matches the standard volume of symmetric k-by-k matrices. The singular-value extension invokes an external result of Yi Han and applies the same distance framework sequentially within the paper; neither step reduces a claimed prediction to a fitted parameter or to a self-citation whose content is itself unverified. The delocalization bound likewise follows from the distance framework without re-importing the target statement. No self-definitional, fitted-input, or uniqueness-via-self-citation pattern appears.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The results rest on the standard subgaussian tail property and independence; no free parameters are fitted to data and no new entities are postulated.

axioms (2)
  • domain assumption Upper-triangular entries are independent and each subgaussian (possibly with different parameters)
    This is the model definition of matrix A used to obtain all tail bounds.
  • standard math Standard subgaussian concentration and decoupling inequalities apply
    Invoked to control distances between eigenvalues in the distance framework.

pith-pipeline@v0.9.0 · 5779 in / 1405 out tokens · 72940 ms · 2026-05-23T01:04:53.113634+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

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

  1. [1]

    and Wood, P

    Bourgain, J., Vu, V. and Wood, P. (2010). On the singularity probability of discrete random matricesJ. Funct. Anal.258559–603

    work page 2010

  2. [2]

    and Sahasrabudhe, J

    Campos, M., Jenssen, M., Michelen, M. and Sahasrabudhe, J. (2025). The singularity proba- bility of a random symmetric matrix is exponentially small.J. Amer. Math. Soc.38179–224

    work page 2025

  3. [3]

    and Sahasrabudhe, J

    Campos, M., Jenssen, M., Michelen, M. and Sahasrabudhe, J. (2024). The least singular value of a random symmetric matrix.Forum Math. Pi.121–69

    work page 2024

  4. [4]

    and Wang, J

    Christoffersen, N., Luh, K., Nguyen, H. and Wang, J. (2024). Eigenvalue gaps of the Laplacian of random graphs.arXiv preprint:2501.00234

    work page arXiv 2024

  5. [5]

    and Shearer, C

    Christoffersen, N., Luh, K., O’Rourke, S. and Shearer, C. (2025). Gaps between Singular Values of Sample Covariance Matrices.arXiv preprint:2502.15002

    work page arXiv 2025

  6. [6]

    P., Tao, T

    Costello, K. P., Tao, T. and Vu, V. (2006). Random symmetric matrices are almost surely nonsingular.Duke Math. J.135395–413

    work page 2006

  7. [7]

    Dabagia, M., Fernandez, M. (2024). The smallest singular value of inhomogenous random rectangular matricesarXiv preprint:2408.14389

    work page arXiv 2024

  8. [8]

    and Wang, H

    Dai, G., Song, Z. and Wang, H. (2024) The Rank and Singular Values of the Inhomogeneous Subgaussian Random MatricesarXiv preprint:2412.18906

    work page arXiv 2024

  9. [9]

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

    work page 1988

  10. [10]

    (1945) On a lemma of Littlewood and OffordBull

    Erd˝ os, P. (1945) On a lemma of Littlewood and OffordBull. Amer. Math. Soc.51898–902

    work page 1945

  11. [11]

    and Yau, H

    Erd˝ os, L., Schlein, B. and Yau, H. (2010). Wegner estimate and level repulsion for wigner random matrices.Int. Math. Res. Not.2010436–479

    work page 2010

  12. [12]

    Hal´ asz G. (1975). On the distribution of additive arithmetic functions.Acta Arithmetica27 143–152

    work page 1975

  13. [13]

    (1977) Estimates for the concentration function of combinatorial number theory and probability.Period

    Hal´ asz G. (1977) Estimates for the concentration function of combinatorial number theory and probability.Period. Math. Hungar.8197–211

    work page 1977

  14. [14]

    Han, Y. (2025). Simplicity of singular value spectrum of random matrices and two-point quantitative invertibility.arXiv preprint:2502.13819

    work page arXiv 2025

  15. [15]

    Han, Y. (2025). Repeated singular values of a random symmetric matrix and decoupled singular value estimates.arXiv preprint:2504.15992

    work page arXiv 2025

  16. [16]

    Han, Y. (2025). On the rank of a random symmetric matrix in the large deviation regime. arXiv preprint:2506.01155

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  17. [17]

    Huang, H. (2020). Rank of sparse Bernoulli matrices.arXiv preprint:2009.13726

    work page arXiv 2020

  18. [18]

    and Zhu, Y

    Hu, Y., Wang, K. and Zhu, Y. (2024). Sparse Hanson-Wright Inequalities with Applications. Preprint arXiv:2410.15652

    work page arXiv 2024

  19. [19]

    Fernandez, M. (2024). A distance theorem for inhomogenous random rectangular matrices Perprint arXiv:2408.06309

    work page arXiv 2024

  20. [20]

    and Sawhney, M

    Jain, V., Sah, A. and Sawhney, M. (2022). Rank deficiency of random matrices.Electron. Commun. Probab.271–9

    work page 2022

  21. [21]

    and Szemer´ edi, E

    Kahn, J., Koml´ os, J. and Szemer´ edi, E. (1995). On the probability that a random±1-matrix is singular.J. Amer. Math. Soc.8223–240

    work page 1995

  22. [22]

    Livshyts, G. V. (2021). The smallest singular value of heavy-tailed not necessarily i.i.d. ran- dom matrices via random rounding.J. Anal. Math.145257–306. 30Z. SONG AND H. WANG

    work page 2021

  23. [23]

    V., Tikhomirov, K

    Livshyts, G. V., Tikhomirov, K. and Vershinin, R. (2021). The smallest singular value of inhomogeneous square random matrices.Ann. Probab.491286–1309

    work page 2021

  24. [24]

    Luh, K., O’Rourke, S. (2020). Eigenvector delocalization for non-Hermitian random matrices and applications.Random Struct. Algorithms57169–210

    work page 2020

  25. [25]

    and Vu, V

    Luh, K. and Vu, V. (2020). Sparse random matrices have simple spectrum.Ann. Inst. Henri Poincar´ e Probab. Stat.562307–2328

    work page 2020

  26. [26]

    Lytova, A., Tikhomirov, K. (2020). On delocalization of eigenvectors of random non- Hermitian matrices.Probab. Theory Relat. Fields177465–524

    work page 2020

  27. [27]

    Naor, A., Youssef, P. (2017). Restricted invertibility revisited. In: A Journey Through Dis- crete Mathematics, pp. 657-691. Springer, Cham

    work page 2017

  28. [28]

    Nguyen, H. (2012). Inverse Littlewood–Offord problems and the singularity of random sym- metric matrices.Duke Math. J.161545–586

    work page 2012

  29. [29]

    Nguyen, H. (2012). On the least singular value of random symmetric matrices.Electron. J. Probab.171–19

    work page 2012

  30. [30]

    and Vu, V

    Nguyen, H., Tao, T. and Vu, V. (2017). Random matrices: tail bounds for gaps between eigenvalues.Probab. Theory Relat. Fields167777–816

    work page 2017

  31. [31]

    Nguyen, H. (2018). Random matrices: overcrowding estimates for the spectrum.J. Funct. Anal.2752197–2224

    work page 2018

  32. [32]

    Rebrova, E., Tikhomirov, K. (2018). Coverings of random ellipsoids, and invertibility of matrices with i.i.d. heavy-tailed entries.Israel J. of Math.227507–544

    work page 2018

  33. [33]

    Rudelson, M., Vershynin, R. (2008). The Littlewood-Offord problem and invertibility of ran- dom matrices.Adv. Math.218600–633

    work page 2008

  34. [34]

    Rudelson, M., Vershynin, R. (2009). Smallest Singular Value of a Random Rectangular Ma- trix.Commun. Pure Appl. Math.621707–1739

    work page 2009

  35. [35]

    Rudelson, M., Vershynin, R. (2013). Hanson-Wright inequality and sub-gaussian concentra- tion.Electron. Commun. Probab.181–9

    work page 2013

  36. [36]

    Rudelson, M., Vershynin, R. (2015). Small Ball Probabilities for Linear Images of High- Dimensional Distributions.Int. Math. Res. Not.20159594–9617

    work page 2015

  37. [37]

    Rudelson, M., Vershynin, R. (2016). No-gaps delocalization for general random matrices. Geom. Funct. Anal.261716–1776

    work page 2016

  38. [38]

    Rudelson, M. (2024). A large deviation inequality for the rank of a random matrixAnn. Probab.521992–2018

    work page 2024

  39. [39]

    and Sawhney, M

    Sah, A., Sahasrabudhe, J. and Sawhney, M. (2025). On the Spielman-Teng Conjecture.Geom. Funct. Anal.35633–671

    work page 2025

  40. [40]

    Spielman, D., Teng, S. (2002). Smoothed analysis of algorithms. In Proceedings of the Inter- national Congress of Mathematicians, Vol. I (Beijing, 2002), pages 597-606

    work page 2002

  41. [41]

    and Vu, V

    Tao, T. and Vu, V. (2006). On random±1 matrices: singularity and determinant.Random Struct. Algorithms281–23

    work page 2006

  42. [42]

    and Vu, V

    Tao, T. and Vu, V. (2006).Additive combinatoricsvolume 105. Cambridge University Press

    work page 2006

  43. [43]

    and Vu, V

    Tao, T. and Vu, V. (2007). On the singularity probability of random Bernoulli matrices.J. Amer. Math. Soc.20603–628

    work page 2007

  44. [44]

    and Vu, V

    Tao, T. and Vu, V. (2009). Inverse Littlewood-Offord Theorems and the Condition Number of Random Discrete Matrices.Ann. of Math.169595–632

    work page 2009

  45. [45]

    and Vu, V

    Tao, T. and Vu, V. (2010). Random matrices: The distribution of the smallest singular values. Geom. Funct. Anal.20260–297

    work page 2010

  46. [46]

    and Vu, V

    Tao, T. and Vu, V. (2017). Random matrices have simple spectrum.Combinatorica37539– 553

    work page 2017

  47. [47]

    Tikhomirov, K. (2020). Singularity of random Bernoulli matrices.Ann. of Math.191593–634

    work page 2020

  48. [48]

    Vershynin, R. (2014). Invertibility of symmetric random matrices.Random Struc. Algorithms 44135–182

    work page 2014

  49. [49]

    Vu, V. (2021). Recent progress in combinatorial random matrix theory.Probab. Surv.18 179–200

    work page 2021

  50. [50]

    discretized grid

    Zhou, S. (2019). Sparse Hanson-Wright inequalities for subgaussian quadratic forms. Bernoulli251603–1639. SYMMETRIC RANDOM MATRIX31 AppendixA.Proof of Proposition 4.10 In these appendices, our main goal is to prove Proposition 4.10. In particular, the proof of Proposition 4.10 is similar to the proof of Theorem 8.1 in [2]. We will adapt their method accor...

    work page 2019