# How to raise a matrix to the power of $13$ without boring, repetitive multiplication?

how can i show

$\begin{pmatrix}1 & 1 & 1 \\0 & 1 & 1 \\0 & 0 & 1\end{pmatrix}^{13}=\begin{pmatrix}1 & 13 & 91 \\0 & 1 & 13 \\0 & 0 & 1\end{pmatrix}$

Is There any way to calculate to avoid boring calculation

like this :

$\begin{pmatrix}1 & 1 & 1 \\0 & 1 & 1 \\0 & 0 & 1\end{pmatrix}\cdot \begin{pmatrix}1 & 1 & 1 \\0 & 1 & 1 \\0 & 0 & 1\end{pmatrix}=\begin{pmatrix}1 & 2 & 3 \\0 & 1 & 2 \\0 & 0 & 1\end{pmatrix}$

$\begin{pmatrix}1 & 2 & 3 \\0 & 1 & 2 \\0 & 0 & 1\end{pmatrix}\cdot \begin{pmatrix}1 & 1 & 1 \\0 & 1 & 1 \\0 & 0 & 1\end{pmatrix}=\begin{pmatrix}1 & 3 & 6 \\0 & 1 & 3 \\0 & 0 & 1\end{pmatrix}$

$\begin{pmatrix}1 & 3 & 6 \\0 & 1 & 3 \\0 & 0 & 1\end{pmatrix}\cdot \begin{pmatrix}1 & 1 & 1 \\0 & 1 & 1 \\0 & 0 & 1\end{pmatrix}=\begin{pmatrix}1 & 4 & 10 \\0 & 1 & 4 \\0 & 0 & 1\end{pmatrix}$

$\begin{pmatrix}1 & 4 & 10 \\0 & 1 & 4 \\0 & 0 & 1\end{pmatrix}\cdot \begin{pmatrix}1 & 1 & 1 \\0 & 1 & 1 \\0 & 0 & 1\end{pmatrix}=\begin{pmatrix}1 & 5 & 15 \\0 & 1 & 5 \\0 & 0 & 1\end{pmatrix}$

$\begin{pmatrix}1 & 5 & 15 \\0 & 1 & 5 \\0 & 0 & 1\end{pmatrix}\cdot \begin{pmatrix}1 & 1 & 1 \\0 & 1 & 1 \\0 & 0 & 1\end{pmatrix}=\begin{pmatrix}1 & 6 & 21 \\0 & 1 & 6 \\0 & 0 & 1\end{pmatrix}$

$\begin{pmatrix}1 & 6 & 21 \\0 & 1 & 6 \\0 & 0 & 1\end{pmatrix}\cdot \begin{pmatrix}1 & 1 & 1 \\0 & 1 & 1 \\0 & 0 & 1\end{pmatrix}=\begin{pmatrix}1 & 7 & 28 \\0 & 1 & 7 \\0 & 0 & 1\end{pmatrix}$

$\begin{pmatrix}1 & 7 & 28 \\0 & 1 & 7 \\0 & 0 & 1\end{pmatrix}\cdot \begin{pmatrix}1 & 1 & 1 \\0 & 1 & 1 \\0 & 0 & 1\end{pmatrix}=\begin{pmatrix}1 & 8 & 36 \\0 & 1 & 8 \\0 & 0 & 1\end{pmatrix}$

...

• Do you not see a pattern? Jul 30, 2014 at 22:22
• Do you recall Pascal's triangle? Jul 30, 2014 at 22:40
• "Is There any way to calculate to avoid boring calculation?" Yes, outsource the job, which is what you did. :) Jul 30, 2014 at 23:00

Use the matrix binomial theorem: $$(A+B)^n=\sum_{k=0}^n\binom{n}{k}A^{n-k}B^k\ ,$$ which is true provided that $AB=BA$. In this case you could start with $$A=I\ ,\quad B=\pmatrix{0&1&1\cr0&0&1\cr0&0&0\cr}\ ;$$ you will find that $B^3$ is the zero matrix, which makes the above expansion very simple.

Possible hint:

Try to use induction on $n$ to show that:

