Formula for powers of $2\times 2$ matrices

Question

Is there a formula for expanding powers of $2\times 2$ matrices? I know that can be done by diagonalizing and then using the spectral decomposition of the matrix, but is there a general formula for $A^n$ in terms of $a,b,c$ and $d$, where $$A=\pmatrix{a&b\\c&d}$$ In the problem I am working on, $A$ is a stochastic matrix, i.e. all entries are non-negative and the row sum is $1$ for each row. I know such a formula exists for stochastic matrices that can be proved by induction, but what I really don't understand is the intuition for guessing that general formula.

Please tell me

1) Whether there is a general formula for powers all $2\times2$ matrices, and

2) Intuition for how to guess the general formula for powers in the special case of a stochastic matrix.

EDIT

As pointed out by zwim in comment, there is a formula for powers of general $2\times 2$ matrices, but that is very cumbersome. From the link he provides, we can see the general formula in terms of the eigen values $\alpha$ and $\beta$ of matrix $A$: $$A^n = \begin{cases}\alpha^n\left(\dfrac{A-\beta I}{\alpha-\beta}\right)+\beta^n\left(\dfrac{A-\alpha I}{\beta-\alpha}\right),&\text{ if }\alpha\ne\beta\\\alpha^{n-1}(nA-(n-1)\alpha I), &\text{ if }\alpha=\beta\end{cases}$$ I proved this by induction. So the new question is: Can you please provide intuition behind this guess for induction?

Some other proof of this formula without induction is also welcome.

Answer 1

The result for the first case (namely, $\alpha\ne\beta$) can be viewed as a direct consequence of Lagrange interpolation, but a wholesome approach to tackle both the case $\alpha\ne\beta$ and the case $\alpha=\beta$ is to divide $x^n$ by the characteristic polynomial $(x-\alpha)(x-\beta)$ of $A$ and then apply the factor theorem.

If we divide $x^n$ by $(x-\alpha)(x-\beta)$, the remainder is a constant or linear polynomial. That is, $$ x^n=(x-\alpha)(x-\beta)q(x)+r(x)\tag{1} $$ for some polynomials $q$ and $r(x)=ax+b$. By Cayley-Hamilton theorem, $(A-\alpha I)(A-\beta I)=0$. Therefore $(1)$ gives $A^n=r(A)=a+bI$ and the problem reduces to finding $a$ and $b$.

When $\alpha\ne\beta$, by substituting $x=\alpha$ and $x=\beta$ into $(1)$, we get \begin{cases} \alpha^n=r(\alpha)=a\alpha+b,\tag{2}\\ \beta^n=r(\beta)=a\beta+b. \end{cases} Solve them for $a$ and $b$, we get the relevant result.

When $\alpha=\beta$, differentiate $(1)$ to get $nx^{n-1}=2(x-\alpha)q(x)+(x-\alpha)^2q'(x)+r'(x)$. Therefore we can obtain $a$ immediately: $$ n\alpha^{n-1}=r'(\alpha)=a.\tag{3} $$ Substitute $(3)$ into $(2)$, we also obtain $b$.

Answer 2

Taking a different approach, it is straightforward to write down a recurrence relation for the powers of a matrix $A$. We can write down the characteristic equation for $A$, which is quadratic when a is $2\times 2$, and by the Cayley Hamilton Theorem, the matrix $A$ satisfies that same polynomial. Suppose our characteristic equation is: $$\lambda^2 + p\lambda + q=0$$ Then we have: $$A^n = -pA^{n-1}-qA^{n-2}, n\ge 2$$ This equation, being linear in the powers of $A$, applies to its individual entries as well, so once you know $A$ and $A^2$, you can produce the others as quick linear combinations, or just produce the sequence for one particular entry of the higher powers, or just one row, or just one column – whatever you need.