Find $k^{th}$ power of a square matrix

I am trying to find the $$A^{k}$$, for all $$k \geq 2$$ of a matrix, $$\begin{pmatrix} a & b \\ 0 & 1 \end{pmatrix}$$

My approach:

$$A^{2}=\begin{pmatrix} a^2 & ab+b \\ 0 & 1 \end{pmatrix}$$

$$A^{3}=\begin{pmatrix} a^3 & a^{2}b+ab+b \\ 0 & 1 \end{pmatrix}$$

$$A^{4}=\begin{pmatrix} a^4 & a^{3}b+a^{2}b+ab+b \\ 0 & 1 \end{pmatrix}$$

$$A^{5}=\begin{pmatrix} a^5 & a^{4}b+a^{3}b+a^{2}b+ab+b \\ 0 & 1 \end{pmatrix}$$

Continuing this way, we obtain

$$A^{k}=\begin{pmatrix} a^k & (a^{k-2}+a^{k-3}+a^{k-4}+.....+1)b \\ 0 & 1 \end{pmatrix}$$

I am stuck here! I was wondering if you could give me some hints to move further. I appreciate your time.

• Your new calculations are correct. It should be easy to spot a pattern for induction now.
– user460426
Commented Sep 6, 2019 at 0:35
• Your formula for $A^k$ doesn't quite match what you've written so far. Commented Sep 6, 2019 at 1:46
• Any hints about how to apply induction in matrix setting? Commented Sep 6, 2019 at 2:09
• @Barsal For the base case, verify that the proposed formula for $A^k$ works when $k = 1$. That is, sub in $k = 1$ into the formula, and make sure you get $A$. For the inductive step, multiply the formula for $A^k$ by $A$. It should hopefully simplify to the formula for $A^{k+1}$. Commented Sep 6, 2019 at 2:37
• Thank you so much! Commented Sep 6, 2019 at 2:47

Hint: Write $$A=D+B$$ here $$D$$ is diagonal. Use that $$B^2=0$$, $$DB=aB$$, $$BD=B$$.

Writing $$A^n$$ as $$\begin{bmatrix}a^n & b_n\\ 0 & 1\end{bmatrix}$$. Expanding $$A^{n+1} = AA^n$$ leads to a recurrence relation of the form: $$b_{n+1} = a b_n + b$$ Since $$b_1 = b$$, solving the recurrence relation will lead to $$b_n = (a^{n-1}+ a^{n-2} + \cdots + 1)b = \begin{cases} \frac{a^n-1}{a-1} b, & a \ne 1\\ nb, & a = 1\end{cases}$$

Not the best way, but you could also try diagonalisation. The caveat with diagonalisation is that for certain values of $$a$$ and $$b$$ (in particular, if $$a = 1$$ and $$b \neq 0$$), the matrix won't be diagonalisable. However, if we make the assumption that $$a \neq 1$$, then we should end the process with a perfectly valid expression for $$A^n$$ that will work for all $$a \neq 1$$, and by continuity, we can conclude that it works for $$a = 1$$ too (or take the formula, and prove by induction).

Also, I know you want hints, so I hid everything behind spoiler boxes.

The eigenvalues are $$1$$ and $$a$$, and we will assume they are different. We have,

$$A - I = \begin{pmatrix} a - 1 & b \\ 0 & 0 \end{pmatrix},$$

with eigenvector $$(-b, a - 1)$$. Also,

$$A - aI = \begin{pmatrix} 0 & b \\ 0 & 1 - a \end{pmatrix},$$

with eigenvector $$(1, 0)$$. So, let

$$P = \begin{pmatrix} 1 & -b \\ 0 & a - 1\end{pmatrix},$$

giving us

$$P^{-1} = \frac{1}{a - 1}\begin{pmatrix} a - 1 & b \\ 0 & 1\end{pmatrix}.$$

We should have

$$A = P\begin{pmatrix} a & 0 \\ 0 & 1\end{pmatrix}P^{-1},$$

so

\begin{align*} A^n &= P\begin{pmatrix} a^n & 0 \\ 0 & 1\end{pmatrix}P^{-1} \\ &= \frac{1}{a - 1}\begin{pmatrix} 1 & -b \\ 0 & a - 1\end{pmatrix}\begin{pmatrix} a^n & 0 \\ 0 & 1\end{pmatrix}\begin{pmatrix} a - 1 & b \\ 0 & 1\end{pmatrix} \\ &= \frac{1}{a - 1}\begin{pmatrix} 1 & -b \\ 0 & a - 1\end{pmatrix}\begin{pmatrix} a^{n+1} - a^n & ba^n \\ 0 & 1\end{pmatrix} \\ &= \frac{1}{a - 1}\begin{pmatrix} a^{n+1} - a^n & ba^n - b \\ 0 & a - 1\end{pmatrix} \\ &= \begin{pmatrix} a^n & b \frac{a^n - 1}{a - 1} \\ 0 & 1\end{pmatrix} \\ &= \begin{pmatrix} a^n & b(1 + a + a^2 + \ldots + a^{n-1}) \\ 0 & 1\end{pmatrix}.\end{align*}

That last formula must hold (at least) for $$a \neq 1$$, but due to the continuity of matrix powers, it must also hold at $$a = 1$$ too.

Hint: Use Cayley–Hamilton: $$A^2-(a+1)A+aI=0$$.

• I got the same results using Caley-Hamilton. Then what will be next step? Commented Sep 6, 2019 at 0:18
• I guess, this method is not a good one for finding large powers of A. Commented Sep 6, 2019 at 0:19
• @Barsal, it is. Just reduce $A^2$ every time. Try the first few powers and you'll see a pattern.
– lhf
Commented Sep 6, 2019 at 0:25
• @Barsal You can use Cayley-Hamilton to show that $A^k=\lambda I+\mu A$ and then use that this also holds when you substitute an eigenvalue of $A$ for $A$ in that equation to solve for the coefficients.
– amd
Commented Sep 6, 2019 at 2:04

To add on to lhf's hints, do you know induction? If so, try to find patterns in each of the 4 entries individually once you have corrected your examples.

• Yeah! I am looking for some pattern to apply induction. Commented Sep 6, 2019 at 0:11
• You should find patterns in the upper left, lower left, and lower right corners. Can you see those? The upper right is a bit trickier Commented Sep 6, 2019 at 0:22
• That's true! I am thinking something like, $A^{}=\begin{pmatrix} a^k & a^{k-2}b+a^{k-3}b+....+2ab+b \\ 0 & 1 \end{pmatrix}$ Commented Sep 6, 2019 at 0:27
• That looks close! Maybe retry on $A^3$ again though? I'm getting something different Commented Sep 6, 2019 at 0:28
• $A^{k}=\begin{pmatrix} a^k & a^{k-2}b+a^{k-3}b+a^{k-4}b+.....+b \\ 0 & 1 \end{pmatrix}$ Is it okay now? Commented Sep 6, 2019 at 0:36

I'm partial to the SVD for this. The eigenvalues are $$a$$ and $$1$$ associated with eigenvectors $$(1,0)$$ and $$(b,1-a)$$ respectively.

So, we get

$$\begin{bmatrix} a & b \\ 0 & 1 \end{bmatrix}^n= \begin{bmatrix} 1 & b \\ 0 & 1-a \end{bmatrix} \begin{bmatrix} a^n & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & \frac{-b}{1-a} \\ 0 & \frac{1}{1-a} \end{bmatrix} = \begin{bmatrix} a^n & \frac{b(1-a^n)}{1-a} \\ 0 & 1 \end{bmatrix}$$