map2.tex 114 KB
Newer Older
1
% Chapter 3, Section 2 _Linear Algebra_ Jim Hefferon
Jim Hefferon's avatar
Jim Hefferon committed
2
%  http://joshua.smcvt.edu/linearalgebra
3 4 5
%  2001-Jun-11
\section{Homomorphisms}
The definition of isomorphism has two conditions.
Jim Hefferon's avatar
Jim Hefferon committed
6 7
In this section we will consider the second one.
We will study maps that 
Jim Hefferon's avatar
Jim Hefferon committed
8 9
are required only to preserve structure,
maps that are not also required to be correspondences. 
10

Jim Hefferon's avatar
Jim Hefferon committed
11 12 13 14
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,
15
we can think of these maps as describing how spaces are alike.
16 17 18 19 20 21 22 23 24 25 26








\subsection{Definition}

\begin{definition}  \label{def:Homo}
Jim Hefferon's avatar
Jim Hefferon committed
27
%<*df:Homo>
28 29
A function between vector spaces \( \map{h}{V}{W} \) that 
preserves\index{preserves structure}\index{structure! preservation} 
Jim Hefferon's avatar
Jim Hefferon committed
30
addition
31 32 33 34 35 36 37 38 39
\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}
Jim Hefferon's avatar
Jim Hefferon committed
40
is a \definend{homomorphism}\index{homomorphism}\index{linear map}%
41
\index{function!structure preserving!\see{homomorphism}}%
42
\index{vector space!homomorphism}\index{vector space!map}
Jim Hefferon's avatar
Jim Hefferon committed
43
or \definend{linear map}\index{linear map|seealso{homomorphism}}.
Jim Hefferon's avatar
Jim Hefferon committed
44
%</df:Homo>
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
\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*}
Jim Hefferon's avatar
Jim Hefferon committed
78
This is not an isomorphism since it is not one-to-one. 
Jim Hefferon's avatar
Jim Hefferon committed
79
For instance, both $\zero$ and $\vec{e}_3$ in $\Re^3$ map to
80 81 82 83
the zero vector in $\Re^2$.
\end{example}

\begin{example} \label{exam:TwoMapsHomoNotIso}
Jim Hefferon's avatar
Jim Hefferon committed
84
The domain and codomain 
Jim Hefferon's avatar
Jim Hefferon committed
85
can be other than spaces of column vectors.
86 87 88 89 90 91 92 93 94
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*}
Jim Hefferon's avatar
Jim Hefferon committed
95
      \begin{mat}
96 97
        a  &b  \\
        c  &d
Jim Hefferon's avatar
Jim Hefferon committed
98
      \end{mat}
99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119
        \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*}
Jim Hefferon's avatar
Jim Hefferon committed
120
    is linear, that is, is a homomorphism.
Jim Hefferon's avatar
Jim Hefferon committed
121
    The check is easy.
122 123 124 125 126 127
    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*}
Jim Hefferon's avatar
Jim Hefferon committed
128 129 130 131
    is not linear.
    To show this we need only produce a single
    linear combination that the map does not preserve.
    Here is one.
132
    \begin{equation*}
Jim Hefferon's avatar
Jim Hefferon committed
133
      \hat{g}(\colvec[r]{0 \\ 0 \\ 0}+\colvec[r]{1 \\ 0 \\ 0})=4
Jim Hefferon's avatar
Jim Hefferon committed
134
      \qquad
Jim Hefferon's avatar
Jim Hefferon committed
135 136
      \hat{g}(\colvec[r]{0 \\ 0 \\ 0})
      +\hat{g}(\colvec[r]{1 \\ 0 \\ 0})=5
137 138 139 140 141 142 143 144
    \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}
Jim Hefferon's avatar
Jim Hefferon committed
145
      \qquad
146 147 148
      \colvec{x \\ y \\ z}
        \mapsunder{t_2}
      \colvec{5x-2y \\ xy}
Jim Hefferon's avatar
Jim Hefferon committed
149
    \end{equation*}
Jim Hefferon's avatar
Jim Hefferon committed
150 151
    Finding a linear combination that the second map does not 
    preserve is easy. 
152
\end{enumerate}
Jim Hefferon's avatar
Jim Hefferon committed
153 154
% The homomorphisms have 
% coordinate functions that are linear combinations of the arguments.
Jim Hefferon's avatar
Jim Hefferon committed
155
% See also \nearbyexercise{exer:GrpahNotALine}.
156 157
\end{example}

Jim Hefferon's avatar
Jim Hefferon committed
158
So one way to think of `homomorphism' 
Jim Hefferon's avatar
Jim Hefferon committed
159 160
is that we are generalizing `isomorphism' (by dropping the condition that
the map is a correspondence),
161
motivated by the observation that many of the properties of
Jim Hefferon's avatar
Jim Hefferon committed
162 163 164 165 166
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.
167 168

