jc1.tex 11.8 KB
Newer Older
1
% Chapter 4, Section 1 _Linear Algebra_ Jim Hefferon
Jim Hefferon's avatar
Jim Hefferon committed
2
%  http://joshua.smcvt.edu/linearalgebra
3 4
%  2001-Jun-12
\chapter{Similarity}
Jim Hefferon's avatar
Jim Hefferon committed
5
We have shown that for any 
6
homomorphism there are bases $B$ and~$D$ such that the 
Jim Hefferon's avatar
Jim Hefferon committed
7
matrix representing the map has a block partial-identity form.
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's avatar
Jim Hefferon committed
17
This representation describes the map as sending
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's avatar
Jim Hefferon committed
22
Under this representation 
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's avatar
Jim Hefferon committed
27
codomain are the same.
Jim Hefferon's avatar
Jim Hefferon committed
28 29
Here we naturally ask for the domain basis and codomain basis to be the same.
That is,
Jim Hefferon's avatar
Jim Hefferon committed
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's avatar
Jim Hefferon committed
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
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's avatar
Jim Hefferon committed
51
%<*ReasonForShiftToComplexNumbers>
Jim Hefferon's avatar
Jim Hefferon committed
52 53 54
This chapter requires that we factor polynomials.
But many polynomials do not factor over the real numbers;
for instance,
Jim Hefferon's avatar
Jim Hefferon committed
55
\( x^2+1 \) does not factor into a product of two linear polynomials
56
with real coefficients;
Jim Hefferon's avatar
Jim Hefferon committed
57
instead it requires complex numbers $x^2+1=(x-i)(x+i)$.
58

Jim Hefferon's avatar
Jim Hefferon committed
59
Consequently in this chapter 
Jim Hefferon's avatar
Jim Hefferon committed
60 61
we shall use complex numbers for our scalars,
including entries in vectors and matrices. 
Jim Hefferon's avatar
Jim Hefferon committed
62
That is, we shift from studying vector spaces over the real numbers
Jim Hefferon's avatar
Jim Hefferon committed
63 64
to vector spaces over the 
complex numbers.\index{complex numbers!vector space over}
65
Any real number is a complex number and
Jim Hefferon's avatar
Jim Hefferon committed
66
in this chapter most of the examples use
Jim Hefferon's avatar
Jim Hefferon committed
67 68
only real numbers but
nonetheless, the critical theorems require that the scalars be complex.
Jim Hefferon's avatar
Jim Hefferon committed
69
%</ReasonForShiftToComplexNumbers>
Jim Hefferon's avatar
Jim Hefferon committed
70 71
So
this first section is a review of complex numbers.
72

Jim Hefferon's avatar
Jim Hefferon committed
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's avatar
Jim Hefferon committed
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
81 82 83 84 85 86 87
\cite{Halmos} and \cite{HoffmanKunze}.






Jim Hefferon's avatar
Jim Hefferon committed
88
\subsectionoptional{Polynomial Factoring and Complex Numbers}
Jim Hefferon's avatar
Jim Hefferon committed
89 90 91
\textit{This subsection is a review only. 
  For a full development, including proofs,
  see \cite{Ebbinghaus}.}
92

Jim Hefferon's avatar
Jim Hefferon committed
93
%<*PolynomialReview0>
Jim Hefferon's avatar
Jim Hefferon committed
94
Consider a polynomial\index{polynomial} 
Jim Hefferon's avatar
Jim Hefferon committed
95
$p(x)=c_nx^n+\dots+c_1x+c_0$ with 
Jim Hefferon's avatar
Jim Hefferon committed
96
leading coefficient\index{polynomial!leading coefficient} 
97
$c_n\neq 0$.
Jim Hefferon's avatar
Jim Hefferon committed
98
The degree\index{polynomial!degree}\index{degree of a polynomial}
Jim Hefferon's avatar
Jim Hefferon committed
99
of the polynomial is~$n$.
Jim Hefferon's avatar
Jim Hefferon committed
100
If $n=0$ then $p$ is a 
Jim Hefferon's avatar
Jim Hefferon committed
101 102
constant polynomial\index{polynomial!constant}\index{constant polynomial} 
$p(x)=c_0$. 
Jim Hefferon's avatar
Jim Hefferon committed
103 104
Constant polynomials that are not the zero polynomial, $c_0\neq 0$, 
have degree zero.
Jim Hefferon's avatar
Jim Hefferon committed
105
We define the zero polynomial to have degree $-\infty$.
Jim Hefferon's avatar
Jim Hefferon committed
106
%</PolynomialReview0>
Jim Hefferon's avatar
Jim Hefferon committed
107

Jim Hefferon's avatar
Jim Hefferon committed
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's avatar
Jim Hefferon committed
115
%<*PolynomialReview1>
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's avatar
Jim Hefferon committed
119
%</PolynomialReview1>
120

