Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
Hint: $5-2=3$, $9-5=4$, $14-9=5$, $20-14=6$, $\ldots$ – njguliyev Oct 21 '13 at 15:08

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|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


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.