Compute the $n$-th power of triangular $3\times3$ matrix

I have the following matrix

$$ \begin{bmatrix} 1 & 2 & 3\\ 0 & 1 & 2\\ 0 & 0 & 1 \end{bmatrix} $$

and I am asked to compute its $n$-th power (to express each element as a function of $n$). I don't know at all what to do. I tried to compute some values manually to see some pattern and deduce a general expression but that didn't gave anything (especially for the top right). Thank you.

Solution 1:

Write this matrix as follows: \begin{equation} \left[ \begin{matrix} 1 & 2&3\\ 0 & 1 & 2\\ 0 & 0 &1 \end{matrix} \right] = I + 2 J+ 3 J^{2}. \end{equation} where \begin{equation} I = \left[ \begin{matrix} 1 & & \\ &1 & \\ & & 1 \end{matrix} \right], ~ J = \left[ \begin{matrix} 0& 1 &0 \\ 0 &0 & 1 \\ 0 & 0& 0 \end{matrix} \right],~ J^2 = \left[ \begin{matrix} 0& 0 &1\\ 0 & 0 &0\\ 0& 0 & 0 \end{matrix} \right], ~ J^{3}=0. \end{equation} With this relation you can expand the power of the matrix into sum of $I$, $J$ and $J^2$.

Solution 2:

Computing the first few powers should allow you to find a pattern for the terms. Below are some terms:

$$\left(\begin{matrix}1 & 2 & 3\\0 & 1 & 2\\0 & 0 & 1\end{matrix}\right), \left(\begin{matrix}1 & 4 & 10\\0 & 1 & 4\\0 & 0 & 1\end{matrix}\right), \left(\begin{matrix}1 & 6 & 21\\0 & 1 & 6\\0 & 0 & 1\end{matrix}\right), \left(\begin{matrix}1 & 8 & 36\\0 & 1 & 8\\0 & 0 & 1\end{matrix}\right), \left(\begin{matrix}1 & 10 & 55\\0 & 1 & 10\\0 & 0 & 1\end{matrix}\right), \left(\begin{matrix}1 & 12 & 78\\0 & 1 & 12\\0 & 0 & 1\end{matrix}\right)$$

All but the top right corner are trivial so lets focus on that pattern. (Although if you look at it carefully you should recognize the terms.)

Terms: $3,10,21,36,55,78$

First difference: $7, 11, 15, 19, 23$

Second difference: $4, 4, 4, 4$

As the second difference is a constant the formula must be a quadratic. As the second difference is 4 then it is in the form $2n^2+bn+c$. Examining the pattern gives formula of $2n^2+n=n(2n+1)$.

So the $n^{th}$ power is given by:

$$\left(\begin{matrix}1 & 2n & n(2n+1)\\0 & 1 & 2n\\0 & 0 & 1\end{matrix}\right)$$

The reason I said you should recognize the pattern is because it is every second term out of this sequence: $1,3,6,10,15,21,27,37,45,55,66,78,\cdots$ which is the triangular numbers.

Solution 3:

Define

$$J = \begin{bmatrix} 0 & 2 & 3\\ 0 & 0 & 2\\ 0 & 0 & 0 \end{bmatrix} $$

so that the problem is to compute $(I+J)^n$. The big, important things to note here are

• $I$ and $J$ commute
• $J^3 = 0$

which enables the following powerful tricks: the first point lets us expand it with the binomial theorem, and the second point lets us truncate to the first few terms:

$$ (I+J)^n = \sum_{k=0}^n \binom{n}{k} I^{n-k} J^k = I + nJ + \frac{n(n-1)}{2} J^2 $$

More generally, for any function $f$ that is analytic at $1$, (such as any polynomial), if you extend it to matrices via Taylor expansion, then under the above conditions, its value at $I+J$ is given by

$$ f(I+J) = \sum_{k=0}^\infty f^{(k)}(1) \frac{J^k}{k!} = f(1) I + f'(1) J + \frac{1}{2} f''(1) J^2 $$

