# Why does this algorithm work?

Given a matrix, $P$, why does finding its eigenvalues, say they are $\{\lambda_1, \lambda_2\}$ then the general form of $p_{ij}^{(n)}=A_{ij}\lambda_1^n+B_{ij}\lambda_2^n$? Thanks.

Added: Context: $P$ is a transition matrix

-
Sorry, but a question about $p_{ij}^{(n)}$ what is it? element of the matrix $P^n$? And what are $A$ and $B$ some numbers right? – maximus Oct 12 '11 at 8:37
@maximus: You are right on both. :) – doob Oct 12 '11 at 8:37
No indexes like $i$ and $j$ in the $p_{ij}^{(n)}$ formula? So every element of the matrix has the same value? – maximus Oct 12 '11 at 8:45
@maximus: Edited – doob Oct 12 '11 at 8:58

If $P$ is a $2\times2$ matrix with eigenvalues $\lambda_1\ne\lambda_2$ then $P=QDQ^{-1}$ where $Q$ is the matrix whose columns are the eigenvectors of $P$ and $D=\pmatrix{\lambda_1&0\cr0&\lambda_2\cr}$. So $P^n=QD^nQ^{-1}$, and $D^n=\pmatrix{\lambda_1^n&0\cr0&\lambda_2^n\cr}$. Can you take it from there?
@doob: Note that this works only for $2\times2$ matrices. General stochastic matrices aren't necessarily diagonalizable. For instance, $$\pmatrix{\frac12&0&0\\\frac12&\frac12&0\\0&\frac12&1}$$ has an eigenvalue $1/2$ with algebraic multiplicity $2$ and geometric multiplicity $1$; it does not have $3$ linearly independent eigenvectors. – joriki Oct 12 '11 at 10:01
Thanks, Gerry and @joriki. I am not quite sure how the $P^n=QD^nQ^{-1}$ mechanism works. My guess is that we are changing the axes of the coordinate system so that we get that diagonal matrix of eigenvalues$^n$. But then we need to change back to the original frame and then...? – doob Oct 12 '11 at 11:59
@doob: when you change it back, you already change it for $D^n$ which you calculated and which contains only powers of eigenvalues on its diagonal. So, when you change coordinate system back, you get that in the original coordinates entries of stochastic matrix are linear combinations of powers of eigenvalues. My explanation may be quite unclear, however your question is not so clear for me as well, so I tried to catch its sense. – Ilya Oct 12 '11 at 12:21