Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published January 2020 | Submitted + Published
Book Section - Chapter Open

Edge Expansion and Spectral Gap of Nonnegative Matrices


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.

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.

Attached Files

Published - 1.9781611975994.73.pdf

Submitted - 1909.12497.pdf


Files (1.7 MB)
Name Size Download all
413.6 kB Preview Download
1.3 MB Preview Download

Additional details

August 19, 2023
October 20, 2023