\begin{lemma}       \label{le:HomoSendsZeroToZero}
Jim Hefferon's avatar
Jim Hefferon committed
169
%<*lm:HomoSendsZeroToZero>
Jim Hefferon's avatar
Jim Hefferon committed
170
A homomorphism sends the zero vector to the zero vector.
Jim Hefferon's avatar
Jim Hefferon committed
171
%</lm:HomoSendsZeroToZero>
172 173 174
\end{lemma}

\begin{lemma}  \label{le:HomoPreserveLinCombo}
Jim Hefferon's avatar
Jim Hefferon committed
175
%<*lm:HomoPreserveLinCombo>
Jim Hefferon's avatar
Jim Hefferon committed
176
The following are equivalent for any map 
Jim Hefferon's avatar
Jim Hefferon committed
177
\( \map{f}{V}{W} \) 
Jim Hefferon's avatar
Jim Hefferon committed
178
between vector spaces.
Jim Hefferon's avatar
Jim Hefferon committed
179
\begin{tfae}
Jim Hefferon's avatar
Jim Hefferon committed
180 181
  \item 
      $f$ is a homomorphism 
182 183 184 185 186 187 188 189 190
  \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 \)
Jim Hefferon's avatar
Jim Hefferon committed
191
\end{tfae}
Jim Hefferon's avatar
Jim Hefferon committed
192
%</lm:HomoPreserveLinCombo>
193 194 195
\end{lemma}

\begin{example}
Jim Hefferon's avatar
Jim Hefferon committed
196
The function \( \map{f}{\Re^2}{\Re^4} \) given by
197 198 199 200 201
\begin{equation*}
  \colvec{x \\ y}
    \mapsunder{f}
  \colvec{x/2 \\ 0 \\ x+y \\ 3y}
\end{equation*}
Jim Hefferon's avatar
Jim Hefferon committed
202
is linear since it satisfies item~(2).
203 204 205 206 207 208 209 210 211 212 213
\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,
Jim Hefferon's avatar
Jim Hefferon committed
214 215 216
some things that hold for isomorphisms fail to hold for
homomorphisms.
One example is in the proof of Lemma~I.\ref{lem:IsoImpliesSameDim}, 
Jim Hefferon's avatar
Jim Hefferon committed
217 218
which shows that an isomorphism between spaces gives 
a correspondence between their bases.
219
Homomorphisms do not give any such correspondence;
Jim Hefferon's avatar
Jim Hefferon committed
220 221
\nearbyexample{ex:RThreeHomoRTwoFirst} shows this and another example is
the zero map between two nontrivial spaces. 
Jim Hefferon's avatar
Jim Hefferon committed
222
Instead, for homomorphisms we have a weaker but still very useful result.
223

Jim Hefferon's avatar
Jim Hefferon committed
224 225
\begin{theorem} \label{th:HomoDetActOnBasis}
%<*th:HomoDetActOnBasis>
Jim Hefferon's avatar
Jim Hefferon committed
226
A homomorphism is determined by its action on a basis:~if
Jim Hefferon's avatar
Jim Hefferon committed
227
$V$ is a vector space with basis
228 229 230 231
\( \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
Jim Hefferon's avatar
Jim Hefferon committed
232 233
there exists a homomorphism from \( V \) to \( W \) sending each
\( \vec{\beta}_i \) to \( \vec{w}_i \), and that homomorphism is unique.
Jim Hefferon's avatar
Jim Hefferon committed
234
%</th:HomoDetActOnBasis>
235 236 237
\end{theorem}

\begin{proof}
Jim Hefferon's avatar
Jim Hefferon committed
238
%<*pf:HomoDetActOnBasis0>
Jim Hefferon's avatar
Jim Hefferon committed
239 240 241 242 243
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
244
$h(\vec{v})=c_1\vec{w}_1+\dots+c_n\vec{w}_n$.
Jim Hefferon's avatar
Jim Hefferon committed
245
This is well defined because, with respect to the basis,
246
the representation of each domain vector \( \vec{v} \) is unique.
Jim Hefferon's avatar
Jim Hefferon committed
247
%</pf:HomoDetActOnBasis0>
248

Jim Hefferon's avatar
Jim Hefferon committed
249
%<*pf:HomoDetActOnBasis1>
Jim Hefferon's avatar
Jim Hefferon committed
250 251
This map is a homomorphism 
because it preserves linear combinations:
252
where \( \vec{v_1}=c_1\vec{\beta}_1+\cdots+c_n\vec{\beta}_n \) and
Jim Hefferon's avatar
Jim Hefferon committed
253 254
\( \vec{v_2}=d_1\vec{\beta}_1+\cdots+d_n\vec{\beta}_n \), here
is the calculation.
255 256
\begin{align*}
  h(r_1\vec{v}_1+r_2\vec{v}_2)
Jim Hefferon's avatar
Jim Hefferon committed
257
  &=h(\,(r_1c_1+r_2d_1)\vec{\beta}_1+\dots+(r_1c_n+r_2d_n)\vec{\beta}_n\,)  \\
258 259 260
  &=(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*}
Jim Hefferon's avatar
Jim Hefferon committed
261
%</pf:HomoDetActOnBasis1>
262

Jim Hefferon's avatar
Jim Hefferon committed
263
%<*pf:HomoDetActOnBasis2>
Jim Hefferon's avatar
Jim Hefferon committed
264
This map is unique because if \( \map{\hat{h}}{V}{W} \) 
265
is another homomorphism satisfying that \( \hat{h}(\vec{\beta}_i)=\vec{w}_i \) 
Jim Hefferon's avatar
Jim Hefferon committed
266
for each \( i \)
267 268
then \( h \) and \( \hat{h} \) have the 
same effect on all of the vectors in the domain. 
Jim Hefferon's avatar
Jim Hefferon committed
269
\begin{multline*}
270 271 272
  \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)  \\  
