5
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ Your new calculations are correct. It should be easy to spot a pattern for induction now. $\endgroup$ – Flowsnake Sep 6 '19 at 0:35
  • 1
    $\begingroup$ Your formula for $A^k$ doesn't quite match what you've written so far. $\endgroup$ – Theo Bendit Sep 6 '19 at 1:46
  • $\begingroup$ Any hints about how to apply induction in matrix setting? $\endgroup$ – Simpson's Paradox Sep 6 '19 at 2:09
  • 2
    $\begingroup$ @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}$. $\endgroup$ – Theo Bendit Sep 6 '19 at 2:37
  • $\begingroup$ Thank you so much! $\endgroup$ – Simpson's Paradox Sep 6 '19 at 2:47
5
$\begingroup$

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

$\endgroup$
0
5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I got the same results using Caley-Hamilton. Then what will be next step? $\endgroup$ – Simpson's Paradox Sep 6 '19 at 0:18
  • $\begingroup$ I guess, this method is not a good one for finding large powers of A. $\endgroup$ – Simpson's Paradox Sep 6 '19 at 0:19
  • 1
    $\begingroup$ @Barsal, it is. Just reduce $A^2$ every time. Try the first few powers and you'll see a pattern. $\endgroup$ – lhf Sep 6 '19 at 0:25
  • $\begingroup$ @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. $\endgroup$ – amd Sep 6 '19 at 2:04
2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Yeah! I am looking for some pattern to apply induction. $\endgroup$ – Simpson's Paradox Sep 6 '19 at 0:11
  • 1
    $\begingroup$ 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 $\endgroup$ – TomGrubb Sep 6 '19 at 0:22
  • $\begingroup$ 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}$ $\endgroup$ – Simpson's Paradox Sep 6 '19 at 0:27
  • 3
    $\begingroup$ That looks close! Maybe retry on $A^3$ again though? I'm getting something different $\endgroup$ – TomGrubb Sep 6 '19 at 0:28
  • $\begingroup$ $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? $\endgroup$ – Simpson's Paradox Sep 6 '19 at 0:36
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.