# Homework 8, 2011

## Question One

Various isomorphisms ${ℝ}^{k+1}\to {Poly}_{k}$ have been mentioned in lectures with hand-waving justification of the fact that they are isomorphisms. In this question we shall prove that they are isomorphisms.

If the case for arbitrary $k$ is a little confusing, you may consider the case for $k=3$. If you do so, at the end you should explain (without proof) how your method could generalise to arbitrary $k$.

On the page linear transformation, it is shown that a linear transformation that is a bijection is also an isomorphism (ie its inverse is automatically linear). You may use this result in the following.

1. We need some preliminary results. Recall that a function $f:X\to Y$ is injective if whenever $x,y\in X$ are such that $f\left(x\right)=f\left(y\right)$ then $x=y$. Show that $T:V\to W$ is an injective linear transformation if and only if whenever $v\in V$ is such that $T\left(v\right)=0$ then $v=0$.

###### Solution

Suppose that $T$ is injective. Let $v\in V$ be such that $T\left(v\right)=0$. Then as $T\left(0\right)=0$ (since $T$ is linear), we must have (as $T$ is injective) $v=0$.

Now suppose that $T$ is such that the only vector with $T\left(v\right)=0$ is $0$ itself. Let $x,y$ be such that $T\left(x\right)=T\left(y\right)$. As $T$ is linear, this means that $T\left(x-y\right)=0$, whence $x-y=0$ and so $x=y$. Hence $T$ is injective.

2. A function $f:X\to Y$ is surjective if whenever $y\in Y$ then there is some $x\in X$ with $f\left(x\right)=y$. Use the results about the number of solutions of $Ax=b$ from Gaussian elimination to deduce that if $T:{ℝ}^{m}\to {ℝ}^{m}$ is injective then it is also surjective.

(Note that both the source and target are ${ℝ}^{m}$.)

###### Solution

Let $T:{ℝ}^{m}\to {ℝ}^{m}$ be injective. Let $A$ be its matrix. Then $Ax=b$ can have at most $1$ solution. Hence in the row reduced form of $A$, we cannot have “free” columns. As $A$ is square, this means that the row reduced form of $A$ cannot have any rows of zeros. Thus $Ax=b$ always has a solution, so $T$ is surjective.

3. We define ${Poly}_{k}$ as the space of smooth1 functions $p:ℝ\to ℝ$ for which their $k+1$th derivative vanishes; that is, ${D}^{k+1}p=0$ where $D$ stands for differentation.

For a vector in ${ℝ}^{k+1}$ we associate a smooth function by the following rule:

$\left[\begin{array}{c}{a}_{1}\\ {a}_{2}\\ ⋮\\ {a}_{k+1}\end{array}\right]↦{a}_{1}+{a}_{2}x+{a}_{3}{x}^{2}+\cdots +{a}_{k+1}{x}^{k}$\begin{bmatrix} a_{1} \\ a_{2} \\ \vdots \\ a_{k+1} \end{bmatrix} \mapsto a_{1} + a_{2} x + a_{3} x^{2} + \cdots + a_{k+1} x^{k}

Using the definition given above of ${Poly}_{k}$, prove that this defines a map $T:{ℝ}^{k+1}\to {Poly}_{k}$ which is an isomorphism. You may assume that the function so defined is linear (once you have proved that its target is ${Poly}_{k}$).

So you may not use any alternative representation of a polynomial, but may use standard facts about differentiation.

###### Hint

In particular, you may assume that if $Df=0$ then $f$ is constant.

###### Solution

We define a map in the opposite direction by sending $p\left(x\right)$ to the vector:

$\left[\begin{array}{c}p\left(0\right)\\ p\prime \left(0\right)\\ \frac{1}{2}p″\left(0\right)\\ ⋮\\ \frac{1}{k!}{p}^{\left(k\right)}\left(0\right)\end{array}\right].$\begin{bmatrix} p(0) \\ p'(0) \\ \frac{1}{2} p''(0) \\ \vdots \\ \frac{1}{k!} p^{(k)}(0) \end{bmatrix}.

Let’s call this $S$. By construction, $S\circ T$ is the identity on ${ℝ}^{k+1}$. To show that this is true in the other direction, we need to show that for a smooth function $p$ with ${D}^{k+1}p=0$ then

