jc1.tex 11.8 KB
 Jim Hefferon committed Dec 05, 2011 1 % Chapter 4, Section 1 _Linear Algebra_ Jim Hefferon  Jim Hefferon committed Nov 16, 2013 2 % http://joshua.smcvt.edu/linearalgebra  Jim Hefferon committed Dec 05, 2011 3 4 % 2001-Jun-12 \chapter{Similarity}  Jim Hefferon committed Jan 17, 2012 5 We have shown that for any  Jim Hefferon committed Dec 05, 2011 6 homomorphism there are bases $B$ and~$D$ such that the  Jim Hefferon committed Nov 18, 2013 7 matrix representing the map has a block partial-identity form.  Jim Hefferon committed Dec 05, 2011 8 9 10 11 12 13 14 15 16 \begin{equation*} \rep{h}{B,D} = \begin{pmat}{c|c} \text{\textit{Identity}} &\text{\textit{Zero}} \\ \hline \text{\textit{Zero}} &\text{\textit{Zero}} \end{pmat} \end{equation*}  Jim Hefferon committed Jan 17, 2012 17 This representation describes the map as sending  Jim Hefferon committed Dec 05, 2011 18 19 20 21 $$c_1\vec{\beta}_1+\dots+c_n\vec{\beta}_n$$ to $$c_1\vec{\delta}_1+\dots+c_k\vec{\delta}_k+\zero+\dots+\zero$$, where $n$ is the dimension of the domain and $$k$$ is the dimension of the range.  Jim Hefferon committed Nov 18, 2013 22 Under this representation  Jim Hefferon committed Dec 05, 2011 23 24 25 26 the action of the map is easy to understand because most of the matrix entries are zero. This chapter considers the special case where the domain and  Jim Hefferon committed Jan 17, 2012 27 codomain are the same.  Jim Hefferon committed Nov 16, 2013 28 29 Here we naturally ask for the domain basis and codomain basis to be the same. That is,  Jim Hefferon committed Nov 18, 2013 30 31 we want a basis $$B$$ so that $$\rep{t}{B,B}$$ is as simple as possible, where we take simple' to mean that it has many zeroes.  Jim Hefferon committed Jan 17, 2012 32 33 34 We will find that we cannot always get a matrix having the above block partial-identity form but we will develop a form that comes close, a  Jim Hefferon committed Dec 05, 2011 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 representation that is nearly diagonal. \section{Complex Vector Spaces} \index{vector space!over complex numbers}  Jim Hefferon committed Jun 14, 2012 51 %<*ReasonForShiftToComplexNumbers>  Jim Hefferon committed Dec 10, 2013 52 53 54 This chapter requires that we factor polynomials. But many polynomials do not factor over the real numbers; for instance,  Jim Hefferon committed Jan 17, 2012 55 $$x^2+1$$ does not factor into a product of two linear polynomials  Jim Hefferon committed Nov 23, 2014 56 with real coefficients;  Jim Hefferon committed Jan 17, 2012 57 instead it requires complex numbers $x^2+1=(x-i)(x+i)$.  Jim Hefferon committed Dec 05, 2011 58   Jim Hefferon committed Nov 18, 2013 59 Consequently in this chapter  Jim Hefferon committed Jan 17, 2012 60 61 we shall use complex numbers for our scalars, including entries in vectors and matrices.  Jim Hefferon committed Nov 18, 2013 62 That is, we shift from studying vector spaces over the real numbers  Jim Hefferon committed Nov 27, 2013 63 64 to vector spaces over the complex numbers.\index{complex numbers!vector space over}  Jim Hefferon committed Dec 05, 2011 65 Any real number is a complex number and  Jim Hefferon committed Jan 17, 2012 66 in this chapter most of the examples use  Jim Hefferon committed Nov 18, 2013 67 68 only real numbers but nonetheless, the critical theorems require that the scalars be complex.  Jim Hefferon committed Dec 10, 2013 69 %  Jim Hefferon committed Nov 18, 2013 70 71 So this first section is a review of complex numbers.  Jim Hefferon committed Dec 05, 2011 72   Jim Hefferon committed Nov 18, 2013 73 74 75 In this book our approach is to shift to this more general context of taking scalars to be complex for the pragmatic reason that we must do so in order to  Jim Hefferon committed Jan 17, 2012 76 77 78 79 80 move forward. However, the idea of doing vector spaces by taking scalars from a structure other than the real numbers is an interesting and useful one. Delightful presentations that take this approach from the start are in  Jim Hefferon committed Dec 05, 2011 81 82 83 84 85 86 87 \cite{Halmos} and \cite{HoffmanKunze}.  Jim Hefferon committed Nov 16, 2013 88 \subsectionoptional{Polynomial Factoring and Complex Numbers}  Jim Hefferon committed Nov 18, 2013 89 90 91 \textit{This subsection is a review only. For a full development, including proofs, see \cite{Ebbinghaus}.}  Jim Hefferon committed Dec 05, 2011 92   Jim Hefferon committed Dec 10, 2013 93 %<*PolynomialReview0>  Jim Hefferon committed Nov 16, 2013 94 Consider a polynomial\index{polynomial}  Jim Hefferon committed Jan 22, 2012 95 $p(x)=c_nx^n+\dots+c_1x+c_0$ with  Jim Hefferon committed Nov 16, 2013 96 leading coefficient\index{polynomial!leading coefficient}  Jim Hefferon committed Nov 23, 2014 97 $c_n\neq 0$.  Jim Hefferon committed Nov 27, 2013 98 The degree\index{polynomial!degree}\index{degree of a polynomial}  Jim Hefferon committed Nov 16, 2013 99 of the polynomial is~$n$.  Jim Hefferon committed Jan 22, 2012 100 If $n=0$ then $p$ is a  Jim Hefferon committed Nov 16, 2013 101 102 constant polynomial\index{polynomial!constant}\index{constant polynomial} $p(x)=c_0$.  Jim Hefferon committed Jan 22, 2012 103 104 Constant polynomials that are not the zero polynomial, $c_0\neq 0$, have degree zero.  Jim Hefferon committed Nov 16, 2013 105 We define the zero polynomial to have degree $-\infty$.  Jim Hefferon committed Dec 10, 2013 106 %  Jim Hefferon committed Jan 22, 2012 107   Jim Hefferon committed Nov 18, 2013 108 109 110 111 112 113 114 \begin{remark} Defining the degree of the zero polynomial to be $-\infty$ %, which most authors do, allows the equation $\text{degree}(fg)=\text{degree}(f)+\text{degree}(g)$ to hold for all polynomials. \end{remark}  Jim Hefferon committed Dec 10, 2013 115 %<*PolynomialReview1>  Jim Hefferon committed Dec 05, 2011 116 117 118 Just as integers have a division operation\Dash e.g., $$4$$ goes $$5$$ times into $$21$$ with remainder $$1$$'\Dash so do polynomials.  Jim Hefferon committed Dec 10, 2013 119 %  Jim Hefferon committed Dec 05, 2011 120   Jim Hefferon committed Jun 14, 2012 121 \begin{theorem}[Division Theorem for Polynomials] \label{th:EuclidForPolys}  Jim Hefferon committed Jan 22, 2012 122 \index{division theorem}\index{polynomial!division theorem}  Jim Hefferon committed Jun 14, 2012 123 %<*th:EuclidForPolys>  Jim Hefferon committed Nov 16, 2013 124 125 Let $$p(x)$$ be a polynomial. If $$d(x)$$ is a non-zero polynomial then there are \definend{quotient} and  Jim Hefferon committed Dec 05, 2011 126 127 \definend{remainder} polynomials $$q(x)$$ and $$r(x)$$ such that \begin{equation*}  Jim Hefferon committed Nov 16, 2013 128  p(x)=d(x)\cdot q(x)+r(x)  Jim Hefferon committed Dec 05, 2011 129 \end{equation*}  Jim Hefferon committed Nov 16, 2013 130 where the degree of $$r(x)$$ is strictly less than the degree of $$d(x)$$.  Jim Hefferon committed Jun 14, 2012 131 %  Jim Hefferon committed Dec 05, 2011 132 133 \end{theorem}  Jim Hefferon committed Nov 16, 2013 134 The point of the integer statement  Jim Hefferon committed Dec 05, 2011 135 136 137 $$4$$ goes $$5$$ times into $$21$$ with remainder $$1$$' is that the remainder is less than $$4$$\Dash while $$4$$ goes $$5$$ times, it does not go $$6$$ times.  Jim Hefferon committed Nov 18, 2013 138 139 Similarly, the final clause of the polynomial division statement is crucial.  Jim Hefferon committed Dec 05, 2011 140 141  \begin{example}  Jim Hefferon committed Nov 16, 2013 142 If $$p(x)=2x^3-3x^2+4x$$ and $$d(x)=x^2+1$$ then $$q(x)=2x-3$$ and  Jim Hefferon committed Dec 05, 2011 143 $$r(x)=2x+3$$.  Jim Hefferon committed Nov 16, 2013 144 Note that $$r(x)$$ has a lower degree than does $$d(x)$$.  Jim Hefferon committed Dec 05, 2011 145 146 \end{example}  Jim Hefferon committed Jun 14, 2012 147 148 \begin{corollary} \label{co:PolyDividedByLinearPolyIsConstant} %<*co:PolyDividedByLinearPolyIsConstant>  Jim Hefferon committed Nov 16, 2013 149 150 The remainder when $$p(x)$$ is divided by $$x-\lambda$$ is the constant polynomial $$r(x)=p(\lambda)$$.  Jim Hefferon committed Jun 14, 2012 151 %  Jim Hefferon committed Dec 05, 2011 152 153 154 \end{corollary} \begin{proof}  Jim Hefferon committed Jun 14, 2012 155 %<*pf:PolyDividedByLinearPolyIsConstant>  Jim Hefferon committed Dec 05, 2011 156 The remainder must be a constant polynomial  Jim Hefferon committed Nov 16, 2013 157 because it is of degree less than the divisor $$x-\lambda$$.  Jim Hefferon committed Nov 18, 2013 158 159 160 To determine the constant, take the theorem's divisor $d(x)$ to be $x-\lambda$ and substitute $$\lambda\/$$ for $x$.  Jim Hefferon committed Jun 14, 2012 161 %  Jim Hefferon committed Dec 05, 2011 162 163 \end{proof}  Jim Hefferon committed Jun 14, 2012 164 %<*PolynomialFactor>  Jim Hefferon committed Nov 16, 2013 165 If a divisor $$d(x)$$ goes into a dividend $$p(x)$$ evenly,  Jim Hefferon committed Dec 05, 2011 166 meaning that $$r(x)$$ is the zero polynomial,  Jim Hefferon committed Nov 18, 2013 167 then $$d(x)$$ is a called a factor\index{factor}\index{polynomial!factor}  Jim Hefferon committed Nov 16, 2013 168 169 170 171 172 of $$p(x)$$. Any root\index{root}\index{polynomial!root} of the factor, any $$\lambda\in\Re$$ such that $$d(\lambda)=0$$, is a root of $$p(x)$$ since $$p(\lambda)=d(\lambda)\cdot q(\lambda)=0$$.  Jim Hefferon committed Jun 14, 2012 173 %  Jim Hefferon committed Dec 05, 2011 174   Jim Hefferon committed Jun 14, 2012 175 176 \begin{corollary} \label{co:RootOfPolyIsAssocLinearFactor} %<*co:RootOfPolyIsAssocLinearFactor>  Jim Hefferon committed Nov 16, 2013 177 178 179 If $$\lambda$$ is a root of the polynomial $$p(x)$$ then $$x-\lambda$$ divides $$p(x)$$ evenly, that is, $x-\lambda$ is a factor of $p(x)$.  Jim Hefferon committed Jun 14, 2012 180 %  Jim Hefferon committed Dec 05, 2011 181 182 \end{corollary}  Jim Hefferon committed Jan 17, 2012 183 \begin{proof}  Jim Hefferon committed Jun 14, 2012 184 %<*pf:RootOfPolyIsAssocLinearFactor>  Jim Hefferon committed Nov 16, 2013 185 By the above corollary $p(x)=(x-\lambda)\cdot q(x)+p(\lambda)$.  Jim Hefferon committed Jan 17, 2012 186 Since $\lambda$ is a root,  Jim Hefferon committed Nov 16, 2013 187 $p(\lambda)=0$ so $x-\lambda$ is a factor.  Jim Hefferon committed Jun 14, 2012 188 %  Jim Hefferon committed Jan 17, 2012 189 190 \end{proof}  Jim Hefferon committed Nov 16, 2013 191 192 193 194 A repeated root of a polynomial is a number $\lambda$ such that the polynomial is evenly divisible by $(x-\lambda)^n$ for some power larger than one. The largest such power is called the  Jim Hefferon committed Nov 29, 2013 195 multiplicity\index{multiplicity, of a root}\index{polynomial!multiplicity}  Jim Hefferon committed Nov 16, 2013 196 197 of~$\lambda$.  Jim Hefferon committed Dec 05, 2011 198 199 Finding the roots and factors of a high-degree polynomial can be hard. But for second-degree polynomials we have the quadratic formula:~the  Jim Hefferon committed Nov 18, 2013 200 roots of $$ax^2+bx+c$$ are these  Jim Hefferon committed Dec 05, 2011 201 202 203 204 205 206 207 208 \begin{equation*} \lambda_1=\frac{-b+\sqrt{b^2-4ac}}{2a} \qquad \lambda_2=\frac{-b-\sqrt{b^2-4ac}}{2a} \end{equation*} (if the discriminant $$b^2-4ac$$ is negative then the polynomial has no real number roots). A polynomial that cannot be factored into two lower-degree polynomials  Jim Hefferon committed Nov 18, 2013 209 with real number coefficients is said to be irreducible over the  Jim Hefferon committed Nov 27, 2013 210 reals.\index{irreducible polynomial}\index{polynomial!irreducible}  Jim Hefferon committed Dec 05, 2011 211   Jim Hefferon committed Jun 14, 2012 212 213 \begin{theorem} \label{th:CubicsAndHigherFactor} %<*th:CubicsAndHigherFactor>  Jim Hefferon committed Dec 05, 2011 214 215 216 217 Any constant or linear polynomial is irreducible over the reals. A quadratic polynomial is irreducible over the reals if and only if its discriminant is negative. No cubic or higher-degree polynomial is irreducible over the reals.  Jim Hefferon committed Jun 14, 2012 218 %  Jim Hefferon committed Dec 05, 2011 219 220 \end{theorem}  Jim Hefferon committed Jun 14, 2012 221 222 \begin{corollary} \label{co:RealPolysFactorIntoLinearsAndQuads} %<*co:RealPolysFactorIntoLinearsAndQuads>  Jim Hefferon committed Dec 05, 2011 223 224 225 226 Any polynomial with real coefficients can be factored into linear and irreducible quadratic polynomials. That factorization is unique; any two factorizations have the same powers of the same factors.  Jim Hefferon committed Jun 14, 2012 227 %  Jim Hefferon committed Dec 05, 2011 228 229 230 \end{corollary} Note the analogy with the prime factorization of integers.  Jim Hefferon committed Nov 16, 2013 231 In both cases the uniqueness clause is very useful.  Jim Hefferon committed Dec 05, 2011 232 233 234 235 236 237 238 239 240 241 242 243 244  \begin{example} Because of uniqueness we know, without multiplying them out, that $$(x+3)^2(x^2+1)^3$$ does not equal $$(x+3)^4(x^2+x+1)^2$$. \end{example} \begin{example} By uniqueness, if $$c(x)=m(x)\cdot q(x)$$ then where $$c(x)=(x-3)^2(x+2)^3$$ and $$m(x)=(x-3)(x+2)^2$$, we know that $$q(x)=(x-3)(x+2)$$. \end{example}  Jim Hefferon committed Jun 14, 2012 245 %<*ComplexNumbers>  Jim Hefferon committed Dec 05, 2011 246 While $$x^2+1$$ has no real roots and so doesn't factor over the real  Jim Hefferon committed Nov 16, 2013 247 numbers, if we imagine a root\Dash traditionally denoted $$i$$,  Jim Hefferon committed Jan 17, 2012 248 so that $$i^2+1=0$$\Dash then $$x^2+1$$ factors into a product of linears  Jim Hefferon committed Dec 05, 2011 249 $$(x-i)(x+i)$$.  Jim Hefferon committed Nov 18, 2013 250 When we adjoin this root $$i$$ to the reals and close the new system with  Jim Hefferon committed Nov 20, 2013 251 respect to addition and multiplication  Jim Hefferon committed Nov 18, 2013 252 then we have the  Jim Hefferon committed Nov 16, 2013 253 complex numbers\index{complex numbers}  Jim Hefferon committed Nov 26, 2014 254 $$\C=\set{a+bi\suchthat \text{a,b\in\R and i^2=-1}}$$.  Jim Hefferon committed Nov 20, 2013 255 256 257 (These are often pictured on a plane with $a$ plotted on the horizontal axis and $b$ on the vertical; note that the distance of the point from the origin is $|a+bi|=\sqrt{a^2+b^2}$.)  Jim Hefferon committed Dec 05, 2011 258   Jim Hefferon committed Nov 16, 2013 259 260 In $$\C$$ all quadratics factor. That is, in contrast with the reals, $\C$ has no irreducible quadratics.  Jim Hefferon committed Jun 14, 2012 261 %  Jim Hefferon committed Dec 05, 2011 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 %Any quadratic polynomial factors over the complex numbers. \begin{equation*} ax^2+bx+c= a\cdot \big(x-\frac{-b+\sqrt{b^2-4ac}}{2a}\big) \cdot \big(x-\frac{-b-\sqrt{b^2-4ac}}{2a}\big) \end{equation*} \begin{example} The second degree polynomial $$x^2+x+1$$ factors over the complex numbers into the product of two first degree polynomials. \begin{equation*} \big(x-\frac{-1+\sqrt{-3}}{2}\big) \big(x-\frac{-1-\sqrt{-3}}{2}\big) = \big(x-(-\frac{1}{2}+\frac{\sqrt{3}}{2}i)\big) \big(x-(-\frac{1}{2}-\frac{\sqrt{3}}{2}i)\big) \end{equation*} \end{example}  Jim Hefferon committed Nov 27, 2013 281 \begin{theorem}[Fundamental Theorem of Algebra] \label{th:FundThmAlg}\index{Fundamental Theorem!of Algebra}  Jim Hefferon committed Dec 05, 2011 282 \hspace*{0em plus2em}  Jim Hefferon committed Jun 14, 2012 283 %<*th:FundThmAlg>  Jim Hefferon committed Dec 05, 2011 284 285 286 Polynomials with complex coefficients factor into linear polynomials with complex coefficients. The factorization is unique.  Jim Hefferon committed Jun 14, 2012 287 %  Jim Hefferon committed Jan 23, 2012 288 \end{theorem}  Jim Hefferon committed Dec 05, 2011 289 290 291 292 293 294 295 296 297 298 299 300  \subsection{Complex Representations}  Jim Hefferon committed Jun 14, 2012 301 %<*ComplexOperations>  Jim Hefferon committed Dec 05, 2011 302 303 304 305 306 307 308 309 310 Recall the definitions of the complex number addition \begin{equation*} (a+bi)\,+\,(c+di)=(a+c)+(b+d)i \end{equation*} and multiplication. \begin{align*} (a+bi)(c+di) &=ac+adi+bci+bd(-1) \\ &=(ac-bd)+(ad+bc)i \end{align*}  Jim Hefferon committed Jun 14, 2012 311 %  Jim Hefferon committed Dec 05, 2011 312 313 314 315 316 317 318  \begin{example} For instance, $$(1-2i)\,+\,(5+4i)=6+2i$$ and $$(2-3i)(4-0.5i)=6.5-13i$$. \end{example}  Jim Hefferon committed Nov 16, 2013 319 320 321 322 With these rules, all of the operations that we've used for real vector spaces carry over unchanged to vector spaces with complex scalars.  Jim Hefferon committed Dec 05, 2011 323 324 325 326 327  \begin{example} Matrix multiplication is the same, although the scalar arithmetic involves more bookkeeping. \begin{multline*}  Jim Hefferon committed Jan 17, 2012 328  \begin{mat}  Jim Hefferon committed Dec 05, 2011 329 330  1+1i &2-0i \\ i &-2+3i  Jim Hefferon committed Jan 17, 2012 331 332  \end{mat} \begin{mat}  Jim Hefferon committed Dec 05, 2011 333 334  1+0i &1-0i \\ 3i &-i  Jim Hefferon committed Jan 17, 2012 335  \end{mat} \\  Jim Hefferon committed Dec 05, 2011 336  \begin{aligned}  Jim Hefferon committed Jan 17, 2012 337  &=\begin{mat}  Jim Hefferon committed Dec 05, 2011 338 339  (1+1i)\cdot(1+0i)+(2-0i)\cdot(3i) &(1+1i)\cdot(1-0i)+(2-0i)\cdot(-i) \\ (i)\cdot(1+0i)+(-2+3i)\cdot(3i) &(i)\cdot(1-0i)+(-2+3i)\cdot(-i)  Jim Hefferon committed Jan 17, 2012 340 341  \end{mat} \\ &=\begin{mat}  Jim Hefferon committed Dec 05, 2011 342 343  1+7i &1-1i \\ -9-5i &3+3i  Jim Hefferon committed Jan 17, 2012 344  \end{mat}  Jim Hefferon committed Dec 05, 2011 345 346 347 348  \end{aligned} \end{multline*} \end{example}  Jim Hefferon committed Nov 18, 2013 349 We shall carry over unchanged from the previous chapters  Jim Hefferon committed Jun 14, 2012 350 everything that we can.  Jim Hefferon committed Dec 05, 2011 351 352 353 354 355 356 For instance, we shall call this \begin{equation*} \sequence{\colvec{1+0i \\ 0+0i \\ \vdots \\ 0+0i}, \dots, \colvec{0+0i \\ 0+0i \\ \vdots \\ 1+0i}} \end{equation*}  Jim Hefferon committed Nov 27, 2013 357 358 the \definend{standard basis}\index{standard basis}\index{basis!standard}% \index{standard basis!complex number scalars}  Jim Hefferon committed Dec 05, 2011 359 360 for $$\C^n$$ as a vector space over $\C$ and again denote it $$\stdbasis_n$$.  Jim Hefferon committed Dec 11, 2014 361 362 363 Another example is that $\polyspace_n$ will be the vector space of degree~$n$ polynomials with coefficients that are complex.  Jim Hefferon committed Dec 05, 2011 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406  `