Jim Hefferon's avatar
Jim Hefferon committed
121
\begin{theorem}[Division Theorem for Polynomials] \label{th:EuclidForPolys}
Jim Hefferon's avatar
Jim Hefferon committed
122
\index{division theorem}\index{polynomial!division theorem}
Jim Hefferon's avatar
Jim Hefferon committed
123
%<*th:EuclidForPolys>
Jim Hefferon's avatar
Jim Hefferon committed
124 125
Let \( p(x) \) be a polynomial.
If \( d(x) \) is a non-zero polynomial then there are \definend{quotient} and
126 127
\definend{remainder} polynomials \( q(x) \) and \( r(x) \) such that
\begin{equation*}
Jim Hefferon's avatar
Jim Hefferon committed
128
  p(x)=d(x)\cdot q(x)+r(x)
129
\end{equation*}
Jim Hefferon's avatar
Jim Hefferon committed
130
where the degree of \( r(x) \) is strictly less than the degree of \( d(x) \).
Jim Hefferon's avatar
Jim Hefferon committed
131
%</th:EuclidForPolys>
132 133
\end{theorem}

Jim Hefferon's avatar
Jim Hefferon committed
134
The point of the integer statement
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's avatar
Jim Hefferon committed
138 139
Similarly, the final clause of the polynomial division statement
is crucial.
140 141

\begin{example}
Jim Hefferon's avatar
Jim Hefferon committed
142
If \( p(x)=2x^3-3x^2+4x \) and \( d(x)=x^2+1 \) then \( q(x)=2x-3 \) and
143
\( r(x)=2x+3 \).
Jim Hefferon's avatar
Jim Hefferon committed
144
Note that \( r(x) \) has a lower degree than does \( d(x) \).
145 146
\end{example}

Jim Hefferon's avatar
Jim Hefferon committed
147 148
\begin{corollary} \label{co:PolyDividedByLinearPolyIsConstant}
%<*co:PolyDividedByLinearPolyIsConstant>
Jim Hefferon's avatar
Jim Hefferon committed
149 150
The remainder when \( p(x) \) is divided by \( x-\lambda \) is the constant
polynomial \( r(x)=p(\lambda) \).
Jim Hefferon's avatar
Jim Hefferon committed
151
%</co:PolyDividedByLinearPolyIsConstant>
152 153 154
\end{corollary}

\begin{proof}
Jim Hefferon's avatar
Jim Hefferon committed
155
%<*pf:PolyDividedByLinearPolyIsConstant>
156
The remainder must be a constant polynomial
Jim Hefferon's avatar
Jim Hefferon committed
157
because it is of degree less than the divisor \( x-\lambda \).
Jim Hefferon's avatar
Jim Hefferon committed
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's avatar
Jim Hefferon committed
161
%</pf:PolyDividedByLinearPolyIsConstant>
162 163
\end{proof}

Jim Hefferon's avatar
Jim Hefferon committed
164
%<*PolynomialFactor>
Jim Hefferon's avatar
Jim Hefferon committed
165
If a divisor \( d(x) \) goes into a dividend \( p(x) \) evenly,
166
meaning that \( r(x) \) is the zero polynomial,
Jim Hefferon's avatar
Jim Hefferon committed
167
then \( d(x) \) is a called a factor\index{factor}\index{polynomial!factor} 
Jim Hefferon's avatar
Jim Hefferon committed
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's avatar
Jim Hefferon committed
173
%</PolynomialFactor>
174

Jim Hefferon's avatar
Jim Hefferon committed
175 176
\begin{corollary}  \label{co:RootOfPolyIsAssocLinearFactor}
%<*co:RootOfPolyIsAssocLinearFactor>
Jim Hefferon's avatar
Jim Hefferon committed
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's avatar
Jim Hefferon committed
180
%</co:RootOfPolyIsAssocLinearFactor>
181 182
\end{corollary}

Jim Hefferon's avatar
Jim Hefferon committed
183
\begin{proof}
Jim Hefferon's avatar
Jim Hefferon committed
184
%<*pf:RootOfPolyIsAssocLinearFactor>
Jim Hefferon's avatar
Jim Hefferon committed
185
By the above corollary $p(x)=(x-\lambda)\cdot q(x)+p(\lambda)$.
Jim Hefferon's avatar
Jim Hefferon committed
186
Since $\lambda$ is a root, 
Jim Hefferon's avatar
Jim Hefferon committed
187
$p(\lambda)=0$ so $x-\lambda$ is a factor.  
Jim Hefferon's avatar
Jim Hefferon committed
188
%</pf:RootOfPolyIsAssocLinearFactor>
Jim Hefferon's avatar
Jim Hefferon committed
189 190
\end{proof}

Jim Hefferon's avatar
Jim Hefferon committed
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's avatar
Jim Hefferon committed
195
multiplicity\index{multiplicity, of a root}\index{polynomial!multiplicity} 
Jim Hefferon's avatar
Jim Hefferon committed
196 197
of~$\lambda$.

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's avatar
Jim Hefferon committed
200
roots of \( ax^2+bx+c \) are these
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's avatar
Jim Hefferon committed
209
with real number coefficients is said to be irreducible over the 
Jim Hefferon's avatar
Jim Hefferon committed
210
reals.\index{irreducible polynomial}\index{polynomial!irreducible}
211