$p\left(x\right)=p\left(0\right)+p\prime \left(0\right)x+\frac{1}{2}p″\left(0\right){x}^{2}+\dots +\frac{1}{k!}{p}^{\left(k\right)}\left(0\right){x}^{k}.$p(x) = p(0) + p'(0)x + \frac{1}{2} p''(0)x^{2} + \dots + \frac{1}{k!} p^{(k)}(0)x^{k}.

Let us write $q\left(x\right)$ for the right hand side. We start by considering ${f}_{k}={D}^{k}\left(p-q\right)$. This satisfies $D{f}_{k}=0$ and so is constant. The constant can be found by evaluating at $0$, where we find that ${f}_{k}\left(0\right)=0$. Next we consider ${f}_{k-1}={D}^{k-1}\left(p-q\right)$. This satisfies $D{f}_{k-1}={f}_{k}=0$, so the same argument applies. We continue in the obvious fashion and finally deduce that $p=q$. Hence $T\circ S$ is the identity on ${Poly}_{k}$ and so $S$ is the inverse of $T$ which is therefore an isomorphism.

4. Define a map $S:{Poly}_{k}\to {ℝ}^{k+1}$ by sending $p\left(x\right)$ to its vector of values at $0,1,\dots ,k$. That is:

$S:p\left(x\right)↦\left[\begin{array}{c}p\left(0\right)\\ p\left(1\right)\\ ⋮\\ p\left(k\right)\end{array}\right]$S \colon p(x) \mapsto \begin{bmatrix} p(0) \\ p(1) \\ \vdots \\ p(k) \end{bmatrix}

You may assume without proof that this is linear. By considering the composition $S\circ T$, or otherwise, prove that $S$ is an isomorphism.

###### Solution

The composition $S\circ T$ is a map from ${ℝ}^{k+1}$ to itself. From the earlier parts, we see that this is an isomorphism if (and only if) it is injective. Since $T$ is an isomorphism, it is injective, and thus we need to show that $S$ is injective.

That is, we need to show that if $S\left(p\right)=0$ then $p=0$. So let $p$ be a polynomial such that for $j=0,1,\dots ,k$, $p\left(j\right)=0$. This means that $p$ is a multiple of $x\left(x-1\right)\left(x-2\right)\dots \left(x-k\right)$. However, that is a polynomial of degree $k+1$ so the only way that $p$ can be a multiple of it is if the multiplier is $0$. Hence $p=0$ and so $S$ is injective.

Thus $S\circ T$ is an isomorphism. We can therefore deduce that $S$ is an isomorphism with inverse $T\left(S\circ T{\right)}^{-1}$.

## Question Two

For each of the following matrices, find isomorphisms ${ℝ}^{n}\to {ℝ}^{n}$ and ${ℝ}^{m}\to {ℝ}^{m}$ which put the matrix in the form:

$\left[\begin{array}{cccccc}1& \dots & 0& 0& \dots & 0\\ ⋮& \ddots & ⋮& ⋮& \ddots & ⋮\\ 0& \dots & 1& 0& \dots & 0\\ ⋮& \ddots & ⋮& ⋮& \ddots & ⋮\\ 0& \dots & 0& 0& \dots & 0\end{array}\right]$\begin{bmatrix} 1 & \dots & 0 & 0 & \dots & 0\\ \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ 0 & \dots & 1 & 0 & \dots & 0 \\ \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ 0 & \dots & 0 & 0 & \dots & 0 \end{bmatrix}

(Note: if at any point you find yourself wanting to invert a matrix, don’t. Just write that the isomorphism that you want is the inverse of the one given by that particular matrix.)

Computers are allowed for the boring computations, but should not be used to solve the whole thing in one go.

1. $\left[\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& 9\\ 10& 11& 12\end{array}\right]$\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \end{bmatrix}
###### Solution

The (extremely) row reduced form of this matrix is

$\left[\begin{array}{ccc}1& 0& -1\\ 0& 1& 2\\ 0& 0& 0\\ 0& 0& 0\end{array}\right]$\begin{bmatrix} 1 & 0 & -1 \\ 0 & 1 & 2 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}

From this, we the factorisation:

