Maximum eigenvalue of a doubly stochastic matrix with deleted row and column

Question

Consider an $n \times n$ irreducible and reversible (in the sense of a Markov chain) stochastic matrix $P$; assume that it has uniform stationary distribution (so, by reversibility, the matrix is symmetric and doubly stochastic).

If, say the first row and column of the matrix was deleted (call this matrix $P'$), is there a good characterization of the maximum eigenvalue of the new matrix? I am able to show that it must be at least $1 - \frac{1}{n-1}$ by considering $\mathbf{w}^T P' \mathbf{w}$ for the vector which has $0$ in the $1^{st}$ co-ordinate and $1$ everywhere else. Since the maximum eigenvalue must be $\le 1$ (Cauchy's interlacing theorem), this is indeed a good approximation as $n$ becomes large.

My question is: is the rate at which this eigenvalue approach $1$ indeed $\frac{1}{n}$?

Edit: Assume that the spectral gap of the Markov chain is bounded away from $0$ as $n \to \infty$. As pointed out in the comments, there is a simple counterexample when the spectral gap is allowed to be arbitrarily small.

Answer 1

The following proof shows that this is indeed the case. Let $\gamma$ denote the spectral gap of $P$ and $\lambda$ denote the absolute value of the eigenvalue of $P$ that achieves the spectral gap. Then, \begin{equation} \rho_1 \le 1 - \frac{\gamma}{2n} \end{equation} for large $n$.

Proof:

Let $\{ \mathbf{u}_i \}$ and $\{ \mathbf{v}_i \}$ respectively denote the set of eigenvectors of $P$ and $P'$ (both are symmetric matrices). Note that $\mathbf{u}_1 = \frac{1}{\sqrt{n}} \mathbf{1}$. In addition, let $\{ \lambda_1 (=1), \lambda_2, \cdots, \lambda_n \}$ be the set of eigenvalues of $P$ and $\{ \rho_1,\rho_2,\cdots,\rho_n\}$ denote the eigenvalues of $P'$.

Observe that, \begin{align} \mathbf{u}_1^T P' \mathbf{u}_1 &= \frac1n \left( \sum_{i,j \in [n]} P_{i,j} - \sum_{j \in [n]} P_{1,j} - \sum_{i \in [n]} P_{i,1} + P_{1,1} \right) \\ &= \frac1n \left( n - 2 + P_{1,1} \right) \\ &\le 1 - \frac1n \tag{1} \label{eq:1} \end{align}

By the eigenvalue decomposition of $P'$, \begin{align*} \mathbf{u}_1^T P' \mathbf{u}_1 = \sum_{i \in [n]} \rho_i \langle \mathbf{u}_1, \mathbf{v}_i \rangle^2 \ge \rho_1 \langle \mathbf{u}_1, \mathbf{v}_1 \rangle^2 - \lambda (1 - \langle \mathbf{u}_1, \mathbf{v}_1 \rangle^2) \end{align*} note that Cauchy interlace theorem implies that $\forall i \ge 2,\ |\rho_i| \le \lambda$.

Combining with eq. \eqref{eq:1}, we have that, \begin{equation} (\rho_1 + \lambda) \langle \mathbf{u}_1, \mathbf{v}_1 \rangle^2 \le 1 + \lambda - \frac1n \tag{2} \label{eq:2} \end{equation}

Now observe that by the Perron Frobenius theorem $\mathbf{v}_1$ can be assumed to have all positive entries. Therefore, \begin{align} \rho_1 = \mathbf{v}_1^T P' \mathbf{v}_1 \le \mathbf{v}_1^T P \mathbf{v}_1 &= \sum_{i \in [n]} \lambda_i \langle \mathbf{u}_i, \mathbf{v}_1 \rangle^2 \\ &\le \langle \mathbf{u}_1, \mathbf{v}_1 \rangle^2 + \lambda (1 - \langle \mathbf{u}_1, \mathbf{v}_1 \rangle^2) \\ \implies \rho_1 - \lambda &\le (1 - \lambda) \langle \mathbf{u}_1, \mathbf{v}_1 \rangle^2 \tag{3} \label{eq:3} \end{align}

Multiplying eqs. \eqref{eq:2} and \eqref{eq:3}, \begin{equation} \rho_1^2 - \lambda^2 \le (1 - \lambda) \left( 1 + \lambda - \frac1n\right) \end{equation} Therefore, \begin{align} \rho_1^2 &\le 1 - \frac{1-\lambda}{n} \\ \implies \rho_1 &\overset{(i)}{\le} 1 - \frac{1 - \lambda}{2n} \end{align} where $(i)$ holds for large $n$.