Jim Hefferon's avatar
Jim Hefferon committed
273 274 275
  =c_1\vec{w}_1+\dots+c_n\vec{w}_n 
  =h(\vec{v})
\end{multline*}
Jim Hefferon's avatar
Jim Hefferon committed
276
They have the same action so they are the same function.
Jim Hefferon's avatar
Jim Hefferon committed
277
%</pf:HomoDetActOnBasis2>
278 279
\end{proof}

Jim Hefferon's avatar
Jim Hefferon committed
280 281
\begin{definition} \label{df:ExtendedLinearly}
%<*df:ExtendedLinearly>
Jim Hefferon's avatar
Jim Hefferon committed
282 283 284 285 286
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}$
Jim Hefferon's avatar
Jim Hefferon committed
287
is \definend{extended linearly}\index{extended, linearly}\index{function!extended linearly}\index{linear extension of a function}
Jim Hefferon's avatar
Jim Hefferon committed
288 289 290 291 292 293
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)$.
Jim Hefferon's avatar
Jim Hefferon committed
294
%</df:ExtendedLinearly>
Jim Hefferon's avatar
Jim Hefferon committed
295 296 297
\end{definition}


298
\begin{example}
Jim Hefferon's avatar
Jim Hefferon committed
299
If we specify a map \( \map{h}{\Re^2}{\Re^2} \)
300 301
that acts on the standard basis $\stdbasis_2$ in this way 
\begin{equation*}
Jim Hefferon's avatar
Jim Hefferon committed
302 303 304
  h(\colvec[r]{1 \\ 0})=\colvec[r]{-1 \\ 1}
  \qquad
  h(\colvec[r]{0 \\ 1})=\colvec[r]{-4 \\ 4}
305
\end{equation*}
Jim Hefferon's avatar
Jim Hefferon committed
306
then we have also specified the action of $h$ on any other member of the domain.
307 308 309
For instance,
the value of $h$ on this argument
\begin{equation*}
Jim Hefferon's avatar
Jim Hefferon committed
310 311 312
  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}
313 314 315 316
\end{equation*}
is a direct consequence of the value of $h$ on the basis vectors.
\end{example}

Jim Hefferon's avatar
Jim Hefferon committed
317
Later in this chapter we shall develop a convenient scheme for computations 
Jim Hefferon's avatar
Jim Hefferon committed
318 319
like this one, using matrices.

Jim Hefferon's avatar
Jim Hefferon committed
320 321
% Just as the isomorphisms of a space with itself are useful and interesting, 
% so too are the homomorphisms of a space with itself.
322

Jim Hefferon's avatar
Jim Hefferon committed
323 324
\begin{definition} \label{df:LinearTransformation}
%<*df:LinearTransformation>
325
A linear map from a space into itself \( \map{t}{V}{V} \) is a
Jim Hefferon's avatar
Jim Hefferon committed
326
\definend{linear transformation}\index{linear transformation}\index{linear transformation|seealso{transformation}}.
Jim Hefferon's avatar
Jim Hefferon committed
327
%</df:LinearTransformation>
328 329 330 331
\end{definition}

\begin{remark}
In this book we use `linear transformation' only in the case where 
Jim Hefferon's avatar
Jim Hefferon committed
332 333
the codomain equals the domain.
However, be aware that other sources may instead use it as a
Jim Hefferon's avatar
Jim Hefferon committed
334
synonym for `homomorphism'.
335 336 337 338
\end{remark}

\begin{example}
The map on $\Re^2$ that projects all vectors down to the $x$-axis
Jim Hefferon's avatar
Jim Hefferon committed
339
is a linear transformation.
340 341 342 343 344 345 346 347 348 349 350 351
\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*}
Jim Hefferon's avatar
Jim Hefferon committed
352
is a linear transformation as this result from calculus shows:
353 354 355 356
\( d(c_1f+c_2g)/dx=c_1\,(df/dx)+c_2\,(dg/dx) \).
\end{example}

\begin{example} \label{ex:MatTransMapLinear}
Jim Hefferon's avatar
Jim Hefferon committed
357
The matrix transpose operation
358
\begin{equation*}
Jim Hefferon's avatar
Jim Hefferon committed
359
  \begin{mat}
