1

Given a matrix $ A = \begin{pmatrix} 1 && 1 && 2 \\ 0 && 1 && 1 \\ 0 && 0 && 1 \end{pmatrix}$ determine the general formula for $A^k$ . I tried to solve it by induction and therefore computed the first steps up to $A^4$. The diagonal seems to stay constantly at 1, while $a_{12}$ and $a_{23}$ are equal to $k$. What I can't figure out is $a_{13}$. I've computed it for $A, A^2, A^3, A^4$ and the values are $2, 5, 9, 14, 20$.

How can I find the general pattern and prove it? Is there a general algorithm for finding $A^k$ where $A \in M_{i,j}(C)$ where M is the set of all matrixes that can be formed with elements from $C$.

andreas.vitikan
  • 1,140

2 Answers2

5

Note that your matrix $A$ has a special form, we have $A = \def\Id{\mathop{\rm Id}\nolimits}\Id{} + N$, where $N$ is a strictly upper triagonal matrix. Hence $N^3 = 0$, an therefore, by the binomial theorem (note $\Id$ and $N$ commute): $$ A^k = (\Id + N)^k = \sum_{i=0}^k \binom ki N^i \Id^{k-i} = \Id + kN + \frac{k(k-1)}2 N^2 $$ In general (look for Jordan normal form) you can write any matrix $A \in \mathbb C^{n\times n}$ as $A = S^{-1}(\Lambda + N)S$ where $S$ is invertible, $\Lambda$ diagonal, $N$ has only $1$ as entries and only on the first superdiagonal, and $\Lambda N = N \Lambda$.

martini
  • 84,101
0

Note that the space of upper triangular matrices is closed under multiplication, so we need only worry about $[A^{k}]_{ij}$ for $i\le j$. Then just work out the relevant difference equations.

We have $[A^{k}]_{ii} = 1$, $[A^{k+1}]_{12} = [A^{k}]_{12} + 1$, $[A^{k+1}]_{21} = [A^{k}]_{21} + 1$, $[A^{k+1}]_{13} = [A^{k}]_{13} + [A^{k}]_{12}+ 2$.

The second and third equations shows that $[A^{k}]_{12} = [A^{k}]_{21} = k$, so the fourth equation becomes $[A^{k+1}]_{13} = [A^{k}]_{13} + k+ 2$, from which we get $[A^{k}]_{13} = \frac{1}{2}k(3+k)$.

Regarding a general algorithm, it depends on what you are asking. From a numerical perspective, the answer is that there is no known general formula (other than repeated squaring, and similar schemes). From a theoretical perspective, the Jordan form can be used to compute a formula (cf. http://en.wikipedia.org/wiki/Jordan_normal_form#Powers).

copper.hat
  • 172,524