map2.tex 114 KB
 Jim Hefferon committed Dec 05, 2011 1 % Chapter 3, Section 2 _Linear Algebra_ Jim Hefferon  Jim Hefferon committed Oct 12, 2013 2 % http://joshua.smcvt.edu/linearalgebra  Jim Hefferon committed Dec 05, 2011 3 4 5 % 2001-Jun-11 \section{Homomorphisms} The definition of isomorphism has two conditions.  Jim Hefferon committed Dec 31, 2011 6 7 In this section we will consider the second one. We will study maps that  Jim Hefferon committed Jan 02, 2012 8 9 are required only to preserve structure, maps that are not also required to be correspondences.  Jim Hefferon committed Dec 05, 2011 10   Jim Hefferon committed Dec 31, 2011 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,  Jim Hefferon committed Jan 01, 2013 15 we can think of these maps as describing how spaces are alike.  Jim Hefferon committed Dec 05, 2011 16 17 18 19 20 21 22 23 24 25 26  \subsection{Definition} \begin{definition} \label{def:Homo}  Jim Hefferon committed May 08, 2012 27 %<*df:Homo>  Jim Hefferon committed Dec 05, 2011 28 29 A function between vector spaces $$\map{h}{V}{W}$$ that preserves\index{preserves structure}\index{structure! preservation}  Jim Hefferon committed Oct 12, 2013 30 addition  Jim Hefferon committed Dec 05, 2011 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 committed Nov 27, 2013 40 is a \definend{homomorphism}\index{homomorphism}\index{linear map}%  Jim Hefferon committed Feb 27, 2012 41 \index{function!structure preserving!\see{homomorphism}}%  Jim Hefferon committed Dec 05, 2011 42 \index{vector space!homomorphism}\index{vector space!map}  Jim Hefferon committed Nov 27, 2013 43 or \definend{linear map}\index{linear map|seealso{homomorphism}}.  Jim Hefferon committed May 08, 2012 44 %  Jim Hefferon committed Dec 05, 2011 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 committed Jan 02, 2012 78 This is not an isomorphism since it is not one-to-one.  Jim Hefferon committed Jan 01, 2012 79 For instance, both $\zero$ and $\vec{e}_3$ in $\Re^3$ map to  Jim Hefferon committed Dec 05, 2011 80 81 82 83 the zero vector in $\Re^2$. \end{example} \begin{example} \label{exam:TwoMapsHomoNotIso}  Jim Hefferon committed Oct 12, 2013 84 The domain and codomain  Jim Hefferon committed Dec 31, 2011 85 can be other than spaces of column vectors.  Jim Hefferon committed Dec 05, 2011 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 committed Dec 31, 2011 95  \begin{mat}  Jim Hefferon committed Dec 05, 2011 96 97  a &b \\ c &d  Jim Hefferon committed Dec 31, 2011 98  \end{mat}  Jim Hefferon committed Dec 05, 2011 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 committed Dec 31, 2011 120  is linear, that is, is a homomorphism.  Jim Hefferon committed Oct 12, 2013 121  The check is easy.  Jim Hefferon committed Dec 05, 2011 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 committed Oct 12, 2013 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.  Jim Hefferon committed Dec 05, 2011 132  \begin{equation*}  Jim Hefferon committed Dec 31, 2011 133  \hat{g}(\colvec[r]{0 \\ 0 \\ 0}+\colvec[r]{1 \\ 0 \\ 0})=4  Jim Hefferon committed Jan 02, 2012 134  \qquad  Jim Hefferon committed Dec 31, 2011 135 136  \hat{g}(\colvec[r]{0 \\ 0 \\ 0}) +\hat{g}(\colvec[r]{1 \\ 0 \\ 0})=5  Jim Hefferon committed Dec 05, 2011 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 committed Jan 01, 2012 145  \qquad  Jim Hefferon committed Dec 05, 2011 146 147 148  \colvec{x \\ y \\ z} \mapsunder{t_2} \colvec{5x-2y \\ xy}  Jim Hefferon committed Dec 31, 2011 149  \end{equation*}  Jim Hefferon committed Jan 01, 2012 150 151  Finding a linear combination that the second map does not preserve is easy.  Jim Hefferon committed Dec 05, 2011 152 \end{enumerate}  Jim Hefferon committed Oct 12, 2013 153 154 % The homomorphisms have % coordinate functions that are linear combinations of the arguments.  Jim Hefferon committed Jan 02, 2012 155 % See also \nearbyexercise{exer:GrpahNotALine}.  Jim Hefferon committed Dec 05, 2011 156 157 \end{example}  Jim Hefferon committed Dec 31, 2011 158 So one way to think of homomorphism'  Jim Hefferon committed Oct 12, 2013 159 160 is that we are generalizing isomorphism' (by dropping the condition that the map is a correspondence),  Jim Hefferon committed Dec 05, 2011 161 motivated by the observation that many of the properties of  Jim Hefferon committed Oct 12, 2013 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.  Jim Hefferon committed Dec 05, 2011 167 168  \begin{lemma} \label{le:HomoSendsZeroToZero}  Jim Hefferon committed May 08, 2012 169 %<*lm:HomoSendsZeroToZero>  Jim Hefferon committed Oct 12, 2013 170 A homomorphism sends the zero vector to the zero vector.  Jim Hefferon committed May 08, 2012 171 %  Jim Hefferon committed Dec 05, 2011 172 173 174 \end{lemma} \begin{lemma} \label{le:HomoPreserveLinCombo}  Jim Hefferon committed May 08, 2012 175 %<*lm:HomoPreserveLinCombo>  Jim Hefferon committed Oct 12, 2013 176 The following are equivalent for any map  Jim Hefferon committed Jan 02, 2012 177 $$\map{f}{V}{W}$$  Jim Hefferon committed Oct 12, 2013 178 between vector spaces.  Jim Hefferon committed Jan 02, 2012 179 \begin{tfae}  Jim Hefferon committed Dec 31, 2011 180 181  \item $f$ is a homomorphism  Jim Hefferon committed Dec 05, 2011 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 committed Jan 02, 2012 191 \end{tfae}  Jim Hefferon committed May 08, 2012 192 %  Jim Hefferon committed Dec 05, 2011 193 194 195 \end{lemma} \begin{example}  Jim Hefferon committed Dec 31, 2011 196 The function $$\map{f}{\Re^2}{\Re^4}$$ given by  Jim Hefferon committed Dec 05, 2011 197 198 199 200 201 \begin{equation*} \colvec{x \\ y} \mapsunder{f} \colvec{x/2 \\ 0 \\ x+y \\ 3y} \end{equation*}  Jim Hefferon committed Dec 31, 2011 202 is linear since it satisfies item~(2).  Jim Hefferon committed Dec 05, 2011 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 committed Oct 12, 2013 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 committed Jan 01, 2012 217 218 which shows that an isomorphism between spaces gives a correspondence between their bases.  Jim Hefferon committed Dec 05, 2011 219 Homomorphisms do not give any such correspondence;  Jim Hefferon committed Dec 31, 2011 220 221 \nearbyexample{ex:RThreeHomoRTwoFirst} shows this and another example is the zero map between two nontrivial spaces.  Jim Hefferon committed Oct 12, 2013 222 Instead, for homomorphisms we have a weaker but still very useful result.  Jim Hefferon committed Dec 05, 2011 223   Jim Hefferon committed May 08, 2012 224 225 \begin{theorem} \label{th:HomoDetActOnBasis} %<*th:HomoDetActOnBasis>  Jim Hefferon committed Jan 01, 2012 226 A homomorphism is determined by its action on a basis:~if  Jim Hefferon committed Oct 12, 2013 227 $V$ is a vector space with basis  Jim Hefferon committed Apr 19, 2014 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 committed Dec 31, 2011 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 committed May 08, 2012 234 %  Jim Hefferon committed Dec 05, 2011 235 236 237 \end{theorem} \begin{proof}  Jim Hefferon committed May 08, 2012 238 %<*pf:HomoDetActOnBasis0>  Jim Hefferon committed Oct 12, 2013 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  Jim Hefferon committed Dec 05, 2011 244 $h(\vec{v})=c_1\vec{w}_1+\dots+c_n\vec{w}_n$.  Jim Hefferon committed Oct 12, 2013 245 This is well defined because, with respect to the basis,  Jim Hefferon committed Dec 05, 2011 246 the representation of each domain vector $$\vec{v}$$ is unique.  Jim Hefferon committed May 08, 2012 247 %  Jim Hefferon committed Dec 05, 2011 248   Jim Hefferon committed May 08, 2012 249 %<*pf:HomoDetActOnBasis1>  Jim Hefferon committed Oct 12, 2013 250 251 This map is a homomorphism because it preserves linear combinations:  Jim Hefferon committed Dec 05, 2011 252 where $$\vec{v_1}=c_1\vec{\beta}_1+\cdots+c_n\vec{\beta}_n$$ and  Jim Hefferon committed Oct 12, 2013 253 254 $$\vec{v_2}=d_1\vec{\beta}_1+\cdots+d_n\vec{\beta}_n$$, here is the calculation.  Jim Hefferon committed Dec 05, 2011 255 256 \begin{align*} h(r_1\vec{v}_1+r_2\vec{v}_2)  Jim Hefferon committed Oct 12, 2013 257  &=h(\,(r_1c_1+r_2d_1)\vec{\beta}_1+\dots+(r_1c_n+r_2d_n)\vec{\beta}_n\,) \\  Jim Hefferon committed Dec 05, 2011 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 committed May 08, 2012 261 %  Jim Hefferon committed Dec 05, 2011 262   Jim Hefferon committed May 08, 2012 263 %<*pf:HomoDetActOnBasis2>  Jim Hefferon committed Oct 12, 2013 264 This map is unique because if $$\map{\hat{h}}{V}{W}$$  Jim Hefferon committed Apr 19, 2014 265 is another homomorphism satisfying that $$\hat{h}(\vec{\beta}_i)=\vec{w}_i$$  Jim Hefferon committed Oct 12, 2013 266 for each $$i$$  Jim Hefferon committed Apr 19, 2014 267 268 then $$h$$ and $$\hat{h}$$ have the same effect on all of the vectors in the domain.  Jim Hefferon committed Jan 01, 2012 269 \begin{multline*}  Jim Hefferon committed Apr 19, 2014 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 committed Jan 01, 2012 273 274 275  =c_1\vec{w}_1+\dots+c_n\vec{w}_n =h(\vec{v}) \end{multline*}  Jim Hefferon committed Oct 12, 2013 276 They have the same action so they are the same function.  Jim Hefferon committed May 08, 2012 277 %  Jim Hefferon committed Dec 05, 2011 278 279 \end{proof}  Jim Hefferon committed Dec 06, 2013 280 281 \begin{definition} \label{df:ExtendedLinearly} %<*df:ExtendedLinearly>  Jim Hefferon committed Oct 12, 2013 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 committed Nov 27, 2013 287 is \definend{extended linearly}\index{extended, linearly}\index{function!extended linearly}\index{linear extension of a function}  Jim Hefferon committed Oct 12, 2013 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 committed Dec 06, 2013 294 %  Jim Hefferon committed Oct 12, 2013 295 296 297 \end{definition}  Jim Hefferon committed Dec 05, 2011 298 \begin{example}  Jim Hefferon committed Jan 01, 2012 299 If we specify a map $$\map{h}{\Re^2}{\Re^2}$$  Jim Hefferon committed Dec 05, 2011 300 301 that acts on the standard basis $\stdbasis_2$ in this way \begin{equation*}  Jim Hefferon committed Dec 31, 2011 302 303 304  h(\colvec[r]{1 \\ 0})=\colvec[r]{-1 \\ 1} \qquad h(\colvec[r]{0 \\ 1})=\colvec[r]{-4 \\ 4}  Jim Hefferon committed Dec 05, 2011 305 \end{equation*}  Jim Hefferon committed Dec 31, 2011 306 then we have also specified the action of $h$ on any other member of the domain.  Jim Hefferon committed Dec 05, 2011 307 308 309 For instance, the value of $h$ on this argument \begin{equation*}  Jim Hefferon committed Dec 31, 2011 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}  Jim Hefferon committed Dec 05, 2011 313 314 315 316 \end{equation*} is a direct consequence of the value of $h$ on the basis vectors. \end{example}  Jim Hefferon committed Jan 01, 2012 317 Later in this chapter we shall develop a convenient scheme for computations  Jim Hefferon committed Dec 31, 2011 318 319 like this one, using matrices.  Jim Hefferon committed Oct 12, 2013 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.  Jim Hefferon committed Dec 05, 2011 322   Jim Hefferon committed May 08, 2012 323 324 \begin{definition} \label{df:LinearTransformation} %<*df:LinearTransformation>  Jim Hefferon committed Dec 05, 2011 325 A linear map from a space into itself $$\map{t}{V}{V}$$ is a  Jim Hefferon committed Nov 27, 2013 326 \definend{linear transformation}\index{linear transformation}\index{linear transformation|seealso{transformation}}.  Jim Hefferon committed May 08, 2012 327 %  Jim Hefferon committed Dec 05, 2011 328 329 330 331 \end{definition} \begin{remark} In this book we use linear transformation' only in the case where  Jim Hefferon committed Oct 12, 2013 332 333 the codomain equals the domain. However, be aware that other sources may instead use it as a  Jim Hefferon committed Dec 31, 2011 334 synonym for homomorphism'.  Jim Hefferon committed Dec 05, 2011 335 336 337 338 \end{remark} \begin{example} The map on $\Re^2$ that projects all vectors down to the $x$-axis  Jim Hefferon committed Oct 12, 2013 339 is a linear transformation.  Jim Hefferon committed Dec 05, 2011 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 committed Jan 01, 2012 352 is a linear transformation as this result from calculus shows:  Jim Hefferon committed Dec 05, 2011 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 committed Dec 31, 2011 357 The matrix transpose operation  Jim Hefferon committed Dec 05, 2011 358 \begin{equation*}  Jim Hefferon committed Dec 31, 2011 359  \begin{mat}  Jim Hefferon committed Dec 05, 2011 360 361  a &b \\ c &d  Jim Hefferon committed Dec 31, 2011 362  \end{mat}  Jim Hefferon committed Dec 05, 2011 363  \;\mapsto\;  Jim Hefferon committed Dec 31, 2011 364  \begin{mat}  Jim Hefferon committed Dec 05, 2011 365 366  a &c \\ b &d  Jim Hefferon committed Dec 31, 2011 367  \end{mat}  Jim Hefferon committed Dec 05, 2011 368 369 \end{equation*} is a linear transformation of $$\matspace_{\nbyn{2}}$$.  Jim Hefferon committed Oct 12, 2013 370 (Transpose is one-to-one and onto and so is in fact  Jim Hefferon committed Dec 31, 2011 371 an automorphism.)  Jim Hefferon committed Dec 05, 2011 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 committed Oct 12, 2013 386 the linear combination $$5f-2g$$ is also a transformation of~$R^2$.  Jim Hefferon committed Dec 05, 2011 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 committed May 08, 2012 394 %<*lm:SpLinFcns>  Jim Hefferon committed Dec 05, 2011 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 committed May 08, 2012 399 %  Jim Hefferon committed Dec 05, 2011 400 401 \end{lemma}  Jim Hefferon committed May 08, 2012 402 %<*SpLinFcns>  Jim Hefferon committed Oct 12, 2013 403 \noindent We denote the space of linear maps from $V$ to~$W$ by  Jim Hefferon committed Nov 27, 2013 404 $$\linmaps{V}{W}$$.\index{linear maps, vector space of}  Jim Hefferon committed May 08, 2012 405 %  Jim Hefferon committed Jan 01, 2012 406   Jim Hefferon committed Dec 05, 2011 407 \begin{proof}  Jim Hefferon committed May 08, 2012 408 %<*pf:SpLinFcns>  Jim Hefferon committed Dec 05, 2011 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 committed May 20, 2012 411 closed under the operations.  Jim Hefferon committed Dec 05, 2011 412 Let $$\map{f,g}{V}{W}$$ be linear.  Jim Hefferon committed Oct 12, 2013 413 Then the operation of function addition is preserved  Jim Hefferon committed Dec 05, 2011 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 committed Oct 12, 2013 422 as is the operation of scalar multiplication of a function.  Jim Hefferon committed Dec 05, 2011 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 committed May 08, 2012 429 %  Jim Hefferon committed Dec 05, 2011 430 431 \end{proof}  Jim Hefferon committed Dec 31, 2011 432 We started this section by  Jim Hefferon committed Oct 12, 2013 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 committed Dec 31, 2011 441 442 In the rest of this chapter we shall work mostly with homomorphisms. This is  Jim Hefferon committed Dec 05, 2011 443 partly because any statement made about homomorphisms is automatically true  Jim Hefferon committed Dec 31, 2011 444 445 about isomorphisms but more because, while the isomorphism concept is more natural,  Jim Hefferon committed Oct 12, 2013 446 447 our experience will show that the homomorphism concept is more fruitful and more central to progress.  Jim Hefferon committed Dec 05, 2011 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 committed Dec 31, 2011 454 455  \partsitem $$h(\colvec{x \\ y \\ z})=\colvec[r]{0 \\ 0}$$ \partsitem $$h(\colvec{x \\ y \\ z})=\colvec[r]{1 \\ 1}$$  Jim Hefferon committed Dec 05, 2011 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 committed Dec 31, 2011 479  &=\colvec[r]{0 \\ 0} \\  Jim Hefferon committed Dec 05, 2011 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 committed Dec 31, 2011 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})  Jim Hefferon committed Dec 05, 2011 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 committed Dec 31, 2011 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$$  Jim Hefferon committed Dec 05, 2011 512 513  \end{exparts} \begin{answer}  Jim Hefferon committed Jan 01, 2012 514 515  For each, we must either check that the map preserves linear combinations or give an example of a linear combination that is  Jim Hefferon committed Dec 05, 2011 516 517 518 519 520  not. \begin{exparts*} \partsitem Yes. The check that it preserves combinations is routine. \begin{align*}  Jim Hefferon committed Dec 31, 2011 521  h(r_1\cdot\begin{mat}  Jim Hefferon committed Dec 05, 2011 522 523  a_1 &b_1 \\ c_1 &d_1  Jim Hefferon committed Dec 31, 2011 524 525  \end{mat} +r_2\cdot\begin{mat}  Jim Hefferon committed Dec 05, 2011 526 527  a_2 &b_2 \\ c_2 &d_2  Jim Hefferon committed Dec 31, 2011 528 529  \end{mat}) &=h(\begin{mat}  Jim Hefferon committed Dec 05, 2011 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 committed Dec 31, 2011 532  \end{mat}) \\  Jim Hefferon committed Dec 05, 2011 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 committed Dec 31, 2011 535  &=r_1\cdot h(\begin{mat}  Jim Hefferon committed Dec 05, 2011 536 537  a_1 &b_1 \\ c_1 &d_1  Jim Hefferon committed Dec 31, 2011 538 539  \end{mat}) +r_2\cdot h(\begin{mat}  Jim Hefferon committed Dec 05, 2011 540 541  a_2 &b_2 \\ c_2 &d_2  Jim Hefferon committed Dec 31, 2011 542  \end{mat})  Jim Hefferon committed Dec 05, 2011 543 544 545 546  \end{align*} \partsitem No. For instance, not preserved is multiplication by the scalar $2$. \begin{equation*}  Jim Hefferon committed Dec 31, 2011 547  h(2\cdot\begin{mat}[r]  Jim Hefferon committed Dec 05, 2011 548 549  1 &0 \\ 0 &1  Jim Hefferon committed Dec 31, 2011 550 551  \end{mat}) =h(\begin{mat}[r]  Jim Hefferon committed Dec 05, 2011 552 553  2 &0 \\ 0 &2  Jim Hefferon committed Dec 31, 2011 554  \end{mat})  Jim Hefferon committed Dec 05, 2011 555 556  =4 \quad\text{while}\quad  Jim Hefferon committed Dec 31, 2011 557  2\cdot h(\begin{mat}[r]  Jim Hefferon committed Dec 05, 2011 558 559  1 &0 \\ 0 &1  Jim Hefferon committed Dec 31, 2011 560  \end{mat})  Jim Hefferon committed Dec 05, 2011 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 committed Dec 20, 2013 566  \begin{multline*}  Jim Hefferon committed Dec 31, 2011 567  h(r_1\cdot\begin{mat} a_1 &b_1 \\ c_1 &d_1 \end{mat}  Jim Hefferon committed Dec 20, 2013 568 569  +r_2\cdot\begin{mat} a_2 &b_2 \\ c_2 &d_2 \end{mat}) \\ \begin{aligned}  Jim Hefferon committed Dec 31, 2011 570  &=h(\begin{mat}  Jim Hefferon committed Dec 05, 2011 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 committed Dec 31, 2011 573  \end{mat}) \\  Jim Hefferon committed Dec 05, 2011 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 committed Dec 31, 2011 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 committed Dec 20, 2013 580 581  \end{aligned} \end{multline*}  Jim Hefferon committed Dec 05, 2011 582  \partsitem No.  Jim Hefferon committed Dec 20, 2013 583 584  An example of a combination that is not preserved is that doing it one way gives this  Jim Hefferon committed Dec 05, 2011 585  \begin{equation*}  Jim Hefferon committed Dec 31, 2011 586  h(\begin{mat}[r]  Jim Hefferon committed Dec 05, 2011 587 588  1 &0 \\ 0 &0  Jim Hefferon committed Dec 31, 2011 589 590  \end{mat} +\begin{mat}[r]  Jim Hefferon committed Dec 05, 2011 591 592  1 &0 \\ 0 &0  Jim Hefferon committed Dec 31, 2011 593 594  \end{mat}) =h(\begin{mat}[r]  Jim Hefferon committed Dec 05, 2011 595 596  2 &0 \\ 0 &0  Jim Hefferon committed Dec 31, 2011 597  \end{mat})  Jim Hefferon committed Dec 05, 2011 598  =4  Jim Hefferon committed Dec 20, 2013 599 600 601  \end{equation*} while the other way gives this. \begin{equation*}  Jim Hefferon committed Dec 31, 2011 602  h(\begin{mat}[r]  Jim Hefferon committed Dec 05, 2011 603 604  1 &0 \\ 0 &0  Jim Hefferon committed Dec 31, 2011 605 606  \end{mat}) +h(\begin{mat}[r]  Jim Hefferon committed Dec 05, 2011 607 608  1 &0 \\ 0 &0  Jim Hefferon committed Dec 31, 2011 609  \end{mat})  Jim Hefferon committed Dec 05, 2011 610 611 612 613 614 615  =1+1 =2 \end{equation*} \end{exparts*} \end{answer} \recommended \item  Jim Hefferon committed Nov 29, 2014 616 617  Show that these are homomorphisms. Are they inverse to each other?  Jim Hefferon committed Dec 05, 2011 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  Jim Hefferon committed Jan 09, 2012 641  property of differentiation that is familiar from calculus.)  Jim Hefferon committed Dec 05, 2011 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 committed Dec 31, 2011 679  \colvec{x \\ y \\ z}\mapsto\colvec[r]{0 \\ 0 \\ 0}  Jim Hefferon committed Dec 05, 2011 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 committed Nov 29, 2014 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}  Jim Hefferon committed Dec 05, 2011 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 committed Dec 31, 2011 737  \begin{mat}[r]  Jim Hefferon committed Dec 05, 2011 738 739  1 &0 \\ 0 &0  Jim Hefferon committed Dec 31, 2011 740  \end{mat}  Jim Hefferon committed Dec 05, 2011 741  \quad\text{and}\quad  Jim Hefferon committed Dec 31, 2011 742  \begin{mat}[r]  Jim Hefferon committed Dec 05, 2011 743 744  0 &0 \\ 0 &1  Jim Hefferon committed Dec 31, 2011 745  \end{mat}  Jim Hefferon committed Dec 05, 2011 746  \end{equation*}  Jim Hefferon committed Jan 01, 2012 747  map to the same member of the codomain, $1\in\Re$.  Jim Hefferon committed Dec 05, 2011 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}  Jim Hefferon committed Jun 07, 2016 832  \item  Jim Hefferon committed Dec 05, 2011 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}  Jim Hefferon committed Jun 07, 2016 852 853  \item Consider this transformation of the plane $$\Re^2$$.  Jim Hefferon committed Dec 05, 2011 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 committed Jan 01, 2012 876  How much extra rope must we add to raise the circle to a constant  Jim Hefferon committed Dec 05, 2011 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 committed Dec 31, 2011 893  \colvec{x \\ y \\ z}\dotprod\colvec[r]{3 \\ -1 \\ -1}=3x-y-z  Jim Hefferon committed Dec 05, 2011 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  Jim Hefferon committed Nov 23, 2016 967  c_{k}\frac{d^k}{dx^k}f+c_{k-1}\frac{d^{k-1}}{dx^{k-1}}f  Jim Hefferon committed Dec 05, 2011 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 committed Dec 20, 2013 976  \begin{multline*}  Jim Hefferon committed Dec 05, 2011 977  h(c\cdot \colvec{x_1 \\ \vdots \\ x_n}  Jim Hefferon committed Dec 20, 2013 978 979  +d\cdot \colvec{y_1 \\ \vdots \\ y_n}) \\ \begin{aligned}  Jim Hefferon committed Dec 05, 2011 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 committed Dec 20, 2013 992 993  \end{aligned} \end{multline*}  Jim Hefferon committed Dec 05, 2011 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 committed Dec 20, 2013 999  \qquad  Jim Hefferon committed Dec 05, 2011 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 committed Jan 01, 2012 1014  The composition preserves linear combinations  Jim Hefferon committed Dec 05, 2011 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 committed Jan 01, 2012 1023  where $\vec{u}_1,\vec{u}_2\in U$ and scalars $c_1,c_2$  Jim Hefferon committed Dec 05, 2011 1024  \end{answer}  Jim Hefferon committed Jun 07, 2016 1025  \item  Jim Hefferon committed Dec 05, 2011 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 committed Dec 31, 2011 1059  \set{\vec{v}_1,\vec{v}_2}=\set{\colvec[r]{1 \\ 0},\colvec[r]{1 \\ 1}}  Jim Hefferon committed Dec 05, 2011 1060  \;\mapsto\;  Jim Hefferon committed Dec 31, 2011 1061  \set{\colvec[r]{1 \\ 1},\colvec[r]{2 \\ 2}}=\set{\vec{w}_1,\vec{w}_2}  Jim Hefferon committed Dec 05, 2011 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 committed Dec 31, 2011 1072 1073  \set{\colvec[r]{1 \\ 0 \\ 0},\colvec[r]{0 \\ 1 \\ 0}} \mapsunder{\pi}\set{\colvec[r]{1 \\ 0},\colvec[r]{0 \\ 1}}  Jim Hefferon committed Dec 05, 2011 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}  Jim Hefferon committed May 11, 2012 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?  Jim Hefferon committed Dec 05, 2011 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 committed Dec 20, 2013 1093 1094 1095  Now, the check is routine. Start with the transpose of the combination. \begin{equation*}  Jim Hefferon committed Dec 31, 2011 1096 1097  \trans{[r\cdot\begin{mat} \ &\vdots \\  Jim Hefferon committed Dec 05, 2011 1098 1099  \cdots &a_{i,j} &\cdots \\ &\vdots  Jim Hefferon committed Dec 31, 2011 1100 1101 1102  \end{mat} +s\cdot\begin{mat} \ &\vdots \\  Jim Hefferon committed Dec 05, 2011 1103 1104  \cdots &b_{i,j} &\cdots \\ &\vdots  Jim Hefferon committed Dec 20, 2013 1105 1106 1107 1108 1109  \end{mat}]} \end{equation*} Combine and take the transpose. \begin{equation*} =\trans{\begin{mat}  Jim Hefferon committed Dec 31, 2011 1110  \ &\vdots \\  Jim Hefferon committed Dec 05, 2011 1111 1112  \cdots &ra_{i,j}+sb_{i,j} &\cdots \\ &\vdots  Jim Hefferon committed Dec 20, 2013 1113 1114  \end{mat}} =\begin{mat}  Jim Hefferon committed Dec 31, 2011 1115  \ &\vdots \\  Jim Hefferon committed Dec 05, 2011 1116 1117  \cdots &ra_{j,i}+sb_{j,i} &\cdots \\ &\vdots  Jim Hefferon committed Dec 20, 2013 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 committed Dec 31, 2011 1123  \ &\vdots \\  Jim Hefferon committed Dec 05, 2011 1124 1125  \cdots &a_{j,i} &\cdots \\ &\vdots  Jim Hefferon committed Dec 31, 2011 1126 1127 1128  \end{mat} +s\cdot\begin{mat} \ &\vdots \\  Jim Hefferon committed Dec 05, 2011 1129 1130  \cdots &b_{j,i} &\cdots \\ &\vdots  Jim Hefferon committed Dec 20, 2013 1131 1132  \end{mat} \\ =r\cdot\trans{\begin{mat}  Jim Hefferon committed Dec 31, 2011 1133  \ &\vdots \\  Jim Hefferon committed Dec 05, 2011 1134 1135  \cdots &a_{j,i} &\cdots \\ &\vdots  Jim Hefferon committed Dec 31, 2011 1136 1137 1138  \end{mat} } +s\cdot\trans{\begin{mat} \ &\vdots \\  Jim Hefferon committed Dec 05, 2011 1139 1140  \cdots &b_{j,i} &\cdots \\ &\vdots  Jim Hefferon committed Dec 31, 2011 1141  \end{mat} }  Jim Hefferon committed Dec 20, 2013 1142  \end{multline*}  Jim Hefferon committed Dec 05, 2011 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 committed Jan 01, 2012 1149  by definition the line segment connecting them is the set  Jim Hefferon committed Dec 05, 2011 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 committed Jan 01, 2012 1188  Now, where $\hat{t}$ is the scalar that we fixed in the first  Jim Hefferon committed Dec 05, 2011 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 committed Dec 20, 2013 1216 1217  a $$k$$-dimensional linear surface in $$\Re^m$$ (possibly it is degenerate).  Jim Hefferon committed Dec 05, 2011 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}  Jim Hefferon committed May 08, 2012 1239  \partsitem Show that the \definend{range space} of this map  Jim Hefferon committed Dec 05, 2011 1240 1241  $$\set{h(\vec{v})\suchthat \vec{v}\in V}$$ is a subspace of the codomain $$W$$.  Jim Hefferon committed May 08, 2012 1242  \partsitem Show that the \definend{null space} of this map  Jim Hefferon committed Dec 05, 2011 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.  Jim Hefferon committed May 08, 2012 1268  \partsitem The null space is nonempty since it contains $\zero_V$, as  Jim Hefferon committed Dec 05, 2011 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  Jim Hefferon committed May 23, 2012 1272  of the inverse image  Jim Hefferon committed Dec 05, 2011 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 committed Dec 20, 2013 1298  Note that $$\zero_W\in X$$ so that the set  Jim Hefferon committed Dec 05, 2011 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 committed Jan 01, 2012 1333  specifying only that $\vec{e}_1$ maps to itself, then  Jim Hefferon committed Dec 05, 2011 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 committed Dec 20, 2013 1366  \begin{multline*}  Jim Hefferon committed Dec 05, 2011 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 committed Dec 20, 2013 1369  f_2(r_1\vec{v}_1+r_2\vec{v}_2)} \\  Jim Hefferon committed Dec 05, 2011 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 committed Dec 20, 2013 1373  \end{multline*}  Jim Hefferon committed Dec 05, 2011 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,  Jim Hefferon committed Jan 09, 2012 1391  and the fact that the composition of linear functions is linear  Jim Hefferon committed Jan 01, 2012 1392  was part of the proof that isomorphism is an equivalence  Jim Hefferon committed Dec 05, 2011 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 committed May 08, 2012 1417 \subsection{Range space and Null space}  Jim Hefferon committed Dec 05, 2011 1418 Isomorphisms and homomorphisms both preserve structure.  Jim Hefferon committed Oct 13, 2013 1419 1420 The difference is that homomorphisms have fewer restrictions, since they needn't be onto and  Jim Hefferon committed Dec 05, 2011 1421 needn't be one-to-one.  Jim Hefferon committed Jan 02, 2012 1422 We will examine what can happen with homomorphisms  Jim Hefferon committed Jul 03, 2012 1423 that cannot happen with isomorphisms.  Jim Hefferon committed Dec 05, 2011 1424   Jim Hefferon committed Oct 13, 2013 1425 1426 First consider the fact that homomorphisms need not be onto.  Jim Hefferon committed Dec 31, 2011 1427 Of course,  Jim Hefferon committed Oct 13, 2013 1428 each function is onto some set, namely its range.  Jim Hefferon committed Dec 31, 2011 1429 For example, the injection map $$\map{\iota}{\Re^2}{\Re^3}$$  Jim Hefferon committed Dec 05, 2011 1430 1431 1432 \begin{equation*} \colvec{x \\ y} \mapsto \colvec{x \\ y \\ 0} \end{equation*}  Jim Hefferon committed Oct 13, 2013 1433 1434 is a homomorphism, and is not onto $\Re^3$. But it is onto the $xy$-plane.  Jim Hefferon committed Dec 05, 2011 1435 1436  \begin{lemma} \label{le:RangeIsSubSp}  Jim Hefferon committed May 08, 2012 1437 %<*lm:RangeIsSubSp>  Jim Hefferon committed Dec 05, 2011 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 committed May 08, 2012 1442 %  Jim Hefferon committed Dec 05, 2011 1443 1444 1445 \end{lemma} \begin{proof}  Jim Hefferon committed May 08, 2012 1446 %<*pf:RangeIsSubSp>  Jim Hefferon committed Dec 05, 2011 1447 1448 Let $\map{h}{V}{W}$ be linear and let $S$ be a subspace of the domain $V$.  Jim Hefferon committed Jan 01, 2012 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$  Jim Hefferon committed Dec 05, 2011 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 committed May 08, 2012 1462 %  Jim Hefferon committed Dec 05, 2011 1463 1464 \end{proof}  Jim Hefferon committed May 08, 2012 1465 1466 1467 \begin{definition} \label{df:RangeSpace} %<*df:RangeSpace> The \definend{range space}\index{range space}\index{homomorphism!range space}  Jim Hefferon committed Dec 05, 2011 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)$$.  Jim Hefferon committed May 08, 2012 1473 The dimension of the range space is the map's  Jim Hefferon committed Dec 05, 2011 1474 \definend{rank}.\index{rank!of a homomorphism}  Jim Hefferon committed May 08, 2012 1475 %  Jim Hefferon committed Dec 05, 2011 1476 1477 \end{definition} \noindent  Jim Hefferon committed Jan 01, 2012 1478 1479 We shall soon see the connection between the rank of a map and the rank of a matrix.  Jim Hefferon committed Dec 05, 2011 1480 1481  \begin{example} \label{ex:DerivMapRnge}  Jim Hefferon committed Jan 01, 2012 1482 For the derivative map  Jim Hefferon committed Dec 05, 2011 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$$  Jim Hefferon committed May 08, 2012 1485 the range space  Jim Hefferon committed Dec 05, 2011 1486 1487 $$\rangespace{d/dx}$$ is the set of quadratic polynomials $$\set{r+sx+tx^2\suchthat r,s,t\in\Re }$$.  Jim Hefferon committed Jan 01, 2012 1488 Thus, this map's rank is~$$3$$.  Jim Hefferon committed Dec 05, 2011 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 committed Dec 31, 2011 1494  \begin{mat}  Jim Hefferon committed Dec 05, 2011 1495 1496  a &b \\ c &d  Jim Hefferon committed Dec 31, 2011 1497  \end{mat}  Jim Hefferon committed Dec 05, 2011 1498  \mapsto  Jim Hefferon committed Dec 31, 2011 1499  (a+b+2d)+cx^2+cx^3  Jim Hefferon committed Dec 05, 2011 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$.  Jim Hefferon committed May 08, 2012 1504 That is, the range space is  Jim Hefferon committed Dec 31, 2011 1505 1506 $$\rangespace{h}=\set{r+sx^2+sx^3\suchthat r,s\in\Re}$$ and so the rank is~$$2$$.  Jim Hefferon committed Dec 05, 2011 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 committed Oct 13, 2013 1512 omitting the onto requirement doesn't make an essential difference.  Jim Hefferon committed Apr 18, 2014 1513 Any homomorphism is onto some space, namely its range.  Jim Hefferon committed Dec 05, 2011 1514   Jim Hefferon committed Apr 18, 2014 1515 However, omitting the one-to-one condition does make a difference.  Jim Hefferon committed Dec 05, 2011 1516 1517 A homomorphism may have many elements of the domain that map to one element of the codomain.  Jim Hefferon committed Oct 13, 2013 1518 Below is a bean sketch of a many-to-one  Jim Hefferon committed Dec 05, 2011 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.  Jim Hefferon committed Apr 18, 2014 1522 1523 (Rather than picture lots of individual $\mapsto$ arrows, each association of many inputs with one output shows only one such arrow.)  Jim Hefferon committed Dec 05, 2011 1524 1525 1526 \begin{center} \includegraphics{ch3.5} % bean to bean; many to one \end{center}  Jim Hefferon committed May 11, 2012 1527 %<*InverseImage>  Jim Hefferon committed Dec 05, 2011 1528 Recall that for any function $\map{h}{V}{W}$,  Jim Hefferon committed Jan 01, 2012 1529 the set of elements of $V$ that map to $$\vec{w}\in W$$  Jim Hefferon committed May 23, 2012 1530 is the \definend{inverse image\/}\index{inverse image}%  Jim Hefferon committed Dec 05, 2011 1531 1532 \index{function! inverse image} $h^{-1}(\vec{w})=\set{\vec{v}\in V\suchthat h(\vec{v})=\vec{w}}$.  Jim Hefferon committed May 11, 2012 1533 %  Jim Hefferon committed Dec 05, 2016 1534 Above, the left side shows three inverse image sets.  Jim Hefferon committed Dec 05, 2011 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 committed Dec 31, 2011 1545 An inverse image set is a vertical line of vectors  Jim Hefferon committed Dec 05, 2011 1546 1547 1548 1549 in the domain. \begin{center} \includegraphics{ch3.11} \end{center}  Jim Hefferon committed Dec 31, 2011 1550 1551 1552