Edge Expansion and Spectral Gap of Nonnegative Matrices

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.

Files

Additional details