360 361
    a  &b  \\
    c  &d
Jim Hefferon's avatar
Jim Hefferon committed
362
  \end{mat}
363
  \;\mapsto\;
Jim Hefferon's avatar
Jim Hefferon committed
364
  \begin{mat}
365 366
    a  &c  \\
    b  &d
Jim Hefferon's avatar
Jim Hefferon committed
367
  \end{mat}
368 369
\end{equation*}
is a linear transformation of \( \matspace_{\nbyn{2}} \).
Jim Hefferon's avatar
Jim Hefferon committed
370
(Transpose is one-to-one and onto and so is in fact 
Jim Hefferon's avatar
Jim Hefferon committed
371
an automorphism.)
372 373 374 375 376 377 378 379 380 381 382 383 384 385
\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*}
Jim Hefferon's avatar
Jim Hefferon committed
386
the linear combination \( 5f-2g \) is also a transformation of~$R^2$.
387 388 389 390 391 392 393
\begin{equation*}
  \colvec{x \\ y}
   \mapsunder{5f-2g}
  \colvec{10x \\ 5x-10y}
\end{equation*}

\begin{lemma} \label{le:SpLinFcns}
Jim Hefferon's avatar
Jim Hefferon committed
394
%<*lm:SpLinFcns>
395 396 397 398
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 \).
Jim Hefferon's avatar
Jim Hefferon committed
399
%</lm:SpLinFcns>
400 401
\end{lemma}

Jim Hefferon's avatar
Jim Hefferon committed
402
%<*SpLinFcns>
Jim Hefferon's avatar
Jim Hefferon committed
403
\noindent We denote the space of linear maps from $V$ to~$W$ by
Jim Hefferon's avatar
Jim Hefferon committed
404
\( \linmaps{V}{W} \).\index{linear maps, vector space of}
Jim Hefferon's avatar
Jim Hefferon committed
405
%</SpLinFcns>
Jim Hefferon's avatar
Jim Hefferon committed
406

407
\begin{proof}
Jim Hefferon's avatar
Jim Hefferon committed
408
%<*pf:SpLinFcns>
409 410
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 
Jim Hefferon's avatar
Jim Hefferon committed
411
closed under the operations.
412
Let \( \map{f,g}{V}{W} \) be linear. 
Jim Hefferon's avatar
Jim Hefferon committed
413
Then the operation of function addition is preserved
414 415 416 417 418 419 420 421
\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*}
Jim Hefferon's avatar
Jim Hefferon committed
422
as is the operation of scalar multiplication of a function.
423 424 425 426 427 428
\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.
Jim Hefferon's avatar
Jim Hefferon committed
429
%</pf:SpLinFcns>
430 431
\end{proof}

Jim Hefferon's avatar
Jim Hefferon committed
432
We started this section by 
Jim Hefferon's avatar
Jim Hefferon committed
433 434 435 436 437 438 439 440
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'.
Jim Hefferon's avatar
Jim Hefferon committed
441 442
In the rest of this chapter we shall work mostly with homomorphisms.
This is
443
partly because any statement made about homomorphisms is automatically true 
Jim Hefferon's avatar
Jim Hefferon committed
444 445
about isomorphisms but more because, 
while the isomorphism concept is more natural, 
Jim Hefferon's avatar
Jim Hefferon committed
446 447
our experience will show that the homomorphism concept 
is more fruitful and more central to progress.
448 449 450 451 452 453

\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}  \)
Jim Hefferon's avatar
Jim Hefferon committed
454 455
      \partsitem \( h(\colvec{x \\ y \\ z})=\colvec[r]{0 \\ 0}  \)
      \partsitem \( h(\colvec{x \\ y \\ z})=\colvec[r]{1 \\ 1}  \)
456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478
      \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} ) \\
Jim Hefferon's avatar
Jim Hefferon committed
479
            &=\colvec[r]{0 \\ 0}                                      \\
480 481 482 483 484 485
            &=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*}
Jim Hefferon's avatar
Jim Hefferon committed
486 487 488
            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})
489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507
          \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}
Jim Hefferon's avatar
Jim Hefferon committed
508 509 510 511
      \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  \)
512 513
    \end{exparts}
    \begin{answer} 
Jim Hefferon's avatar
Jim Hefferon committed
514 515
      For each, we must either check that the map preserves linear combinations
      or give an example of a linear combination that is 
516 517 518 519 520
      not.
      \begin{exparts*}
        \partsitem Yes.
           The check that it preserves combinations is routine.
           \begin{align*}
Jim Hefferon's avatar
Jim Hefferon committed
521
             h(r_1\cdot\begin{mat}
522 523
                 a_1  &b_1  \\
                 c_1  &d_1
Jim Hefferon's avatar
Jim Hefferon committed
524 525
               \end{mat}
              +r_2\cdot\begin{mat}
526 527
                 a_2  &b_2  \\
                 c_2  &d_2
Jim Hefferon's avatar
Jim Hefferon committed
528 529
               \end{mat})
              &=h(\begin{mat}
530 531
                 r_1a_1+r_2a_2  &r_1b_1+r_2b_2  \\
                 r_1c_1+r_2c_2  &r_1d_1+r_2d_2
Jim Hefferon's avatar
Jim Hefferon committed
532
               \end{mat})                    \\
