17
$\begingroup$

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?

$\endgroup$
29
$\begingroup$

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!

$\endgroup$
55
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Very nice approach +1 $\endgroup$ – Amzoti Sep 20 '13 at 15:24
  • 2
    $\begingroup$ Thank you for your proof! Unfortunately I'm somewhat too early into my linear algebra career to really understand your approach. :) $\endgroup$ – Jimmy C Sep 20 '13 at 16:16
  • $\begingroup$ @JimmyC You are welcome:) $\endgroup$ – user63181 Sep 20 '13 at 16:25
  • $\begingroup$ @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... $\endgroup$ – Module Dec 15 '13 at 18:22
  • $\begingroup$ Get $30$ at the beginning of the day. :) $\endgroup$ – mrs Dec 20 '13 at 7:45
18
$\begingroup$

Hint:

Use Mathematical Induction.

$\endgroup$
8
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – rschwieb Sep 20 '13 at 15:00
  • 1
    $\begingroup$ 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. $\endgroup$ – user2566092 Sep 20 '13 at 15:44
7
$\begingroup$

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

$\endgroup$
5
$\begingroup$

Although another answer is hardly needed at this point, here is yet another way of thinking about this. Note that, for any real numbers $x$ and $y$, one has $$ \begin{pmatrix} 1 & x \\ 0 & 1 \\ \end{pmatrix} \cdot \begin{pmatrix} 1 & y \\ 0 & 1 \\ \end{pmatrix} = \begin{pmatrix} 1 & x+y \\ 0 & 1 \\ \end{pmatrix}.$$ We have learned that:

  • The set of matrices of the form $\begin{pmatrix} 1 & \text{stuff} \\ 0 & 1 \\ \end{pmatrix}$ is closed under multiplication.
  • To multiply two such matrices, you just need to add the stuff in the top right corner.

As a corollary, we conclude that: $$ \begin{pmatrix} 1 & 1 \\ 0 & 1 \\ \end{pmatrix}^n = \underbrace{ \begin{pmatrix} 1 & 1 \\ 0 & 1 \\ \end{pmatrix} \cdots \begin{pmatrix} 1 & 1 \\ 0 & 1 \\ \end{pmatrix} }_{n \text{ times}} = \begin{pmatrix} 1 & \underbrace{1+ \ldots + 1}_{n \text{ times}} \\ 0 & 1 \\ \end{pmatrix} = \begin{pmatrix} 1 & n \\ 0 & 1 \\ \end{pmatrix}. $$


Remark: If you like, you can think of the map $$ x \mapsto \begin{pmatrix} 1 & x \\ 0 & 1 \\ \end{pmatrix}$$ as being a homomorphism from the real numbers under addition to the $2 \times 2$ invertible real matrices under multiplication.

$\endgroup$
  • $\begingroup$ This was rather enlightning, thanks for such a late answer! $\endgroup$ – Jimmy C Sep 29 '14 at 7:55
  • 1
    $\begingroup$ As a slight generalization, see dual numbers. $\endgroup$ – sdcvvc Mar 29 '15 at 14:38
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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 \frac{1}{k!}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}. $$

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