% Chapter 3, Section 2 _Linear Algebra_ Jim Hefferon % http://joshua.smcvt.edu/linearalgebra % 2001-Jun-11 \section{Homomorphisms} The definition of isomorphism has two conditions. In this section we will consider the second one. We will study maps that are required only to preserve structure, maps that are not also required to be correspondences. Experience shows that these maps are tremendously useful. For one thing we shall see in the second subsection below that while isomorphisms describe how spaces are the same, we can think of these maps as describing how spaces are alike. \subsection{Definition} \begin{definition} \label{def:Homo} %<*df:Homo> A function between vector spaces $$\map{h}{V}{W}$$ that preserves\index{preserves structure}\index{structure! preservation} addition \begin{center} if $$\vec{v}_1,\vec{v}_2\in V$$ then $$h(\vec{v}_1+\vec{v}_2)=h(\vec{v}_1)+h(\vec{v}_2)$$ \end{center} and scalar multiplication \begin{center} if $$\vec{v}\in V$$ and $$r\in\Re$$ then $$h(r\cdot\vec{v})=r\cdot h(\vec{v})$$ \end{center} is a \definend{homomorphism}\index{homomorphism}\index{linear map}% \index{function!structure preserving!\see{homomorphism}}% \index{vector space!homomorphism}\index{vector space!map} or \definend{linear map}\index{linear map|seealso{homomorphism}}. % \end{definition} \begin{example} \label{ex:RThreeHomoRTwoFirst} The projection\index{projection} map $$\map{\pi}{\Re^3}{\Re^2}$$ \begin{equation*} \colvec{x \\ y \\ z} \mapsunder{\pi} \colvec{x \\ y} \end{equation*} is a homomorphism. It preserves addition \begin{equation*} \pi(\colvec{x_1 \\ y_1 \\ z_1}\!+\!\colvec{x_2 \\ y_2 \\ z_2}) = \pi(\colvec{x_1+x_2 \\ y_1+y_2 \\ z_1+z_2}) = \colvec{x_1+x_2 \\ y_1+y_2} = \pi(\colvec{x_1 \\ y_1 \\ z_1}) + \pi(\colvec{x_2 \\ y_2 \\ z_2}) \end{equation*} and scalar multiplication. \begin{equation*} \pi(r\cdot\colvec{x_1 \\ y_1 \\ z_1}) = \pi(\colvec{rx_1 \\ ry_1 \\ rz_1}) = \colvec{rx_1 \\ ry_1} = r\cdot\pi(\colvec{x_1 \\ y_1 \\ z_1}) \end{equation*} This is not an isomorphism since it is not one-to-one. For instance, both $\zero$ and $\vec{e}_3$ in $\Re^3$ map to the zero vector in $\Re^2$. \end{example} \begin{example} \label{exam:TwoMapsHomoNotIso} The domain and codomain can be other than spaces of column vectors. Both of these are homomorphisms; the verifications are straightforward. \begin{enumerate} \item $$\map{f_1}{\polyspace_2}{\polyspace_3}$$ given by \begin{equation*} a_0+a_1x+a_2x^2 \;\mapsto\; a_0x+(a_1/2)x^2+(a_2/3)x^3 \end{equation*} \item $$\map{f_2}{M_{\nbyn{2}}}{\Re}$$ given by \begin{equation*} \begin{mat} a &b \\ c &d \end{mat} \mapsto a+d \end{equation*} \end{enumerate} \end{example} \begin{example} Between any two spaces there is a \definend{zero homomorphism},% \index{zero homomorphism}\index{homomorphism!zero}\index{function!zero} mapping every vector in the domain to the zero vector in the codomain. \end{example} \begin{example} These two suggest why we use the term linear map'. \begin{enumerate} \item The map $$\map{g}{\Re^3}{\Re}$$ given by \begin{equation*} \colvec{x \\ y \\ z} \mapsunder{g} 3x+2y-4.5z \end{equation*} is linear, that is, is a homomorphism. The check is easy. In contrast, the map $$\map{\hat{g}}{\Re^3}{\Re}$$ given by \begin{equation*} \colvec{x \\ y \\ z} \mapsunder{\hat{g}} 3x+2y-4.5z+1 \end{equation*} is not linear. To show this we need only produce a single linear combination that the map does not preserve. Here is one. \begin{equation*} \hat{g}(\colvec[r]{0 \\ 0 \\ 0}+\colvec[r]{1 \\ 0 \\ 0})=4 \qquad \hat{g}(\colvec[r]{0 \\ 0 \\ 0}) +\hat{g}(\colvec[r]{1 \\ 0 \\ 0})=5 \end{equation*} \item The first of these two maps $$\map{t_1,t_2}{\Re^3}{\Re^2}$$ is linear while the second is not. \begin{equation*} \colvec{x \\ y \\ z} \mapsunder{t_1} \colvec{5x-2y \\ x+y} \qquad \colvec{x \\ y \\ z} \mapsunder{t_2} \colvec{5x-2y \\ xy} \end{equation*} Finding a linear combination that the second map does not preserve is easy. \end{enumerate} % The homomorphisms have % coordinate functions that are linear combinations of the arguments. % See also \nearbyexercise{exer:GrpahNotALine}. \end{example} So one way to think of homomorphism' is that we are generalizing isomorphism' (by dropping the condition that the map is a correspondence), motivated by the observation that many of the properties of isomorphisms have only to do with the map's structure-preservation property. The next two results are examples of this motivation. In the prior section we saw a proof for each that only uses preservation of addition and preservation of scalar multiplication, and therefore applies to homomorphisms. \begin{lemma} \label{le:HomoSendsZeroToZero} %<*lm:HomoSendsZeroToZero> A homomorphism sends the zero vector to the zero vector. % \end{lemma} \begin{lemma} \label{le:HomoPreserveLinCombo} %<*lm:HomoPreserveLinCombo> The following are equivalent for any map $$\map{f}{V}{W}$$ between vector spaces. \begin{tfae} \item $f$ is a homomorphism \item $f(c_1\cdot\vec{v}_1+c_2\cdot\vec{v}_2) =c_1\cdot f(\vec{v}_1)+c_2\cdot f(\vec{v}_2)$ for any $$c_1,c_2\in\Re$$ and $$\vec{v}_1,\vec{v}_2\in V$$ \item $f(c_1\cdot\vec{v}_1+\dots+c_n\cdot\vec{v}_n) =c_1\cdot f(\vec{v}_1)+\dots+c_n\cdot f(\vec{v}_n)$ for any $$c_1,\dots,c_n\in\Re$$ and $$\vec{v}_1,\ldots,\vec{v}_n\in V$$ \end{tfae} % \end{lemma} \begin{example} The function $$\map{f}{\Re^2}{\Re^4}$$ given by \begin{equation*} \colvec{x \\ y} \mapsunder{f} \colvec{x/2 \\ 0 \\ x+y \\ 3y} \end{equation*} is linear since it satisfies item~(2). \begin{equation*} \colvec{r_1(x_1/2)+r_2(x_2/2) \\ 0 \\ r_1(x_1+y_1)+r_2(x_2+y_2) \\ r_1(3y_1)+r_2(3y_2)} = r_1\colvec{x_1/2 \\ 0 \\ x_1+y_1 \\ 3y_1} + r_2\colvec{x_2/2 \\ 0 \\ x_2+y_2 \\ 3y_2} \end{equation*} \end{example} However, some things that hold for isomorphisms fail to hold for homomorphisms. One example is in the proof of Lemma~I.\ref{lem:IsoImpliesSameDim}, which shows that an isomorphism between spaces gives a correspondence between their bases. Homomorphisms do not give any such correspondence; \nearbyexample{ex:RThreeHomoRTwoFirst} shows this and another example is the zero map between two nontrivial spaces. Instead, for homomorphisms we have a weaker but still very useful result. \begin{theorem} \label{th:HomoDetActOnBasis} %<*th:HomoDetActOnBasis> A homomorphism is determined by its action on a basis:~if $V$ is a vector space with basis $$\sequence{\vec{\beta}_1,\dots,\vec{\beta}_n}$$, if $W$ is a vector space, and if $$\vec{w}_1,\dots,\vec{w}_n\in W$$ (these codomain elements need not be distinct) then there exists a homomorphism from $$V$$ to $$W$$ sending each $$\vec{\beta}_i$$ to $$\vec{w}_i$$, and that homomorphism is unique. % \end{theorem} \begin{proof} %<*pf:HomoDetActOnBasis0> For any input $\vec{v}\in V$ let its expression with respect to the basis be $$\vec{v}=c_1\vec{\beta}_1+\dots+c_n\vec{\beta}_n$$. Define the associated output by using the same coordinates $h(\vec{v})=c_1\vec{w}_1+\dots+c_n\vec{w}_n$. This is well defined because, with respect to the basis, the representation of each domain vector $$\vec{v}$$ is unique. % %<*pf:HomoDetActOnBasis1> This map is a homomorphism because it preserves linear combinations: where $$\vec{v_1}=c_1\vec{\beta}_1+\cdots+c_n\vec{\beta}_n$$ and $$\vec{v_2}=d_1\vec{\beta}_1+\cdots+d_n\vec{\beta}_n$$, here is the calculation. \begin{align*} h(r_1\vec{v}_1+r_2\vec{v}_2) &=h(\,(r_1c_1+r_2d_1)\vec{\beta}_1+\dots+(r_1c_n+r_2d_n)\vec{\beta}_n\,) \\ &=(r_1c_1+r_2d_1)\vec{w}_1+\dots+(r_1c_n+r_2d_n)\vec{w}_n \\ &=r_1h(\vec{v}_1)+r_2h(\vec{v}_2) \end{align*} % %<*pf:HomoDetActOnBasis2> This map is unique because if $$\map{\hat{h}}{V}{W}$$ is another homomorphism satisfying that $$\hat{h}(\vec{\beta}_i)=\vec{w}_i$$ for each $$i$$ then $$h$$ and $$\hat{h}$$ have the same effect on all of the vectors in the domain. \begin{multline*} \hat{h}(\vec{v}) =\hat{h}(c_1\vec{\beta}_1+\dots+c_n\vec{\beta}_n) =c_1 \hat{h}(\vec{\beta}_1)+\dots+c_n \hat{h}(\vec{\beta}_n) \\ =c_1\vec{w}_1+\dots+c_n\vec{w}_n =h(\vec{v}) \end{multline*} They have the same action so they are the same function. % \end{proof} \begin{definition} \label{df:ExtendedLinearly} %<*df:ExtendedLinearly> Let $V$ and~$W$ be vector spaces and let $B=\sequence{\vec{\beta}_1,\ldots,\vec{\beta}_n}$ be a basis for~$V$. A function defined on that basis $\map{f}{B}{W}$ is \definend{extended linearly}\index{extended, linearly}\index{function!extended linearly}\index{linear extension of a function} to a function $\map{\hat{f}}{V}{W}$ if for all $\vec{v}\in V$ such that $\vec{v}=c_1\vec{\beta}_1+\cdots+c_n\vec{\beta}_n$, the action of the map is $\hat{f}(\vec{v})=c_1\cdot f(\vec{\beta}_1) +\cdots+c_n\cdot f(\vec{\beta}_n)$. % \end{definition} \begin{example} If we specify a map $$\map{h}{\Re^2}{\Re^2}$$ that acts on the standard basis $\stdbasis_2$ in this way \begin{equation*} h(\colvec[r]{1 \\ 0})=\colvec[r]{-1 \\ 1} \qquad h(\colvec[r]{0 \\ 1})=\colvec[r]{-4 \\ 4} \end{equation*} then we have also specified the action of $h$ on any other member of the domain. For instance, the value of $h$ on this argument \begin{equation*} h(\colvec[r]{3 \\ -2})=h(3\cdot \colvec[r]{1 \\ 0}-2\cdot \colvec[r]{0 \\ 1}) =3\cdot h(\colvec[r]{1 \\ 0})-2\cdot h(\colvec[r]{0 \\ 1}) =\colvec[r]{5 \\ -5} \end{equation*} is a direct consequence of the value of $h$ on the basis vectors. \end{example} Later in this chapter we shall develop a convenient scheme for computations like this one, using matrices. % Just as the isomorphisms of a space with itself are useful and interesting, % so too are the homomorphisms of a space with itself. \begin{definition} \label{df:LinearTransformation} %<*df:LinearTransformation> A linear map from a space into itself $$\map{t}{V}{V}$$ is a \definend{linear transformation}\index{linear transformation}\index{linear transformation|seealso{transformation}}. % \end{definition} \begin{remark} In this book we use linear transformation' only in the case where the codomain equals the domain. However, be aware that other sources may instead use it as a synonym for homomorphism'. \end{remark} \begin{example} The map on $\Re^2$ that projects all vectors down to the $x$-axis is a linear transformation. \begin{equation*} \colvec{x \\ y}\mapsto\colvec{x \\ 0} \end{equation*} \end{example} \begin{example} The derivative map $$\map{d/dx}{\polyspace_n}{\polyspace_n}$$ \begin{equation*} a_0+a_1x+\cdots+a_nx^n \mapsunder{d/dx} a_1+2a_2x+3a_3x^2+\cdots+na_nx^{n-1} \end{equation*} is a linear transformation as this result from calculus shows: $$d(c_1f+c_2g)/dx=c_1\,(df/dx)+c_2\,(dg/dx)$$. \end{example} \begin{example} \label{ex:MatTransMapLinear} The matrix transpose operation \begin{equation*} \begin{mat} a &b \\ c &d \end{mat} \;\mapsto\; \begin{mat} a &c \\ b &d \end{mat} \end{equation*} is a linear transformation of $$\matspace_{\nbyn{2}}$$. (Transpose is one-to-one and onto and so is in fact an automorphism.) \end{example} We finish this subsection about maps by recalling that we can linearly combine maps. For instance, for these maps from $$\Re^2$$ to itself \begin{equation*} \colvec{x \\ y} \mapsunder{f} \colvec{2x \\ 3x-2y} \quad\text{and}\quad \colvec{x \\ y} \mapsunder{g} \colvec{0 \\ 5x} \end{equation*} the linear combination $$5f-2g$$ is also a transformation of~$R^2$. \begin{equation*} \colvec{x \\ y} \mapsunder{5f-2g} \colvec{10x \\ 5x-10y} \end{equation*} \begin{lemma} \label{le:SpLinFcns} %<*lm:SpLinFcns> For vector spaces $$V$$ and $$W$$, the set of linear functions from $$V$$ to $$W$$ is itself a vector space, a subspace of the space of all functions from $$V$$ to $$W$$. % \end{lemma} %<*SpLinFcns> \noindent We denote the space of linear maps from $V$ to~$W$ by $$\linmaps{V}{W}$$.\index{linear maps, vector space of} % \begin{proof} %<*pf:SpLinFcns> This set is non-empty because it contains the zero homomorphism. So to show that it is a subspace we need only check that it is closed under the operations. Let $$\map{f,g}{V}{W}$$ be linear. Then the operation of function addition is preserved \begin{align*} (f+g)(c_1\vec{v}_1+c_2\vec{v}_2) &=f(c_1\vec{v}_1+c_2\vec{v}_2) + g(c_1\vec{v}_1+c_2\vec{v}_2) \\ &=c_1f(\vec{v}_1)+c_2f(\vec{v}_2) +c_1g(\vec{v}_1)+c_2g(\vec{v}_2) \\ &=c_1\bigl(f+g\bigr)(\vec{v}_1)+c_2\bigl(f+g\bigr)(\vec{v}_2) \end{align*} as is the operation of scalar multiplication of a function. \begin{align*} (r\cdot f)(c_1\vec{v}_1+c_2\vec{v}_2) &=r(c_1f(\vec{v}_1)+c_2f(\vec{v}_2)) \\ &=c_1(r\cdot f)(\vec{v}_1)+c_2(r\cdot f)(\vec{v}_2) \end{align*} Hence $$\linmaps{V}{W}$$ is a subspace. % \end{proof} We started this section by defining homomorphism' as a generalization of isomorphism', by isolating the structure preservation property. Some of the points about isomorphisms carried over unchanged, while we adapted others. Note, however, that the idea of homomorphism' is in no way somehow secondary to that of isomorphism'. In the rest of this chapter we shall work mostly with homomorphisms. This is partly because any statement made about homomorphisms is automatically true about isomorphisms but more because, while the isomorphism concept is more natural, our experience will show that the homomorphism concept is more fruitful and more central to progress. \begin{exercises} \recommended \item Decide if each $$\map{h}{\Re^3}{\Re^2}$$ is linear. \begin{exparts*} \partsitem $$h(\colvec{x \\ y \\ z})=\colvec{x \\ x+y+z}$$ \partsitem $$h(\colvec{x \\ y \\ z})=\colvec[r]{0 \\ 0}$$ \partsitem $$h(\colvec{x \\ y \\ z})=\colvec[r]{1 \\ 1}$$ \partsitem $$h(\colvec{x \\ y \\ z})=\colvec{2x+y \\ 3y-4z}$$ \end{exparts*} \begin{answer} \begin{exparts} \partsitem Yes. The verification is straightforward. \begin{align*} h( c_1\cdot\colvec{x_1 \\ y_1 \\ z_1} +c_2\cdot\colvec{x_2 \\ y_2 \\ z_2} ) &=h( \colvec{c_1x_1+c_2x_2 \\ c_1y_1+c_2y_2 \\ c_1z_1+c_2z_2} ) \\ &=\colvec{c_1x_1+c_2x_2 \\ c_1x_1+c_2x_2+c_1y_1+c_2y_2+c_1z_1+c_2z_2} \\ &=c_1\cdot\colvec{x_1 \\ x_1+y_1+z_1} +c_2\cdot\colvec{x_2 \\ c_2+y_2+z_2} \\ &=c_1\cdot h(\colvec{x_1 \\ y_1 \\ z_1}) +c_2\cdot h(\colvec{x_2 \\ y_2 \\ z_2}) \end{align*} \partsitem Yes. The verification is easy. \begin{align*} h(c_1\cdot\colvec{x_1 \\ y_1 \\ z_1} +c_2\cdot\colvec{x_2 \\ y_2 \\ z_2}) &=h( \colvec{c_1x_1+c_2x_2 \\ c_1y_1+c_2y_2 \\ c_1z_1+c_2z_2} ) \\ &=\colvec[r]{0 \\ 0} \\ &=c_1\cdot h(\colvec{x_1 \\ y_1 \\ z_1}) +c_2\cdot h(\colvec{x_2 \\ y_2 \\ z_2}) \end{align*} \partsitem No. An example of an addition that is not respected is this. \begin{equation*} h(\colvec[r]{0 \\ 0 \\ 0}+\colvec[r]{0 \\ 0 \\ 0}) =\colvec[r]{1 \\ 1} \neq h(\colvec[r]{0 \\ 0 \\ 0})+h(\colvec[r]{0 \\ 0 \\ 0}) \end{equation*} \partsitem Yes. The verification is straightforward. \begin{align*} h( c_1\cdot\colvec{x_1 \\ y_1 \\ z_1} +c_2\cdot\colvec{x_2 \\ y_2 \\ z_2} ) &=h( \colvec{c_1x_1+c_2x_2 \\ c_1y_1+c_2y_2 \\ c_1z_1+c_2z_2} ) \\ &=\colvec{2(c_1x_1+c_2x_2)+(c_1y_1+c_2y_2) \\ 3(c_1y_1+c_2y_2)-4(c_1z_1+c_2z_2)} \\ &=c_1\cdot\colvec{2x_1+y_1 \\ 3y_1-4z_1} +c_2\cdot\colvec{2x_2+y_2 \\ 3y_2-4z_2} \\ &=c_1\cdot h(\colvec{x_1 \\ y_1 \\ z_1}) +c_2\cdot h(\colvec{x_2 \\ y_2 \\ z_2}) \end{align*} \end{exparts} \end{answer} \recommended \item Decide if each map $$\map{h}{\matspace_{\nbyn{2}}}{\Re}$$ is linear. \begin{exparts} \partsitem $$h(\begin{mat} a &b \\ c &d \end{mat})=a+d$$ \partsitem $$h(\begin{mat} a &b \\ c &d \end{mat})=ad-bc$$ \partsitem $$h(\begin{mat} a &b \\ c &d \end{mat})=2a+3b+c-d$$ \partsitem $$h(\begin{mat} a &b \\ c &d \end{mat})=a^2+b^2$$ \end{exparts} \begin{answer} For each, we must either check that the map preserves linear combinations or give an example of a linear combination that is not. \begin{exparts*} \partsitem Yes. The check that it preserves combinations is routine. \begin{align*} h(r_1\cdot\begin{mat} a_1 &b_1 \\ c_1 &d_1 \end{mat} +r_2\cdot\begin{mat} a_2 &b_2 \\ c_2 &d_2 \end{mat}) &=h(\begin{mat} r_1a_1+r_2a_2 &r_1b_1+r_2b_2 \\ r_1c_1+r_2c_2 &r_1d_1+r_2d_2 \end{mat}) \\ &=(r_1a_1+r_2a_2)+(r_1d_1+r_2d_2) \\ &=r_1(a_1+d_1)+r_2(a_2+d_2) \\ &=r_1\cdot h(\begin{mat} a_1 &b_1 \\ c_1 &d_1 \end{mat}) +r_2\cdot h(\begin{mat} a_2 &b_2 \\ c_2 &d_2 \end{mat}) \end{align*} \partsitem No. For instance, not preserved is multiplication by the scalar $2$. \begin{equation*} h(2\cdot\begin{mat}[r] 1 &0 \\ 0 &1 \end{mat}) =h(\begin{mat}[r] 2 &0 \\ 0 &2 \end{mat}) =4 \quad\text{while}\quad 2\cdot h(\begin{mat}[r] 1 &0 \\ 0 &1 \end{mat}) =2\cdot 1=2 \end{equation*} \partsitem Yes. This is the check that it preserves combinations of two members of the domain. \begin{multline*} h(r_1\cdot\begin{mat} a_1 &b_1 \\ c_1 &d_1 \end{mat} +r_2\cdot\begin{mat} a_2 &b_2 \\ c_2 &d_2 \end{mat}) \\ \begin{aligned} &=h(\begin{mat} r_1a_1+r_2a_2 &r_1b_1+r_2b_2 \\ r_1c_1+r_2c_2 &r_1d_1+r_2d_2 \end{mat}) \\ &=2(r_1a_1+r_2a_2)+3(r_1b_1+r_2b_2) +(r_1c_1+r_2c_2)-(r_1d_1+r_2d_2) \\ &=r_1(2a_1+3b_1+c_1-d_1) +r_2(2a_2+3b_2+c_2-d_2) \\ &=r_1\cdot h(\begin{mat} a_1 &b_1 \\ c_1 &d_1 \end{mat} +r_2\cdot h(\begin{mat} a_2 &b_2 \\ c_2 &d_2 \end{mat}) \end{aligned} \end{multline*} \partsitem No. An example of a combination that is not preserved is that doing it one way gives this \begin{equation*} h(\begin{mat}[r] 1 &0 \\ 0 &0 \end{mat} +\begin{mat}[r] 1 &0 \\ 0 &0 \end{mat}) =h(\begin{mat}[r] 2 &0 \\ 0 &0 \end{mat}) =4 \end{equation*} while the other way gives this. \begin{equation*} h(\begin{mat}[r] 1 &0 \\ 0 &0 \end{mat}) +h(\begin{mat}[r] 1 &0 \\ 0 &0 \end{mat}) =1+1 =2 \end{equation*} \end{exparts*} \end{answer} \recommended \item Show that these are homomorphisms. Are they inverse to each other? \begin{exparts} \partsitem $$\map{d/dx}{\polyspace_3}{\polyspace_2}$$ given by $$a_0+a_1x+a_2x^2+a_3x^3$$ maps to $$a_1+2a_2x+3a_3x^2$$ \partsitem $$\map{\int}{\polyspace_2}{\polyspace_3}$$ given by $$b_0+b_1x+b_2x^2$$ maps to $$b_0x+(b_1/2)x^2+(b_2/3)x^3$$ \end{exparts} \begin{answer} The check that each is a homomorphisms is routine. Here is the check for the differentiation map. \begin{multline*} \frac{d}{dx}(r\cdot (a_0+a_1x+a_2x^2+a_3x^3) +s\cdot (b_0+b_1x+b_2x^2+b_3x^3)) \\ \begin{aligned} &=\frac{d}{dx}((ra_0+sb_0)+(ra_1+sb_1)x+(ra_2+sb_2)x^2 +(ra_3+sb_3)x^3) \\ &=(ra_1+sb_1)+2(ra_2+sb_2)x+3(ra_3+sb_3)x^2 \\ &=r\cdot (a_1+2a_2x+3a_3x^2)+s\cdot (b_1+2b_2x+3b_3x^2) \\ &=r\cdot \frac{d}{dx}(a_0+a_1x+a_2x^2+a_3x^3) +s\cdot \frac{d}{dx} (b_0+b_1x+b_2x^2+b_3x^3) \end{aligned} \end{multline*} (An alternate proof is to simply note that this is a property of differentiation that is familiar from calculus.) These two maps are not inverses as this composition does not act as the identity map on this element of the domain. \begin{equation*} 1\in\polyspace_3\;\mapsunder{d/dx}\; 0\in\polyspace_2\;\mapsunder{\int}\; 0\in\polyspace_3 \end{equation*} \end{answer} \item Is (perpendicular) projection from $$\Re^3$$ to the $$xz$$-plane a homomorphism? Projection to the $$yz$$-plane? To the $$x$$-axis? The $$y$$-axis? The $$z$$-axis? Projection to the origin? \begin{answer} Each of these projections is a homomorphism. Projection to the $xz$-plane and to the $yz$-plane are these maps. \begin{equation*} \colvec{x \\ y \\ z}\mapsto\colvec{x \\ 0 \\ z} \qquad \colvec{x \\ y \\ z}\mapsto\colvec{0 \\ y \\ z} \end{equation*} Projection to the $x$-axis, to the $y$-axis, and to the $z$-axis are these maps. \begin{equation*} \colvec{x \\ y \\ z}\mapsto\colvec{x \\ 0 \\ 0} \qquad \colvec{x \\ y \\ z}\mapsto\colvec{0 \\ y \\ 0} \qquad \colvec{x \\ y \\ z}\mapsto\colvec{0 \\ 0 \\ z} \end{equation*} And projection to the origin is this map. \begin{equation*} \colvec{x \\ y \\ z}\mapsto\colvec[r]{0 \\ 0 \\ 0} \end{equation*} Verification that each is a homomorphism is straightforward. (The last one, of course, is the zero transformation on $\Re^3$.) \end{answer} \item Verify that each map is a homomorphism. \begin{exparts} \partsitem $\map{h}{\polyspace_3}{\Re^2}$ given by \begin{equation*} ax^2+bx+c\mapsto \colvec{a+b \\ a+c} \end{equation*} \partsitem $\map{f}{\Re^2}{\Re^3}$ given by \begin{equation*} \colvec{x \\ y}\mapsto\colvec{0 \\ x-y \\ 3y} \end{equation*} \end{exparts} \begin{answer} \begin{exparts} \partsitem This verifies that the map preserves linear combinations. By \nearbylemma{le:HomoPreserveLinCombo} that suffices to show that it is a homomorphism. \begin{multline*} h(\,d_1(a_1x^2+b_1x+c_1)+d_2(a_2x^2+b_2x+c_2)\,) \\ \begin{aligned} &=h((d_1a_1+d_2a_2)x^2+(d_1b_1+d_2b_2)x+(d_1c_1+d_2c_2)) \\ &=\colvec{(d_1a_1+d_2a_2)+(d_1b_1+d_2b_2) \\ (d_1a_1+d_2a_2)+(d_1c_1+d_2c_2)} \\ &=\colvec{d_1a_1+d_1b_1 \\ d_1a_1+d_1c_1}+ \colvec{d_2a_2+d_2b_2 \\ d_2a_2+d_2c_2} \\ &=d_1\colvec{a_1+b_1 \\ a_1+c_1}+ d_2\colvec{a_2+b_2 \\ a_2+c_2} \\ &=d_1\cdot h(a_1x^2+b_1x+c_1)+d_2\cdot h(a_2x^2+b_2x+c_2) \end{aligned} \end{multline*} \partsitem It preserves linear combinations. \begin{align*} f(\,a_1\colvec{x_1 \\ y_1}+a_2\colvec{x_2 \\ y_2}\,) &=f(\,\colvec{a_1x_1+a_2x_2 \\ a_1y_1+a_2y_2}\,) \\ &=\colvec{0 \\ (a_1x_1+a_2x_2)-(a_1y_1+a_2y_2) \\ 3(a_1y_1+a_2y_2) } \\ &=a_1\colvec{0 \\ x_1-y_1 \\ 3y_1} +a_2\colvec{0 \\ x_2-y_2 \\ 3y_2} \\ &=a_1f(\colvec{x_1 \\ y_1})+a_2f(\colvec{x_2 \\ y_2}) \end{align*} \end{exparts} \end{answer} \item Show that, while the maps from \nearbyexample{exam:TwoMapsHomoNotIso} preserve linear operations, they are not isomorphisms. \begin{answer} The first is not onto; for instance, there is no polynomial that is sent the constant polynomial $p(x)=1$. The second is not one-to-one; both of these members of the domain \begin{equation*} \begin{mat}[r] 1 &0 \\ 0 &0 \end{mat} \quad\text{and}\quad \begin{mat}[r] 0 &0 \\ 0 &1 \end{mat} \end{equation*} map to the same member of the codomain, $1\in\Re$. \end{answer} \item Is an identity map a linear transformation? \begin{answer} Yes;~in any space $$\text{id}(c\cdot \vec{v}+d\cdot \vec{w}) = c\cdot \vec{v}+d\cdot \vec{w} = c\cdot\text{id}(\vec{v})+d\cdot\text{id}(\vec{w})$$. \end{answer} \recommended \item \label{exer:GrpahNotALine} Stating that a function is linear' is different than stating that its graph is a line. \begin{exparts} \partsitem The function $$\map{f_1}{\Re}{\Re}$$ given by $$f_1(x)=2x-1$$ has a graph that is a line. Show that it is not a linear function. \partsitem The function $$\map{f_2}{\Re^2}{\Re}$$ given by \begin{equation*} \colvec{x \\ y} \mapsto x+2y \end{equation*} does not have a graph that is a line. Show that it is a linear function. \end{exparts} \begin{answer} \begin{exparts} \partsitem This map does not preserve structure since $$f(1+1)=3$$, while $$f(1)+f(1)=2$$. \partsitem The check is routine. \begin{align*} f(r_1\cdot\colvec{x_1 \\ y_1}+r_2\cdot\colvec{x_2 \\ y_2}) &=f(\colvec{r_1x_1+r_2x_2 \\ r_1y_1+r_2y_2}) \\ &=(r_1x_1+r_2x_2)+2(r_1y_1+r_2y_2) \\ &=r_1\cdot (x_1+2y_1)+r_2\cdot (x_2+2y_2) \\ &=r_1\cdot f(\colvec{x_1 \\ y_1})+r_2\cdot f(\colvec{x_2 \\ y_2}) \end{align*} \end{exparts} \end{answer} \recommended \item Part of the definition of a linear function is that it respects addition. Does a linear function respect subtraction? \begin{answer} Yes. Where $$\map{h}{V}{W}$$ is linear, $$h(\vec{u}-\vec{v}) =h(\vec{u}+(-1)\cdot\vec{v}) =h(\vec{u})+(-1)\cdot h(\vec{v}) =h(\vec{u})-h(\vec{v})$$. \end{answer} \item Assume that $$h$$ is a linear transformation of $$V$$ and that $$\sequence{\vec{\beta}_1,\ldots,\vec{\beta}_n}$$ is a basis of $$V$$. Prove each statement. \begin{exparts} \partsitem If $$h(\vec{\beta}_i)=\zero$$ for each basis vector then $$h$$ is the zero map. \partsitem If $$h(\vec{\beta}_i)=\vec{\beta}_i$$ for each basis vector then $$h$$ is the identity map. \partsitem If there is a scalar $$r$$ such that $$h(\vec{\beta}_i)=r\cdot\vec{\beta}_i$$ for each basis vector then $$h(\vec{v})=r\cdot\vec{v}$$ for all vectors in $V$. \end{exparts} \begin{answer} \begin{exparts} \partsitem Let $$\vec{v}\in V$$ be represented with respect to the basis as $$\vec{v}=c_1\vec{\beta}_1+\dots+c_n\vec{\beta}_n$$. Then $$h(\vec{v})=h(c_1\vec{\beta}_1+\dots+c_n\vec{\beta}_n) =c_1h(\vec{\beta}_1)+\dots+c_nh(\vec{\beta}_n) =c_1\cdot\zero+\dots+c_n\cdot\zero =\zero$$. \partsitem This argument is similar to the prior one. Let $$\vec{v}\in V$$ be represented with respect to the basis as $$\vec{v}=c_1\vec{\beta}_1+\dots+c_n\vec{\beta}_n$$. Then $$h(c_1\vec{\beta}_1+\dots+c_n\vec{\beta}_n) =c_1h(\vec{\beta}_1)+\dots+c_nh(\vec{\beta}_n) =c_1\vec{\beta}_1+\dots+c_n\vec{\beta}_n =\vec{v}$$. \partsitem As above, only $$c_1h(\vec{\beta}_1)+\dots+c_nh(\vec{\beta}_n) =c_1r\vec{\beta}_1+\dots+c_nr\vec{\beta}_n =r(c_1\vec{\beta}_1+\dots+c_n\vec{\beta}_n) =r\vec{v}$$. \end{exparts} \end{answer} \item Consider the vector space $$\Re^+$$ where vector addition and scalar multiplication are not the ones inherited from $\Re$ but rather are these: $$a+b$$ is the product of $$a$$ and $$b$$, and $$r\cdot a$$ is the $$r$$-th power of $$a$$. (This was shown to be a vector space in an earlier exercise.) Verify that the natural logarithm map $$\map{\ln}{\Re^+}{\Re}$$ is a homomorphism between these two spaces. Is it an isomorphism? \begin{answer} That it is a homomorphism follows from the familiar rules that the logarithm of a product is the sum of the logarithms $\ln(ab)=\ln(a)+\ln(b)$ and that the logarithm of a power is the multiple of the logarithm $\ln(a^r)=r\ln(a)$. This map is an isomorphism because it has an inverse, namely, the exponential map, so it is a correspondence, and therefore it is an isomorphism. \end{answer} \item Consider this transformation of the plane $$\Re^2$$. \begin{equation*} \colvec{x \\ y} \mapsto \colvec{x/2 \\ y/3} \end{equation*} Find the image under this map of this ellipse. \begin{equation*} \set{\colvec{x \\ y} \suchthat (x^2/4)+(y^2/9)=1} \end{equation*} \begin{answer} Where $$\hat{x}=x/2$$ and $$\hat{y}=y/3$$, the image set is \begin{equation*} \set{\colvec{\hat{x} \\ \hat{y}} \suchthat \frac{\displaystyle (2\hat{x})^2}{\displaystyle 4} +\frac{\displaystyle (3\hat{y})^2}{\displaystyle 9}=1} =\set{\colvec{\hat{x} \\ \hat{y}} \suchthat \hat{x}^2+\hat{y}^2=1} \end{equation*} the unit circle in the $$\hat{x}\hat{y}$$-plane. \end{answer} \recommended \item Imagine a rope wound around the earth's equator so that it fits snugly (suppose that the earth is a sphere). How much extra rope must we add to raise the circle to a constant six feet off the ground? \begin{answer} The circumference function $r\mapsto 2\pi r$ is linear. Thus we have $2\pi\cdot (r_{\text{earth}}+6)- 2\pi\cdot (r_{\text{earth}})=12\pi$. Observe that it takes the same amount of extra rope to raise the circle from tightly wound around a basketball to six feet above that basketball as it does to raise it from tightly wound around the earth to six feet above the earth. \end{answer} \recommended \item Verify that this map $$\map{h}{\Re^3}{\Re}$$ \begin{equation*} \colvec{x \\ y \\ z}\;\mapsto\; \colvec{x \\ y \\ z}\dotprod\colvec[r]{3 \\ -1 \\ -1}=3x-y-z \end{equation*} is linear. Generalize. \begin{answer} Verifying that it is linear is routine. \begin{align*} h(c_1\cdot \colvec{x_1 \\ y_1 \\ z_1} +c_2\cdot \colvec{x_2 \\ y_2 \\ z_2}) &=h(\colvec{c_1x_1+c_2x_2 \\ c_1y_1+c_2y_2 \\ c_1z_1+c_2z_2}) \\ &=3(c_1x_1+c_2x_2)-(c_1y_1+c_2y_2)-(c_1z_1+c_2z_2) \\ &=c_1\cdot (3x_1-y_1-z_1)+c_2\cdot (3x_2-y_2-z_2) \\ &=c_1\cdot h(\colvec{x_1 \\ y_1 \\ z_1}) +c_2\cdot h(\colvec{x_2 \\ y_2 \\ z_2}) \end{align*} The natural guess at a generalization is that for any fixed $$\vec{k}\in\Re^3$$ the map $$\vec{v}\mapsto\vec{v}\dotprod\vec{k}$$ is linear. This statement is true. It follows from properties of the dot product we have seen earlier: $$(\vec{v}+\vec{u})\dotprod\vec{k}=\vec{v}\dotprod\vec{k}+ \vec{u}\dotprod\vec{k}$$ and $$(r\vec{v})\dotprod\vec{k}=r(\vec{v}\dotprod\vec{k})$$. (The natural guess at a generalization of this generalization, that the map from $$\Re^n$$ to $$\Re$$ whose action consists of taking the dot product of its argument with a fixed vector $$\vec{k}\in\Re^n$$ is linear, is also true.) \end{answer} \item \label{exer:HomoRONeMultByScalar} Show that every homomorphism from $$\Re^1$$ to $$\Re^1$$ acts via multiplication by a scalar. Conclude that every nontrivial linear transformation of $$\Re^1$$ is an isomorphism. Is that true for transformations of $$\Re^2$$? $$\Re^n$$? \begin{answer} Let $$\map{h}{\Re^1}{\Re^1}$$ be linear. A linear map is determined by its action on a basis, so fix the basis $$\sequence{1}$$ for $$\Re^1$$. For any $$r\in\Re^1$$ we have that $$h(r)=h(r\cdot 1)=r\cdot h(1)$$ and so $$h$$ acts on any argument $r$ by multiplying it by the constant $$h(1)$$. If $$h(1)$$ is not zero then the map is a correspondence\Dash its inverse is division by $$h(1)$$\Dash so any nontrivial transformation of $\Re^1$ is an isomorphism. This projection map is an example that shows that not every transformation of $$\Re^n$$ acts via multiplication by a constant when $$n>1$$, including when $n=2$. \begin{equation*} \colvec{x_1 \\ x_2 \\ \vdots \\ x_n} \mapsto\colvec{x_1 \\ 0 \\ \vdots \\ 0} \end{equation*} \end{answer} \item %(This will be used in \nearbyexercise{exer:Cosets} below.) \begin{exparts} \partsitem Show that for any scalars $$a_{1,1},\dots, a_{m,n}$$ this map $$\map{h}{\Re^n}{\Re^m}$$ is a homomorphism. \begin{equation*} \colvec{x_1 \\ \vdots \\ x_n} \mapsto \colvec{a_{1,1}x_1+\dots+a_{1,n}x_n \\ \vdots \\ a_{m,1}x_1+\cdots+a_{m,n}x_n} \end{equation*} \partsitem Show that for each $i$, the $$i$$-th derivative operator $d^i/dx^i$ is a linear transformation of $$\polyspace_n$$. Conclude that for any scalars $$c_k,\ldots, c_0$$ this map is a linear transformation of that space. \begin{equation*} f\mapsto c_{k}\frac{d^k}{dx^k}f+c_{k-1}\frac{d^{k-1}}{dx^{k-1}}f +\dots+ c_1\frac{d}{dx}f+c_0f \end{equation*} \end{exparts} \begin{answer} \begin{exparts} \partsitem Where $$c$$ and $$d$$ are scalars, we have this. \begin{multline*} h(c\cdot \colvec{x_1 \\ \vdots \\ x_n} +d\cdot \colvec{y_1 \\ \vdots \\ y_n}) \\ \begin{aligned} &=h(\colvec{cx_1+dy_1 \\ \vdots \\ cx_n+dy_n}) \\ &=\colvec{a_{1,1}(cx_1+dy_1)+\dots+a_{1,n}(cx_n+dy_n) \\ \vdots \\ a_{m,1}(cx_1+dy_1)+\dots+a_{m,n}(cx_n+dy_n)} \\ &=c\cdot\colvec{a_{1,1}x_1+\dots+a_{1,n}x_n \\ \vdots \\ a_{m,1}x_1+\dots+a_{m,n}x_n} +d\cdot\colvec{a_{1,1}y_1+\dots+a_{1,n}y_n \\ \vdots \\ a_{m,1}y_1+\dots+a_{m,n}y_n} \\ &=c\cdot h(\colvec{x_1 \\ \vdots \\ x_n}) +d\cdot h(\colvec{y_1 \\ \vdots \\ y_n}) \end{aligned} \end{multline*} \partsitem Each power $i$ of the derivative operator is linear because of these rules familiar from calculus. \begin{equation*} \frac{d^i}{dx^i}(\,f(x)+g(x)\,)=\frac{d^i}{dx^i}f(x) +\frac{d^i}{dx^i}g(x) \qquad \frac{d^i}{dx^i}\,r\cdot f(x)=r\cdot\frac{d^i}{dx^i}f(x) \end{equation*} Thus the given map is a linear transformation of $$\polyspace_n$$ because any linear combination of linear maps is also a linear map. \end{exparts} \end{answer} \item \nearbylemma{le:SpLinFcns} shows that a sum of linear functions is linear and that a scalar multiple of a linear function is linear. Show also that a composition of linear functions is linear. \begin{answer} (This argument has already appeared, as part of the proof that isomorphism is an equivalence.) Let $\map{f}{U}{V}$ and $\map{g}{V}{W}$ be linear. The composition preserves linear combinations \begin{multline*} \composed{g}{f}(c_1\vec{u}_1+c_2\vec{u}_2) =g(\,f(c_1\vec{u}_1+c_2\vec{u}_2)\,) =g(\,c_1f(\vec{u}_1)+c_2f(\vec{u}_2)\,) \\ =c_1\cdot g(f(\vec{u}_1))+c_2\cdot g(f(\vec{u}_2)) =c_1\cdot \composed{g}{f}(\vec{u}_1) +c_2\cdot \composed{g}{f}(\vec{u}_2) \end{multline*} where $\vec{u}_1,\vec{u}_2\in U$ and scalars $c_1,c_2$ \end{answer} \item Where $$\map{f}{V}{W}$$ is linear, suppose that $$f(\vec{v}_1)=\vec{w}_1$$, \ldots, $$f(\vec{v}_n)=\vec{w}_n$$ for some vectors $$\vec{w}_1$$, \ldots, $$\vec{w}_n$$ from $$W$$. \begin{exparts} \partsitem If the set of $$\vec{w}\,$$'s is independent, must the set of $$\vec{v}\,$$'s also be independent? \partsitem If the set of $$\vec{v}\,$$'s is independent, must the set of $$\vec{w}\,$$'s also be independent? \partsitem If the set of $$\vec{w}\,$$'s spans $$W$$, must the set of $$\vec{v}\,$$'s span $$V$$? \partsitem If the set of $$\vec{v}\,$$'s spans $$V$$, must the set of $$\vec{w}\,$$'s span $$W$$? \end{exparts} \begin{answer} \begin{exparts} \partsitem Yes. The set of $\vec{w}\,$'s cannot be linearly independent if the set of $\vec{v}\,$'s is linearly dependent because any nontrivial relationship in the domain $$\zero_V=c_1\vec{v}_1+\dots+c_n\vec{v}_n$$ would give a nontrivial relationship in the range $$f(\zero_V)=\zero_W=f(c_1\vec{v}_1+\dots+c_n\vec{v}_n) =c_1f(\vec{v}_1)+\dots+c_nf(\vec{v}_n) =c_1\vec{w}+\dots+c_n\vec{w}_n$$. \partsitem Not necessarily. For instance, the transformation of $$\Re^2$$ given by \begin{equation*} \colvec{x \\ y} \mapsto \colvec{x+y \\ x+y} \end{equation*} sends this linearly independent set in the domain to a linearly dependent image. \begin{equation*} \set{\vec{v}_1,\vec{v}_2}=\set{\colvec[r]{1 \\ 0},\colvec[r]{1 \\ 1}} \;\mapsto\; \set{\colvec[r]{1 \\ 1},\colvec[r]{2 \\ 2}}=\set{\vec{w}_1,\vec{w}_2} \end{equation*} \partsitem Not necessarily. An example is the projection map $$\map{\pi}{\Re^3}{\Re^2}$$ \begin{equation*} \colvec{x \\ y \\ z}\mapsto\colvec{x \\ y} \end{equation*} and this set that does not span the domain but maps to a set that does span the codomain. \begin{equation*} \set{\colvec[r]{1 \\ 0 \\ 0},\colvec[r]{0 \\ 1 \\ 0}} \mapsunder{\pi}\set{\colvec[r]{1 \\ 0},\colvec[r]{0 \\ 1}} \end{equation*} \partsitem Not necessarily. For instance, the injection map $\map{\iota}{\Re^2}{\Re^3}$ sends the standard basis $\stdbasis_2$ for the domain to a set that does not span the codomain. (\textit{Remark.} However, the set of $\vec{w}$'s does span the range. A proof is easy.) \end{exparts} \end{answer} \item Generalize \nearbyexample{ex:MatTransMapLinear} by proving that for every appropriate domain and codomain the matrix transpose map is linear. What are the appropriate domains and codomains? \begin{answer} Recall that the entry in row~$i$ and column~$j$ of the transpose of $M$ is the entry $m_{j,i}$ from row~$j$ and column~$i$ of $M$. Now, the check is routine. Start with the transpose of the combination. \begin{equation*} \trans{[r\cdot\begin{mat} \ &\vdots \\ \cdots &a_{i,j} &\cdots \\ &\vdots \end{mat} +s\cdot\begin{mat} \ &\vdots \\ \cdots &b_{i,j} &\cdots \\ &\vdots \end{mat}]} \end{equation*} Combine and take the transpose. \begin{equation*} =\trans{\begin{mat} \ &\vdots \\ \cdots &ra_{i,j}+sb_{i,j} &\cdots \\ &\vdots \end{mat}} =\begin{mat} \ &\vdots \\ \cdots &ra_{j,i}+sb_{j,i} &\cdots \\ &\vdots \end{mat} \end{equation*} Then bring out the scalars, and un-transpose. \begin{multline*} =r\cdot\begin{mat} \ &\vdots \\ \cdots &a_{j,i} &\cdots \\ &\vdots \end{mat} +s\cdot\begin{mat} \ &\vdots \\ \cdots &b_{j,i} &\cdots \\ &\vdots \end{mat} \\ =r\cdot\trans{\begin{mat} \ &\vdots \\ \cdots &a_{j,i} &\cdots \\ &\vdots \end{mat} } +s\cdot\trans{\begin{mat} \ &\vdots \\ \cdots &b_{j,i} &\cdots \\ &\vdots \end{mat} } \end{multline*} The domain is $$\matspace_{\nbym{m}{n}}$$ while the codomain is $$\matspace_{\nbym{n}{m}}$$. \end{answer} \item \begin{exparts} \partsitem Where $$\vec{u},\vec{v}\in \Re^n$$, by definition the line segment connecting them is the set $$\ell=\set{t\cdot\vec{u}+(1-t)\cdot\vec{v}\suchthat t\in [0..1]}$$. Show that the image, under a homomorphism $h$, of the segment between $\vec{u}$ and $\vec{v}$ is the segment between $h(\vec{u})$ and $h(\vec{v})$. \partsitem A subset of $$\Re^n$$ is \definend{convex}\index{convex set} if, for any two points in that set, the line segment joining them lies entirely in that set. (The inside of a sphere is convex while the skin of a sphere is not.) Prove that linear maps from $$\Re^n$$ to $$\Re^m$$ preserve the property of set convexity. \end{exparts} \begin{answer} \begin{exparts} \partsitem For any homomorphism $$\map{h}{\Re^n}{\Re^m}$$ we have \begin{equation*} h(\ell) =\set{h(t\cdot\vec{u}+(1-t)\cdot\vec{v})\suchthat t\in [0..1]} =\set{t\cdot h(\vec{u})+(1-t)\cdot h(\vec{v})\suchthat t\in [0..1]} \end{equation*} which is the line segment from $h(\vec{u})$ to $h(\vec{v})$. \partsitem We must show that if a subset of the domain is convex then its image, as a subset of the range, is also convex. Suppose that $$C\subseteq \Re^n$$ is convex and consider its image $h(C)$. To show $h(C)$ is convex we must show that for any two of its members, $\vec{d}_1$ and $\vec{d}_2$, the line segment connecting them \begin{equation*} \ell=\set{t\cdot\vec{d}_1+(1-t)\cdot\vec{d}_2\suchthat t\in [0..1]} \end{equation*} is a subset of $h(C)$. Fix any member $\hat{t}\cdot\vec{d}_1+(1-\hat{t})\cdot\vec{d}_2$ of that line segment. Because the endpoints of $\ell$ are in the image of $C$, there are members of $C$ that map to them, say $h(\vec{c}_1)=\vec{d}_1$ and $h(\vec{c}_2)=\vec{d}_2$. Now, where $\hat{t}$ is the scalar that we fixed in the first sentence of this paragraph, observe that $h(\hat{t}\cdot\vec{c}_1+(1-\hat{t})\cdot\vec{c}_2) =\hat{t}\cdot h(\vec{c}_1)+(1-\hat{t})\cdot h(\vec{c}_2) =\hat{t}\cdot\vec{d}_1+(1-\hat{t})\cdot\vec{d}_2$ Thus, any member of $\ell$ is a member of $h(C)$, and so $h(C)$ is convex. \end{exparts} \end{answer} \recommended \item \label{exer:HomosPresLinStruc} Let $$\map{h}{\Re^n}{\Re^m}$$ be a homomorphism. \begin{exparts} \partsitem Show that the image under $$h$$ of a line in $$\Re^n$$ is a (possibly degenerate) line in $$\Re^m$$. \partsitem What happens to a $$k$$-dimensional linear surface? \end{exparts} \begin{answer} \begin{exparts} \partsitem For $$\vec{v}_0,\vec{v}_1\in\Re^n$$, the line through $$\vec{v}_0$$ with direction $$\vec{v}_1$$ is the set $\set{\vec{v}_0+t\cdot \vec{v}_1\suchthat t\in\Re}$. The image under $h$ of that line $\set{h(\vec{v}_0+t\cdot \vec{v}_1)\suchthat t\in\Re} =\set{h(\vec{v}_0)+t\cdot h(\vec{v}_1)\suchthat t\in\Re}$ is the line through $h(\vec{v}_0)$ with direction $h(\vec{v}_1)$. If $$h(\vec{v}_1)$$ is the zero vector then this line is degenerate. \partsitem A $$k$$-dimensional linear surface in $$\Re^n$$ maps to a $$k$$-dimensional linear surface in $$\Re^m$$ (possibly it is degenerate). The proof is just like that the one for the line. \end{exparts} \end{answer} \item Prove that the restriction of a homomorphism to a subspace of its domain is another homomorphism. \begin{answer} Suppose that $$\map{h}{V}{W}$$ is a homomorphism and suppose that $$S$$ is a subspace of $$V$$. Consider the map $$\map{\hat{h}}{S}{W}$$ defined by $$\hat{h}(\vec{s})=h(\vec{s})$$. (The only difference between $\hat{h}$ and $h$ is the difference in domain.) Then this new map is linear: $$\hat{h}(c_1\cdot\vec{s}_1+c_2\cdot\vec{s}_2)= h(c_1\vec{s}_1+c_2\vec{s}_2)=c_1h(\vec{s}_1)+c_2h(\vec{s}_2)= c_1\cdot\hat{h}(\vec{s}_1)+c_2\cdot\hat{h}(\vec{s}_2)$$. \end{answer} \item Assume that $$\map{h}{V}{W}$$ is linear. \begin{exparts} \partsitem Show that the \definend{range space} of this map $$\set{h(\vec{v})\suchthat \vec{v}\in V}$$ is a subspace of the codomain $$W$$. \partsitem Show that the \definend{null space} of this map $$\set{\vec{v}\in V\suchthat h(\vec{v})=\zero_W}$$ is a subspace of the domain $$V$$. \partsitem Show that if $$U$$ is a subspace of the domain $$V$$ then its image $$\set{h(\vec{u})\suchthat \vec{u}\in U}$$ is a subspace of the codomain $$W$$. This generalizes the first item. \partsitem Generalize the second item. \end{exparts} \begin{answer} This will appear as a lemma in the next subsection. \begin{exparts} \partsitem The range is nonempty because $$V$$ is nonempty. To finish we need to show that it is closed under combinations. A combination of range vectors has the form, where $$\vec{v}_1,\dots,\vec{v}_n\in V$$, \begin{equation*} c_1\cdot h(\vec{v}_1)+\dots+c_n\cdot h(\vec{v}_n) = h(c_1\vec{v}_1)+\dots+h(c_n\vec{v}_n) = h(c_1\cdot \vec{v}_1+\dots+c_n\cdot \vec{v}_n), \end{equation*} which is itself in the range as $$c_1\cdot \vec{v}_1+\dots+c_n\cdot \vec{v}_n$$ is a member of domain $$V$$. Therefore the range is a subspace. \partsitem The null space is nonempty since it contains $\zero_V$, as $$\zero_V$$ maps to $$\zero_W$$. It is closed under linear combinations because, where $$\vec{v}_1,\dots,\vec{v}_n\in V$$ are elements of the inverse image $$\set{\vec{v}\in V\suchthat h(\vec{v})=\zero_W}$$, for $$c_1,\ldots,c_n\in\Re$$ \begin{equation*} \zero_W=c_1\cdot h(\vec{v}_1)+\dots+c_n\cdot h(\vec{v}_n) =h(c_1\cdot \vec{v}_1+\dots+c_n\cdot \vec{v}_n) \end{equation*} and so $$c_1\cdot \vec{v}_1+\dots+c_n\cdot \vec{v}_n$$ is also in the inverse image of $$\zero_W$$. \partsitem This image of $$U$$ nonempty because $$U$$ is nonempty. For closure under combinations, where $$\vec{u}_1,\ldots,\vec{u}_n\in U$$, \begin{equation*} c_1\cdot h(\vec{u}_1)+\dots+c_n\cdot h(\vec{u}_n) = h(c_1\cdot \vec{u}_1)+\dots+h(c_n\cdot \vec{u}_n) = h(c_1\cdot \vec{u}_1+\dots+c_n\cdot \vec{u}_n) \end{equation*} which is itself in $$h(U)$$ as $$c_1\cdot \vec{u}_1+\dots+c_n\cdot \vec{u}_n$$ is in $$U$$. Thus this set is a subspace. \partsitem The natural generalization is that the inverse image of a subspace of is a subspace. Suppose that $$X$$ is a subspace of $$W$$. Note that $$\zero_W\in X$$ so that the set $$\set{\vec{v}\in V \suchthat h(\vec{v})\in X}$$ is not empty. To show that this set is closed under combinations, let $$\vec{v}_1,\dots,\vec{v}_n$$ be elements of $$V$$ such that $$h(\vec{v}_1)=\vec{x}_1$$, \ldots, $$h(\vec{v}_n)=\vec{x}_n$$ and note that \begin{equation*} h(c_1\cdot \vec{v}_1+\dots+c_n\cdot \vec{v}_n) =c_1\cdot h(\vec{v}_1)+\dots+c_n\cdot h(\vec{v}_n) =c_1\cdot \vec{x}_1+\dots+c_n\cdot \vec{x}_n \end{equation*} so a linear combination of elements of $$h^{-1}(X)$$ is also in $$h^{-1}(X)$$. \end{exparts} \end{answer} \item Consider the set of isomorphisms from a vector space to itself. Is this a subspace of the space $$\linmaps{V}{V}$$ of homomorphisms from the space to itself? \begin{answer} No; the set of isomorphisms does not contain the zero map (unless the space is trivial). \end{answer} \item Does \nearbytheorem{th:HomoDetActOnBasis} need that $\sequence{\vec{\beta}_1,\ldots,\vec{\beta}_n}$ is a basis? That is, can we still get a well-defined and unique homomorphism if we drop either the condition that the set of $\vec{\beta}$'s be linearly independent, or the condition that it span the domain? \begin{answer} If $\sequence{\vec{\beta}_1,\ldots,\vec{\beta}_n}$ doesn't span the space then the map needn't be unique. For instance, if we try to define a map from $\Re^2$ to itself by specifying only that $\vec{e}_1$ maps to itself, then there is more than one homomorphism possible; both the identity map and the projection map onto the first component fit this condition. If we drop the condition that $\sequence{\vec{\beta}_1,\ldots,\vec{\beta}_n}$ is linearly independent then we risk an inconsistent specification (i.e, there could be no such map). An example is if we consider $\sequence{\vec{e}_2,\vec{e}_1,2\vec{e}_1}$, and try to define a map from $\Re^2$ to itself that sends $\vec{e}_2$ to itself, and sends both $\vec{e}_1$ and $2\vec{e}_1$ to $\vec{e}_1$. No homomorphism can satisfy these three conditions. \end{answer} \item Let $$V$$ be a vector space and assume that the maps $$\map{f_1,f_2}{V}{\Re^1}$$ are linear. \begin{exparts} \partsitem Define a map $$\map{F}{V}{\Re^2}$$ whose component functions are the given linear ones. \begin{equation*} \vec{v}\mapsto\colvec{f_1(\vec{v}) \\ f_2(\vec{v})} \end{equation*} Show that $$F$$ is linear. \partsitem Does the converse hold\Dash is any linear map from $$V$$ to $$\Re^2$$ made up of two linear component maps to $$\Re^1$$? \partsitem Generalize. \end{exparts} \begin{answer} \begin{exparts} \partsitem Briefly, the check of linearity is this. \begin{multline*} F(r_1\cdot \vec{v}_1+r_2\cdot \vec{v}_2) =\colvec{f_1(r_1\vec{v}_1+r_2\vec{v}_2) \\ f_2(r_1\vec{v}_1+r_2\vec{v}_2)} \\ =r_1\colvec{f_1(\vec{v}_1) \\ f_2(\vec{v}_1)} +r_2\colvec{f_1(\vec{v}_2) \\ f_2(\vec{v}_2)} =r_1\cdot F(\vec{v}_1)+r_2\cdot F(\vec{v}_2) \end{multline*} \partsitem Yes. Let $$\map{\pi_1}{\Re^2}{\Re^1}$$ and $$\map{\pi_2}{\Re^2}{\Re^1}$$ be the projections \begin{equation*} \colvec{x \\ y}\mapsunder{\pi_1} x \quad\text{and}\quad \colvec{x \\ y}\mapsunder{\pi_2} y \end{equation*} onto the two axes. Now, where $$f_1(\vec{v})=\pi_1(F(\vec{v}))$$ and $$f_2(\vec{v})=\pi_2(F(\vec{v}))$$ we have the desired component functions. \begin{equation*} F(\vec{v})= \colvec{f_1(\vec{v}) \\ f_2(\vec{v})} \end{equation*} They are linear because they are the composition of linear functions, and the fact that the composition of linear functions is linear was part of the proof that isomorphism is an equivalence relation (alternatively, the check that they are linear is straightforward). \partsitem In general, a map from a vector space $$V$$ to an $$\Re^n$$ is linear if and only if each of the component functions is linear. The verification is as in the prior item. \end{exparts} \end{answer} \end{exercises} \subsection{Range space and Null space} Isomorphisms and homomorphisms both preserve structure. The difference is that homomorphisms have fewer restrictions, since they needn't be onto and needn't be one-to-one. We will examine what can happen with homomorphisms that cannot happen with isomorphisms. First consider the fact that homomorphisms need not be onto. Of course, each function is onto some set, namely its range. For example, the injection map $$\map{\iota}{\Re^2}{\Re^3}$$ \begin{equation*} \colvec{x \\ y} \mapsto \colvec{x \\ y \\ 0} \end{equation*} is a homomorphism, and is not onto $\Re^3$. But it is onto the $xy$-plane. \begin{lemma} \label{le:RangeIsSubSp} %<*lm:RangeIsSubSp> Under a homomorphism, the image of any subspace of the domain is a subspace of the codomain. In particular, the image of the entire space, the range of the homomorphism, is a subspace of the codomain. % \end{lemma} \begin{proof} %<*pf:RangeIsSubSp> Let $\map{h}{V}{W}$ be linear and let $S$ be a subspace of the domain $V$. The image $h(S)$ is a subset of the codomain $W$, which is nonempty because $S$ is nonempty. Thus, to show that $h(S)$ is a subspace of $W$ we need only show that it is closed under linear combinations of two vectors. If $h(\vec{s}_1)$ and $h(\vec{s}_2)$ are members of $h(S)$ then $c_1\cdot h(\vec{s}_1)+c_2\cdot h(\vec{s}_2) = h(c_1\cdot \vec{s}_1)+h(c_2\cdot \vec{s}_2) = h(c_1\cdot \vec{s}_1+c_2\cdot \vec{s}_2)$ is also a member of $h(S)$ because it is the image of $$c_1\cdot \vec{s}_1+c_2\cdot \vec{s}_2$$ from $$S$$. % \end{proof} \begin{definition} \label{df:RangeSpace} %<*df:RangeSpace> The \definend{range space}\index{range space}\index{homomorphism!range space} of a homomorphism $$\map{h}{V}{W}$$ is \begin{equation*} \rangespace{h}=\set{h(\vec{v})\suchthat \vec{v}\in V} \end{equation*} sometimes denoted $$h(V)$$. The dimension of the range space is the map's \definend{rank}.\index{rank!of a homomorphism} % \end{definition} \noindent We shall soon see the connection between the rank of a map and the rank of a matrix. \begin{example} \label{ex:DerivMapRnge} For the derivative map $$\map{d/dx}{\polyspace_3}{\polyspace_3}$$ given by $$a_0+a_1x+a_2x^2+a_3x^3 \mapsto a_1+2a_2x+3a_3x^2$$ the range space $$\rangespace{d/dx}$$ is the set of quadratic polynomials $$\set{r+sx+tx^2\suchthat r,s,t\in\Re }$$. Thus, this map's rank is~$$3$$. \end{example} \begin{example} \label{ex:MatToPolyRnge} With this homomorphism $$\map{h}{M_{\nbyn{2}}}{\polyspace_3}$$ \begin{equation*} \begin{mat} a &b \\ c &d \end{mat} \mapsto (a+b+2d)+cx^2+cx^3 \end{equation*} an image vector in the range can have any constant term, must have an $x$ coefficient of zero, and must have the same coefficient of $x^2$ as of $x^3$. That is, the range space is $$\rangespace{h}=\set{r+sx^2+sx^3\suchthat r,s\in\Re}$$ and so the rank is~$$2$$. \end{example} The prior result shows that, in passing from the definition of isomorphism to the more general definition of homomorphism, omitting the onto requirement doesn't make an essential difference. Any homomorphism is onto some space, namely its range. However, omitting the one-to-one condition does make a difference. A homomorphism may have many elements of the domain that map to one element of the codomain. Below is a bean sketch of a many-to-one map between sets.\appendrefs{many-to-one maps}\spacefactor=1000 % It shows three elements of the codomain that are each the image of many members of the domain. (Rather than picture lots of individual $\mapsto$ arrows, each association of many inputs with one output shows only one such arrow.) \begin{center} \includegraphics{ch3.5} % bean to bean; many to one \end{center} %<*InverseImage> Recall that for any function $\map{h}{V}{W}$, the set of elements of $V$ that map to $$\vec{w}\in W$$ is the \definend{inverse image\/}\index{inverse image}% \index{function! inverse image} $h^{-1}(\vec{w})=\set{\vec{v}\in V\suchthat h(\vec{v})=\vec{w}}$. % Above, the left side shows three inverse image sets. \begin{example} Consider the projection\index{projection} $$\map{\pi}{\Re^3}{\Re^2}$$ \begin{equation*} \colvec{x \\ y \\ z} \mapsunder{\pi} \colvec{x \\ y} \end{equation*} which is a homomorphism that is many-to-one. An inverse image set is a vertical line of vectors in the domain. \begin{center} \includegraphics{ch3.11} \end{center} One example is this. \begin{equation*} \pi^{-1}(\colvec[r]{1 \\ 3})=\set{\colvec[r]{1 \\ 3 \\ z}\suchthat z\in\Re} \end{equation*} \end{example} \begin{example} \label{ex:RTwoHomoREasyOneMap} This homomorphism $\map{h}{\Re^2}{\Re^1}$ \begin{equation*} \colvec{x \\ y} \mapsunder{h} x+y \end{equation*} is also many-to-one. For a fixed $w\in\Re^1$ the inverse image $h^{-1}(w)$ \begin{center} \includegraphics{ch3.12} \end{center} is the set of plane vectors whose components add to $w$. \end{example} % The above examples have only to do with the % fact that we are considering functions, % specifically, many-to-one functions. % They show the inverse images % as sets of vectors that are % related to the image vector $\vec{w}$. % But these are more than just arbitrary functions, they are % homomorphisms; what do the two preservation % conditions say about the relationships? In generalizing from isomorphisms to homomorphisms by dropping the one-to-one condition we lose the property that, intuitively, the domain is the same'' as the range. We lose, that is, that the domain corresponds perfectly to the range. The examples below illustrate that what we retain is that a homomorphism describes how the domain is analogous to'' or like'' the range. \begin{example} \label{ex:RThreeHomoRTwo} %\label{exPicProj} We think of $\Re^3$ as like $\Re^2$ except that vectors have an extra component. That is, we think of the vector with components $x$, $y$, and~$z$ as like the vector with components $x$ and~$y$. Defining the projection map $\pi$ makes precise which members of the domain we are thinking of as related to which members of the codomain. To understanding how the preservation conditions in the definition of homomorphism show that the domain elements are like the codomain elements, start by picturing $\Re^2$ as the $xy$-plane inside of $\Re^3$ (the $xy$~plane inside of $\Re^3$ is a set of three-tall vectors with a third component of zero and so does not precisely equal the set of two-tall vectors~$\Re^2$, but this embedding makes the picture much clearer). The preservation of addition property says that vectors in $$\Re^3$$ act like their shadows in the plane. \begin{center} \small \begin{tabular}{@{}c@{}c@{}c@{}c@{}c@{}} \includegraphics{ch3.1} &&\includegraphics{ch3.2} &&\includegraphics{ch3.3} \\[1.5ex] {\small $\colvec{x_1 \\ y_1 \\ z_1}$ above $\colvec{x_1 \\ y_1}$} &{\small \ plus\ } &{\small $\colvec{x_2 \\ y_2 \\ z_2}$ above $\colvec{x_2 \\ y_2}$} &{\small \ equals\ } &{\small $\colvec{x_1+y_1 \\ y_1+y_2 \\ z_1+z_2}$ above $\colvec{x_1+x_2 \\ y_1+y_2}$} \end{tabular} \end{center} \noindent Thinking of $\pi(\vec{v})$ as the shadow'' of $\vec{v}$ in the plane gives this restatement: the sum of the shadows $\pi(\vec{v}_1)+\pi(\vec{v}_2)$ equals the shadow of the sum $\pi(\vec{v}_1+\vec{v}_2)$. Preservation of scalar multiplication is similar. Drawing the codomain $\Re^2$ on the right gives a picture that is uglier but is more faithful to the bean sketch above. \begin{center} \small \includegraphics{ch3.4} \end{center} Again, the domain vectors that map to $\vec{w}_1$ lie in a vertical line; one is drawn, in gray. Call any member of this inverse image $\pi^{-1}(\vec{w}_1)$ a $\vec{w}_1$~vector.'' Similarly, there is a vertical line of $\vec{w}_2$~vectors'' and a vertical line of $\vec{w}_1+\vec{w}_2$~vectors.'' Now, saying that $\pi$ is a homomorphism is recognizing that if $\pi(\vec{v}_1)=\vec{w}_1$ and $\pi(\vec{v}_2)=\vec{w}_2$ then $\pi(\vec{v}_1+\vec{v}_2)=\pi(\vec{v}_1)+\pi(\vec{v}_2) =\vec{w}_1+\vec{w}_2$. That is, the classes add:~any $$\vec{w}_1$$~vector plus any $$\vec{w}_2$$~vector equals a $$\vec{w}_1+\vec{w}_2$$~vector. Scalar multiplication is similar. So although $\Re^3$ and $\Re^2$ are not isomorphic $\pi$ describes a way in which they are alike:~vectors in $\Re^3$ add as do the associated vectors in $\Re^2$\Dash vectors add as their shadows add. \end{example} \begin{example} \label{ex:RTwoHomoRHardOne} A homomorphism can express an analogy between spaces that is more subtle than the prior one. For the map from \nearbyexample{ex:RTwoHomoREasyOneMap} \begin{equation*} \colvec{x \\ y} \mapsunder{h} x+y \end{equation*} fix two numbers in the range $w_1, w_2\in\Re$. A $\vec{v}_1$ that maps to $w_1$ has components that add to $w_1$, so the inverse image $h^{-1}(w_1)$ is the set of vectors with endpoint on the diagonal line $x+y=w_1$. Think of these as $w_1$ vectors.'' Similarly we have $w_2$ vectors'' and $w_1+w_2$ vectors.'' The addition preservation property says this. \begin{center} \small \begin{tabular}{@{}ccccc@{}} \includegraphics{ch3.6} &&\includegraphics{ch3.7} &&\includegraphics{ch3.8} \\[1.5ex] {\small a $w_1$ vector''} &{\small plus} &{\small a $w_2$ vector''} &{\small equals} &{\small a $w_1+w_2$ vector''} \end{tabular} \end{center} Restated, if we add a $w_1$~vector to a $w_2$~vector then $h$ maps the result to a $w_1+w_2$ vector. Briefly, the sum of the images is the image of the sum. Even more briefly, $$h(\vec{v}_1)+h(\vec{v}_2)=h(\vec{v}_1+\vec{v}_2)$$. % (The preservation of scalar multiplication condition has a % similar restatement.) \end{example} \begin{example} \label{ex:PicRThreeToRTwo} The inverse images can be structures other than lines. For the linear map $$\map{h}{\Re^3}{\Re^2}$$ \begin{equation*} \colvec{x \\ y \\ z} \mapsto \colvec{x \\ x} \end{equation*} the inverse image sets are planes $x=0$, $x=1$, etc., perpendicular to the $$x$$-axis. \begin{center} \small \includegraphics{ch3.9} \end{center} \end{example} We won't describe how every homomorphism that we will use is an analogy because the formal sense that we make of alike in that~\ldots'' is a homomorphism exists such that~\ldots'. Nonetheless, the idea that a homomorphism between two spaces expresses how the domain's vectors fall into classes that act like the range's vectors is a good way to view homomorphisms. Another reason that we won't treat all of the homomorphisms that we see as above is that many vector spaces are hard to draw, e.g., a space of polynomials. But there is nothing wrong with leveraging spaces that we can draw: from the three examples \ref{ex:RThreeHomoRTwo}, \ref{ex:RTwoHomoRHardOne}, and~\ref{ex:PicRThreeToRTwo} we draw two insights. The first insight is that in all three examples the inverse image of the range's zero vector is a line or plane through the origin. It is therefore a subspace of the domain. \begin{lemma} \label{le:NullspIsSubSp} %<*lm:NullspIsSubSp> For any homomorphism the inverse image of a subspace of the range is a subspace of the domain. In particular, the inverse image of the trivial subspace of the range is a subspace of the domain. % \end{lemma} \noindent (The examples above consider inverse images of single vectors but this result is about inverse images of sets $h^{-1}(S)=\set{\vec{v}\in V\suchthat h(\vec{v})\in S}$. We use the same term for both by taking the inverse image of a single element $h^{-1}(\vec{w})$ to be the inverse image of the one-element set $h^{-1}(\set{\vec{w}})$.) \begin{proof} %<*pf:NullspIsSubSp> Let $\map{h}{V}{W}$ be a homomorphism and let $S$ be a subspace of the range space of $h$. Consider the inverse image of $S$. It is nonempty because it contains $\zero_V$, since $$h(\zero_V)=\zero_W$$ and $$\zero_W$$ is an element of $S$ as $S$ is a subspace. To finish we show that $h^{-1}(S)$ is closed under linear combinations. Let $$\vec{v}_1$$ and $$\vec{v}_2$$ be two of its elements, so that $h(\vec{v}_1)$ and $h(\vec{v}_2)$ are elements of $S$. Then $c_1\vec{v}_1+c_2\vec{v}_2$ is an element of the inverse image $h^{-1}(S)$ because $h(c_1\vec{v}_1+c_2\vec{v}_2) =c_1h(\vec{v}_1)+c_2h(\vec{v}_2)$ is a member of $S$. % \end{proof} \begin{definition} \label{df:NullSpace} %<*df:NullSpace> The \definend{null space}\index{homomorphism!null space}\index{null space} or \definend{kernel}\index{kernel, of linear map} of a linear map $$\map{h}{V}{W}$$ is the inverse image of $\zero_W$. \begin{equation*} \nullspace{h}=h^{-1}(\zero_W)=\set{\vec{v}\in V\suchthat h(\vec{v})=\zero_W} \end{equation*} The dimension of the null space is the map's \definend{nullity}\index{nullity}\index{homomorphism!nullity}. % \end{definition} \begin{center} \includegraphics{ch3.10} \end{center} \begin{example} The map from \nearbyexample{ex:DerivMapRnge} has this null space $$\nullspace{d/dx}=\set{a_0+0x+0x^2+0x^3\suchthat a_0\in\Re}$$ so its nullity is $1$. \end{example} \begin{example} The map from \nearbyexample{ex:MatToPolyRnge} has this null space, and nullity $2$. \begin{equation*} \nullspace{h}=\set{\begin{mat} a &b \\ 0 &-(a+b)/2 \end{mat}\suchthat a,b\in\Re} \end{equation*} \end{example} Now for the second insight from the above examples. In \nearbyexample{ex:RThreeHomoRTwo} each of the vertical lines squashes down to a single point\Dash in passing from the domain to the range, $\pi$ takes all of these one-dimensional vertical lines and maps them to a point, leaving the range smaller than the domain by one dimension. Similarly, in \nearbyexample{ex:RTwoHomoRHardOne} the two-dimensional domain compresses to a one-dimensional range by breaking the domain into the diagonal lines and maps each of those to a single member of the range. Finally, in \nearbyexample{ex:PicRThreeToRTwo} the domain breaks into planes which get squashed to a point and so the map starts with a three-dimensional domain but ends two smaller, with a one-dimensional range. (The codomain is two-dimensional but the range is one-dimensional and the dimension of the range is what matters.) \begin{theorem} \label{th:RankPlusNullEqDim} \index{rank!of a homomorphism} %<*th:RankPlusNullEqDim> A linear map's rank plus its nullity equals the dimension of its domain. % \end{theorem} \begin{proof} %<*pf:RankPlusNullEqDim0> Let $$\map{h}{V}{W}$$ be linear and let $$B_N=\sequence{\vec{\beta}_1,\ldots,\vec{\beta}_k}$$ be a basis for the null space. Expand that to a basis $$B_V=\sequence{\vec{\beta}_1,\dots,\vec{\beta}_k, \vec{\beta}_{k+1},\dots,\vec{\beta}_n}$$ for the entire domain, using Corollary~Two.III.\ref{cor:LIExpBas}. We shall show that $$B_R=\sequence{ h(\vec{\beta}_{k+1}),\dots,h(\vec{\beta}_n)}$$ is a basis for the range space. Then counting the size of the bases gives the result. % %<*pf:RankPlusNullEqDim1> To see that $$B_R$$ is linearly independent, consider $$\zero_W=c_{k+1}h(\vec{\beta}_{k+1})+\dots+c_nh(\vec{\beta}_n)$$. We have $$\zero_W=h(c_{k+1}\vec{\beta}_{k+1}+\dots+c_n\vec{\beta}_n)$$ and so $$c_{k+1}\vec{\beta}_{k+1}+\dots+c_n\vec{\beta}_n$$ is in the null space of $h$. As $$B_N$$ is a basis for the null space there are scalars $$c_1,\dots,c_k$$ satisfying this relationship. \begin{equation*} c_1\vec{\beta}_1+\dots+c_k\vec{\beta}_k = c_{k+1}\vec{\beta}_{k+1}+\dots+c_n\vec{\beta}_n \end{equation*} But this is an equation among members of $$B_V$$, which is a basis for $$V$$, so each $c_i$ equals $0$. Therefore $$B_R$$ is linearly independent. % %<*pf:RankPlusNullEqDim2> To show that $$B_R$$ spans the range space consider a member of the range space $$h(\vec{v})$$. Express $$\vec{v}$$ as a linear combination $\vec{v}=c_1\vec{\beta}_1+\dots+c_n\vec{\beta}_n$ of members of $$B_V$$. This gives $h(\vec{v})=h(c_1\vec{\beta}_1+\dots+c_n\vec{\beta}_n) =c_1h(\vec{\beta}_1)+\dots+c_kh(\vec{\beta}_k) +c_{k+1}h(\vec{\beta}_{k+1})+\dots+c_nh(\vec{\beta}_n)$ and since $\vec{\beta}_1$, \ldots, $\vec{\beta}_k$ are in the null space, we have that $h(\vec{v})=\zero+\dots+\zero +c_{k+1}h(\vec{\beta}_{k+1})+\dots+c_nh(\vec{\beta}_n)$. Thus, $h(\vec{v})$ is a linear combination of members of $$B_R$$, and so $B_R$ spans the range space. % \end{proof} \begin{example} Where $$\map{h}{\Re^3}{\Re^4}$$ is \begin{equation*} \colvec{x \\ y \\ z} \mapsunder{h} \colvec{x \\ 0 \\ y \\ 0} \end{equation*} the range space and null space are \begin{equation*} \rangespace{h}= \set{\colvec{a \\ 0 \\ b \\ 0}\suchthat a,b\in\Re } \quad\text{and}\quad \nullspace{h}= \set{\colvec{0 \\ 0 \\ z}\suchthat z\in\Re } \end{equation*} and so the rank of $h$ is $2$ while the nullity is $1$. \end{example} \begin{example} If $$\map{t}{\Re}{\Re}$$ is the linear transformation $$x\mapsto -4x,$$ then the range is $$\rangespace{t}=\Re$$. The rank is $1$ and the nullity is $0$. \end{example} \begin{corollary} \label{cor:RankDecreases} The rank of a linear map is less than or equal to the dimension of the domain. Equality holds if and only if the nullity of the map is $0$. \end{corollary} We know that an isomorphism exists between two spaces if and only if the dimension of the range equals the dimension of the domain. We have now seen that for a homomorphism to exist a necessary condition is that the dimension of the range must be less than or equal to the dimension of the domain. For instance, there is no homomorphism from $$\Re^2$$ onto $$\Re^3$$. There are many homomorphisms from $$\Re^2$$ into $$\Re^3$$, but none onto. The range space of a linear map can be of dimension strictly less than the dimension of the domain and so linearly independent sets in the domain may map to linearly dependent sets in the range. (\nearbyexample{ex:DerivMapRnge}'s derivative transformation on $\polyspace_3$ has a domain of dimension~$4$ but a range of dimension~$3$ and the derivative sends $\set{1,x,x^2,x^3}$ to $\set{0,1,2x,3x^2}$). That is, under a homomorphism independence may be lost. In contrast, dependence stays. \begin{lemma} \label{lm:ImageLinearlyDependentIsLinearlyDependent} %<*lm:ImageLinearlyDependentIsLinearlyDependent> Under a linear map, the image of a linearly dependent set is linearly dependent. % \end{lemma} \begin{proof} %<*pf:ImageLinearlyDependentIsLinearlyDependent> Suppose that $$c_1\vec{v}_1+\dots+c_n\vec{v}_n=\zero_V$$ with some $c_i$ nonzero. Apply $h$ to both sides: $$h(c_1\vec{v}_1+\dots+c_n\vec{v}_n)=c_1h(\vec{v}_1)+\dots+c_nh(\vec{v}_n)$$ and $$h(\zero_V)=\zero_W$$. Thus we have $c_1h(\vec{v}_1)+\dots+c_nh(\vec{v}_n)=\zero_W$ with some $c_i$ nonzero. % \end{proof} When is independence not lost? The obvious sufficient condition is when the homomorphism is an isomorphism. This condition is also necessary; see \nearbyexercise{exer:NonSingIffPreservLI}. We will finish this subsection comparing homomorphisms with isomorphisms by observing that a one-to-one homomorphism is an isomorphism from its domain onto its range. % \begin{definition} % A linear map that is one-to-one is % {\em nonsingular}\index{homomorphism!nonsingular}% % \index{nonsingular!homomorphism}. % \end{definition} % %\begin{remark} % \noindent (In the next section we will see the connection % between this use of nonsingular' for maps and its familiar % use for matrices.) \begin{example} This one-to-one homomorphism $$\map{\iota}{\Re^2}{\Re^3}$$ \begin{equation*} \colvec{x \\ y} \mapsunder{\iota} \colvec{x \\ y \\ 0} \end{equation*} gives a correspondence between $$\Re^2$$ and the $$xy$$-plane subset of $$\Re^3$$. \end{example} % The prior observation allows us to adapt some results about isomorphisms. \begin{theorem} \label{th:OOHomoEquivalence} %<*th:OOHomoEquivalence> Where $$V$$ is an $$n$$-dimensional vector space, these are equivalent statements about a linear map $$\map{h}{V}{W}$$. \begin{tfae} \item $$h$$ is one-to-one \item $$h$$ has an inverse from its range to its domain that is a linear map \item $$\nullspace{h}=\set{\zero\,}$$, that is, $$\nullity(h)=0$$ \item $$\rank (h)=n$$ \item if $$\sequence{\vec{\beta}_1,\dots,\vec{\beta}_n}$$ is a basis for $$V$$ then $$\sequence{h(\vec{\beta}_1),\dots,h(\vec{\beta}_n)}$$ is a basis for $$\rangespace{h}$$ \end{tfae} % \end{theorem} \begin{proof} %<*pf:OOHomoEquivalence0> We will first show that $$\text{(1)} \Longleftrightarrow \text{(2)}$$. We will then show that $$\text{(1)}\implies \text{(3)}\implies \text{(4)}\implies \text{(5)}\implies \text{(2)}$$. % %<*pf:OOHomoEquivalence1> For $$\text{(1)} \Longrightarrow \text{(2)}$$, suppose that the linear map $h$ is one-to-one, and therefore has an inverse $\map{h^{-1}}{\rangespace{h}}{V}$. The domain of that inverse is the range of $h$ and thus a linear combination of two members of it has the form $c_1h(\vec{v}_1)+c_2h(\vec{v}_2)$. On that combination, the inverse $$h^{-1}$$ gives this. \begin{align*} h^{-1}(c_1h(\vec{v}_1)+c_2h(\vec{v}_2)) &=h^{-1}(h(c_1\vec{v}_1+c_2\vec{v}_2)) \\ &=\composed{h^{-1}}{h}\;(c_1\vec{v}_1+c_2\vec{v}_2) \\ &=c_1\vec{v}_1+c_2\vec{v}_2 \\ % &=c_1\composed{h^{-1}}{h}\,(\vec{v}_1) % +c_2\composed{h^{-1}}{h}\,(\vec{v}_2) \\ &=c_1\cdot h^{-1}(h(\vec{v}_1))+c_2\cdot h^{-1}(h(\vec{v}_2)) \end{align*} Thus if a linear map has an inverse then the inverse must be linear. But this also gives the $$\text{(2)} \Longrightarrow \text{(1)}$$ implication, because the inverse itself must be one-to-one. % %<*pf:OOHomoEquivalence2> Of the remaining implications, $$\text{(1)}\implies \text{(3)}$$ holds because any homomorphism maps $$\zero_V$$ to $$\zero_W$$, but a one-to-one map sends at most one member of $$V$$ to $$\zero_W$$. Next, $$\text{(3)} \implies \text{(4)}$$ is true since rank plus nullity equals the dimension of the domain. % %<*pf:OOHomoEquivalence3> For $$\text{(4)} \implies \text{(5)}$$, to show that $$\sequence{h(\vec{\beta}_1),\dots,h(\vec{\beta}_n)}$$ is a basis for the range space we need only show that it is a spanning set, because by assumption the range has dimension $n$. Consider $h(\vec{v})\in\rangespace{h}$. Expressing $\vec{v}$ as a linear combination of basis elements produces $$h(\vec{v})=h(\lincombo{c}{\vec{\beta}})$$, which gives that $$h(\vec{v})=c_1h(\vec{\beta}_1)+\dots+c_nh(\vec{\beta}_n)$$, as desired. % %<*pf:OOHomoEquivalence4> Finally, for the $$\text{(5)}\implies \text{(2)}$$ implication, assume that $$\sequence{\vec{\beta}_1,\dots,\vec{\beta}_n}$$ is a basis for $$V$$ so that $$\sequence{h(\vec{\beta}_1),\dots,h(\vec{\beta}_n)}$$ is a basis for $$\rangespace{h}$$. Then every $$\vec{w}\in\rangespace{h}$$ has the unique representation $$\vec{w}=c_1h(\vec{\beta}_1)+\dots+c_nh(\vec{\beta}_n)$$. Define a map from $$\rangespace{h}$$ to $V$ by \begin{equation*} \vec{w} \;\mapsto\; \lincombo{c}{\vec{\beta}} \end{equation*} (uniqueness of the representation makes this well-defined). Checking that it is linear and that it is the inverse of $h$ are easy. % \end{proof} We have seen that a linear map expresses how the structure of the domain is like that of the range. We can think of such a map as organizing the domain space into inverse images of points in the range. In the special case that the map is one-to-one, each inverse image is a single point and the map is an isomorphism between the domain and the range. \begin{exercises} \recommended \item Let $$\map{h}{\polyspace_3}{\polyspace_4}$$ be given by $$p(x)\mapsto x\cdot p(x)$$. Which of these are in the null space? Which are in the range space? \begin{exparts*} \partsitem $$x^3$$ \partsitem $$0$$ \partsitem $$7$$ \partsitem $$12x-0.5x^3$$ \partsitem $$1+3x^2-x^3$$ \end{exparts*} \begin{answer} First, to answer whether a polynomial is in the null space, we have to consider it as a member of the domain $\polyspace_3$. To answer whether it is in the range space, we consider it as a member of the codomain $\polyspace_4$. That is, for $p(x)=x^4$, the question of whether it is in the range space is sensible but the question of whether it is in the null space is not because it is not even in the domain. \begin{exparts} \partsitem The polynomial $x^3\in\polyspace_3$ is not in the null space because $h(x^3)=x^4$ is not the zero polynomial in $\polyspace_4$. The polynomial $x^3\in\polyspace_4$ is in the range space because $x^2\in\polyspace_3$ is mapped by $h$ to $x^3$. \partsitem The answer to both questions is, Yes, because $h(0)=0$.'' The polynomial $0\in\polyspace_3$ is in the null space because it is mapped by $h$ to the zero polynomial in $\polyspace_4$. The polynomial $0\in\polyspace_4$ is in the range space because it is the image, under $h$, of $0\in\polyspace_3$. \partsitem The polynomial $7\in\polyspace_3$ is not in the null space because $h(7)=7x$ is not the zero polynomial in $\polyspace_4$. The polynomial $7\in\polyspace_4$ is not in the range space because there is no member of the domain that when multiplied by $x$ gives the constant polynomial $p(x)=7$. \partsitem The polynomial $12x-0.5x^3\in\polyspace_3$ is not in the null space because $h(12x-0.5x^3)=12x^2-0.5x^4$. The polynomial $12x-0.5x^3\in\polyspace_4$ is in the range space because it is the image of $12-0.5x^2$. \partsitem The polynomial $1+3x^2-x^3\in\polyspace_3$ is not in the null space because $h(1+3x^2-x^3)=x+3x^3-x^4$. The polynomial $1+3x^2-x^3\in\polyspace_4$ is not in the range space because of the constant term. \end{exparts} \end{answer} \item Find the range space and the rank of each homomorphism. \begin{exparts} \partsitem $\map{h}{\polyspace_3}{\Re^2}$ given by \begin{equation*} ax^2+bx+c\mapsto \colvec{a+b \\ a+c} \end{equation*} \partsitem $\map{f}{\Re^2}{\Re^3}$ given by \begin{equation*} \colvec{x \\ y}\mapsto\colvec{0 \\ x-y \\ 3y} \end{equation*} \end{exparts} \begin{answer} \begin{exparts} \partsitem The range of $h$ is all of the codomain~$\Re^2$ because given \begin{equation*} \colvec{x \\ y}\in\Re^2 \end{equation*} it is the image under~$h$ of the domain vector $0x^2+bx+c$. So the rank of~$h$ is~$2$. \partsitem The range is the $yz$~plane. Any \begin{equation*} \colvec{0 \\ a \\ b} \end{equation*} is the image under~$f$ of this domain vector. \begin{equation*} \colvec{a+b/3 \\ b/3} \end{equation*} So the rank of the map is~$2$. \end{exparts} \end{answer} \recommended \item Find the range space and rank of each map. \begin{exparts} \partsitem $$\map{h}{\Re^2}{\polyspace_3}$$ given by \begin{equation*} \colvec{a \\ b}\mapsto a+ax+ax^2 \end{equation*} \partsitem $$\map{h}{\matspace_{\nbyn{2}}}{\Re}$$ given by \begin{equation*} \begin{mat} a &b \\ c &d \end{mat} \mapsto a+d \end{equation*} \partsitem $$\map{h}{\matspace_{\nbyn{2}}}{\polyspace_2}$$ given by \begin{equation*} \begin{mat} a &b \\ c &d \end{mat} \mapsto a+b+c+dx^2 \end{equation*} \partsitem the zero map $$\map{Z}{\Re^3}{\Re^4}$$ \end{exparts} \begin{answer} \begin{exparts} \partsitem The range space is \begin{equation*} \rangespace{h} =\set{a+ax+ax^2\in\polyspace_3\suchthat a,b\in\Re} =\set{a\cdot(1+x+x^2)\suchthat a\in\Re} \end{equation*} and so the rank is one. \partsitem The range space \begin{equation*} \rangespace{h}= \set{a+d\suchthat a,b,c,d\in\Re} \end{equation*} is all of $\Re$ (we can get any real number by taking $d$ to be $0$ and taking $a$ to be the desired number). Thus, the rank is one. \partsitem The range space is $\rangespace{h}=\set{r+sx^2\suchthat r,s\in\Re}$. The rank is two. \partsitem The range space is the trivial subspace of $$\Re^4$$ so the rank is zero. \end{exparts} \end{answer} \recommended \item For each linear map in the prior exercise, find the null space and nullity. \begin{answer} \begin{exparts} \partsitem The null space is \begin{align*} \nullspace{h} &=\set{\colvec{a \\ b}\in\Re^2\suchthat a+ax+ax^2+0x^3=0+0x+0x^2+0x^3} \\ &=\set{\colvec{0 \\ b}\suchthat b\in\Re} \end{align*} and so the nullity is one. \partsitem The null space is this. \begin{equation*} \nullspace{h} =\set{\begin{mat} a &b \\ c &d \end{mat} \suchthat a+d=0} =\set{\begin{mat} -d &b \\ c &d \end{mat} \suchthat b,c,d\in\Re } \end{equation*} Thus the nullity is three. \partsitem The null space \begin{equation*} \nullspace{h} =\set{\begin{mat} a &b \\ c &d \end{mat} \suchthat a+b+c=0,\,d=0} =\set{\begin{mat} -b-c &b \\ c &0 \end{mat} \suchthat b,c\in\Re } \end{equation*} is a dimension~$2$ space, so the nullity is two. \partsitem Every vector in the domain is mapped to the zero vector so the nullspace is $\nullspace{h}=\Re^3$. \end{exparts} \end{answer} \recommended \item Find the nullity of each map below. \begin{exparts*} \partsitem $$\map{h}{\Re^5}{\Re^8}$$ of rank five \partsitem $$\map{h}{\polyspace_3}{\polyspace_3}$$ of rank one \partsitem $$\map{h}{\Re^6}{\Re^3}$$, an onto map \partsitem $$\map{h}{\matspace_{\nbyn{3}}}{\matspace_{\nbyn{3}}}$$, onto \end{exparts*} \begin{answer} For each, use the result that the rank plus the nullity equals the dimension of the domain. \begin{exparts*} \partsitem $0$ \partsitem $3$ \partsitem $3$ \partsitem $0$ \end{exparts*} \end{answer} \recommended \item What is the null space of the differentiation transformation $$\map{d/dx}{\polyspace_n}{\polyspace_n}$$? What is the null space of the second derivative, as a transformation of $$\polyspace_n$$? The $$k$$-th derivative? \begin{answer} Because \begin{equation*} \frac{d}{dx}\,(a_0+a_1x+\cdots+a_nx^n) =a_1+2a_2x+3a_3x^2+\cdots+na_nx^{n-1} \end{equation*} we have this. \begin{align*} \nullspace{\frac{d}{dx}} &=\set{a_0+\cdots+a_nx^n\suchthat a_1+2a_2x+\cdots+na_nx^{n-1} =0+0x+\cdots+0x^{n-1}} \\ &=\set{a_0+\cdots+a_nx^n\suchthat \text{$a_1=0$, and $a_2=0$, \ldots, $a_n=0$}} \\ &=\set{a_0+0x+0x^2+\cdots+0x^n\suchthat a_0\in\Re} \end{align*} In the same way, \begin{equation*} \nullspace{\frac{d^k}{dx^k}} =\set{a_0+a_1x+\cdots+a_nx^n\suchthat a_0,\ldots,a_{k-1}\in\Re} \end{equation*} for $$k\leq n$$. \end{answer} \item For the map $\map{h}{\Re^3}{\Re^2}$ given by \begin{equation*} \colvec{x \\ y \\ z} \mapsto \colvec{x+y \\ x+z} \end{equation*} find the range space, rank, null space, and nullity. \begin{answer} To see that the range space is all of~$\Re^2$ note that for any $u,v\in\Re$ this system has a solution. \begin{equation*} \begin{linsys}{3} x &+ &y & & &= &u \\ x & & &+ &z &= &v \end{linsys} \grstep{-\rho_1+\rho_2} \begin{linsys}{3} x &+ &y & & &= &u \\ & &-y &+ &z &= &-u+v \end{linsys} \end{equation*} (In fact, because there is a free variable, $z$, it has infinitely many solutions.) Thus the rank, the dimension of the range space, is~$2$. Since the rank plus the nullity equals the dimension of the domain, we know that the nullity is~$1$. Finding the null space verifies that: \begin{equation*} \begin{linsys}{3} x &+ &y & & &= &0 \\ x & & &+ &z &= &0 \end{linsys} \grstep{-\rho_1+\rho_2} \begin{linsys}{3} x &+ &y & & &= &0 \\ & &-y &+ &z &= &0 \end{linsys} \end{equation*} the nullspace is this set \begin{equation*} \set{\colvec{-1 \\ 1 \\ 1}\cdot z\suchthat z \in \Re} \end{equation*} which is one-dimensional. \end{answer} \item \label{exer:CondTwoProjMap} \nearbyexample{ex:RThreeHomoRTwo} restates the first condition in the definition of homomorphism as the shadow of a sum is the sum of the shadows'. Restate the second condition in the same style. \begin{answer} The shadow of a scalar multiple is the scalar multiple of the shadow. \end{answer} \item For the homomorphism $$\map{h}{\polyspace_3}{\polyspace_3}$$ given by $$h(a_0+a_1x+a_2x^2+a_3x^3)=a_0+(a_0+a_1)x+(a_2+a_3)x^3$$ find these. \begin{exparts*} \partsitem $$\nullspace{h}$$ \partsitem $$h^{-1}(2-x^3)$$ \partsitem $$h^{-1}(1+x^2)$$ \end{exparts*} \begin{answer} \begin{exparts} \partsitem Setting $a_0+(a_0+a_1)x+(a_2+a_3)x^3=0+0x+0x^2+0x^3$ gives $a_0=0$ and $a_0+a_1=0$ and $a_2+a_3=0$, so the null space is $$\set{-a_3x^2+a_3x^3\suchthat a_3\in\Re}$$. \partsitem Setting $a_0+(a_0+a_1)x+(a_2+a_3)x^3=2+0x+0x^2-x^3$ gives that $a_0=2$, and $a_1=-2$, and $a_2+a_3=-1$. Taking $a_3$ as a parameter, and renaming it $a_3=a$ gives this set description $$\set{2-2x+(-1-a)x^2+ax^3\suchthat a\in\Re} =\set{(2-2x-x^2)+a\cdot(-x^2+x^3)\suchthat a\in\Re}$$. \partsitem This set is empty because the range of $h$ includes only those polynomials with a $0x^2$ term. \end{exparts} \end{answer} \recommended \item For the map $$\map{f}{\Re^2}{\Re}$$ given by \begin{equation*} f(\colvec{x \\ y})=2x+y \end{equation*} sketch these inverse image sets:~$$f^{-1}(-3)$$, $$f^{-1}(0)$$, and $$f^{-1}(1)$$. \begin{answer} All inverse images are lines with slope $-2$. \begin{center} \includegraphics{ch3.74} \end{center} \end{answer} \recommended \item Each of these transformations of $$\polyspace_3$$ is one-to-one. For each, find the inverse. \begin{exparts} \partsitem $$a_0+a_1x+a_2x^2+a_3x^3\mapsto a_0+a_1x+2a_2x^2+3a_3x^3$$ \partsitem $$a_0+a_1x+a_2x^2+a_3x^3\mapsto a_0+a_2x+a_1x^2+a_3x^3$$ \partsitem $$a_0+a_1x+a_2x^2+a_3x^3\mapsto a_1+a_2x+a_3x^2+a_0x^3$$ \partsitem $$a_0+a_1x+a_2x^2+a_3x^3\mapsto a_0+(a_0+a_1)x+(a_0+a_1+a_2)x^2+(a_0+a_1+a_2+a_3)x^3$$ \end{exparts} \begin{answer} These are the inverses. \begin{exparts} \partsitem $$a_0+a_1x+a_2x^2+a_3x^3\mapsto a_0+a_1x+(a_2/2)x^2+(a_3/3)x^3$$ \partsitem $$a_0+a_1x+a_2x^2+a_3x^3\mapsto a_0+a_2x+a_1x^2+a_3x^3$$ \partsitem $$a_0+a_1x+a_2x^2+a_3x^3\mapsto a_3+a_0x+a_1x^2+a_2x^3$$ \partsitem $$a_0+a_1x+a_2x^2+a_3x^3\mapsto a_0+(a_1-a_0)x+(a_2-a_1)x^2+(a_3-a_2)x^3$$ \end{exparts} For instance, for the second one, the map given in the question sends $0+1x+2x^2+3x^3\mapsto 0+2x+1x^2+3x^3$ and then the inverse above sends $0+2x+1x^2+3x^3\mapsto 0+1x+2x^2+3x^3$. So this map is actually self-inverse. \end{answer} \item Describe the null space and range space of a transformation given by $$\vec{v}\mapsto 2\vec{v}$$. \begin{answer} For any vector space $V$, the null space \begin{equation*} \set{\vec{v}\in V\suchthat 2\vec{v}=\zero} \end{equation*} is trivial, while the range space \begin{equation*} \set{\vec{w}\in V\suchthat \text{$\vec{w}=2\vec{v}$ for some $\vec{v}\in V$}} \end{equation*} is all of $$V$$, because every vector $\vec{w}$ is twice some other vector, specifically, it is twice $(1/2)\vec{w}$. (Thus, this transformation is actually an automorphism.) \end{answer} \item List all pairs $$(\text{rank}(h),\text{nullity}(h))$$ that are possible for linear maps from $\Re^5$ to $\Re^3$. \begin{answer} Because the rank plus the nullity equals the dimension of the domain (here, five), and the rank is at most three, the possible pairs are:~$$(3,2)$$, $$(2,3)$$, $$(1,4)$$, and~$$(0,5)$$. Coming up with linear maps that show that each pair is indeed possible is easy. \end{answer} \item Does the differentiation map $$\map{d/dx}{\polyspace_n}{\polyspace_n}$$ have an inverse? \begin{answer} No (unless $$\polyspace_n$$ is trivial), because the two polynomials $$f_0(x)=0$$ and $$f_1(x)=1$$ have the same derivative; a map must be one-to-one to have an inverse. \end{answer} \recommended \item Find the nullity of this map $$\map{h}{\polyspace_n}{\Re}$$. \begin{equation*} a_0+a_1x+\dots+a_nx^n\mapsto\int_{x=0}^{x=1}a_0+a_1x+\dots+a_nx^n\,dx \end{equation*} \begin{answer} The null space is this. \begin{multline*} \set{a_0+a_1x+\dots+a_nx^n\suchthat a_0(1)+\frac{\displaystyle a_1}{\displaystyle 2}(1^2) +\dots +\frac{\displaystyle a_n}{\displaystyle n+1}(1^{n+1})=0} \\ =\set{a_0+a_1x+\dots+a_nx^n\suchthat a_0+(a_1/2)+\dots+(a_{n}/n+1)=0} \end{multline*} Thus the nullity is $$n$$. \end{answer} \item \begin{exparts} \partsitem Prove that a homomorphism is onto if and only if its rank equals the dimension of its codomain. \partsitem Conclude that a homomorphism between vector spaces with the same dimension is one-to-one if and only if it is onto. \end{exparts} \begin{answer} \begin{exparts} \partsitem One direction is obvious:~if the homomorphism is onto then its range is the codomain and so its rank equals the dimension of its codomain. For the other direction assume that the map's rank equals the dimension of the codomain. Then the map's range is a subspace of the codomain, and has dimension equal to the dimension of the codomain. Therefore, the map's range must equal the codomain, and the map is onto. (The therefore' is because there is a linearly independent subset of the range that is of size equal to the dimension of the codomain, but any such linearly independent subset of the codomain must be a basis for the codomain, and so the range equals the codomain.) \partsitem By \nearbytheorem{th:OOHomoEquivalence}, a homomorphism is one-to-one if and only if its nullity is zero. Because rank plus nullity equals the dimension of the domain, it follows that a homomorphism is one-to-one if and only if its rank equals the dimension of its domain. But this domain and codomain have the same dimension, so the map is one-to-one if and only if it is onto. \end{exparts} \end{answer} \item \label{exer:NonSingIffPreservLI} Show that a linear map is one-to-one if and only if it preserves linear independence. \begin{answer} We are proving that $$\map{h}{V}{W}$$ is one-to-one if and only if for every linearly independent subset $$S$$ of $$V$$ the subset $$h(S)=\set{h(\vec{s})\suchthat \vec{s}\in S}$$ of $$W$$ is linearly independent. One half is easy\Dash by \nearbytheorem{th:OOHomoEquivalence}, if $$h$$ is not one-to-one then its null space is nontrivial, that is, it contains more than just the zero vector. So where $$\vec{v}\neq\zero_V$$ is in that null space, the singleton set $$\set{\vec{v\,}}$$ is independent while its image $$\set{h(\vec{v})}=\set{\zero_W}$$ is not. For the other half, assume that $$h$$ is one-to-one and so by \nearbytheorem{th:OOHomoEquivalence} has a trivial null space. Then for any $$\vec{v}_1,\dots,\vec{v}_n\in V$$, the relation \begin{equation*} \zero_W= c_1\cdot h(\vec{v}_1)+\dots+c_n\cdot h(\vec{v}_n) =h(c_1\cdot \vec{v}_1+\dots+c_n\cdot \vec{v}_n) \end{equation*} implies the relation $$c_1\cdot \vec{v}_1+\dots+c_n\cdot \vec{v}_n=\zero_V$$. Hence, if a subset of $$V$$ is independent then so is its image in $$W$$. \textit{Remark.} The statement is that a linear map is one-to-one if and only if it preserves independence for \emph{all} sets (that is, if a set is independent then its image is also independent). A map that is not one-to-one may well preserve some independent sets. One example is this map from $\Re^3$ to $\Re^2$. \begin{equation*} \colvec{x \\ y \\ z}\mapsto\colvec{x+y+z \\ 0} \end{equation*} Linear independence is preserved for this set \begin{equation*} \set{\colvec[r]{1 \\ 0 \\ 0}}\mapsto\set{\colvec[r]{1 \\ 0}} \end{equation*} and (in a somewhat more tricky example) also for this set \begin{equation*} \set{\colvec[r]{1 \\ 0 \\ 0},\colvec[r]{0 \\ 1 \\ 0}} \mapsto\set{\colvec[r]{1 \\ 0}} \end{equation*} (recall that in a set, repeated elements do not appear twice). However, there are sets whose independence is not preserved under this map \begin{equation*} \set{\colvec[r]{1 \\ 0 \\ 0},\colvec[r]{0 \\ 2 \\ 0}} \mapsto\set{\colvec[r]{1 \\ 0},\colvec[r]{2 \\ 0}} \end{equation*} and so not all sets have independence preserved. \end{answer} \item \label{exer:DimRngLessImpMapOnto} \nearbycorollary{cor:RankDecreases} says that for there to be an onto homomorphism from a vector space $V$ to a vector space $W$, it is necessary that the dimension of $W$ be less than or equal to the dimension of $V$. Prove that this condition is also sufficient; use \nearbytheorem{th:HomoDetActOnBasis} to show that if the dimension of $W$ is less than or equal to the dimension of $V$, then there is a homomorphism from $V$ to $W$ that is onto. \begin{answer} (We use the notation from \nearbytheorem{th:HomoDetActOnBasis}.) Fix a basis $\sequence{\vec{\beta}_1,\dots,\vec{\beta}_n}$ for $V$ and a basis $\sequence{\vec{w}_1,\ldots,\vec{w}_k}$ for $W$. If the dimension $k$ of $W$ is less than or equal to the dimension $n$ of $V$ then the theorem gives a linear map from $V$ to $W$ determined in this way. \begin{equation*} \vec{\beta}_1\mapsto\vec{w}_1,\,\dots,\,\vec{\beta}_k\mapsto\vec{w}_k \quad\text{and}\quad \vec{\beta}_{k+1}\mapsto\vec{w}_k, \,\dots,\,\vec{\beta}_n\mapsto\vec{w}_k \end{equation*} We need only to verify that this map is onto. We can write any member of $W$ as a linear combination of basis elements $c_1\cdot \vec{w}_1+\dots+c_k\cdot \vec{w}_k$. This vector is the image, under the map described above, of $c_1\cdot \vec{\beta}_1+\dots+c_k\cdot \vec{\beta}_k +0\cdot \vec{\beta}_{k+1}\dots+0\cdot \vec{\beta}_n$. Thus the map is onto. \end{answer} \recommended \item Recall that the null space is a subset of the domain and the range space is a subset of the codomain. Are they necessarily distinct? Is there a homomorphism that has a nontrivial intersection of its null space and its range space? \begin{answer} Yes. For the transformation of $$\Re^2$$ given by \begin{equation*} \colvec{x \\ y}\mapsunder{h}\colvec{0 \\ x} \end{equation*} we have this. \begin{equation*} \nullspace{h}=\set{\colvec{0 \\ y}\suchthat y\in\Re} =\rangespace{h} \end{equation*} \textit{Remark.} We will see more of this in the fifth chapter. \end{answer} \item Prove that the image of a span equals the span of the images. That is, where $$\map{h}{V}{W}$$ is linear, prove that if $$S$$ is a subset of $$V$$ then $$h(\spanof{S})$$ equals $$\spanof{h(S)}$$. This generalizes \nearbylemma{le:RangeIsSubSp} since it shows that if $$U$$ is any subspace of $$V$$ then its image $$\set{h(\vec{u})\suchthat \vec{u}\in U}$$ is a subspace of $$W$$, because the span of the set $U$ is $U$. \begin{answer} This is a simple calculation. \begin{align*} h(\spanof{S}) &=\set{h(c_1\vec{s}_1+\dots+c_n\vec{s}_n) \suchthat \text{$$c_1,\dots,c_n\in\Re$$ and $$\vec{s}_1,\dots,\vec{s}_n\in S$$} } \\ &=\set{c_1h(\vec{s}_1)+\dots+c_nh(\vec{s}_n) \suchthat \text{$$c_1,\dots,c_n\in\Re$$ and $$\vec{s}_1,\dots,\vec{s}_n\in S$$} } \\ &=\spanof{h(S)} \end{align*} \end{answer} \item \label{exer:Cosets} \begin{exparts} \partsitem Prove that for any linear map $$\map{h}{V}{W}$$ and any $$\vec{w}\in W$$, the set $$h^{-1}(\vec{w})$$ has the form \begin{equation*} h^{-1}(\vec{w})= \set{\vec{v}+\vec{n}\suchthat \text{$\vec{v},\vec{n}\in V$ and $\vec{n}\in\nullspace{h}$ and $h(\vec{v})=\vec{w}$}} \end{equation*} (if $$h$$ is not onto and $\vec{w}$ is not in the range of $h$ then this set is empty since its third condition cannot be satisfied). Such a set is a \definend{coset}\index{coset} of $$\nullspace{h}$$ and we denote it as $$\vec{v}+\nullspace{h}$$. \partsitem Consider the map $$\map{t}{\Re^2}{\Re^2}$$ given by \begin{equation*} \colvec{x \\ y} \mapsunder{t} \colvec{ax+by \\ cx+dy} \end{equation*} for some scalars $a$, $b$, $c$, and $d$. Prove that $$t$$ is linear. \partsitem Conclude from the prior two items that for any linear system of the form \begin{equation*} \begin{linsys}{2} ax &+ &by &= &e \\ cx &+ &dy &= &f \end{linsys} \end{equation*} we can write the solution set (the vectors are members of $\Re^2$) \begin{equation*} \set{\vec{p}+\vec{h}\suchthat \text{$$\vec{h}$$ satisfies the associated homogeneous system} } \end{equation*} where $$\vec{p}$$ is a particular solution of that linear system (if there is no particular solution then the above set is empty). \partsitem Show that this map $$\map{h}{\Re^n}{\Re^m}$$ is linear \begin{equation*} \colvec{x_1 \\ \vdots \\ x_n} \mapsto \colvec{a_{1,1}x_1+\dots+a_{1,n}x_n \\ \vdots \\ a_{m,1}x_1+\dots+a_{m,n}x_n} \end{equation*} for any scalars $$a_{1,1}$$, \ldots, $$a_{m,n}$$. Extend the conclusion made in the prior item. \partsitem Show that the $$k$$-th derivative map is a linear transformation of $$\polyspace_n$$ for each $$k$$. Prove that this map is a linear transformation of the space \begin{equation*} f\mapsto \frac{d^k}{dx^k}f+c_{k-1}\frac{d^{k-1}}{dx^{k-1}}f +\dots+ c_1\frac{d}{dx}f+c_0f \end{equation*} for any scalars $$c_k$$, \ldots, $$c_0$$. Draw a conclusion as above. \end{exparts} \begin{answer} \begin{exparts} \partsitem We will show the sets are equal $h^{-1}(\vec{w}) =\set{\vec{v}+\vec{n}\suchthat \vec{n}\in\nullspace{h} }$ by mutual inclusion. For the $\set{\vec{v}+\vec{n}\suchthat \vec{n}\in\nullspace{h} } \subseteq h^{-1}(\vec{w})$ direction, just note that $h(\vec{v}+\vec{n})=h(\vec{v})+h(\vec{n})$ equals $\vec{w}$, and so any member of the first set is a member of the second. For the $h^{-1}(\vec{w}) \subseteq\set{\vec{v}+\vec{n}\suchthat \vec{n}\in\nullspace{h} }$ direction, consider $\vec{u}\in h^{-1}(\vec{w})$. Because $$h$$ is linear, $$h(\vec{u})=h(\vec{v})$$ implies that $$h(\vec{u}-\vec{v})=\zero$$. We can write $$\vec{u}-\vec{v}$$ as $$\vec{n}$$, and then we have that $\vec{u}\in\set{\vec{v}+\vec{n}\suchthat \vec{n}\in\nullspace{h} }$, as desired, because $\vec{u}=\vec{v}+(\vec{u}-\vec{v})$. \partsitem This check is routine. \partsitem This is immediate. \partsitem For the linearity check, briefly, where $$c,d$$ are scalars and $$\vec{x},\vec{y}\in\Re^n$$ have components $$x_1,\dots,x_n$$ and $$y_1,\dots,y_n$$, we have this. \begin{align*} h(c\cdot \vec{x}+d\cdot \vec{y}) &=\colvec{a_{1,1}(cx_1+dy_1)+\dots+a_{1,n}(cx_n+dy_n) \\ \vdots \\ a_{m,1}(cx_1+dy_1)+\dots+a_{m,n}(cx_n+dy_n)} \\ &=\colvec{a_{1,1}cx_1+\dots+a_{1,n}cx_n \\ \vdots \\ a_{m,1}cx_1+\dots+a_{m,n}cx_n} +\colvec{a_{1,1}dy_1+\dots+a_{1,n}dy_n \\ \vdots \\ a_{m,1}dy_1+\dots+a_{m,n}dy_n} \\ &=c\cdot h(\vec{x})+d\cdot h(\vec{y}) \end{align*} The appropriate conclusion is that $$\text{General}=\text{Particular}+\text{Homogeneous}$$. \partsitem Each power of the derivative is linear because of the rules \begin{equation*} \frac{d^k}{dx^k}(f(x)+g(x))=\frac{d^k}{dx^k}f(x) +\frac{d^k}{dx^k}g(x) \quad\text{and}\quad \frac{d^k}{dx^k}rf(x)=r\frac{d^k}{dx^k}f(x) \end{equation*} from calculus. Thus the given map is a linear transformation of the space because any linear combination of linear maps is also a linear map by \nearbylemma{le:SpLinFcns}. The appropriate conclusion is $$\text{General}=\text{Particular}+\text{Homogeneous}$$, where the associated homogeneous differential equation has a constant of $$0$$. \end{exparts} \end{answer} \item Prove that for any transformation $$\map{t}{V}{V}$$ that is rank one, the map given by composing the operator with itself $$\map{\composed{t}{t}}{V}{V}$$ satisfies $$\composed{t}{t}=r\cdot t$$ for some real number $$r$$. \begin{answer} Because the rank of $$t$$ is one, the range space of $$t$$ is a one-dimensional set. Taking $\sequence{h(\vec{v})}$ as a basis (for some appropriate $\vec{v}$), we have that for every $\vec{w}\in V$, the image $h(\vec{w})\in V$ is a multiple of this basis vector\Dash associated with each $\vec{w}$ there is a scalar $$c_{\vec{w}}$$ such that $$t(\vec{w})=c_{\vec{w}}t(\vec{v})$$. Apply $$t$$ to both sides of that equation and take $$r$$ to be $$c_{t(\vec{v})}$$ \begin{equation*} \composed{t}{t}(\vec{w}) =t(c_{\vec{w}}\cdot t(\vec{v})) =c_{\vec{w}}\cdot\composed{t}{t}(\vec{v}) =c_{\vec{w}}\cdot c_{t(\vec{v})}\cdot t(\vec{v}) =c_{\vec{w}}\cdot r\cdot t(\vec{v}) =r\cdot c_{\vec{w}}\cdot t(\vec{v}) =r\cdot t(\vec{w}) \end{equation*} to get the desired conclusion. \end{answer} \item Let $$\map{h}{V}{\Re}$$ be a homomorphism, but not the zero homomorphism. Prove that if $$\sequence{\vec{\beta}_1,\dots,\vec{\beta}_n}$$ is a basis for the null space and if $$\vec{v}\in V$$ is not in the null space then $$\sequence{\vec{v},\vec{\beta}_1,\dots,\vec{\beta}_n}$$ is a basis for the entire domain $$V$$. \begin{answer} By assumption, $$h$$ is not the zero map and so a vector $$\vec{v}\in V$$ exists that is not in the null space. Note that $$\sequence{h(\vec{v})}$$ is a basis for $$\Re$$, because it is a size-one linearly independent subset of $$\Re$$. Consequently $$h$$ is onto, as for any $$r\in\Re$$ we have $$r=c\cdot h(\vec{v})$$ for some scalar $$c$$, and so $$r=h(c\vec{v})$$. Thus the rank of $$h$$ is one. Because the nullity is $n$, the dimension of the domain of $$h$$, the vector space $$V$$, is $$n+1$$. We can finish by showing $$\set{\vec{v},\vec{\beta}_1,\dots,\vec{\beta}_n}$$ is linearly independent, as it is a size~$n+1$ subset of a dimension~$n+1$ space. Because $$\set{\vec{\beta}_1,\dots,\vec{\beta}_n}$$ is linearly independent we need only show that $$\vec{v}$$ is not a linear combination of the other vectors. But $$c_1\vec{\beta}_1+\dots+c_n\vec{\beta}_n=\vec{v}$$ would give $$-\vec{v}+c_1\vec{\beta}_1+\dots+c_n\vec{\beta}_n=\zero$$ and applying $$h$$ to both sides would give a contradiction. \end{answer} \item Show that for any space $$V$$ of dimension $$n$$, the \definend{dual space}\index{dual space}\index{vector space!dual} \begin{equation*} \linmaps{V}{\Re}=\set{\map{h}{V}{\Re}\suchthat \text{$$h$$ is linear}} \end{equation*} is isomorphic to $$\Re^n$$. It is often denoted $V^\ast$. Conclude that $$V^\ast\isomorphicto V$$. \begin{answer} Fix a basis $$\sequence{\vec{\beta}_1,\dots,\vec{\beta}_n}$$ for $$V$$. We shall prove that this map \begin{equation*} h\mapsunder{\Phi} \colvec{h(\vec{\beta}_1) \\ \vdots \\ h(\vec{\beta}_n)} \end{equation*} is an isomorphism from $$V^\ast$$ to $$\Re^n$$. To see that $\Phi$ is one-to-one, assume that $h_1$ and $h_2$ are members of $V^\ast$ such that $\Phi(h_1)=\Phi(h_2)$. Then \begin{equation*} \colvec{h_1(\vec{\beta}_1) \\ \vdots \\ h_1(\vec{\beta}_n)} =\colvec{h_2(\vec{\beta}_1) \\ \vdots \\ h_2(\vec{\beta}_n)} \end{equation*} and consequently, $h_1(\vec{\beta}_1)=h_2(\vec{\beta}_1)$, etc. But a homomorphism is determined by its action on a basis, so $$h_1=h_2$$, and therefore $$\Phi$$ is one-to-one. To see that $\Phi$ is onto, consider \begin{equation*} \colvec{x_1 \\ \vdots \\ x_n} \end{equation*} for $$x_1,\ldots,x_n\in\Re$$. This function $h$ from $V$ to $\Re$ \begin{equation*} c_1\vec{\beta}_1+\dots+c_n\vec{\beta}_n \mapsunder{h} c_1x_1+\dots+c_nx_n \end{equation*} is linear and $\Phi$ maps it to the given vector in $\Re^n$, so $$\Phi$$ is onto. The map $$\Phi$$ also preserves structure:~where \begin{align*} c_1\vec{\beta}_1+\dots+c_n\vec{\beta}_n &\mapsunder{h_1} c_1h_1(\vec{\beta}_1)+\dots+c_nh_1(\vec{\beta}_n) \\ c_1\vec{\beta}_1+\dots+c_n\vec{\beta}_n &\mapsunder{h_2} c_1h_2(\vec{\beta}_1)+\dots+c_nh_2(\vec{\beta}_n) \end{align*} we have \begin{multline*} (r_1h_1+r_2h_2)(c_1\vec{\beta}_1+\dots+c_n\vec{\beta}_n) \\ \begin{aligned} &= c_1(r_1h_1(\vec{\beta}_1)+r_2h_2(\vec{\beta}_1)) +\dots +c_n(r_1h_1(\vec{\beta}_n)+r_2h_2(\vec{\beta}_n)) \\ &= r_1(c_1h_1(\vec{\beta}_1)+\dots+c_nh_1(\vec{\beta}_n)) + r_2(c_1h_2(\vec{\beta}_1)+\dots+c_nh_2(\vec{\beta}_n)) \end{aligned} \end{multline*} so $$\Phi(r_1h_1+r_2h_2)=r_1\Phi(h_1)+r_2\Phi(h_2)$$. \end{answer} \item Show that any linear map is the sum of maps of rank one. \begin{answer} Let $$\map{h}{V}{W}$$ be linear and fix a basis $$\sequence{\vec{\beta}_1,\dots,\vec{\beta}_n}$$ for $$V$$. Consider these $$n$$ maps from $$V$$ to $$W$$ \begin{equation*} h_1(\vec{v})=c_1\cdot h(\vec{\beta}_1), \quad h_2(\vec{v})=c_2\cdot h(\vec{\beta}_2), \quad\ldots\quad, h_n(\vec{v})=c_n\cdot h(\vec{\beta}_n) \end{equation*} for any $$\vec{v}=c_1\vec{\beta}_1+\dots+c_n\vec{\beta}_n$$. Clearly $$h$$ is the sum of the $$h_i$$'s. We need only check that each $$h_i$$ is linear:~where $$\vec{u}=d_1\vec{\beta}_1+\dots+d_n\vec{\beta}_n$$ we have $$h_i(r\vec{v}+s\vec{u})=rc_i+sd_i=rh_i(\vec{v})+sh_i(\vec{u})$$. \end{answer} \item Is is homomorphic to' an equivalence relation? (\textit{Hint:}~the difficulty is to decide on an appropriate meaning for the quoted phrase.) \begin{answer} Either yes (trivially) or no (nearly trivially). If we take $$V$$ is homomorphic to' $$W$$ to mean there is a homomorphism from $$V$$ into (but not necessarily onto) $$W$$, then every space is homomorphic to every other space as a zero map always exists. If we take $$V$$ `is homomorphic to' $$W$$ to mean there is an onto homomorphism from $$V$$ to $$W$$ then the relation is not an equivalence. For instance, there is an onto homomorphism from $$\Re^3$$ to $$\Re^2$$ (projection is one) but no homomorphism from $$\Re^2$$ onto $$\Re^3$$ by \nearbycorollary{cor:RankDecreases}, so the relation is not reflexive.\appendrefs{equivalence relations} \end{answer} \item Show that the range spaces and null spaces of powers of linear maps $$\map{t}{V}{V}$$ form descending \begin{equation*} V\supseteq \rangespace{t}\supseteq\rangespace{t^2}\supseteq\ldots \end{equation*} and ascending \begin{equation*} \set{\vec{0}}\subseteq\nullspace{t}\subseteq\nullspace{t^2}\subseteq\ldots \end{equation*} chains. Also show that if $$k$$ is such that $$\rangespace{t^k}=\rangespace{t^{k+1}}$$ then all following range spaces are equal: $$\rangespace{t^k}=\rangespace{t^{k+1}}=\rangespace{t^{k+2}}\ldots\,$$. Similarly, if $$\nullspace{t^k}=\nullspace{t^{k+1}}$$ then $$\nullspace{t^k}=\nullspace{t^{k+1}}=\nullspace{t^{k+2}}=\ldots\,$$. \begin{answer} That they form the chains is obvious. For the rest, we show here that $$\rangespace{t^{j+1}}=\rangespace{t^{j}}$$ implies that $$\rangespace{t^{j+2}}=\rangespace{t^{j+1}}$$. Induction then applies. Assume that $$\rangespace{t^{j+1}}=\rangespace{t^{j}}$$. Then $$\map{t}{\rangespace{t^{j+1}}}{\rangespace{t^{j+2}}}$$ is the same map, with the same domain, as $$\map{t}{\rangespace{t^{j}}}{\rangespace{t^{j+1}}}$$. Thus it has the same range: $$\rangespace{t^{j+2}}=\rangespace{t^{j+1}}$$. \end{answer} \end{exercises}