6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If your matrix is the matrix of $1/n$'s, then deleting a row and column, the maximal eigenvalue is $1-\frac 1n$. $\endgroup$ – Anthony Quas Feb 6 at 21:48
  • $\begingroup$ @AnthonyQuas That is true, but it this generally (in an order sense) the case for all matrices that satisfy the criterion in the question? $\endgroup$ – Television Feb 6 at 21:49
  • 3
    $\begingroup$ No - if $A$ is the all $1/n$ matrix, then $B=(1-\epsilon)I + \epsilon A$ is doubly stochastic, but the maximal eigenvalue is $1-\epsilon/n$, so that if $\epsilon=1/n^{17}$, then the maximal eigenvalue is $1-n^{-18}$. $\endgroup$ – Anthony Quas Feb 6 at 21:51
  • 1
    $\begingroup$ @AnthonyQuas Ok, that is a good example. With $\epsilon = \frac{1}{n^2}$, say, it gives a different rate of convergence. Perhaps the question is more interesting with an additional constraint: the $2^{nd}$ eigenvalue of $P_n$ is bounded away from $1$ as $n \to \infty$. This would avoid cases where $P$ looks almost like $I$, which is a limiting case of irreducibility. $\endgroup$ – Television Feb 6 at 22:03
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.