$\left[\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& 9\\ 10& 11& 12\end{array}\right]=\left[\begin{array}{cccc}1& 2& 0& 0\\ 4& 5& 0& 0\\ 7& 8& 1& 0\\ 10& 11& 0& 1\end{array}\right]\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 0\\ 0& 0& 0\end{array}\right]{\left[\begin{array}{ccc}1& 0& 1\\ 0& 1& -2\\ 0& 0& 1\end{array}\right]}^{-1}$\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \end{bmatrix} = \begin{bmatrix} 1 & 2 & 0 & 0\\ 4 & 5 & 0 & 0\\ 7 & 8 & 1 & 0\\ 10 & 11 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & -2 \\ 0 & 0 & 1 \end{bmatrix}^{-1}
2. $\left[\begin{array}{ccc}1& 2& 1\\ 1& 3& 3\\ 1& 4& 6\end{array}\right]$\begin{bmatrix} 1 & 2 & 1 \\ 1 & 3 & 3 \\ 1 & 4 & 6 \end{bmatrix}
###### Solution

This row reduces (eventually) to the identity matrix. We therefore get the factorisation'':

$\left[\begin{array}{ccc}1& 2& 1\\ 1& 3& 3\\ 1& 4& 6\end{array}\right]=\left[\begin{array}{ccc}1& 2& 1\\ 1& 3& 3\\ 1& 4& 6\end{array}\right]\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]$\begin{bmatrix} 1 & 2 & 1 \\ 1 & 3 & 3 \\ 1 & 4 & 6 \end{bmatrix} = \begin{bmatrix} 1 & 2 & 1 \\ 1 & 3 & 3 \\ 1 & 4 & 6 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}
3. $\left[\begin{array}{cccc}3& 8& 7& 2\\ 4& 11& 10& 3\\ 5& 14& 13& 4\\ 6& 17& 16& 5\end{array}\right]$\begin{bmatrix} 3 & 8 & 7 & 2 \\ 4 & 11 & 10 & 3 \\ 5 & 14 & 13 & 4 \\ 6 & 17 & 16 & 5 \end{bmatrix}
###### Solution

For this one, we obtain:

$\left[\begin{array}{cccc}3& 8& 7& 2\\ 4& 11& 10& 3\\ 5& 14& 13& 4\\ 6& 17& 16& 5\end{array}\right]=\left[\begin{array}{cccc}3& 8& 0& 0\\ 4& 11& 0& 0\\ 5& 14& 1& 0\\ 6& 17& 0& 1\end{array}\right]\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right]{\left[\begin{array}{cccc}1& 0& 3& 2\\ 0& 1& -2& -1\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right]}^{-1}$\begin{bmatrix} 3 & 8 & 7 & 2 \\ 4 & 11 & 10 & 3 \\ 5 & 14 & 13 & 4 \\ 6 & 17 & 16 & 5 \end{bmatrix} = \begin{bmatrix} 3 & 8 & 0 & 0 \\ 4 & 11 & 0 & 0 \\ 5 & 14 & 1 & 0 \\ 6 & 17 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} 1 & 0 & 3 & 2 \\ 0 & 1 & -2 & -1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}^{-1}

## Question Three

Let $T:{Poly}_{3}\to {Poly}_{3}$ be the linear transformation that translates a polynomial by $1$. That is, $T\left(p\right)\left(t\right)=p\left(t+1\right)$.

1. Show that $1$ is the only eigenvalue of $T$ and find the corresponding eigenvectors (there is a straightforward argument for this which does not involve taking any determinants).

###### Hint

For a polynomial $p\left(t\right)$, consider what happens to the term of highest degree when applying $T$.

###### Solution

The coefficient of the term of highest degree in $p\left(t\right)$ and $T\left(p\right)\left(t\right)$ is the same. Hence if $T\left(p\right)=\lambda p$ then we must have $\lambda =1$. In this case, $p\left(t+1\right)=p\left(t\right)$ for all $t$, and so for any $n\in ℕ$ and $t\in ℝ$, $p\left(t+n\right)=p\left(t\right)$. But this is not possible for a non-constant polynomial, so $p\left(t\right)$ must be constant. Hence the eigenvectors are the constant polynomials.

2. Explain why the linear transformation $p↦T\left(p\right)-p$ is nilpotent.

###### Hint

Consider what happens to the degree of $p$.

###### Solution

Since $T\left(p\right)$ and $p$ have the same term of highest degree, $T\left(p\right)-p$ must be of lower degree than $p$. Hence applying it at most $4$ times, we must get $0$. Thus $p↦T\left(p\right)-p$ is nilpotent.