As examples of things whose result you can check simply (so you can still use the method even if you're uncomfortable with it, because you can check the result), you can compute the inverse by

$$ (I+J)^{-1} = I - J + J^2 = \begin{bmatrix} 1 & -2 & 1\\ 0 & 1 & -2\\ 0 & 0 & 1 \end{bmatrix} $$

and if you want a square root, you can get

$$\sqrt{I+J} = I + \frac{1}{2} J - \frac{1}{8} J^2 = \begin{bmatrix} 1 & 1 & 1\\ 0 & 1 & 1\\ 0 & 0 & 1 \end{bmatrix} $$

(These are actually special cases of $(I+J)^n$ by the generalized binomial theorem for values of $n$ that aren't nonnegative integers)

Solution 4:

Let $I=\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}$, $A=\begin{pmatrix}0&1&0\\0&0&1\\0&0&0\end{pmatrix}$ and $B=\begin{pmatrix}0&0&1\\0&0&0\\0&0&0\end{pmatrix}$. Then $M=I+2A+3B$.

You can prove that for any $n$, $M^n$ can be written as $M^n=\lambda_n I + a_n A + b_n B$ (because it's upper triangular and the symmetry along the ascending diagonal will remain).

So $M^{n+1}=M^nM=(\lambda_n I + a_n A + b_n B) (I + 2A + 3B) = \dots$

Using this, compute $\lambda_n$, and then $a_n$ and finally $b_n$.

Solution 5:

Here is another variation based upon walks in graphs.

We interpret the matrix $A=(a_{i,j})_{1\leq i,j\leq 3}$ with \begin{align*} A= \begin{pmatrix} 1 & 2 & 3\\ \color{grey}{0} & 1 & 2\\ \color{grey}{0} & \color{grey}{0} & 1 \end{pmatrix} \end{align*} as adjacency matrix of a graph with three nodes $P_1,P_2$ and $P_3$ and for each entry $a_{i,j}\neq 0$ with a directed edge from $P_i$ to $P_j$ weighted with $a_{i,j}$.

 

Note: When calculating the $n$-th power $A^n=\left(a_{i,j}^{(n)}\right)_{1\leq i,j\leq 3}$ we can interpret the element $a_{i,j}^{(n)}$ of $A^n$ as the number of (weighted) paths of length $n$ from $P_i$ to $P_j$. The entries of $A=(a_{i,j})_{1\leq i,j\leq 3}$ are the weighted paths of length $1$ from $P_i$ to $P_j$.

See e.g. chapter 1 of Topics in Algebraic Combinatorics by Richard P. Stanley.

Let's look at the corresponding graph and check for walks of length $n$.

• We see there are no directed edges from $P_2$ to $P_1$ and no directed edges from $P_3$ to $P_2$ and from $P_3$ to $P_1$ which implies there are no walks of length $n$ either. So, $A^n$ has due to the specific triangle structure of $A$ necessarily zeroes at the same locations as $A$. \begin{align*} A^n= \begin{pmatrix} . & . & .\\ \color{grey}{0} & . & .\\ \color{grey}{0} & \color{grey}{0} & . \end{pmatrix} \end{align*}

• It is also easy to consider the walks of length $n$ from $P_i$ to $P_i$. There is only one possibility to loop along the vertex weighted with $1$ from $P_i$ to $P_i$ and so the entries $a_{i,i}^{(n)}$ are \begin{align*} 1\cdot 1\cdot 1\cdots 1 = 1^n=1 \end{align*} and we obtain \begin{align*} A^n= \begin{pmatrix} 1& . & .\\ \color{grey}{0} & 1 & .\\ \color{grey}{0} & \color{grey}{0} & 1 \end{pmatrix} \end{align*}

and now the more interesting part

• $P_1$ to $P_2$:

  The walks of length $n$ from $P_1$ to $P_2$ can start with zero or more loops at $P_1$ followed by a step (weigthed with $2$) from $P_1$ to $P_2$ and finally zero or more loops at $P_2$. All the loops are weighted with $1$. There are $n$ possibilities to walk this way \begin{align*} a_{1,2}^{(n)}=2\cdot 1^{n-1}+1\cdot 2\cdot 1^{n-2}+\cdots +1^{n-2}\cdot 2\cdot 1+1^{n-1}\cdot 2=2n \end{align*}

• $P_2$ to $P_3$:

  Symmetry is trump. When looking at the graph we observe the same situation as before from $P_1$ to $P_2$ and conclude

\begin{align*} a_{2,3}^{(n)}=2n \end{align*}

• $P_1$ to $P_3$:

  Here are two different types of walks of length $n$ possible. The first walk uses the weight $3$ edge from $P_1$ to $P_3$ as we did when walking from $P_1$ to $P_2$ along the weight $2$ edge. This part gives therefore \begin{align*} 3\cdot 1^{n-1}+1\cdot 3\cdot 1^{n-2}+\cdots +1^{n-2}\cdot 3\cdot 1+1^{n-1}\cdot 3=3n\tag{1} \end{align*} The other type of walk of length $n$ uses the hop via $P_2$. We observe it is some kind of concatenation of walks as considered before from $P_1$ to $P_2$ and from $P_2$ to $P_3$. In fact there are $\binom{n}{2}$ possibilities to place two $2$'s in a walk of length $n$. All other steps are loops at $P_1,P_2$ and $P_3$ and we obtain \begin{align*} \binom{n}{2}\cdot 2\cdot 2=2n(n-1)\tag{2} \end{align*} Summing up (1) and (2) gives \begin{align*} a_{1,3}^{(n)}=3n+2n(n-1)=n(2n+1) \end{align*}

and we finally obtain

\begin{align*} A^n=\left(a_{i,j}^{(n)}\right)_{1\leq i,j\leq 3}=\begin{pmatrix} 1& 2n & n(2n+1)\\ \color{grey}{0} & 1 & 2n\\ \color{grey}{0} & \color{grey}{0} & 1 \end{pmatrix} \end{align*}