Edge Expansion and Spectral Gap of Nonnegative Matrices

Jenish C. Mehta, Leonard J. Schulman

The classic graphical Cheeger inequalities state that if $M$ is an $n\times n$ symmetric doubly stochastic matrix, then \[ \frac{1-λ_{2}(M)}{2}\leqϕ(M)\leq\sqrt{2\cdot(1-λ_{2}(M))}…