$$\begin{pmatrix}1 & 1 & 1 \\0 & 1 & 1 \\0 & 0 & 1\end{pmatrix}^{n}=\begin{pmatrix}1 & n & \frac{n(n+1)}{2} \\0 & 1 & n \\0 & 0 & 1\end{pmatrix}$$

• is there any rule for this kind of matrix or lectures which determine those kind of matrix which have that property
– Educ
Jul 30, 2014 at 22:26
• You might want to try looking up Jordan block matrices. Jul 30, 2014 at 22:27
• It is triangular with one, so a quick calc shows you that it will keep that form. As for the exact values, you have to make an educated guess. Jul 30, 2014 at 22:27
• @JimmyK4542 correct me if I'm wrong, but this doesn't look to me like a Jordan block matrix, the upper-right 1 is not adjacent to the diagonal. Feb 15, 2015 at 20:09

The matrix is the sum of the identity and a nilpotent upper triangular matrix, $I + N$ where:

$$N = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix}$$

Since $(I+N)^{13} = I^{13} + 13 I^{12} N + \binom{13}{2} I^{11} N^2 + \binom{13}{3} I^{10}N^3 + \ldots$, it suffices to note:

$$N^2 = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}, N^3 = 0$$

In other words:

$$(I+N)^{13} = I + 13N + 78N^2 = \begin{pmatrix} 1 & 13 & 91 \\ 0 & 1 & 13 \\ 0 & 0 & 1 \end{pmatrix}$$

Another solution is repeated squaring. Strictly speaking this is also repetitive multiplication, but in a much more smart way, so I present it as an answer as well. It only requires 5 matrix multiplications instead of 13.

One just has to realize that

$A^{13} = A^8 A^4 A$

$A^4$ is given by $(A^2)^2$, so two multiplications and $A^8$ is obtained by one additional squaring. Multiplying everything requires another two, which gives 5 total multiplications.

By the way, this works for arbitrary matrices, not only those decomposable in a nilpotent and diagonal component. Also it is very efficient for higher exponents. $A^{1013}$ is doable by hand in not much more time than $A^{13}$.

$A = \begin{pmatrix}0 & 1 & 1 \\0 & 0& 1 \\0 & 0 & 0\end{pmatrix}$, then $A^2 = \begin{pmatrix}0 & 0& 1 \\0 & 0& 0 \\0 & 0 & 0\end{pmatrix}$ and then $A^k = \begin{pmatrix}0 & 0& 0 \\0 & 0& 0 \\0 & 0 & 0\end{pmatrix}$ for $k \geq 3$

Now your matrix is equal to $I + A$, use binomial expression to conclude. That's why you have 13 and 91 = 13 + $\frac{13\times12}{1\times 2}$

A combinatoric perspective follows from writing the matrix multiplication in index notation i.e. $(AB)_{ij}=A_{ik}B_{kj}$ (I'll use the Einstein convention, i.e. doubled indices are summed implicitly.)

Note that the components $A_{ij}$ of your matrix $A$ equal 1 if $i\leq j$ and zero otherwise. Suppose we now take some arbitrary power of $A$; we will obtain

$$(A^{N})_{ij} = A_{i\,n_1}\,A_{i\,n_1}\,A_{i\,n_1}\cdots A_{n_{N-n}\,j}$$ (note the $N-1$ dummy indices.) In order for this product to not vanish, we must have $$i\leq n_1\leq n_2\leq\cdots\leq n_{N-1}\leq j$$ which in particular implies that $(A^N)_{ij}=0$ for $i \leq j$. If $j=i+1$, then there are $N$ ways to choose the $n_i's$: we pick one of the $N$ $"\leq"$ symbols, and take all $n_i$ to the left(right) to be zero (one). Each such set of $n_i's$ contributes a term in the (implied) summation, and so we conclude that $(A^N)_{i,i+1}=N$.

If we instead have $j=i+2$, then we must make two such selections to sort the dummy indices into values of 0,1,2. Therefore there are a total of $\binom{N}{2}=\dfrac{1}{2}N(N+1)$ terms and thus this is the value of $(A^N)_{i,i+2}$ as well.

Note that nowhere in this method was it assumed that the matrix is $3\times 3$. Consequently the approach generalizes; proceeding along the lines set out above, we finally conclude that we have $\boxed{(A^N)_{i,j}=\binom{N}{j-i}}$ as the general result.