Rate of convergence of transition matrix when the probability of self edge is spread evenly across all other nodes.

Question

Given a transition matrix $A$ of size $n$ (all elements are non-zero), if we construct another transition matrix $A'$ such that $A'[i][j] = A[i][j] + A[i][i]/(n-1) \,$ and $A'[i][i] = 0$ for all $0 \leq i,j < n$, then will $A'$'s second largest eigenvalue be greater than $A$'s second largest eigenvalue? I am interested in convergent properties. Empirically I see that $A'$'s second largest eigenvalue is always greater than $A$'s second largest eigenvalue, but fail to show it theoretically.

Answer 1

Without the "all elements are nonzero" requirement, you have a trivial counterexample by starting with the identity matrix, in which case the second largest eigenvalue is $1$ originally (because the induced graph of the Markov chain isn't connected) and isn't after the transformation (because the induced graph of the Markov chain is connected).

You should expect this observation to stick around after a small enough perturbation of the identity matrix. It doesn't actually work in the 2-node case, because with 2 nodes $A'$ is always $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$ regardless of what $A$ was. (I assume that for your purposes you measure eigenvalues by their absolute value so that $-1$ is "large".)

But with 3 nodes, you can look at

$$A=\begin{bmatrix} 0.98 & 0.01 & 0.01 \\ 0.01 & 0.98 & 0.01 \\ 0.01 & 0.01 & 0.98 \end{bmatrix}$$

which turns into

$$A'=\begin{bmatrix} 0 & 1/2 & 1/2 \\ 1/2 & 0 & 1/2 \\ 1/2 & 1/2 & 0 \end{bmatrix}$$

and the second largest eigenvalue goes from a magnitude of 0.97 to a magnitude of 0.5.

In actuality, I would expect your operation to make the second largest eigenvalue get smaller, not larger, because the second largest eigenvalue (in absolute value) is a measure of the barrier to mixing over the whole graph. Your operation speeds up mixing by making every node more connected to every other node.