2

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.

Martund
  • 14,706
  • 2
  • 13
  • 30
  • There is a formula with $a,b,c,d$ but it's very combinatorial, while formula based on eigenvalues is more straightforward. https://www.jstor.org/stable/10.4169/math.mag.88.4.280?seq=1 – zwim Feb 16 '20 at 10:15
  • May the downvoter be kind enough to justify, so that I can put a better question next time?? – Martund Feb 16 '20 at 13:58

2 Answers2

2

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$.

user1551
  • 139,064
  • How would you prove that $2(A-\alpha I)q(A)+(A-\alpha I)^2q'(A)=0$ if both of the eigen values of $A$ are $\alpha$?? – Martund Feb 16 '20 at 17:21
  • @Martund That isn't necessarily zero and it is not my intention to prove that it's zero. When $\alpha=\beta$, the two equations in $(2)$ become identical and we are one equation short. The purpose of the equality $nx^{n-1}=2(x-\alpha)q(x)+(x-\alpha)^2q'(x)+r'(x)$ is to provide an additional equation that lets us determine $a$ and $b$. Once $a$ and $b$ is found (regardless of whether $\alpha=\beta$ or $\alpha\ne\beta$), since $x^n=(x-\alpha)(x-\beta)q(x)+r(x)$, we have $A^n=r(A)=aA+bI$. – user1551 Feb 16 '20 at 18:19
  • Nice answer, thank you very much! – Martund Feb 17 '20 at 00:37
0

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.

G Tony Jacobs
  • 31,218