Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
Hint: $5-2=3$, $9-5=4$, $14-9=5$, $20-14=6$, $\ldots$ –  njguliyev Oct 21 '13 at 15:08
add comment

2 Answers 2

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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