Infinite power of doubly stochastic matrix without using diagonalization

Question

Given $$M := \frac17 \begin{bmatrix} 3 & 1 & 1 & 1 & 1 \\ 1 & 3 & 1 & 1 & 1 \\ 1 & 1 & 3 & 1 & 1 \\ 1 & 1 & 1 & 3 & 1 \\ 1 & 1 & 1 & 1 & 3 \end{bmatrix}$$ find $$\lim _{n \to \infty} M^n$$

---

We can express,

$$ M = \frac{1}{7}\left(\begin{matrix} -1 & -1 & -1 & -1 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \end{matrix}\right)\left(\begin{matrix} 2 & 0 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 & 7 \end{matrix}\right)\left(\begin{matrix} \frac{-1}{5} & \frac{4}{5} & \frac{-1}{5} & \frac{-1}{5} & \frac{-1}{5} \\ \frac{-1}{5} & \frac{-1}{5} & \frac{4}{5} & \frac{-1}{5} & \frac{-1}{5} \\ \frac{-1}{5} & \frac{-1}{5} & \frac{-1}{5} & \frac{4}{5} & \frac{-1}{5} \\ \frac{-1}{5} & \frac{-1}{5} & \frac{-1}{5} & \frac{-1}{5} & \frac{4}{5} \\ \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} \end{matrix}\right) $$

And evaluate, $$ \lim _{n \rightarrow \infty} M^{n} = \lim _{n \rightarrow \infty} P\left(\begin{matrix} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{matrix}\right)P^{-1} = \frac{1}{5}\left(\begin{matrix} 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \end{matrix}\right) $$ where I used that, $$ P = \left(\begin{matrix} -1 & -1 & -1 & -1 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \end{matrix}\right) \,\,\,\,\,\& \,\,\,\,\, P^{-1} = \left(\begin{matrix} \frac{-1}{5} & \frac{4}{5} & \frac{-1}{5} & \frac{-1}{5} & \frac{-1}{5} \\ \frac{-1}{5} & \frac{-1}{5} & \frac{4}{5} & \frac{-1}{5} & \frac{-1}{5} \\ \frac{-1}{5} & \frac{-1}{5} & \frac{-1}{5} & \frac{4}{5} & \frac{-1}{5} \\ \frac{-1}{5} & \frac{-1}{5} & \frac{-1}{5} & \frac{-1}{5} & \frac{4}{5} \\ \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} \end{matrix}\right) $$

This traditional way of diagonalization involves not just finding eigenvalues but also eigenvectors (in other words find P).

Finding eigenvalues for this is easy. I consider, $$ A=\left[\begin{array}{lllll} 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \end{array}\right] $$ which clearly has eigenvalues $\lambda_1 = 0$ (with algebraic multiplicity = $4$) and $\lambda_2 = 5$ (with algebraic multiplicity = $1$).

The eigenvalues for our first Matrix $M = \frac{1}{7}\left(A + 2I\right)$ are therefore, $\lambda_1 = \frac{2}{7}$ (with algebraic multiplicity = $4$) and $\lambda_2 = 1$ (with algebraic multiplicity = $1$).

Is there any way we can efficiently compute, $\lim _{n \rightarrow \infty} M^{n}$, without calculating eigenvectors i.e., without computing matrices $P$ and $P^{-1}$?

Answer 1

The usual method for this is diagonalisation, but here there's a simpler way because $M$ is of a special form.

Let $J$ be the $5 \times 5$ matrix composed with ones only, so that $J^2=5J$, thus $J^n=5^{n-1}J$ for $n \geq 1$. Then $7M=2I+J$.

Therefore,

$$\begin{aligned} 7^n M^n &=\sum_{k=0}^n {\binom{n}{k} 2^k J^{n-k}}\\ &= 2^nI+\sum_{k=1}^n{\binom{n}{k}2^{n-k}5^{k-1}J}\\ &= 2^nI+\frac{1}{5}\left(\sum_{k=0}^n{\binom{n}{k}2^{n-k}5^k}-2^n\right)J\end{aligned}$$

So $7^nM^n=2^nI-\frac{2^n}{5} J+\frac{(2+5)^n}{5}J$. Thus, $M^n = \frac{J}{5}+\frac{2^n}{7^n}I-\frac{2^n}{5 \cdot 7^n}J$ and $M^n \rightarrow \frac{J}{5}$.

Answer 2

$${\rm M} := \frac27 \, {\rm I}_5 + \frac17 \, {\Bbb 1}_5 {\Bbb 1}_5^\top$$

Since matrix ${\Bbb 1}_5 {\Bbb 1}_5^\top$ is rank-$1$, its nonzero eigenvalue is equal to its trace. Thus, its characteristic polynomial is

$$q (s) := s^4 (s - 5)$$

Hence, the characteristic polynomial of ${\rm M}$ is

$$\det \left( s {\rm I} - {\rm M} \right) = \frac{1}{7^5} q ( 7 s - 2 ) = \cdots = (s-1) \left( s - \frac27 \right)^4$$

Since matrix ${\rm M}$ is stochastic, it has the eigenpair $\left(1, \frac{1}{\sqrt{5}}{\Bbb 1}_5 \right)$. Using the spectral decomposition,

$${\rm M}^k = 1^k \left( \frac{1}{\sqrt{5}}{\Bbb 1}_5 \right) \left( \frac{1}{\sqrt{5}}{\Bbb 1}_5 \right)^\top + \left( \frac27 \right)^k {\rm R}$$

and, thus,

$$\lim {\rm M}^k = 1^{\infty} \left( \frac{1}{\sqrt{5}}{\Bbb 1}_5 \right) \left( \frac{1}{\sqrt{5}}{\Bbb 1}_5 \right)^\top + \left( \frac27 \right)^{\infty} {\rm R} = \color{blue}{\frac15 {\Bbb 1}_5 {\Bbb 1}_5^\top}$$