The least singular value of a random symmetric matrix

Marcelo Campos; Matthew Jenssen; Marcus Michelen; Julian Sahasrabudhe

doi:10.48550/arXiv.2203.06141

The least singular value of a random symmetric matrix

Marcelo Campos, Matthew Jenssen, Marcus Michelen, Julian Sahasrabudhe

Mathematics

Research output: Working paper/Preprint › Preprint

16 Downloads (Pure)

Abstract

Let A be a n×n symmetric matrix with (A_i,j)_i≤j, independent and identically distributed according to a subgaussian distribution. We show that
ℙ(σ_min(A)≤ε/√n)≤Cε+e^−cn,
where σ_min(A) denotes the least singular value of A and the constants C,c>0 depend only on the distribution of the entries of A. This result confirms a folklore conjecture on the lower-tail asymptotics of the least singular value of random symmetric matrices and is best possible up to the dependence of the constants on the distribution of A_i,j. Along the way, we prove that the probability A has a repeated eigenvalue is e^−Ω(n), thus confirming a conjecture of Nguyen, Tao and Vu.

Original language	English
Publisher	arXiv
DOIs	https://doi.org/10.48550/arXiv.2203.06141
Publication status	Published - 11 Mar 2022

Bibliographical note

44 pages + 30 page supplement. The supplement builds on our previous work arXiv:2105.11384 and provides the proof of a technical quasi-randomness statement

Keywords

math.PR
math.CO

Access to Document

10.48550/arXiv.2203.06141Licence: Creative Commons: Attribution (CC BY)

CamposM2022leastOther version, 894 KBLicence: Creative Commons: Attribution (CC BY)

Cite this

@techreport{523e6a87fea747438eefa11ce2dff4f7,

title = "The least singular value of a random symmetric matrix",

abstract = "Let A be a n×n symmetric matrix with (Ai,j)i≤j, independent and identically distributed according to a subgaussian distribution. We show thatℙ(σmin(A)≤ε/√n)≤Cε+e−cn,where σmin(A) denotes the least singular value of A and the constants C,c>0 depend only on the distribution of the entries of A. This result confirms a folklore conjecture on the lower-tail asymptotics of the least singular value of random symmetric matrices and is best possible up to the dependence of the constants on the distribution of Ai,j. Along the way, we prove that the probability A has a repeated eigenvalue is e−Ω(n), thus confirming a conjecture of Nguyen, Tao and Vu.",

keywords = "math.PR, math.CO",

author = "Marcelo Campos and Matthew Jenssen and Marcus Michelen and Julian Sahasrabudhe",

note = "44 pages + 30 page supplement. The supplement builds on our previous work arXiv:2105.11384 and provides the proof of a technical quasi-randomness statement",

year = "2022",

month = mar,

day = "11",

doi = "10.48550/arXiv.2203.06141",

language = "English",

publisher = "arXiv",

type = "WorkingPaper",

institution = "arXiv",

}

TY - UNPB

T1 - The least singular value of a random symmetric matrix

AU - Campos, Marcelo

AU - Jenssen, Matthew

AU - Michelen, Marcus

AU - Sahasrabudhe, Julian

N1 - 44 pages + 30 page supplement. The supplement builds on our previous work arXiv:2105.11384 and provides the proof of a technical quasi-randomness statement

PY - 2022/3/11

Y1 - 2022/3/11

N2 - Let A be a n×n symmetric matrix with (Ai,j)i≤j, independent and identically distributed according to a subgaussian distribution. We show thatℙ(σmin(A)≤ε/√n)≤Cε+e−cn,where σmin(A) denotes the least singular value of A and the constants C,c>0 depend only on the distribution of the entries of A. This result confirms a folklore conjecture on the lower-tail asymptotics of the least singular value of random symmetric matrices and is best possible up to the dependence of the constants on the distribution of Ai,j. Along the way, we prove that the probability A has a repeated eigenvalue is e−Ω(n), thus confirming a conjecture of Nguyen, Tao and Vu.

AB - Let A be a n×n symmetric matrix with (Ai,j)i≤j, independent and identically distributed according to a subgaussian distribution. We show thatℙ(σmin(A)≤ε/√n)≤Cε+e−cn,where σmin(A) denotes the least singular value of A and the constants C,c>0 depend only on the distribution of the entries of A. This result confirms a folklore conjecture on the lower-tail asymptotics of the least singular value of random symmetric matrices and is best possible up to the dependence of the constants on the distribution of Ai,j. Along the way, we prove that the probability A has a repeated eigenvalue is e−Ω(n), thus confirming a conjecture of Nguyen, Tao and Vu.

KW - math.PR

KW - math.CO

U2 - 10.48550/arXiv.2203.06141

DO - 10.48550/arXiv.2203.06141

M3 - Preprint

BT - The least singular value of a random symmetric matrix

PB - arXiv

ER -

The least singular value of a random symmetric matrix

Abstract

Bibliographical note

Keywords

Access to Document

Fingerprint

Cite this