Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

8 Answers 8

up vote 27 down vote accepted

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!

share|improve this answer
    
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}$$

share|improve this answer
1  
Very nice approach +1 –  Amzoti Sep 20 '13 at 15:24
2  
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. :) –  Babak S. Dec 20 '13 at 7:45

Hint:

Use Mathematical Induction.

share|improve this answer

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?

share|improve this answer
3  
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
1  
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$.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
    
This was rather enlightning, thanks for such a late answer! –  Jimmy C Sep 29 at 7:55
    
No problem! Incidentally, I knew these matrices would behave like a copy of $\mathbb{R}$ because I knew that the "$ax+b$ group" of affine transformations of $\mathbb{R}$ is isomorphic to the group of matrices $\{ \left( \begin{smallmatrix} a & b \\ 0 & a \\ \end{smallmatrix} \right) : a,b \in \mathbb{R}, a \neq 0\}$. The affine transformations where the slope $a$ equals $1$ is just the subgroup of translations $x \mapsto x+b$, which is isomorphic to $\mathbb{R}$. –  Mike F Sep 30 at 19:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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