3. Find an isomorphism ${ℝ}^{4}\to {Poly}_{3}$ (equivalently, a basis of ${Poly}_{3}$) so that the corresponding matrix of $T$ has the form $I+N$ where $N$ is a matrix whose only non-zero elements are some $1$s on the superdiagonal.

###### Solution

The matrix $N$ is the matrix of $p↦T\left(p\right)-p$. The kernel of this is $1$ so we put that first. Then $T\left(t\right)-t=\left(t+1\right)-t=1$ so $t$ can be the next vector. Now $T\left({t}^{2}\right)-{t}^{2}={t}^{2}+2t+1-{t}^{2}=2t+1$, so $T\left(\frac{1}{2}\left({t}^{2}-t\right)\right)-\frac{1}{2}\left({t}^{2}-t\right)=t+\frac{1}{2}-\frac{1}{2}=t$. Finally, $T\left({t}^{3}\right)-{t}^{3}=3{t}^{2}+3t+1$, so $\frac{1}{3}{t}^{3}-\frac{1}{2}{t}^{2}-\frac{5}{6}t$ is the last.

4. What, if any, changes do you have to make if we replace $T$ by the transformation $p\left(t\right)↦p\left(t-1\right)$?

###### Solution

Some signs will change in the basis elements.

## Question Four

Eigenvalues and eigenvectors make sense for any linear transformation $T:V\to V$, even if $V$ is not finite dimensional.

Remember that eigenvectors must be non-zero.

1. Consider ${ℝ}^{ℕ}$, the space of all sequences in $ℝ$. Define $T:{ℝ}^{ℕ}\to {ℝ}^{ℕ}$ to be the transformation that shifts sequences by $1$. That is, if $s=\left({s}_{n}\right)$ and $T\left(s\right)=\left({r}_{n}\right)$ then ${r}_{1}=0$ and for $n\ge 2$, ${r}_{n}={s}_{n-1}$.

(Here, the first term in a sequence is indexed by $1$.)

Find the eigenvalues and eigenvectors of $T$.

###### Solution

This has no eigenvalues or eigenvectors. Let $\left({s}_{n}\right)$ be a non-zero sequence and suppose that $k$ is such that ${s}_{k}$ is the first non-zero term in $\left({s}_{n}\right)$. Then if $T\left(s\right)=\left({r}_{n}\right)$, ${r}_{k}={s}_{k-1}=0$ (or, if $k=1$, ${r}_{1}=0$ by definition). So the only possibility for $T\left(s\right)=\lambda s$ is if $\lambda =0$. But $T\left(s\right)\ne 0$ so this isn’t possible either.

2. The same, but with the shift in the other direction. So if $s=\left({s}_{n}\right)$ and $T\left(s\right)=\left({r}_{n}\right)$ then ${r}_{n}={s}_{n+1}$.

###### Solution

This has lots of eigenvectors and eigenvalues. In fact, for any $\lambda$, we get an eigenvector by taking the sequence $\left(1,\lambda ,{\lambda }^{2},\dots \right)$. Up to scalar multiples, these are all the eigenvectors.

3. In Homework 8 from 2010, it was asked to show that the linear transformation $f\left(t\right)↦tf\left(t\right)$ has no eigenvectors (on $C\left(\left[0,1\right],ℝ\right)$). Suppose that $g\in C\left(\left[0,1\right],ℝ\right)$ is such that the linear transformation $f\left(t\right)↦g\left(t\right)f\left(t\right)$ has an eigenvector. What can you say about $g\left(t\right)$?

###### Solution

Suppose that $g$ is such that multiplication by $g$ has an eigenvector, say $f$. Then there is some $\lambda$ such that $gf=\lambda f$. So for $t\in \left[0,1\right]$, $g\left(t\right)f\left(t\right)=\lambda f\left(t\right)$. If $f\left(t\right)\ne 0$, we can divide by $f\left(t\right)$ to get $g\left(t\right)=\lambda$. Thus, on the set $\left\{t:f\left(t\right)\ne 0\right\}$, we must have $g\left(t\right)$ constant. But on the set $\left\{t:f\left(t\right)=0\right\}$, we can have $g\left(t\right)$ almost anything. The only proviso is that $g$ must be continuous.

In particular, if $f$ has only an isolated $0$, then $g$ is constant everywhere.

1. A smooth function is one that can be differentiated as many times as you like.