533 534
              &=(r_1a_1+r_2a_2)+(r_1d_1+r_2d_2)    \\
              &=r_1(a_1+d_1)+r_2(a_2+d_2)          \\
Jim Hefferon's avatar
Jim Hefferon committed
535
              &=r_1\cdot h(\begin{mat}
536 537
                             a_1  &b_1  \\
                             c_1  &d_1
Jim Hefferon's avatar
Jim Hefferon committed
538 539
                            \end{mat})
                +r_2\cdot h(\begin{mat}
540 541
                             a_2  &b_2  \\
                             c_2  &d_2
Jim Hefferon's avatar
Jim Hefferon committed
542
                            \end{mat})
543 544 545 546
           \end{align*}
        \partsitem No.
          For instance, not preserved is multiplication by the scalar $2$.
          \begin{equation*}
Jim Hefferon's avatar
Jim Hefferon committed
547
            h(2\cdot\begin{mat}[r]
548 549
                1  &0  \\
                0  &1  
Jim Hefferon's avatar
Jim Hefferon committed
550 551
              \end{mat})
            =h(\begin{mat}[r]
552 553
                2  &0  \\
                0  &2  
Jim Hefferon's avatar
Jim Hefferon committed
554
              \end{mat})
555 556
            =4
            \quad\text{while}\quad
Jim Hefferon's avatar
Jim Hefferon committed
557
            2\cdot h(\begin{mat}[r]
558 559
                1  &0  \\
                0  &1  
Jim Hefferon's avatar
Jim Hefferon committed
560
              \end{mat})
561 562 563 564 565
            =2\cdot 1=2
          \end{equation*}
        \partsitem Yes.
           This is the check that it preserves combinations of two members of
           the domain.
Jim Hefferon's avatar
Jim Hefferon committed
566
           \begin{multline*}
Jim Hefferon's avatar
Jim Hefferon committed
567
             h(r_1\cdot\begin{mat} a_1 &b_1 \\ c_1 &d_1 \end{mat}
Jim Hefferon's avatar
Jim Hefferon committed
568 569
               +r_2\cdot\begin{mat} a_2 &b_2 \\ c_2 &d_2 \end{mat})     \\
             \begin{aligned}
Jim Hefferon's avatar
Jim Hefferon committed
570
             &=h(\begin{mat} 
571 572
                   r_1a_1+r_2a_2 &r_1b_1+r_2b_2   \\ 
                   r_1c_1+r_2c_2 &r_1d_1+r_2d_2 
Jim Hefferon's avatar
Jim Hefferon committed
573
                 \end{mat})                                 \\
574 575 576 577
             &=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)              \\
Jim Hefferon's avatar
Jim Hefferon committed
578 579
             &=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})
Jim Hefferon's avatar
Jim Hefferon committed
580 581
             \end{aligned}
           \end{multline*}
582
        \partsitem No.
Jim Hefferon's avatar
Jim Hefferon committed
583 584
          An example of a combination that is not preserved is that
          doing it one way gives this
585
          \begin{equation*}
Jim Hefferon's avatar
Jim Hefferon committed
586
            h(\begin{mat}[r]
587 588
              1  &0  \\
              0  &0
Jim Hefferon's avatar
Jim Hefferon committed
589 590
            \end{mat}
            +\begin{mat}[r]
591 592
              1  &0  \\
              0  &0
Jim Hefferon's avatar
Jim Hefferon committed
593 594
            \end{mat})
           =h(\begin{mat}[r]
595 596
              2  &0  \\
              0  &0
Jim Hefferon's avatar
Jim Hefferon committed
597
            \end{mat})
598
           =4
Jim Hefferon's avatar
Jim Hefferon committed
599 600 601
           \end{equation*}
           while the other way gives this.
           \begin{equation*}
Jim Hefferon's avatar
Jim Hefferon committed
602
            h(\begin{mat}[r]
603 604
              1  &0  \\
              0  &0
Jim Hefferon's avatar
Jim Hefferon committed
605 606
            \end{mat})
            +h(\begin{mat}[r]
607 608
              1  &0  \\
              0  &0
Jim Hefferon's avatar
Jim Hefferon committed
609
            \end{mat})
610 611 612 613 614 615
            =1+1
            =2
          \end{equation*}
      \end{exparts*}   
    \end{answer}
  \recommended \item
Jim Hefferon's avatar
Jim Hefferon committed
616 617
    Show that these are homomorphisms.
    Are they inverse to each other?
618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640
    \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 
641
      property of differentiation that is familiar from calculus.)
642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678

      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*}
Jim Hefferon's avatar
Jim Hefferon committed
679
         \colvec{x \\ y \\ z}\mapsto\colvec[r]{0 \\ 0 \\ 0}
