Finite reversible Cheeger inequality

Set $q_{xy}=\pi (x)P(x,y)$. By [F3], $q_{xy}=q_{yx}$; by [F1] its row sums are $\pi (x)$, and by [F2] its column sums are also $\pi (y)$. For a real-valued function $f$ define ${\displaystyle \mathcal{E}(f)=\frac{1}{2}\sum _{x,y}{q}_{xy}(f(x)-f(y){)}^2\mathrm{.}}$ Expanding the square and using these row and column sums gives $\mathcal{E}(f)=⟨f,(I-P)f{⟩}_{\pi }$.

Suppose $f\ge 0$ and its support has $\pi$-mass at most $1\mathrm{/}2$. For $t\ge 0$, let $S_t=\{x:f(x{)}^2>t\}$. The finite layer-cake identities give ${\int }_0^{\mathrm{\infty }}\pi (S_t)dt={\sum }_x\pi (x)f(x{)}^2$ and ${\int }_0^{\mathrm{\infty }}Q(S_t,S_t^c)dt=\frac{1}{2}{\sum }_{x,y}{q}_{xy}\mathrm{\mid }f(x{)}^2-f(y{)}^2\mathrm{\mid }$. Every nonempty $S_t$ is admissible in the definition of $\varphi$, so the latter integral is at least $\varphi \mathrm{\parallel }f{\mathrm{\parallel }}_{2,\pi }^2$. Apply [F5] to the finite weighted sum with weights $q_{xy}\mathrm{/}2$ and the factors $f(x)-f(y)$ and $f(x)+f(y)$. It bounds the integral above by $\sqrt{\mathcal{E}(f)\cdot \frac{1}{2}{\sum }_{x,y}{q}_{xy}(f(x)+f(y){)}^2}$; using $(a+b{)}^2\le 2a^2+2b^2$ and the row and column sums makes the second factor at most $2\mathrm{\parallel }f{\mathrm{\parallel }}_{2,\pi }^2$. If $f\mathrm{\ne }0$, division yields $\mathcal{E}(f)\ge ({\varphi }^2\mathrm{/}2)\mathrm{\parallel }f{\mathrm{\parallel }}_{2,\pi }^2$; for $f=0$ it is immediate.

Let $g$ be a real function with ${\sum }_x\pi (x)g(x)=0$. A weighted median $m$ exists by sorting the finitely many values of $g$ until their cumulative $\pi$-mass reaches $1\mathrm{/}2$; hence each of $g_{+}=(g-m{)}_{+}$ and $g_{-}=(m-g{)}_{+}$ has support mass at most $1\mathrm{/}2$. For every pair $x,y$, $((g-m)(x)-(g-m)(y){)}^2\ge (g_{+}(x)-g_{+}(y){)}^2+(g_{-}(x)-g_{-}(y){)}^2$. Therefore step 1.1 gives $\mathcal{E}(g)=\mathcal{E}(g-m)\ge \mathcal{E}(g_{+})+\mathcal{E}(g_{-})$.

Apply steps 2.1 and 2.2 to $g_{+}$ and $g_{-}$. Their squared norms sum to $\mathrm{\parallel }g-m{\mathrm{\parallel }}_{2,\pi }^2=\mathrm{\parallel }g{\mathrm{\parallel }}_{2,\pi }^2+m^2\ge \mathrm{\parallel }g{\mathrm{\parallel }}_{2,\pi }^2$ because $g$ has mean zero. Thus $\mathcal{E}(g)\ge ({\varphi }^2\mathrm{/}2)\mathrm{\parallel }g{\mathrm{\parallel }}_{2,\pi }^2$.

Detailed balance makes $P$ self-adjoint for $⟨\cdot ,\cdot {⟩}_{\pi }$, since exchanging $x,y$ in the finite sum proves $⟨f,Pg{⟩}_{\pi }=⟨Pf,g{⟩}_{\pi }$. Constants are $1$-eigenvectors. For any complex-valued $f$, weighted Cauchy–Schwarz and the row sums give $\mathrm{\mid }Pf(x){\mathrm{\mid }}^2=\mathrm{\mid }{\sum }_{y}P(x,y)f(y){\mathrm{\mid }}^2\le {\sum }_{y}P(x,y)\mathrm{\mid }f(y){\mathrm{\mid }}^2$. Summing against $\pi (x)$ and using stationarity gives $\mathrm{\parallel }Pf{\mathrm{\parallel }}_{2,\pi }\le \mathrm{\parallel }f{\mathrm{\parallel }}_{2,\pi }$. Thus every eigenvalue is at most $1$ and $1$ is the top eigenvalue. If a real function satisfies $Pf=f$, choose a state where it attains its maximum. Its value is a convex average of neighboring values, so every state reached with positive transition probability has the same maximum; irreducibility propagates this to every state. Thus the real $1$-eigenspace consists only of constants. For a complex $1$-eigenvector, its real and imaginary parts are real $1$-eigenvectors, so the same conclusion holds. By [F4], choose an orthonormal eigenbasis with first vector the normalized constant vector and eigenvalues $1={\lambda }_1>{\lambda }_2\ge \cdots$. Expanding any mean-zero vector in the remaining basis vectors shows directly that its Rayleigh quotient for $I-P$ is a weighted average of $1-{\lambda }_j$, whose minimum is $1-{\lambda }_2$. Step 3.1 bounds every real mean-zero quotient below by ${\varphi }^2\mathrm{/}2$; applying that inequality to the real and imaginary parts gives the same bound for complex vectors. This proves the claim. A possible negative eigenvalue near $-1$ does not affect the algebraic gap.