# How can I show that $\begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix}^n = \begin{pmatrix} 1 & n \\ 0 & 1\end{pmatrix}$?

Well, the original task was to figure out what the following expression evaluates to for any $n$.

$$\begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix}^{\large n}$$

By trying out different values of $n$, I found the pattern: $$\begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix}^{\large n} = \begin{pmatrix} 1 & n \\ 0 & 1\end{pmatrix}$$

But I have yet to figure out how to prove it algebraically.

Suggestions?

-

Use induction on $n$.

(1) Prove the base case (trivial), perhaps even establish the case for $n = 2$ (two base cases here are not necessary, but as you found, it helps reveal the pattern.)

(2) Then assume it holds for $n = k$.

(3) Finally, show that from this assumption, it holds for $n = k+1$.

You've established the base case(s). Now, (2) assume the inductive hypothesis (IH) $$\begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix}^k = \begin{pmatrix} 1 & k \\ 0 & 1\end{pmatrix}.$$

Then, $$\begin{pmatrix} 1 & 1\\ 0 & 1 \end{pmatrix}^{k + 1} = \begin{pmatrix} 1 & 1\\ 0 & 1\end{pmatrix} \begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix}^k \quad \overset{IH}{=} \quad \begin{pmatrix} 1 & 1\\ 0 & 1\end{pmatrix} \begin{pmatrix} 1 & k \\ 0 & 1\end{pmatrix}=\quad\cdots$$

I think you can take it from here!

-
This was really helpful, thanks! –  Jimmy C Sep 20 '13 at 16:18
You're welcome, Jimmy! –  amWhy Sep 20 '13 at 16:19

The matrix $$N=\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}$$ is nilpotent with index 2 of nilpotency: $N^2=0$ so by the binomial formula we have

$$\begin{pmatrix} 1 & 1\\ 0 & 1 \end{pmatrix}^n=(I_2+N)^n=\sum_{k=0}^n {n\choose k}N^k={n\choose 0}I_2+{n\choose 1}N=I_2+nN=\begin{pmatrix} 1& n\\ 0 & 1 \end{pmatrix}$$

-
Very nice approach +1 –  Amzoti Sep 20 '13 at 15:24
Thank you for your proof! Unfortunately I'm somewhat too early into my linear algebra career to really understand your approach. :) –  Jimmy C Sep 20 '13 at 16:16
@JimmyC You are welcome:) –  Sami Ben Romdhane Sep 20 '13 at 16:25
@JimmyC he took the matrix and split it into the identity matrix which has the ones diagonally and that matrix N that he had defined. Then by applying Newton's binomial formula... –  Module Dec 15 '13 at 18:22
Get $30$ at the beginning of the day. :) –  B. S. Dec 20 '13 at 7:45

Hint:

Use Mathematical Induction.

-

Geometrically, your matrix represents a shear transformation that preserves the horizontal direction and shifts the vertical direction by the horizontal direction. What happens geometrically if you apply the same shear transformation $n$ times?

-
This is good explanation and intuition about what it does, but it doesn't seem to offer any information in the way of a proof. –  rschwieb Sep 20 '13 at 15:00
I guess it depends on how formal you want a proof to be. In my opinion, geometry can be enough for a proof, and e.g. I'd argue you don't have to use trig identities to "prove" the formula for powers of a 2-d rotation matrix rotating by angle $\theta$. I think you can even argue the other way around, and e.g. "prove" angle addition trig identities by taking a product of rotation matrices. –  user2566092 Sep 20 '13 at 15:44

Powers of matrices occur in solving recurrence relations.

If you write $$\begin{pmatrix} x_{n+1} \\ y_{n+1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix} \begin{pmatrix} x_n \\ y_n \end{pmatrix}$$ then clearly $$\begin{pmatrix} x_{n} \\ y_{n} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix}^n \begin{pmatrix} x_0 \\ y_0 \end{pmatrix}$$ and also $$x_{n+1}=x_n+y_n, \qquad y_{n+1}=y_n$$ from which you get $$x_n = x_0 + n\ y_0, \qquad y_n = y_0$$ The first column of $A^n$ is given by taking $x_0=1$ and $y_0=0$, and so is $(1 \ 0)^T$.

The second column is given by taking $x_0=0$ and $y_0=1$, and so is $(n \ 1)^T$.

-

The statement is true for an arbitrary complex number $n$, with matrix logarithm. All the $\log$s below refer to the natural logarithm.

For convenience, let's set $$A = \begin{pmatrix} 0 & a \\ 0 & 0 \end{pmatrix}.$$

We know that if $k \in \mathbb N$ and $k \ge 2$, then $A^k = O$. Therefore, $$\exp A = \sum_{k=0}^\infty A^k = I + A.$$

All eigenvalues of $A$ are zero, so $A$ is the principal logarithm. $$\log \left( I + A \right) = A.$$

This leads to $$\log \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$$

And $$\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}^n = \exp \begin{pmatrix} 0 & n \\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}.$$

-

$$\left(% \begin{array}{cc} 1 & 1 \\ 0 & 1 \end{array}\right) = 1 + A \quad\mbox{where}\quad A = \left(% \begin{array}{cc} 0 & 1 \\ 0 & 0 \end{array}\right)$$ Notice that $A^{2} = 0$. It means that a function ${\rm f}\left(A\right)$ is ${\it linear}$ in $A$. For instance, $\left(1 + \mu A\right)^{n} = \alpha + \beta A$. Also

$$nA\left(1 + \mu A\right)^{n -1} = \alpha' + \beta' A \quad\Longrightarrow\quad nA\left(\alpha + \beta A\right) = \left(1 + \mu A\right)\left(\alpha' + \beta' A\right) = \alpha' + \beta' A + \mu\alpha' A$$

$$\mbox{That's means}\quad 0 = \alpha'\,,\quad n\alpha = \beta' + \mu\alpha'= \beta'\,, \quad\mbox{with}\quad \left.\alpha\right\vert_{\mu\ =\ 0} = 1\ \mbox{and}\ \left.\beta\right\vert_{\mu\ =\ 0} = 0\$$

Then, $\alpha = 1$ and $\beta = n\mu$:

$$\begin{array}{|c|}\hline\\ \color{#ff0000}{\large\quad% \left(1 + \mu A\right)^{n} \color{#000000}{\ =\ } 1 + n\mu A \quad\color{#000000}{\Longrightarrow}\quad \left(1 + A\right)^{n} \color{#000000}{\ =\ } 1 + nA \quad} \\ \\ \hline \end{array}$$

Or 'easy way': $$\left(1 + A\right)^{n} = 1\ +\ \overbrace{\quad{n \choose 1}\quad}^{=\ n}\ A\ +\ \overbrace{\quad{n \choose 2}\,A^{2} + \cdots\quad}^{=\ 0}$$

-