680 681 682 683
      \end{equation*}
      Verification that each is a homomorphism is straightforward.
      (The last one, of course, is the zero transformation on $\Re^3$.)  
     \end{answer}
Jim Hefferon's avatar
Jim Hefferon committed
684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728
  \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}


729 730 731 732 733 734 735 736
  \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*}
Jim Hefferon's avatar
Jim Hefferon committed
737
        \begin{mat}[r]
738 739
          1  &0  \\
          0  &0  
Jim Hefferon's avatar
Jim Hefferon committed
740
        \end{mat}
741
        \quad\text{and}\quad
Jim Hefferon's avatar
Jim Hefferon committed
742
        \begin{mat}[r]
743 744
          0  &0  \\
          0  &1  
Jim Hefferon's avatar
Jim Hefferon committed
745
        \end{mat}
746
      \end{equation*}
Jim Hefferon's avatar
Jim Hefferon committed
747
      map to the same member of the codomain, $1\in\Re$.
748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831
     \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}
832
  \item
833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851
    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}
852 853
  \item 
     Consider this transformation of the plane \( \Re^2 \).
854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875
     \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).
Jim Hefferon's avatar
Jim Hefferon committed
876
    How much extra rope must we add to raise the circle to a constant
877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892
    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\;
Jim Hefferon's avatar
Jim Hefferon committed
893
      \colvec{x \\ y \\ z}\dotprod\colvec[r]{3 \\ -1 \\ -1}=3x-y-z
894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966
    \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
967
          c_{k}\frac{d^k}{dx^k}f+c_{k-1}\frac{d^{k-1}}{dx^{k-1}}f
968 969 970 971 972 973 974 975
             +\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.
Jim Hefferon's avatar
Jim Hefferon committed
976
          \begin{multline*}
977
            h(c\cdot \colvec{x_1 \\ \vdots \\ x_n} 
Jim Hefferon's avatar
Jim Hefferon committed
978 979
              +d\cdot \colvec{y_1 \\ \vdots \\ y_n})                     \\
            \begin{aligned}
980 981 982 983 984 985 986 987 988 989 990 991
            &=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})
Jim Hefferon's avatar
Jim Hefferon committed
992 993
            \end{aligned}
          \end{multline*}
994 995 996 997 998
        \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)
Jim Hefferon's avatar
Jim Hefferon committed
999
            \qquad
1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013
            \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.
Jim Hefferon's avatar
Jim Hefferon committed
1014
      The composition preserves linear combinations
1015 1016 1017 1018 1019 1020 1021 1022
      \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*}
Jim Hefferon's avatar
Jim Hefferon committed
1023
      where $\vec{u}_1,\vec{u}_2\in U$ and scalars $c_1,c_2$ 
1024
    \end{answer}
1025
  \item
1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058
    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*}
Jim Hefferon's avatar
Jim Hefferon committed
1059
            \set{\vec{v}_1,\vec{v}_2}=\set{\colvec[r]{1 \\ 0},\colvec[r]{1 \\ 1}}
1060
            \;\mapsto\;
Jim Hefferon's avatar
Jim Hefferon committed
1061
            \set{\colvec[r]{1 \\ 1},\colvec[r]{2 \\ 2}}=\set{\vec{w}_1,\vec{w}_2}
1062 1063 1064 1065 1066 1067 1068 1069 1070 1071
          \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*}
Jim Hefferon's avatar
Jim Hefferon committed
1072 1073
            \set{\colvec[r]{1 \\ 0 \\ 0},\colvec[r]{0 \\ 1 \\ 0}}
            \mapsunder{\pi}\set{\colvec[r]{1 \\ 0},\colvec[r]{0 \\ 1}}
1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086
          \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}
1087 1088 1089
    by proving that for every appropriate domain and codomain
    the matrix transpose map is linear.
    What are the appropriate domains and codomains?
1090 1091 1092
    \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$.
Jim Hefferon's avatar
Jim Hefferon committed
1093 1094 1095
      Now, the check is routine.
      Start with the transpose of the combination. 
      \begin{equation*}
Jim Hefferon's avatar
Jim Hefferon committed
1096 1097
        \trans{[r\cdot\begin{mat}
                \    &\vdots          \\
1098 1099
             \cdots &a_{i,j} &\cdots \\
                    &\vdots
Jim Hefferon's avatar
Jim Hefferon committed
1100 1101 1102
           \end{mat}
         +s\cdot\begin{mat}
                \    &\vdots          \\
1103 1104
             \cdots &b_{i,j} &\cdots \\
                    &\vdots
Jim Hefferon's avatar
Jim Hefferon committed
1105 1106 1107 1108 1109
           \end{mat}]} 
      \end{equation*}
      Combine and take the transpose.               
      \begin{equation*}
        =\trans{\begin{mat}
Jim Hefferon's avatar
Jim Hefferon committed
1110
                 \       &\vdots                    \\
1111 1112
                  \cdots &ra_{i,j}+sb_{i,j} &\cdots \\
                         &\vdots
Jim Hefferon's avatar
Jim Hefferon committed
1113 1114
                \end{mat}}                               
        =\begin{mat}
