22
$\begingroup$

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.

$\endgroup$
35
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ It seemed more in line with what the OP had been trying. It would also let the OP see if their approach (and the powers of the matrix) were correct. $\endgroup$ – Ian Miller Jan 2 '17 at 1:28
  • 2
    $\begingroup$ This is a great approach to "guess the formula" (and it is enough for any practical purpose), but it is not enough to constitute a proof. Could you please make it complete (or at least mention in the body that it still needs a proof)? $\endgroup$ – dtldarek Jan 2 '17 at 9:57
37
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for your answer, interesting because it takes a different approach to my original idea, I will study it. $\endgroup$ – Trevör Jan 2 '17 at 12:06
28
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Thank you so much for your answer, interesting because it takes a different approach than my original idea, I will study it. $\endgroup$ – Trevör Jan 2 '17 at 12:06
15
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ An essential point is that the matrices commute $\endgroup$ – Rene Schipperus Jan 2 '17 at 2:29
  • $\begingroup$ @ReneSchipperus : It's not really essential. The essential thing is that the vector space generated by the matrices is an algebra: $\forall X,Y\in Vect(I, A, B), XY \in Vect(I, A, B)$ (which is equivalent to $\forall X,Y\in \{I, A, B\}, XY \in Vect(I, A, B)$, because it's a vector space and you can use distributivity). In the general case, you would us the algebra of upper-triangular matrices, compute the coefficients on the diagonal, then right above the diagonal and keep going, and you'll only need the values already computed because the matrices are upper triangular. $\endgroup$ – xavierm02 Jan 2 '17 at 13:17
11
$\begingroup$

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

 enter image description here

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*}

$\endgroup$
6
$\begingroup$

Using symmetry, write the recurrence relation

$$\begin{pmatrix} a_{n+1} & b_{n+1}&c_{n+1}\\ 0 & a_{n+1} & b_{n+1}\\ 0 & 0 &a_{n+1} \end{pmatrix}= \begin{pmatrix} 1 & 2&3\\ 0 & 1 & 2\\ 0 & 0 &1 \end{pmatrix} \begin{pmatrix} a_{n} & b_{n}&c_{n}\\ 0 & a_{n} & b_{n}\\ 0 & 0 &a_{n} \end{pmatrix}.$$

Then $$\begin{cases}a_{n+1}=a_n\\ b_{n+1}=b_n+2a_n\\ c_{n+1}=c_n+2b_n+3a_n.\end{cases}$$

We solve with

$$a_n=Cst=1,\\b_n=2(n-1)+Cst=2n,\\ c_n=4t_{n-1}+3(n-1)+Cst=2n^2+n,$$

where $t_n$ denotes a triangular number, using the initial conditions $a_1=1,b_1=2,c_1=3$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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