General element of a stochastic matrix P^n via eigenvalues

Question

Studying "Markov's Chain" by J.R.Norris, I found the following: given the stochastic matrix $$ \begin{pmatrix} 0 & 1 & 0\\ 0 & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & 0 & \frac{1}{2} \end{pmatrix}$$ we can express $ p_{11}^{(n)} = (P^n)_{11}$ (the element of indeces 1,1 of $P^n$) as combination of the eigenvalues of $P$, mainly $$ p_{11}^n = a+b(i/2)^n + c(-i/2)^n$$ the eigenvalues of $P$ being $1, \pm i/2$. Now, I was asked in an exercise to find $p_{35}^{(n)}$ of the following matrix $$ \begin{pmatrix} 0 & 1 &0 &0 &0 &0 \\ 0 & 1/5 & 4/5 &0 &0 &0 \\ 0 &0 &2/5&3/5 &0 &0\\0 &0 &0 &3/5&2/5 &0\\0 &0 &0 &0&4/5&1/5\\0 &0 &0 &0 &0&1 \end{pmatrix}$$ the eigenvalues being $0,1/5,2/5,3/5,4/5,1$. Looking at the solution, I found $$ p_{35}^{(n)}=a(3/5)^n+b(4/5)+c$$ combination of last three eigenvalues (why?). What I've never studied is why we can do this way. Is the hypothesis of $P$ stochastic necessary or is there a more general result? Can you help? Any reference would do. Thanks

Answer 1

You are probably already familiar with taking matrix powers with diagonalization, but that is the essential reason why the eigenvalues appear.

For a diagonalizable matrix $P$, we can say: $$ P=SDS^{-1}\;\;\;\implies\;\;\;P^n=SD^nS^{-1} $$ where $D$ is the diagonal matrix of eigenvalues. This is why the eigenvalues appear naturally in the output.

So in the case above: $$ p_{35}^{(n)} = 3\left(\frac{2}{5}\right)^n + 3\left(\frac{4}{5}\right)^n - 6\left(\frac{3}{5}\right)^n, $$ I believe.