EIGENVALUE GAPS OF RANDOM PERTURBATIONS OF LARGE MATRICES KYLE LUH RYAN VOGEL AND ALAN YU

2025-08-25 0 0 382.26KB 10 页 10玖币

侵权投诉

EIGENVALUE GAPS OF RANDOM PERTURBATIONS OF LARGE MATRICES

KYLE LUH, RYAN VOGEL, AND ALAN YU

Abstract. The current work applies some recent combinatorial tools due to Jain to control the eigenvalue

gaps of a matrix Mn=M+Nnwhere Mis deterministic, symmetric with large operator norm and Nnis

a random symmetric matrix with subgaussian entries. One consequence of our tail bounds is that Mnhas

simple spectrum with probability at least 1 −exp(−n2/15) which improves on a result of Nguyen, Tao and

Vu in terms of both the probability and the size of the matrix M.

1. Introduction

The gaps between eigenvalues of a random matrix have occupied probablists since the introduction of random

matrix theory [24, 25]. These gap statistics have been studied for a large set of models and with a wide

variety of techniques (see [8, 3, 19, 4, 2, 16] and the references therein). An interesting question, originally

posed by the computer science community in relation to the notorious graph isomorphism problem, was to

obtain estimates on the smallest gap size, δmin, of a random matrix [1]. In fact, at the time, it was not

known whether the gap was non-zero with high probability. This fact was ﬁrst established in [20]. This

result followed shortly by a more quantitative estimate of the gap size in [14].

In the present work, we examine n×nrandom matrices of the form Mn=M+Nnwhere Mis a deterministic,

symmetric matrix and Nnis a symmetric random matrix with centered entries. In [14], the authors obtained

some quantitative estimates on the gap sizes of Mnwhen Mhas operator norm that is at most polynomial

in n, the size of the matrix.

Theorem 1.1. [14, Theorem 2.6] Let Nnbe populated with centered, subgaussian random variables of vari-

ance 1. If kMk ≤ ncfor some constant c > 0, then for any ﬁxed C > 0, there exists a C0such that

P(δmin ≤n−C0)≤n−C.

A simple consequence of this theorem is that Nnhas simple spectrum with probability at most n−Cfor any

C > 0. In the present work, we build on some recent combinatorial techniques in random matrix theory

[6, 7, 5, 9, 10, 11, 13]. Using this method, we provide the ﬁrst tail bounds for gap sizes of Mnwhen M

can have operator norm exponential in the size of the matrix. An immediate consequence of our result is

an improved estimate on the probability of having simple spectrum that is exponentially small in n, rather

than polynomial. The rest of the article is devoted to the proof of our main theorem.

Deﬁnition 1.2. A random variable Xis subgaussian if there exists a constant K > 0 so that for all t > 0,

P(|X| ≥ t)≤2 exp −t2

K2.

Theorem 1.3. Let Mn=M+Nnwhere kMk ≤ exp(n1/16). We deﬁne λi:= λi(Mn)where

λ1≤λ2≤ ··· ≤ λn.

K. Luh was supported in part by the Ralph E. Powe Junior Faculty Enhancement Award.

R. Vogel was supported in part by the CU Boulder REU program.

A. Yu was supported in part by the CU Boulder REU program.

arXiv:2211.00606v1 [math.PR] 1 Nov 2022

We let δi=λi+1 −λiand δmin = miniδi. For α≥exp(−n2/15)and ν= (C1.3kMkα−1n7/6)−4log(α−1)

log n,

P(δmin ≤ν)≤α.

Specializing the above theorem to a gap size of zero yields a bound on the probability of having simple

spectrum.

Corollary 1.4. Under the hypotheses of Theorem 1.3, the probability that Mnhas simple spectrum is greater

than 1−exp(−n2/15).

2. Proof Strategy

We begin with the strategy ﬁrst proposed in [20, 14]. We decompose Mnas

Mn=Mn−1x

xTmnn (1)

where Mn−1is the n−1×n−1 matrix in the upper left, xis an n−1×1 vector and mnn is the remaining

random variable in the lower right.

By deﬁnition, for the i-th eigenvalue λi(Mn) with unit eigenvector v,

Mn−1x

xTmnn  v0

vn=λi(Mn)v0

vnwhere we have written v=v0

vn.

If we examine the top n−1 coordinates, we ﬁnd that

(Mn−1−λi(Mn))v0+vnx= 0.

Now consider taking the innerproduct of the above equation with the eigenvector wcorresponding to

λi(Mn−1), the i-th eigenvalue of Mn−1. We obtain

|vnwTx|=|(λi(Mn−1)−λi(Mn)||wTv0|≤|(λi(Mn−1)−λi(Mn)|.(2)

By Cauchy’s interlacing law, for any η > 0, the event λi+1(Mn)−λi(Mn)≤ηimplies the event |(λi(Mn−1)−

λi(Mn)| ≤ η. This, in turn, by (2), implies the event |vnwTx| ≤ η. We cannot guarantee that vnis large

or even non-zero, but since vis a unit vector, there must be some coordinate that is of size greater than

n−1/2. Taking a union bound over all [n], we can assume that |vn| ≥ n−1/2. Thus, we need to bound the

probability that |wTx| ≤ ηn1/2.

Crucially, wand xare independent. Therefore, the problem reduces to an issue of anti-concentration. If

we condition on w, this falls under the domain of Littlewood-Oﬀord theory [12]. In a long series of works,

it has been established that the anti-concentration of wTxis determined by the arithmetic structure of w.

The bulk of the argument now is to show that eigenvectors of random matrices are disordered. In random

matrix theory, this is usually established by Inverse Littlewood-Oﬀord theory [21] or covering arguments

via the Least Common Denominator [15]. Both of these breakthrough ideas have some drawbacks. The

arguments that invoke Inverse Littlewood-Oﬀord theory are only capable of providing inverse polynomial

bounds on the probability of various events. The covering arguments, on the other hand, are sensitive to

the operator norm of the random matrix and tend to break down when the norm is too large. Although the

Inverse Littlewood-Oﬀord theory is more robust to the size of the operator norm, even this method can only

handle norms polynomial in the size of the matrix. A recent combinatorial innovation [6] provides a method

of bypassing the inverse theorems and extracting super-polynomial probability bounds. This method has

been applied successfully to many discrete random matrix questions [5, 13, 7, 9, 11]. In [10], Jain introduced

a method of lattice approximations to extend least singular value bounds to matrices of superpolynomial

norm perturbed by i.i.d. random matrices. In our argumement, we adapt Jain’s lattice approximation to

the symmetric random matrix. The key idea is to approximate subsets of a vector so that when we restrict

our attention to those columns of the random matrix, there are many completely independent rows. This is

an insight that dates back to [22].

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

EIGENVALUEGAPSOFRANDOMPERTURBATIONSOFLARGEMATRICESKYLELUH,RYANVOGEL,ANDALANYUAbstract.ThecurrentworkappliessomerecentcombinatorialtoolsduetoJaintocontroltheeigenvaluegapsofamatrixMn=M+NnwhereMisdeterministic,symmetricwithlargeoperatornormandNnisarandomsymmetricmatrixwithsubgaussianentries.Oneconsequ...

展开>> 收起<<

EIGENVALUE GAPS OF RANDOM PERTURBATIONS OF LARGE MATRICES KYLE LUH RYAN VOGEL AND ALAN YU.pdf

共10页,预览2页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

EIGENVALUE GAPS OF RANDOM PERTURBATIONS OF LARGE MATRICES KYLE LUH RYAN VOGEL AND ALAN YU

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: