Paper Info
Title
Edge Expansion and Spectral Gap of Nonnegative Matrices.
Abstract
The classic graphical Cheeger inequalities state that if M is an n × nsymmetric doubly stochastic matrix, then [MATH HERE] where [MATH HERE] is the edge expansion of M, and λ2(M) is the second largest eigenvalue of M. We study the relationship between ϕ(A) and the spectral gap 1 − Re λ2(A) for any doubly stochastic matrix A (not necessarily symmetric), where λ2(A) is a nontrivial eigenvalue of A with maximum real part. Fiedler showed that the upper bound on ϕ(A) is unaffected, i.e., [MATH HERE]. With regards to the lower bound on ϕ(A), there are known constructions with [MATH HERE] 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 X n doubly stochastic matrices An, for which [MATH HERE] 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, [MATH HERE] As a consequence, unlike the symmetric case, there is a (necessary) loss of a factor of nα for 1/2 ≤ α ≤ 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 λ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 of r − Re λ2(R), obtaining a two-sided quantitative version of the Perron-Frobenius theorem.
Year
DOI
Venue
2020
10.5555/3381089.3381162
SODA '20: ACM-SIAM Symposium on Discrete Algorithms Salt Lake City Utah January, 2020
Field
DocType
Citations 
Discrete mathematics,Computer science,Matrix (mathematics),Spectral gap
Conference
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Jenish C. Mehta100.34
Leonard J. Schulman21328136.88