I need to calculate $x^{50}$ [duplicate]

Solution 1:

This is a very elementary approach based on finding the general form. If we do $x^2$, we find $$x^2=\begin{pmatrix}1&0&0\\1&1&0\\1&0&1\end{pmatrix},~~x^4=\begin{pmatrix}1&0&0\\2&1&0\\2&0&1\end{pmatrix}$$ so I guess that we have $$x^{2k}=\begin{pmatrix}1&0&0\\k&1&0\\k&0&1\end{pmatrix}$$ An inductive approach adimits this general form is valid for integers $k>0$.

Solution 2:

Start by computing $X^2 = \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}$.

Since $X^2 = I + N$ where $N^2 = 0$, and what you ask for is $(X^2)^{25} = I^{25} + 25I^{24}N + (\ldots)N^2$, the answer may be found by inspection:

$$ X^{50} = I + 25N $$

Solution 3:

The graph with adjacency matrix $$x:=\begin{pmatrix}1&0&0\\1&0&1\\0&1&0\end{pmatrix}$$ is drawn below:

For $i,j \in \{1,2,3\}$, the element in cell $(i,j)$ in $x^{50}$ is the number of walks from vertex $i$ to vertex $j$ of length $50$ in the above graph.

We can thus immediately deduce from the graph structure that $x^{50}$ has the form $$x^{50}:=\begin{pmatrix}1&0&0\\?&1&0\\?&0&1\end{pmatrix}$$ since $50$ is even.

With a bit of thought, we can surmise that there are $25$ walks from vertex $2$ to vertex $1$ of length $50$ (we can land at vertex $1$ after step $1,3,\ldots,49$, after which the walk is determined). Similarly, there are $25$ walks from vertex $3$ to vertex $1$ of length $50$.

Hence $$x^{50}:=\begin{pmatrix}1&0&0\\25&1&0\\25&0&1\end{pmatrix}.$$

Solution 4:

The Jordan Decomposition yields $$ \left[ \begin{array}{r} 1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{array} \right] = \left[ \begin{array}{r} 0 & 0 & 2 \\ -1 & 1 & 1 \\ 1 & 1 & 0 \end{array} \right] \left[ \begin{array}{r} -1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{array} \right] \left[ \begin{array}{r} 0 & 0 & 2 \\ -1 & 1 & 1 \\ 1 & 1 & 0 \end{array} \right]^{-1} $$ Block matrices are easier to raise to a power: $$ \begin{align} \left[ \begin{array}{r} 1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{array} \right]^{50} &= \left[ \begin{array}{r} 0 & 0 & 2 \\ -1 & 1 & 1 \\ 1 & 1 & 0 \end{array} \right] \left[ \begin{array}{r} -1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{array} \right]^{50} \left[ \begin{array}{r} 0 & 0 & 2 \\ -1 & 1 & 1 \\ 1 & 1 & 0 \end{array} \right]^{-1}\\[6pt] &= \left[ \begin{array}{r} 0 & 0 & 2 \\ -1 & 1 & 1 \\ 1 & 1 & 0 \end{array} \right] \left[ \begin{array}{r} 1 & 0 & 0 \\ 0 & 1 & 50 \\ 0 & 0 & 1 \end{array} \right] \left[ \begin{array}{r} 0 & 0 & 2 \\ -1 & 1 & 1 \\ 1 & 1 & 0 \end{array} \right]^{-1}\\[6pt] &= \left[ \begin{array}{r} 1 & 0 & 0 \\ 25 & 1 & 0 \\ 25 & 0 & 1 \end{array} \right] \end{align} $$

Solution 5:

Evaluate the first few powers and guess $\begin{pmatrix}1&0&0\\1&0&1\\0&1&0\end{pmatrix}^{2n}$ = $\begin{pmatrix}1&0&0\\n&1&0\\n&0&1\end{pmatrix}$, proof by induction. Then $x^{50}=\begin{pmatrix}1&0&0\\25&1&0\\25&0&1\end{pmatrix}$.