Edge Expansion and Spectral Gap of Nonnegative Matrices
share
The classic graphical Cheeger inequalities state that if M is an n× n symmetric doubly stochastic matrix, then 1-λ_2(M)/2≤ϕ(M)≤√(2·(1-λ_2(M))) where ϕ(M)=min_S⊆[n],|S|≤ n/2(1/|S|∑_i∈ S,j∉SM_i,j) 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., ϕ(A)≤√(2·(1-Reλ_2(A))). With regards to the lower bound on ϕ(A), there are known constructions with ϕ(A)∈Θ(1-Reλ_2(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 ϕ(A_n)≤1-Reλ_2(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λ_2(A)/35· n. Our second result extends these bounds to general nonnegative matrices R, obtaining a two-sided quantitative refinement of the Perron-Frobenius theorem in which the edge expansion ϕ(R) (appropriately defined), a quantitative measure of the irreducibility of R, controls the gap between the Perron-Frobenius eigenvalue and the next-largest real part of any eigenvalue.
READ FULL TEXT