% Chapter 4, Section 1 _Linear Algebra_ Jim Hefferon
% http://joshua.smcvt.edu/linearalgebra
% 2001-Jun-12
\chapter{Similarity}
We have shown that for any
homomorphism there are bases $B$ and~$D$ such that the
matrix representing the map has a block partial-identity form.
\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*}
This representation describes the map as sending
\( 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.
Under this representation
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
codomain are the same.
Here we naturally ask for the domain basis and codomain basis to be the same.
That is,
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.
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
representation that is nearly diagonal.
\section{Complex Vector Spaces}
\index{vector space!over complex numbers}
%<*ReasonForShiftToComplexNumbers>
This chapter requires that we factor polynomials.
But many polynomials do not factor over the real numbers;
for instance,
\( x^2+1 \) does not factor into a product of two linear polynomials
with real coefficients;
instead it requires complex numbers $x^2+1=(x-i)(x+i)$.
Consequently in this chapter
we shall use complex numbers for our scalars,
including entries in vectors and matrices.
That is, we shift from studying vector spaces over the real numbers
to vector spaces over the
complex numbers.\index{complex numbers!vector space over}
Any real number is a complex number and
in this chapter most of the examples use
only real numbers but
nonetheless, the critical theorems require that the scalars be complex.
%
So
this first section is a review of complex numbers.
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
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
\cite{Halmos} and \cite{HoffmanKunze}.
\subsectionoptional{Polynomial Factoring and Complex Numbers}
\textit{This subsection is a review only.
For a full development, including proofs,
see \cite{Ebbinghaus}.}
%<*PolynomialReview0>
Consider a polynomial\index{polynomial}
$p(x)=c_nx^n+\dots+c_1x+c_0$ with
leading coefficient\index{polynomial!leading coefficient}
$c_n\neq 0$.
The degree\index{polynomial!degree}\index{degree of a polynomial}
of the polynomial is~$n$.
If $n=0$ then $p$ is a
constant polynomial\index{polynomial!constant}\index{constant polynomial}
$p(x)=c_0$.
Constant polynomials that are not the zero polynomial, $c_0\neq 0$,
have degree zero.
We define the zero polynomial to have degree $-\infty$.
%
\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}
%<*PolynomialReview1>
Just as integers have a division operation\Dash e.g.,
`\( 4 \) goes \( 5 \) times into \( 21 \) with remainder \( 1 \)'\Dash so
do polynomials.
%
\begin{theorem}[Division Theorem for Polynomials] \label{th:EuclidForPolys}
\index{division theorem}\index{polynomial!division theorem}
%<*th:EuclidForPolys>
Let \( p(x) \) be a polynomial.
If \( d(x) \) is a non-zero polynomial then there are \definend{quotient} and
\definend{remainder} polynomials \( q(x) \) and \( r(x) \) such that
\begin{equation*}
p(x)=d(x)\cdot q(x)+r(x)
\end{equation*}
where the degree of \( r(x) \) is strictly less than the degree of \( d(x) \).
%
\end{theorem}
The point of the integer statement
`\( 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.
Similarly, the final clause of the polynomial division statement
is crucial.
\begin{example}
If \( p(x)=2x^3-3x^2+4x \) and \( d(x)=x^2+1 \) then \( q(x)=2x-3 \) and
\( r(x)=2x+3 \).
Note that \( r(x) \) has a lower degree than does \( d(x) \).
\end{example}
\begin{corollary} \label{co:PolyDividedByLinearPolyIsConstant}
%<*co:PolyDividedByLinearPolyIsConstant>
The remainder when \( p(x) \) is divided by \( x-\lambda \) is the constant
polynomial \( r(x)=p(\lambda) \).
%
\end{corollary}
\begin{proof}
%<*pf:PolyDividedByLinearPolyIsConstant>
The remainder must be a constant polynomial
because it is of degree less than the divisor \( x-\lambda \).
To determine the constant, take the theorem's divisor
$d(x)$ to be $x-\lambda$ and
substitute \( \lambda\/ \) for $x$.
%
\end{proof}
%<*PolynomialFactor>
If a divisor \( d(x) \) goes into a dividend \( p(x) \) evenly,
meaning that \( r(x) \) is the zero polynomial,
then \( d(x) \) is a called a factor\index{factor}\index{polynomial!factor}
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 \).
%
\begin{corollary} \label{co:RootOfPolyIsAssocLinearFactor}
%<*co:RootOfPolyIsAssocLinearFactor>
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)$.
%
\end{corollary}
\begin{proof}
%<*pf:RootOfPolyIsAssocLinearFactor>
By the above corollary $p(x)=(x-\lambda)\cdot q(x)+p(\lambda)$.
Since $\lambda$ is a root,
$p(\lambda)=0$ so $x-\lambda$ is a factor.
%
\end{proof}
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
multiplicity\index{multiplicity, of a root}\index{polynomial!multiplicity}
of~$\lambda$.
Finding the roots and factors of a high-degree polynomial can be hard.
But for second-degree polynomials we have the quadratic formula:~the
roots of \( ax^2+bx+c \) are these
\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
with real number coefficients is said to be irreducible over the
reals.\index{irreducible polynomial}\index{polynomial!irreducible}
\begin{theorem} \label{th:CubicsAndHigherFactor}
%<*th:CubicsAndHigherFactor>
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.
%
\end{theorem}
\begin{corollary} \label{co:RealPolysFactorIntoLinearsAndQuads}
%<*co:RealPolysFactorIntoLinearsAndQuads>
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.
%
\end{corollary}
Note the analogy with the prime factorization of integers.
In both cases the uniqueness clause is very useful.
\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}
%<*ComplexNumbers>
While \( x^2+1 \) has no real roots and so doesn't factor over the real
numbers, if we imagine a root\Dash traditionally denoted \( i \),
so that \( i^2+1=0 \)\Dash then \( x^2+1 \) factors into a product of linears
\( (x-i)(x+i) \).
When we adjoin this root \( i \) to the reals and close the new system with
respect to addition and multiplication
then we have the
complex numbers\index{complex numbers}
\( \C=\set{a+bi\suchthat \text{$a,b\in\R$ and $i^2=-1$}} \).
(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}$.)
In \( \C \) all quadratics factor.
That is, in contrast with the reals, $\C$ has no irreducible quadratics.
%
%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}
\begin{theorem}[Fundamental Theorem of Algebra] \label{th:FundThmAlg}\index{Fundamental Theorem!of Algebra}
\hspace*{0em plus2em}
%<*th:FundThmAlg>
Polynomials with complex coefficients factor into linear
polynomials with complex coefficients.
The factorization is unique.
%
\end{theorem}
\subsection{Complex Representations}
%<*ComplexOperations>
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*}
%
\begin{example}
For instance,
\( (1-2i)\,+\,(5+4i)=6+2i \) and
\( (2-3i)(4-0.5i)=6.5-13i \).
\end{example}
With these rules, all of
the operations that we've used
for real vector spaces carry over unchanged to vector spaces with complex
scalars.
\begin{example}
Matrix multiplication is the same, although the scalar arithmetic involves more
bookkeeping.
\begin{multline*}
\begin{mat}
1+1i &2-0i \\
i &-2+3i
\end{mat}
\begin{mat}
1+0i &1-0i \\
3i &-i
\end{mat} \\
\begin{aligned}
&=\begin{mat}
(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)
\end{mat} \\
&=\begin{mat}
1+7i &1-1i \\
-9-5i &3+3i
\end{mat}
\end{aligned}
\end{multline*}
\end{example}
We shall carry over unchanged from the previous chapters
everything that we can.
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*}
the \definend{standard basis}\index{standard basis}\index{basis!standard}%
\index{standard basis!complex number scalars}
for \( \C^n \) as a vector space over $\C$
and again denote it \( \stdbasis_n \).
Another example is that
$\polyspace_n$ will be the vector space of degree~$n$ polynomials with
coefficients that are complex.