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

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


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.


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)