Finding $n$-th power of transition matrix Is there any shortcut to find $P^{n}=\begin{pmatrix} 1-p & p \\ q & 1-q \end{pmatrix}^n$ quickly and elegantly? 
This type of matrix often comes up while dealing with Markov chains. Diagonalization takes way too much time. I need to find eigenvalues, eigenvectors and all that...
 A: Hint
Let $$J=\begin{pmatrix}0&1\\1&0 \end{pmatrix}$$.
Then $$P=(1-q) I +p J$$
And $$[J,I]=0$$ so you can use the standard binomial development and use $J^2=I$.

To be more precise as $JI=IJ$ you have:
$$P^n= \left( (1-q) I +p J \right)^n=\sum_{k=0}^n \begin{pmatrix} n \\k\end{pmatrix}(1-q)^k p^{n-k} I^k J^{n-k}$$
and:
$$J^m = \begin{cases} J \text{ if } m \text{ is odd}\\I \text{ if } m \text{ is even.} \end{cases}$$
A: Let $S$ be the matrix
$$
S=
\begin{bmatrix}
1&p\\1&-q
\end{bmatrix}
\ ,
$$
which has on the columns the eigenvectors to the eigenvalues $1, 1-p-q$. Then
$$
\begin{aligned}
S^{-1}PS &=
\begin{bmatrix}
1&0\\0&1-p-q
\end{bmatrix}
\ ,
\\
P &=
S
\begin{bmatrix}
1&0\\0&1-p-q
\end{bmatrix}
S^{-1}\ ,
\\[2mm]
&\qquad\text{ so }
\\[2mm]
P^n &=
S
\begin{bmatrix}
1^n&0\\0&(1-p-q)^n
\end{bmatrix}
S^{-1}\ .
\end{aligned}
$$
A: The eigenvalues are $1, -(p+q-1)$
$P = \frac {1}{p+q}\begin{bmatrix} 1&-p\\1&q \end{bmatrix}\begin{bmatrix} 1\\&-(p+q-1) \end{bmatrix}\begin{bmatrix} q&p\\-1&1 \end{bmatrix}\\
P^n= \frac {1}{p+q}\begin{bmatrix} 1&-p\\1&q \end{bmatrix}\begin{bmatrix} 1\\&\lambda^n \end{bmatrix}\begin{bmatrix} q&p\\-1&1 \end{bmatrix}\\
P^n =\frac {1}{p+q}\begin{bmatrix} q+p\lambda^n&p(1-\lambda^n)\\q(1-\lambda)^n&p+q\lambda^n \end{bmatrix} $
A: If a $2x2$ real matrix $A$ has distinct real eigenvalues $\lambda_1$ and $\lambda_2$, it can be split into a linear combination of projections onto its eigenspaces $A=\lambda_1P_1+\lambda_2P_2$ with $P_1P_2=P_2P_1=0$. Since any projection is idempotent, with this decomposition we have $A^n = \lambda_1^nP_1+\lambda_2^nP_2$. The two projection matrices for this decomposition are $$P_1 = {A-\lambda_2 I \over \lambda_1-\lambda_2} \\ P_2 = {A-\lambda_1 I\over \lambda_2-\lambda_1}.$$ The eigenvalues of your matrix $P$ are easily found by inspection: $1$ is always an eigenvalue of a stochastic matrix and the other is $\operatorname{tr}P-1=1-p-q$. Assuming that $p$ and $q$ are both nonzero, applying the above decomposition to $P$ gives $$P^n = \begin{bmatrix}{q\over p+q} & {p\over p+q} \\ {q\over p+q} & {p\over p+q} \end{bmatrix} + (1-p-q)^n \begin{bmatrix}{p\over p+q} & -{p\over p+q} \\ -{q\over p+q} & {q\over p+q}\end{bmatrix}.$$
