The following is claimed in Remark 3.1 in this paper (page 6). Let $M$ and $M'$ be $\pi$-reversible Markov chains on $X$ with eigenvalues $1=\lambda_0 \ge \lambda_1 \ge \cdots \ge \lambda_{|X|-1}$ and $1=\lambda_0' \ge \lambda_1' \ge \cdots \ge \lambda_{|X|-1}'$, respectively. Assume that $M'(x,y) \le M(x,y)$ for all $x \neq y$. Then, for all $i$, $\lambda_i \le \lambda_i'$.
In the paper, it says that this follows from the minimax characterization of eigenvalues. Why does this follow from the minimax characterization? Is this an immediate consequence of it?
I would appreciate any help or reference.
Thanks!
what you are looking for is actually a collection of results. I assume both chains are irreducible. Consider the matrix
1.) $\big(M'-M\big)$
this has $\mathbf 1$ in its kernel, with non-negative entries on the diagonal and non-positive entries on the off diagonal. By Gerschgorin Discs, all eigenvalues of $\big(M'-M\big)$ have non-negative real parts.
2.) since they are both $\pi$-invariant and reversible, they have the same stationary distribution and are both similar to real symmetric matrices $S'$ and $S$ via the same diagonal matrix $D^\frac{1}{2}$, i.e. $S' = D^\frac{1}{2}M'D^\frac{-1}{2}$ and $S = D^\frac{1}{2}MD^\frac{-1}{2}$. Then $\big(S'-S\big)\succeq \mathbf 0$ because $\big(S'-S\big)$ is a real symmetric matrix with no negative eigenvalues by (1). For more information on $D$ ref If $P$ is the transition matrix of a reversible Markov chain, why are its eigenvalues real?
3.) $\big(S'-S\big)\succeq \mathbf 0\iff S'\succeq S$ and this implies the eigenvalues of $S'$ weakly dominate those of $S$. In other words $\lambda_i'\geq \lambda_i$ for $i \in \big\{1,2,...,n\big\}$ since by similarity $M'$ and $S'$ must have the same eigenvalues and also $M$ and $S$ must have the same eigenvalues by similarity. I suppose you could prove the dominance relation via min-max characterization, though I prefer looking at it via Cauchy Interlacing; I gave a proof here.
EDIT: A question on eigenvalues of non-negative matrices.