Power of Stochastic Matrix

Given the stochastic matrix $$Q = \begin{pmatrix}0&2/3&1/3\\1/3&0&2/3\\2/3&1/3&0\\\end{pmatrix}\in \mathbb{R}^{3\times3}$$ I wish to compute $Q_{1,1}^n$ (the entry in the first row and first column) for $n\in \mathbb{N}$.

I did so by diagonalizing $Q=PDP^{-1}\implies Q^n=PD^nP^{-1}$. The computation of the (complex) eigenvectors however takes time.

Is there a more elegant way to find $Q_{1,1}^n$?

Solution 1:

Following the comment by @kimchi lover, since the matrix is stochastic and circulant, the eigenvalues are $1, \lambda = \frac{2}{3} e^{2 \pi i/3} + \frac{1}{3} e^{4 \pi i/3} = \frac{1}{2}\left(-1 + \frac{i}{\sqrt{3}} \right)$, and $\overline{\lambda} = \frac{1}{2}\left(-1 - \frac{i}{\sqrt{3}} \right)$. Thus $D^n = \text{diag} \, (1, \lambda^n, \bar{\lambda}^n)$.

The matrix $P$ of eigenvectors is a Fourier matrix, with entries $P_{k\ell} = \frac{1}{3} e^{2(k-1)(\ell-1) \pi i/3}$, and $P^{-1} = P$.

Note that $\lambda^6 = - \frac{1}{27}$, thus $\lambda^n = \left( \frac{-1}{27} \right)^k \lambda^\ell$ if $n = 6k + \ell$. So you only have to find $\lambda^2, \dots, \lambda^5$.

Also note that $P_{1\ell} = P_{\ell 1} = \frac{1}{\sqrt{3}}$ for all $\ell$.

Then $$ Q^n_{1,1} = P_{11}^2 + \lambda^n P_{12}^2 + \bar{\lambda}^n P_{13}^2 = \frac{1}{3} \left(1 + 2 \, \Re \, \lambda^n \right) $$ The answer can then be worked out explicitly. Since $|\lambda| < 1$, this also shows explicitly that $Q_{1,1} \to \frac{1}{3}$ as $n \to \infty$.