Jim Hefferon's avatar
Jim Hefferon committed
1115
              \     &\vdots                    \\
1116 1117
            \cdots &ra_{j,i}+sb_{j,i} &\cdots \\
                   &\vdots
Jim Hefferon's avatar
Jim Hefferon committed
1118 1119 1120 1121 1122
          \end{mat}                               
      \end{equation*}
      Then bring out the scalars, and un-transpose.
      \begin{multline*} 
        =r\cdot\begin{mat}
Jim Hefferon's avatar
Jim Hefferon committed
1123
             \     &\vdots          \\
1124 1125
            \cdots &a_{j,i} &\cdots \\
                   &\vdots
Jim Hefferon's avatar
Jim Hefferon committed
1126 1127 1128
          \end{mat}
         +s\cdot\begin{mat}
             \      &\vdots          \\
1129 1130
            \cdots &b_{j,i} &\cdots \\
                   &\vdots
Jim Hefferon's avatar
Jim Hefferon committed
1131 1132
          \end{mat}                             \\   
        =r\cdot\trans{\begin{mat}
Jim Hefferon's avatar
Jim Hefferon committed
1133
             \      &\vdots          \\
1134 1135
            \cdots &a_{j,i} &\cdots \\
                   &\vdots
Jim Hefferon's avatar
Jim Hefferon committed
1136 1137 1138
          \end{mat} }
         +s\cdot\trans{\begin{mat}
              \     &\vdots          \\
1139 1140
            \cdots &b_{j,i} &\cdots \\
                   &\vdots
Jim Hefferon's avatar
Jim Hefferon committed
1141
          \end{mat} }
Jim Hefferon's avatar
Jim Hefferon committed
1142
      \end{multline*}
1143 1144 1145 1146 1147 1148
      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 \), 
Jim Hefferon's avatar
Jim Hefferon committed
1149
        by definition the line segment connecting them is the set
1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187
        \( \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$.
Jim Hefferon's avatar
Jim Hefferon committed
1188
          Now, where $\hat{t}$ is the scalar that we fixed in the first
1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215
          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
Jim Hefferon's avatar
Jim Hefferon committed
1216 1217
          a \( k \)-dimensional linear surface in
          \( \Re^m \) (possibly it is degenerate).
1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238
          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}
1239
      \partsitem Show that the \definend{range space} of this map 
1240 1241
        \( \set{h(\vec{v})\suchthat \vec{v}\in V} \) is a subspace of 
        the codomain \( W \).
1242
      \partsitem Show that the \definend{null space} of this map
1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267
        \( \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.
1268
        \partsitem The null space is nonempty since it contains $\zero_V$, as
1269 1270 1271
          \( \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 
1272
          of the inverse image 
1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297
          \( \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 \).
Jim Hefferon's avatar
Jim Hefferon committed
1298
          Note that \( \zero_W\in X \) so that the set
1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332
          \( \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 
Jim Hefferon's avatar
Jim Hefferon committed
1333
     specifying only that $\vec{e}_1$ maps to itself, then 
1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365
     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.
Jim Hefferon's avatar
Jim Hefferon committed
1366
          \begin{multline*}
1367 1368
            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) \\ 
Jim Hefferon's avatar
Jim Hefferon committed
1369
                        f_2(r_1\vec{v}_1+r_2\vec{v}_2)}           \\
1370 1371 1372
            =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)
Jim Hefferon's avatar
Jim Hefferon committed
1373
          \end{multline*}
1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390
        \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,
1391
          and the fact that the composition of linear functions is linear
Jim Hefferon's avatar
Jim Hefferon committed
1392
          was part of the proof that isomorphism is an equivalence
1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416
          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}















Jim Hefferon's avatar
Jim Hefferon committed
1417
\subsection{Range space and Null space}
1418
Isomorphisms and homomorphisms both preserve structure.
Jim Hefferon's avatar
Jim Hefferon committed
1419 1420
The difference is that homomorphisms have fewer restrictions, since they
needn't be onto and
1421
needn't be one-to-one.
Jim Hefferon's avatar
Jim Hefferon committed
1422
We will examine what can happen with homomorphisms
1423
that cannot happen with isomorphisms. 
1424

Jim Hefferon's avatar
Jim Hefferon committed
1425 1426
First consider the fact that 
homomorphisms need not be onto.
Jim Hefferon's avatar
Jim Hefferon committed
1427
Of course, 
Jim Hefferon's avatar
Jim Hefferon committed
1428
each function is onto some set, namely its range.
Jim Hefferon's avatar
Jim Hefferon committed
1429
For example, the injection map \( \map{\iota}{\Re^2}{\Re^3} \)
1430 1431 1432
\begin{equation*}
  \colvec{x \\ y} \mapsto \colvec{x \\ y \\ 0}
