Edge Expansion and Spectral Gap of Nonnegative Matrices
Edge Expansion and Spectral Gap of Nonnegative Matrices
复制标题
非负矩阵的边扩展和谱间隙
DOI：
10.1137/1.9781611975994.73
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Schulman, Leonard J.
中科院分区：
文献类型：
--
作者：
Mehta, Jenish C.;Schulman, Leonard J.
经典图解Cheeger不等式指出，如果M是一个n×n对称双随机矩阵，则其中是M的边展开，λ2(M)是M的第二大特征值。我们研究了任意双随机矩阵A（不一定对称）的φ(A)与谱间隙1 – Re λ2(A)之间的关系，其中λ2(A)是A的具有最大实部的非平凡特征值。 Fiedler 证明 φ(A) 的上限不受影响，即 。关于 φ(A) 的下界，已知的构造表明至少对下界 φ(A) 有一定的依赖性。在我们的第一个结果中，我们提供了 n×n 双随机矩阵 An 的指数更好的构造，实际上，我们矩阵的所有非平凡特征值都是 0，即使矩阵是高度非扩展的。我们通过证明对于任何双随机矩阵 A，进一步证明这个界限在正确的范围内（直到 n 的指数），因此，与对称情况不同，在非对称设置中，谱间隙会（必要）损失下界 φ 的因子。我们的第二个结果将这些界限扩展到具有非负项的一般矩阵 R，以获得 Perron-Frobenius 定理的双边间隙细化。回想一下 Perron-Frobenius 定理，对于这样的 R，存在一个非负特征值 r，使得 R 的所有特征值都位于半径 r 约为 0 的闭盘内。此外，如果 Ri 不可约，这意味着 φ(R) > 0（对于适当定义的 φ），则 ris 为正且所有其他特征值位于开盘内，因此（特征值按实部排序），Reλ2(R) <r。 Fiedler 结果的扩展提供了一个上限，而我们的结果提供了以 r– Re λ2(R) 表示的 φ(R) 上相应的下界，从而获得了 Perron-Frobenius 定理的两侧定量版本。
The classic graphical Cheeger inequalities state that ifMis ann×n symmetricdoubly stochastic matrix, thenwhere is the edge expansion ofM, and λ2(M) is the second largest eigenvalue ofM. We study the relationship betweenφ(A) and the spectral gap 1 – Re λ2(A) foranydoubly stochastic matrixA(not necessarily symmetric), where λ2(A) is a nontrivial eigenvalue ofAwith maximum real part. Fiedler showed that the upper bound onφ(A) is unaffected, i.e., . With regards to the lower bound onφ(A), there are known constructions withindicating that at least a mild dependence onnis necessary to lower boundφ(A).In our first result, we provide anexponentiallybetter construction ofn×ndoubly stochastic matricesAn, for whichIn fact,allnontrivial eigenvalues of our matrices are 0, even though the matrices are highlynonexpanding. We further show that this bound is in the correct range (up to the exponent ofn), by showing that for any doubly stochastic matrixA,As a consequence, unlike the symmetric case, there is a (necessary) loss of a factor of in lower boundingφby the spectral gap in the nonsymmetric setting.Our second result extends these bounds to general matricesRwith nonnegative entries, to obtain a two-sidedgappedrefinement of the Perron-Frobenius theorem. Recall from the Perron-Frobenius theorem that for suchR, there is a nonnegative eigenvaluersuch that all eigenvalues ofRlie within the closed disk of radiusrabout 0. Further, ifRis irreducible, which meansφ(R) > 0 (for suitably definedφ), thenris positive and all other eigenvalues lie within theopendisk, so (with eigenvalues sorted by real part), Reλ2(R) <r. An extension of Fiedler's result provides an upper bound and our result provides the corresponding lower bound onφ(R) in terms ofr– Re λ2(R), obtaining a two-sided quantitative version of the Perron-Frobenius theorem.
登录
查看更多内容
DOI：
--
发表时间：
1985
期刊：
--
影响因子：
--
作者：
N. Alon;V. Milman
通讯作者：
N. Alon;V. Milman
DOI：
10.1016/0024-3795(81)90106-3
发表时间：
2020-11
期刊：
--
影响因子：
--
作者：
Tzuong-Tsieng Moh
通讯作者：
Tzuong-Tsieng Moh
DOI：
--
发表时间：
1982-07
期刊：
--
影响因子：
--
作者：
P. Flajolet
通讯作者：
P. Flajolet
DOI：
10.1007/0-387-22081-x_7
发表时间：
2020-05
期刊：
An Introduction to Probabilistic Number Theory
影响因子：
--
作者：
Don Redmond
通讯作者：
Don Redmond
DOI：
--
发表时间：
2017
期刊：
影响因子：
--
作者：
Koninklijke Nederlandse Akademie van Wetenschappen
通讯作者：
Koninklijke Nederlandse Akademie van Wetenschappen