pith. sign in

arxiv: 2506.01155 · v2 · submitted 2025-06-01 · 🧮 math.PR

On the rank of a random symmetric matrix in the large deviation regime

Yi Han This is my paper

Pith reviewed 2026-05-19 11:53 UTC · model grok-4.3

classification 🧮 math.PR
keywords random symmetric matrixmatrix ranklarge deviationsubgaussian entriessingularity probabilityErdős-Rényi graph
0
0 comments X

The pith

Random symmetric matrix has rank at least n-k for k up to c sqrt(n) with probability at least 1-exp(-c' k n).

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

This paper establishes a large deviation bound showing that the corank of a random symmetric matrix stays small with extremely high probability. For an n by n matrix whose entries are i.i.d. subgaussian with unit variance, the chance that the rank drops by k or more is at most exp(-c' k n) whenever k is at most a constant times sqrt(n). A reader cares because the bound quantifies the rarity of near-singular behavior far more sharply than earlier results that only controlled the exact singularity probability. The same style of estimate is proved for adjacency matrices of dense Erdős-Rényi graphs.

Core claim

Let A be an n by n random symmetric matrix with independent identically distributed subgaussian entries of unit variance. The paper proves that there exist fixed constants c and c' greater than zero such that for every integer k satisfying 1 ≤ k ≤ c sqrt(n), the probability that the rank of A is at least n minus k is at least 1 minus exp(-c' k n). A parallel large deviation inequality is established for the rank of the adjacency matrix of a dense Erdős-Rényi graph.

What carries the argument

The large deviation inequality that upper-bounds the probability of corank at least k by exp(-c' k n) for k up to order sqrt(n).

If this is right

  • The probability that the matrix is singular is at most exp(-c' n).
  • This sharpens the exponential smallness of the singularity probability established in earlier work on random symmetric matrices.
  • The adjacency matrix of a dense Erdős-Rényi graph obeys the same large deviation bound on its corank.
  • The estimate remains valid uniformly for all corank values from 1 up to order sqrt(n).

Where Pith is reading between the lines

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

  • The actual typical corank may concentrate on a much smaller scale than sqrt(n), such as logarithmic in n.
  • The underlying method could be adapted to other ensembles, including matrices with mild dependence among entries.
  • The bound supplies a tool for controlling the distribution of the smallest eigenvalues of the matrix.

Load-bearing premise

The matrix entries are independent and identically distributed subgaussian random variables with unit variance.

What would settle it

For moderate n, say n=100, and k around 5, if direct sampling shows that the fraction of matrices with corank at least k is substantially larger than exp(-c' k n), the claimed tail bound would be contradicted.

read the original abstract

Let $A$ be an $n\times n$ random symmetric matrix with independent identically distributed subgaussian entries of unit variance. We prove the following large deviation inequality for the rank of $A$: for all $1\leq k\leq c\sqrt{n}$, $$\mathbb{P}(\operatorname{Rank}(A)\geq n-k)\geq 1-\exp(-c'kn),$$ for some fixed constants $c,c'>0$. A similar large deviation inequality is proven for the rank of the adjacency matrix of dense Erdos-Renyi graphs. This corank estimate enhances the recent breakthrough of Campos, Jensen, Michelen and Sahasrabudhe that the singularity probability of a random symmetric matrix is exponentially small, and echoes a large deviation inequality of Mark Rudelson for the rank of a random matrix with independent entries.

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

1 major / 1 minor

Summary. The manuscript claims to establish a large deviation inequality for the rank of an n×n random symmetric matrix A with i.i.d. subgaussian entries of unit variance. Specifically, it asserts that for some fixed constants c, c' > 0 and all 1 ≤ k ≤ c√n, P(Rank(A) ≥ n − k) ≥ 1 − exp(−c′kn). An analogous inequality is proven for the adjacency matrix of dense Erdős-Rényi graphs. This result extends the exponential smallness of the singularity probability obtained by Campos, Jensen, Michelen and Sahasrabudhe to a tail bound in the small-corank regime.

Significance. If the central inequality holds, the paper provides a valuable quantitative refinement of rank concentration results for random symmetric matrices, offering exponential tail bounds up to corank of order √n. This strengthens recent breakthroughs in the area and aligns with analogous results for non-symmetric random matrices due to Rudelson. The use of inverse Littlewood-Offord theory for anti-concentration is appropriately extended, and the manuscript contributes meaningfully to probabilistic combinatorics.

major comments (1)
  1. [Proof of the large deviation inequality] The control of the probability that a k-dimensional subspace lies in the kernel, as used to bound P(corank(A) > k), relies on anti-concentration for the image of the subspace under A. While the base Campos–Jensen–Michelen–Sahasrabudhe argument gives exp(−Ω(n)) small-ball probabilities for vectors, the joint control for k directions via nets on the Grassmannian introduces an entropy term. Please clarify explicitly (e.g., in the relevant lemma or equation) how this entropy factor combines with the anti-concentration exponent to preserve a linear dependence on kn in the final bound, ensuring it does not degrade for k up to c√n.
minor comments (1)
  1. [Introduction] The statement of the main result could benefit from a brief remark on how the constant c is chosen to ensure the argument goes through.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive comment on the proof. We address the major comment below and will update the manuscript to provide the requested explicit clarification on the entropy and anti-concentration combination.

read point-by-point responses

  1. Referee: [Proof of the large deviation inequality] The control of the probability that a k-dimensional subspace lies in the kernel, as used to bound P(corank(A) > k), relies on anti-concentration for the image of the subspace under A. While the base Campos–Jensen–Michelen–Sahasrabudhe argument gives exp(−Ω(n)) small-ball probabilities for vectors, the joint control for k directions via nets on the Grassmannian introduces an entropy term. Please clarify explicitly (e.g., in the relevant lemma or equation) how this entropy factor combines with the anti-concentration exponent to preserve a linear dependence on kn in the final bound, ensuring it does not degrade for k up to c√n.

    Authors: We agree that an explicit accounting of the entropy term is needed. In Section 3, we cover the Grassmannian Gr(k,n) by an ε-net (ε fixed, independent of k and n) whose cardinality is at most exp(O(kn)). For each fixed net subspace V we invoke the multi-dimensional anti-concentration (Lemma 3.3), which extends the vector case of Campos–Jensen–Michelen–Sahasrabudhe to give P(A(V)={0}) ≤ exp(−c kn) with c>0 absolute; the extension follows by applying the one-dimensional small-ball bound along an orthonormal basis of V and using sub-Gaussian tail decay to control the joint probability. The union bound therefore yields exp(O(kn))·exp(−c kn)=exp(−(c−O(1))kn). Choosing the final constant c′ smaller than this difference produces the claimed exp(−c′ kn) bound. The argument is uniform in k≤c√n because neither the net cardinality nor the anti-concentration constant introduces further k-dependent error terms that would degrade the linear exponent in this range. We will insert a short displayed calculation immediately after the net lemma to make this arithmetic explicit. revision: yes

Circularity Check

0 steps flagged

No circularity: direct probabilistic proof from i.i.d. subgaussian assumptions

full rationale

The paper establishes the stated large-deviation lower bound on P(Rank(A) ≥ n−k) via anti-concentration and union-bound arguments over the Grassmannian, building on the external Campos–Jensen–Michelen–Sahasrabudhe singularity result. No parameter is fitted to the target tail, no quantity is defined in terms of itself, and the cited prior work is by distinct authors. The derivation therefore remains self-contained against the model assumptions and does not reduce to any of the enumerated circular patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the standard modeling assumption of i.i.d. subgaussian entries together with background large-deviation and concentration tools from probability theory.

axioms (1)
  • domain assumption The entries are i.i.d. subgaussian random variables with unit variance.
    This defines the random matrix model for which the rank tail bound is claimed.

pith-pipeline@v0.9.0 · 5657 in / 1326 out tokens · 65857 ms · 2026-05-19T11:53:11.214812+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

39 extracted references · 39 canonical work pages

  1. [1]

    Graphs with integral spectrum

    Omran Ahmadi et al. “Graphs with integral spectrum”. In: Linear Algebra and its Applications 430.1 (2009), pp. 547–552

    work page 2009

  2. [2]

    Sharp transition of th e invertibility of the adja- cency matrices of sparse random graphs

    Anirban Basak and Mark Rudelson. “Sharp transition of th e invertibility of the adja- cency matrices of sparse random graphs”. In: Probability theory and related fields 180 (2021), pp. 233–308

    work page 2021

  3. [3]

    On the singularity probability of discrete random matrices

    Jean Bourgain, Van H Vu, and Philip Matchett Wood. “On the singularity probability of discrete random matrices”. In: Journal of Functional Analysis 258.2 (2010), pp. 559– 603

    work page 2010

  4. [4]

    On the singularity of random symme tric matrices

    Marcelo Campos et al. “On the singularity of random symme tric matrices”. In: Duke Math. J. 170.5 (2021), pp. 881–907. issn: 0012-7094,1547-7398

    work page 2021

  5. [5]

    Singularity of random symmetric m atrices revisited

    Marcelo Campos et al. “Singularity of random symmetric m atrices revisited”. In: Proceedings of the American Mathematical Society 150.7 (2022), pp. 3147–3159

    work page 2022

  6. [6]

    The least singular value of a rando m symmetric matrix

    Marcelo Campos et al. “The least singular value of a rando m symmetric matrix”. In: Forum of Mathematics, Pi . Vol. 12. Cambridge University Press. 2024, e3

    work page 2024

  7. [7]

    The singularity probability of a r andom symmetric matrix is exponentially small

    Marcelo Campos et al. “The singularity probability of a r andom symmetric matrix is exponentially small”. In: J. Amer. Math. Soc. 38.1 (2025), pp. 179–224. issn: 0894- 0347,1088-6834

    work page 2025

  8. [8]

    Perfect state transfer in qu antum spin networks

    Matthias Christandl et al. “Perfect state transfer in qu antum spin networks”. In: Physical review letters 92.18 (2004), p. 187902

    work page 2004

  9. [9]

    Perfect transfer of arbitra ry states in quantum spin net- works

    Matthias Christandl et al. “Perfect transfer of arbitra ry states in quantum spin net- works”. In: Physical Review A—Atomic, Molecular, and Optical Physics 71.3 (2005), p. 032312

    work page 2005

  10. [10]

    Lower bounds for the smallest singular value of structured random matrices

    Nicholas Cook. “Lower bounds for the smallest singular value of structured random matrices”. In: The Annals of probability 46.6 (2018), pp. 3442–3500

    work page 2018

  11. [11]

    The rank of random graphs

    Kevin P Costello and Van H Vu. “The rank of random graphs” . In: Random Structures & Algorithms 33.3 (2008), pp. 269–285

    work page 2008

  12. [12]

    Random symm etric matrices are al- most surely nonsingular

    Kevin P. Costello, Terence Tao, and Van Vu. “Random symm etric matrices are al- most surely nonsingular”. In: Duke Math. J. 135.2 (2006), pp. 395–413. issn: 0012- 7094,1547-7398

    work page 2006

  13. [13]

    On the number of integral graphs

    Kevin P. Costello and Parker Williams. “On the number of integral graphs”. In: Linear Algebra Appl. 493 (2016), pp. 447–454. issn: 0024-3795,1873-1856

    work page 2016

  14. [14]

    Quantum Cayley networks of the hypercube

    Christopher Facer, Jason Twamley, and James Cresser. “ Quantum Cayley networks of the hypercube”. In: Physical Review A—Atomic, Molecular, and Optical Physics 77.1 (2008), p. 012334

    work page 2008

  15. [15]

    Singularity of random sy mmetric matrices—a com- binatorial approach to improved bounds

    Asaf Ferber and Vishesh Jain. “Singularity of random sy mmetric matrices—a com- binatorial approach to improved bounds”. In: Forum of Mathematics, Sigma . Vol. 7. Cambridge University Press. 2019, e22

    work page 2019

  16. [16]

    Random symmetric matrices: rank dis tribution and irreducibil- ity of the characteristic polynomial

    Asaf Ferber et al. “Random symmetric matrices: rank dis tribution and irreducibil- ity of the characteristic polynomial”. In: Mathematical Proceedings of the Cambridge Philosophical Society. Vol. 174. 2. Cambridge University Press. 2023, pp. 233–246

    work page 2023

  17. [17]

    Singularity of the k-core of a random graph

    Asaf Ferber et al. “Singularity of the k-core of a random graph”. In: Duke Mathematical Journal 172.7 (2023), pp. 1293–1332

    work page 2023

  18. [18]

    The exact rank of sparse random graphs

    Margalit Glasgow et al. “The exact rank of sparse random graphs”. In: arXiv preprint arXiv:2303.05435 (2023). REFERENCES 47

    work page arXiv 2023

  19. [19]

    Repeated singular values of a random symmetric matrix and decoupled singular value estimates

    Yi Han. “Repeated singular values of a random symmetric matrix and decoupled singular value estimates”. In: arXiv preprint arXiv:2504.15992 (2025)

    work page arXiv 2025

  20. [20]

    Rank de ficiency of random ma- trices

    Vishesh Jain, Ashwin Sah, and Mehtaab Sawhney. “Rank de ficiency of random ma- trices”. In: Electronic Communications in Probability 27 (2022), pp. 1–9

    work page 2022

  21. [21]

    Singul arity of discrete random matrices

    Vishesh Jain, Ashwin Sah, and Mehtaab Sawhney. “Singul arity of discrete random matrices”. In: Geometric and Functional Analysis 31 (2021), pp. 1160–1218

    work page 2021

  22. [22]

    On theprobability that a random± 1- matrix is singular

    Jeff Kahn, J´ anos Koml´ os, and Endre Szemer´ edi. “On theprobability that a random± 1- matrix is singular”. In: Journal of the American Mathematical Society 8.1 (1995), pp. 223–240

    work page 1995

  23. [23]

    On the determinant of (0-1) matrices

    J´ anos Koml´ os. “On the determinant of (0-1) matrices”. In: Studia Scientiarium Math- ematicarum Hungarica 2 (1967), pp. 7–21

    work page 1967

  24. [24]

    The smallest singular value of heav y-tailed not necessarily iid random matrices via random rounding

    Galyna V Livshyts. “The smallest singular value of heav y-tailed not necessarily iid random matrices via random rounding”. In: Journal d’Analyse Math´ ematique 145.1 (2021), pp. 257–306

    work page 2021

  25. [25]

    Symmetric random matrices over finite fields

    Kenneth Maples. Symmetric random matrices over finite fields. Announcement, http://user.math.uzh.ch/maples/maples.symma.pdf

    work page

  26. [26]

    Inverse Littlewood-Offord problems and t he singularity of ran- dom symmetric matrices

    Hoi H. Nguyen. “Inverse Littlewood-Offord problems and t he singularity of ran- dom symmetric matrices”. In: Duke Math. J. 161.4 (2012), pp. 545–586. issn: 0012- 7094,1547-7398

    work page 2012

  27. [27]

    On subspaces spanned by random selec tions of ± 1 vectors

    Andrew M Odlyzko. “On subspaces spanned by random selec tions of ± 1 vectors”. In: journal of combinatorial theory, Series A 47.1 (1988), pp. 124–133

    work page 1988

  28. [28]

    A large deviation inequality for the ra nk of a random matrix

    Mark Rudelson. “A large deviation inequality for the ra nk of a random matrix”. In: The Annals of Probability 52.5 (2024), pp. 1992–2018

    work page 2024

  29. [29]

    Hanson-Wright ine quality and sub-Gaussian concentration

    Mark Rudelson and Roman Vershynin. “Hanson-Wright ine quality and sub-Gaussian concentration”. In: Electron. Commun. Probab. 18 (2013), no. 82, 9. issn: 1083-589X

    work page 2013

  30. [30]

    No-gaps delocaliz ation for general random matrices

    Mark Rudelson and Roman Vershynin. “No-gaps delocaliz ation for general random matrices”. In: Geometric and Functional Analysis 26.6 (2016), pp. 1716–1776

    work page 2016

  31. [31]

    Small ball probabi lities for linear images of high-dimensional distributions

    Mark Rudelson and Roman Vershynin. “Small ball probabi lities for linear images of high-dimensional distributions”. In: International Mathematics Research Notices 2015.19 (2015), pp. 9594–9617

    work page 2015

  32. [32]

    The Littlewood–Offo rd problem and invert- ibility of random matrices

    Mark Rudelson and Roman Vershynin. “The Littlewood–Offo rd problem and invert- ibility of random matrices”. In: Advances in Mathematics 218.2 (2008), pp. 600–633

    work page 2008

  33. [33]

    Singular values of Ga ussian matrices and perma- nent estimators

    Mark Rudelson and Ofer Zeitouni. “Singular values of Ga ussian matrices and perma- nent estimators”. In: Random Structures & Algorithms 48.1 (2016), pp. 183–212

    work page 2016

  34. [34]

    Parameters of integral circu- lant graphs and periodic quantum dynamics

    Nitin Saxena, Simone Severini, and Igor E Shparlinski. “Parameters of integral circu- lant graphs and periodic quantum dynamics”. In: International Journal of Quantum Information 5.03 (2007), pp. 417–430

    work page 2007

  35. [35]

    On the singularity probability of random Bernoulli matri- ces

    Terence Tao and Van Vu. “On the singularity probability of random Bernoulli matri- ces”. In: Journal of the American Mathematical Society 20.3 (2007), pp. 603–628

    work page 2007

  36. [36]

    Quantitative invertibility of non-Hermitian random matri- ces

    Konstantin Tikhomirov. “Quantitative invertibility of non-Hermitian random matri- ces”. In: ICM—International Congress of Mathematicians. Vol. 4. Section s 5–8 . EMS Press, Berlin, 2023, pp. 3292–3313

    work page 2023

  37. [37]

    Singularity of random Bernou lli matrices

    Konstantin Tikhomirov. “Singularity of random Bernou lli matrices”. In: Annals of Mathematics 191.2 (2020), pp. 593–634

    work page 2020

  38. [38]

    Invertibility of symmetric random m atrices

    Roman Vershynin. “Invertibility of symmetric random m atrices”. In: Random Struc- tures & Algorithms 44.2 (2014), pp. 135–182. 48 REFERENCES

    work page 2014

  39. [39]

    Recent progress in combinatorial random mat rix theory

    Van H. Vu. “Recent progress in combinatorial random mat rix theory”. In: Probab. Surv. 18 (2021), pp. 179–200. issn: 1549-5787. Department of Mathematics, Massachusetts Institute of Tec hnology, Cambridge, MA Email address : hanyi16@mit.edu

    work page 2021