Jim Hefferon's avatar
Jim Hefferon committed
212 213
\begin{theorem}  \label{th:CubicsAndHigherFactor}
%<*th:CubicsAndHigherFactor>
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's avatar
Jim Hefferon committed
218
%</th:CubicsAndHigherFactor>
219 220
\end{theorem}

Jim Hefferon's avatar
Jim Hefferon committed
221 222
\begin{corollary}  \label{co:RealPolysFactorIntoLinearsAndQuads}
%<*co:RealPolysFactorIntoLinearsAndQuads>
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's avatar
Jim Hefferon committed
227
%</co:RealPolysFactorIntoLinearsAndQuads>
228 229 230
\end{corollary}

Note the analogy with the prime factorization of integers.
Jim Hefferon's avatar
Jim Hefferon committed
231
In both cases the uniqueness clause is very useful.
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's avatar
Jim Hefferon committed
245
%<*ComplexNumbers>
246
While \( x^2+1 \) has no real roots and so doesn't factor over the real
Jim Hefferon's avatar
Jim Hefferon committed
247
numbers, if we imagine a root\Dash traditionally denoted \( i \), 
Jim Hefferon's avatar
Jim Hefferon committed
248
so that \( i^2+1=0 \)\Dash then \( x^2+1 \) factors into a product of linears
249
\( (x-i)(x+i) \).
Jim Hefferon's avatar
Jim Hefferon committed
250
When we adjoin this root \( i \) to the reals and close the new system with
Jim Hefferon's avatar
Jim Hefferon committed
251
respect to addition and multiplication
Jim Hefferon's avatar
Jim Hefferon committed
252
then we have the 
Jim Hefferon's avatar
Jim Hefferon committed
253
complex numbers\index{complex numbers}
254
\( \C=\set{a+bi\suchthat \text{$a,b\in\R$ and $i^2=-1$}} \).
Jim Hefferon's avatar
Jim Hefferon committed
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}$.)
258

Jim Hefferon's avatar
Jim Hefferon committed
259 260
In \( \C \) all quadratics factor. 
That is, in contrast with the reals, $\C$ has no irreducible quadratics.
Jim Hefferon's avatar
Jim Hefferon committed
261
%</ComplexNumbers>
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's avatar
Jim Hefferon committed
281
\begin{theorem}[Fundamental Theorem of Algebra] \label{th:FundThmAlg}\index{Fundamental Theorem!of Algebra}
282
\hspace*{0em plus2em}
Jim Hefferon's avatar
Jim Hefferon committed
283
%<*th:FundThmAlg>
284 285 286
Polynomials with complex coefficients factor into linear
polynomials with complex coefficients.
The factorization is unique.
Jim Hefferon's avatar
Jim Hefferon committed
287
%</th:FundThmAlg>
Jim Hefferon's avatar
Jim Hefferon committed
288
\end{theorem}
289 290 291 292 293 294 295 296 297 298 299 300











\subsection{Complex Representations}
Jim Hefferon's avatar
Jim Hefferon committed
301
%<*ComplexOperations>
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's avatar
Jim Hefferon committed
311
%</ComplexOperations>
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's avatar
Jim Hefferon committed
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.
323 324 325 326 327

\begin{example}
Matrix multiplication is the same, although the scalar arithmetic involves more
bookkeeping.
\begin{multline*}
Jim Hefferon's avatar
Jim Hefferon committed
328
  \begin{mat}
329 330
     1+1i  &2-0i  \\
      i    &-2+3i
Jim Hefferon's avatar
Jim Hefferon committed
331 332
  \end{mat}
  \begin{mat}
333 334
     1+0i  &1-0i  \\
     3i    &-i
Jim Hefferon's avatar
Jim Hefferon committed
335
  \end{mat}             \\
336
 \begin{aligned}
Jim Hefferon's avatar
Jim Hefferon committed
337
  &=\begin{mat}
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's avatar
Jim Hefferon committed
340 341
  \end{mat}                                                  \\
  &=\begin{mat}
342 343
     1+7i  &1-1i  \\
    -9-5i  &3+3i
Jim Hefferon's avatar
Jim Hefferon committed
344
  \end{mat}
345 346 347 348
 \end{aligned}
\end{multline*}
\end{example}

Jim Hefferon's avatar
Jim Hefferon committed
349
We shall carry over unchanged from the previous chapters
Jim Hefferon's avatar
Jim Hefferon committed
350
everything that we can. 
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's avatar
Jim Hefferon committed
357 358
the \definend{standard basis}\index{standard basis}\index{basis!standard}%
\index{standard basis!complex number scalars} 
359 360
for \( \C^n \) as a vector space over $\C$
and again denote it \( \stdbasis_n \).
361 362 363
Another example is that
$\polyspace_n$ will be the vector space of degree~$n$ polynomials with 
coefficients that are complex. 
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