CaltechAUTHORS
  A Caltech Library Service

Edge Expansion and Spectral Gap of Nonnegative Matrices

Mehta, Jenish C. and Schulman, Leonard J. (2020) Edge Expansion and Spectral Gap of Nonnegative Matrices. In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics , Philadelphia, PA, pp. 1200-1213. ISBN 978-1-61197-599-4. https://resolver.caltech.edu/CaltechAUTHORS:20200828-114509192

[img] PDF - Published Version
Creative Commons Attribution.

1278Kb
[img] PDF - Submitted Version
See Usage Policy.

403Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200828-114509192

Abstract

The classic graphical Cheeger inequalities state that if M is an n × n symmetric doubly stochastic matrix, then 1−λ₂(M)/2 ≤ ϕ(M) ≤ √2⋅(1−λ₂(M)) where ϕ(M) = min_(S⊆[n],|S|≤n/2)(1|S|∑_(i∈S,j∉S)M_(i,j)) is the edge expansion of M, and λ₂(M) is the second largest eigenvalue of M. We study the relationship between φ(A) and the spectral gap 1 – Re λ₂(A) for any doubly stochastic matrix A (not necessarily symmetric), where λ₂(A) is a nontrivial eigenvalue of A with maximum real part. Fiedler showed that the upper bound on φ(A) is unaffected, i.e., ϕ(A) ≤ √2⋅(1−Reλ₂(A)). With regards to the lower bound on φ(A), there are known constructions with ϕ(A) ∈ Θ(1−Reλ₂(A)/log n) indicating that at least a mild dependence on n is necessary to lower bound φ(A). In our first result, we provide an exponentially better construction of n × n doubly stochastic matrices A_n, for which ϕ(An) ≤ 1−Reλ₂(A_n)/√n. In fact, all nontrivial eigenvalues of our matrices are 0, even though the matrices are highly nonexpanding. We further show that this bound is in the correct range (up to the exponent of n), by showing that for any doubly stochastic matrix A, ϕ(A) ≥ 1−Reλ₂(A)/35⋅n As a consequence, unlike the symmetric case, there is a (necessary) loss of a factor of n^α for ½ ≤ α ≤ 1 in lower bounding φ by the spectral gap in the nonsymmetric setting. Our second result extends these bounds to general matrices R with nonnegative entries, to obtain a two-sided gapped refinement of the Perron-Frobenius theorem. Recall from the Perron-Frobenius theorem that for such R, there is a nonnegative eigenvalue r such that all eigenvalues of R lie within the closed disk of radius r about 0. Further, if R is irreducible, which means φ(R) > 0 (for suitably defined φ), then r is positive and all other eigenvalues lie within the open disk, so (with eigenvalues sorted by real part), Re λ₂(R) < r. An extension of Fiedler's result provides an upper bound and our result provides the corresponding lower bound on φ(R) in terms of r – Re λ₂(R), obtaining a two-sided quantitative version of the Perron-Frobenius theorem.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1137/1.9781611975994.73DOIArticle
https://arxiv.org/abs/1909.12497arXivDiscussion Paper
ORCID:
AuthorORCID
Schulman, Leonard J.0000-0001-9901-2797
Additional Information:© 2020 by SIAM. Published under the terms of the Creative Commons CC BY 4.0 license. We thank Shanghua Teng, Ori Parzanchevski and Umesh Vazirani for illuminating conversations. JCM would like to thank Luca Trevisan for his course “Graph Partitioning and Expanders” on VentureLabs, which got the author interested in Spectral Graph Theory. Research was supported by NSF grants 1319745, 1553477, 1618795, and 1909972; BSF grant 2012333; and, during a residency of LJS at the Israel Institute for Advanced Studies, by a EURIAS Senior Fellowship co-funded by the Marie Skłodowska-Curie Actions under the 7th Framework Programme.
Funders:
Funding AgencyGrant Number
NSFCCF-1319745
NSFCCF-1553477
NSFCCF-1618795
NSFCCF-1909972
Binational Science Foundation (USA-Israel)2012333
Israel Institute for Advanced StudiesUNSPECIFIED
EURIAS Senior FellowshipUNSPECIFIED
Marie Curie FellowshipUNSPECIFIED
Record Number:CaltechAUTHORS:20200828-114509192
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20200828-114509192
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:105141
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:28 Aug 2020 21:24
Last Modified:28 Aug 2020 21:24

Repository Staff Only: item control page