\end{equation*}
Jim Hefferon's avatar
Jim Hefferon committed
1433 1434
is a homomorphism, and is not onto $\Re^3$. 
But it is onto the $xy$-plane.
1435 1436

\begin{lemma}   \label{le:RangeIsSubSp}
Jim Hefferon's avatar
Jim Hefferon committed
1437
%<*lm:RangeIsSubSp>
1438 1439 1440 1441
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.
Jim Hefferon's avatar
Jim Hefferon committed
1442
%</lm:RangeIsSubSp>
1443 1444 1445
\end{lemma}

\begin{proof}
Jim Hefferon's avatar
Jim Hefferon committed
1446
%<*pf:RangeIsSubSp>
1447 1448
Let $\map{h}{V}{W}$ be linear and let $S$ be a subspace of the domain 
$V$.
Jim Hefferon's avatar
Jim Hefferon committed
1449 1450 1451
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$
1452 1453 1454 1455 1456 1457 1458 1459 1460 1461
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 \).
Jim Hefferon's avatar
Jim Hefferon committed
1462
%</pf:RangeIsSubSp>
1463 1464
\end{proof}

Jim Hefferon's avatar
Jim Hefferon committed
1465 1466 1467
\begin{definition} \label{df:RangeSpace}
%<*df:RangeSpace>
The \definend{range space}\index{range space}\index{homomorphism!range space}
1468 1469 1470 1471 1472
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) \).
1473
The dimension of the range space is the map's
1474
\definend{rank}.\index{rank!of a homomorphism}
Jim Hefferon's avatar
Jim Hefferon committed
1475
%</df:RangeSpace>
1476 1477
\end{definition}
\noindent 
Jim Hefferon's avatar
Jim Hefferon committed
1478 1479
We shall soon see the connection between the rank of a map and the rank of a 
matrix.
1480 1481

\begin{example}  \label{ex:DerivMapRnge}
Jim Hefferon's avatar
Jim Hefferon committed
1482
For the derivative map 
1483 1484
\( \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 \)
1485
the range space 
1486 1487
\( \rangespace{d/dx} \) is the set of quadratic polynomials
\( \set{r+sx+tx^2\suchthat r,s,t\in\Re } \).
Jim Hefferon's avatar
Jim Hefferon committed
1488
Thus, this map's rank is~\( 3 \).
1489 1490 1491 1492 1493
\end{example}

\begin{example}  \label{ex:MatToPolyRnge}
With this homomorphism \( \map{h}{M_{\nbyn{2}}}{\polyspace_3} \)
\begin{equation*}
Jim Hefferon's avatar
Jim Hefferon committed
1494
  \begin{mat}
1495 1496
    a  &b  \\
    c  &d
Jim Hefferon's avatar
Jim Hefferon committed
1497
  \end{mat}
1498
  \mapsto
Jim Hefferon's avatar
Jim Hefferon committed
1499
  (a+b+2d)+cx^2+cx^3
1500 1501 1502 1503
\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$.
1504
That is, the range space is
Jim Hefferon's avatar
Jim Hefferon committed
1505 1506
\( \rangespace{h}=\set{r+sx^2+sx^3\suchthat r,s\in\Re} \)
and so the rank is~\( 2 \).
1507 1508 1509 1510 1511
\end{example}

The prior result shows that, 
in passing from the definition of isomorphism to the more
general definition of homomorphism,  
Jim Hefferon's avatar
Jim Hefferon committed
1512
omitting the onto requirement doesn't make an essential difference.
1513
Any homomorphism is onto some space, namely its range.
1514

1515
However, omitting the one-to-one condition does make a difference. 
1516 1517
A homomorphism may have many elements
of the domain that map to one element of the codomain.
Jim Hefferon's avatar
Jim Hefferon committed
1518
Below is a bean sketch of a many-to-one 
1519 1520 1521
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.
1522 1523
(Rather than picture lots of individual $\mapsto$ arrows, each association
of many inputs with one output shows only one such arrow.)
1524 1525 1526
\begin{center}  
  \includegraphics{ch3.5}  % bean to bean; many to one
\end{center}
1527
%<*InverseImage>
1528
Recall that for any function $\map{h}{V}{W}$, 
Jim Hefferon's avatar
Jim Hefferon committed
1529
the set of elements of $V$ that map to \( \vec{w}\in W \)
1530
is the  \definend{inverse image\/}\index{inverse image}%
1531 1532
\index{function! inverse image}   
$h^{-1}(\vec{w})=\set{\vec{v}\in V\suchthat h(\vec{v})=\vec{w}}$.
1533
%</InverseImage>
1534
Above, the left side shows three inverse image sets.
1535 1536 1537 1538 1539 1540 1541 1542 1543 1544

\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.
Jim Hefferon's avatar
Jim Hefferon committed
1545
An inverse image set is a vertical line of vectors
1546 1547 1548 1549
in the domain.
\begin{center}
  \includegraphics{ch3.11}
\end{center}
Jim Hefferon's avatar
Jim Hefferon committed
1550 1551 1552