\documentstyle[12pt]{article}

\textwidth6.25in
\textheight8.5in
\oddsidemargin.25in
\topmargin0in

%\renewcommand{\baselinestretch}{2.0}

\def\be{\begin{equation}}
\def\ee{\end{equation}}
%\def\i{\noindent{\bf}
\def\IP{\hbox{\rm I\kern -1.6pt{\rm P}}}
\def\IC{{\hbox{\rm C\kern-.58em{\raise.53ex\hbox{$\scriptscriptstyle|$}}
    \kern-.55em{\raise.53ex\hbox{$\scriptscriptstyle|$}} }}}
\def\IN{\hbox{I\kern-.2em\hbox{N}}}
\def\IR{\hbox{\rm I\kern-.2em\hbox{\rm R}}}
\def\ZZ{\hbox{{\rm Z}\kern-.3em{\rm Z}}}
\def\IT{\hbox{\rm T\kern-.38em{\raise.415ex\hbox{$\scriptstyle|$}} }}

\newtheorem{theorem}{Theorem}[section]
%\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{remark}[theorem]{Remark}

\begin{document}

%\title{Applied Linear Algebra I}
%\author{N. Chernov}
%\nodate
%\maketitle

%\begin{abstract}


\renewcommand{\theequation}{\arabic{section}.\arabic{equation}}

\section{Vector spaces}
\label{sec1}

\noindent {\bf
1.1 Definition (Vector space)}

Let $V$ be a set with a binary operation +, $F$ a field,
and $(c,v)\mapsto cv$ be a mapping from $F\times V$ into $V$.
Then $V$ is called a {\em vector space over} $F$ (or a
{\em linear space over} $F$) if
\begin{tabbing}
$\ \ \ \ $ \= (i) $u+v=v+u
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $
\= for all $u,v\in V$\\
\> (ii) $u+(v+w)=(u+v)+w$ \> for all $u,v,w\in V$\\
\> (iii) $\exists 0\in V:\, v+0=v$ \> for all $v\in V$\\
\> (iv) $\forall u\in V \ \exists -u\in V:\  u+(-u)=0$\\
\> (v) $(ab)v=a(bv)$ \> for all $a,b\in F$ and $v\in V$\\
\> (vi) $(a+b)v=av+bv$ \> for all $a,b\in F$ and $v\in V$\\
\> (vii) $a(u+v)=au+av$ \> for all $a\in F$ and $u,v\in V$\\
\> (viii) $1v=v$ \> for all $v\in V$\\
\end{tabbing}
Note that (i)-(iv) mean that $(V,+)$ is an abelian group.
The mapping $(c,v)\mapsto cv$ is called {\em scalar
multiplication}, the elements of $F$ {\em scalars},
the elements of $V$ {\em vectors}. The vector $0\in V$
is called {\em zero vector} (do not confuse it with 0 in $F$).

In this course we practically study two cases: $F=\IR$ and
$F=\IC$. We call them {\em real vector spaces} and
{\em complex vector spaces}, respectively. \\

\noindent {\bf
1.2 Examples of vector spaces}

a) $F$ field, $F^n=\{(x_1,\ldots,x_n):\, x_i\in F\}$
$n$-tuple space. The operations are defined by
\begin{eqnarray*}
  (x_1,\ldots,x_n)+(y_1,\ldots,y_n)&=&(x_1+y_1,\ldots,x_n+y_n)\\
  c(x_1,\ldots,x_n)&=&(cx_1,\ldots,cx_n)
\end{eqnarray*}
Note that $\IR^2$ and $\IR^3$ can be interpreted as
ordinary plane and space, respectively, in rectangular
coordinate systems.

b) $F$ field, $S$ set, $V=\{f:\, S\to F\}$ (arbitrary
functions from $S$ to $F$). The operations are defined by
\begin{eqnarray*}
  (f+g)(s)&=&f(s)+g(s)\ \ \ \ \ \ {\rm for}\ \  f,g\in V,\ s\in S\\
  (cf)(s)&=&cf(s)\ \ \ \ \ \ \ \ \ \ \ \ {\rm for}\ \  c\in F,\ f\in V,\ s\in S\\
\end{eqnarray*}

c) $C[0,1]$ - the space of continuous functions on $[0,1]$;
$C^r[0,1]$ - the space of functions on $[0,1]$ that have
(at least) $r$ continuous derivatives. The operations
are defined as in (b). Here the closed interval $[0,1]$
may be replaced by any open or closed interval in $\IR$
or the entire real line.

d) $P_n(\IR)$ - the space of all real polynomials of
degree $\leq n$ with real coefficients. Also, $P(\IR)$
the space of all real polynomials (of any degree)
with real coefficients.

e) $F$ field, $F^{m\times n}$ the space of
$m\times n$ matrices with components in $F$.
For $A\in F^{m\times n}$ denote by $A_{ij}$
the component of the matrix $A$
in the $i$th row and the $j$th column, $i\in [1,m]$,
$j\in [1,n]$. Then the operations are defined by
\begin{eqnarray*}
  (A+B)_{ij}&=&A_{ij}+B_{ij}\\
  (cA)_{ij}&=&cA_{ij}
\end{eqnarray*}

\noindent {\bf
1.3 Basic properties of vector spaces}

The following properties follow easily from the definition:
\begin{eqnarray*}
  c0 &=& 0\\
  0v &=& 0\\
  (-1)v &=& -v\\
  cv=0 &\Rightarrow& c=0\ \ {\rm or}\ \ v=0
\end{eqnarray*}

\noindent {\bf
1.4 Definition (Linear combination)}

Let $v_1,\ldots,v_n\in V$ and $c_1,\ldots,c_n\in F$.
Then the vector $c_1v_1+\cdots +c_nv_n$
is called a {\em linear combination} of
$v_1,\ldots,v_n$.\\

\noindent {\bf
1.5 Definition (Subspace)}

A subset of a vector space $V$ which is itself a vector
space with respect to the operations in $V$ is called
a {\em subspace} of $V$. \\

\noindent {\bf
1.6 Theorem (Subspace criterion)}

A non-empty subset $W$ of a vector space $V$ is a subspace
of $V$ if and only if
$$
    au+bv\in W\ \ \ \ {\rm for}\ {\rm all}\ \ a,b\in F,\ u,v\in W
$$

\noindent {\bf
1.7 Examples of subspaces}

a) $C^r[0,1]$ is a subspace of $C[0,1]$ for all $r\geq 1$.

b) $P_n(\IR)$ is a subspace of $P(\IR)$.

c) the space of symmetric $n\times n$ matrices (i.e.
such that $A_{ij}=A_{ji}$) is a subspace of $F^{n\times n}$,
the space of all $n\times n$ matrices.

d) the space of antisymmetric $n\times n$ matrices (i.e. such that
$A){ij}=-A_{ji}$) is a subspace of $F^{n\times n}$, the space of
all $n\times n$ matrices. Note that for any antisymmetric matrix
$A_{ii}=0$, i.e. the main diagonal is zero.

e) $W=\{0\}$ is a trivial subspace in any vector space (it only
contains the zero vector).

f) If $C$ is a collection of subspaces of $V$, then their
intersection $$
   \cap_{W\in C} W
$$
is a subspace of $V$. This is not true for unions. \\

\noindent {\bf
1.8 Definition (Span)}

Let $A$ be a subset of a vector space $V$. Denote by
$C$ the collection of all subspaces of $V$ that contain $A$.
Then the {\em span} of $A$ is the subspace of $V$ defined by
$$
   {\rm span}\, A=\cap_{W\in C} W
$$

\noindent {\bf
1.9 Theorem}

span$\, A$ is the set of all linear combinations
of elements of $A$. \\

\noindent {\bf
1.10 Example}

If $W_1,W_2\subset V$ are subspaces, then
$$
   {\rm span}\, (W_1\cup W_2)=W_1+W_2
$$
where
$$
   W_1+W_2\stackrel{\rm def}{=}\{u+v:\, u\in W_1,\, v\in W_2\}
$$

\noindent {\bf
1.11 Linear independence, linear dependence}

A finite set of vectors $v_1,\ldots,v_n$ is said to be {\em linearly
independent} (loosely, one can say that the vectors
$v_1,\ldots,v_n$ are linearly independent), if
$c_1v_1+\cdots +c_nv_n=0$ implies $c_1=\cdots =c_n=0$.
In other words, all nontrivial linear combinations are different from zero.
Otherwise, the set $\{v_1,\ldots,v_n\}$ is said to be
linearly dependent.

An infinite set of vectors is said to be linearly
independent if every finite subset of it is
linearly independent. \\

\noindent {\bf
1.12 Examples}

a) in the space $\IR^n$, the vectors
\begin{eqnarray*}
   e_1=(1,0,0,\ldots,0)\\
   e_2=(0,1,0,\ldots,0)\\
     \ldots\\
   e_n=(0,0,0,\ldots,1)
\end{eqnarray*}
are linearly independent.

b) In $P_n(\IR)$, the polynomials $1,x,x^2,\ldots,x^n$ are
linearly independent. In $P(\IR)$, the infinite collection of
polynomials $\{x^i\}$, $0\leq i<\infty$, is linearly independent.

c) If the set of vectors contains a zero vector, it is linearly
dependent.

d) In $\IR^2$ (=the ordinary $xy$ plane), two vectors are linearly
dependent iff they are collinear (parallel). Any three or more
vectors in $\IR^2$ are linearly dependent.

e) In $\IR^3$ (=the ordinary space) three vectors are linearly
dependent iff they are coplanar (belong in one plane). Any four or
more vectors are linearly dependent.\\

\newpage

\noindent {\bf 1.13 Theorem}

(a) If a set $S$ of vectors is linearly dependent, then some
vector $v\in S$ is a linear combination of other vectors
$v_1,\ldots,v_m\in S$, i.e. $v=c_1v_1+\cdots +c_mv_m$ and $v\neq
v_i$ for $1\leq i\leq m$. In that case span$\, S=\,$span$\,
S\setminus\{v\}$.

(b) Let $V\neq\{0\}$.
If a finite subset $S\subset V$ of vectors spans $V$, then
there is a linearly independent subset $S'\subset S$ that also
spans $V$. \\


\noindent {\bf 1.14 Basis}

A {\em basis} of $V$ is a linearly independent set $B\subset V$
which spans the entire $V$, i.e. span$\, B=V$. The space $V$ is
said to be finite dimensional if it has a finite basis. \\

\noindent {\bf 1.15 Examples}

a) The vectors $\{e_1,\ldots,e_n\}$ make a basis is $\IR^n$.

b) The polynomials $1,x,\ldots,x^n$ make a basis in $P_n(\IR)$.
The infinite collection of polynomials $\{x^i\}_{i=0}^{\infty}$
make a basis in $P(\IR)$. \\

\noindent {\bf 1.16 Theorem}

Let $V$ be spanned by $u_1,\ldots,u_m$, and let
$v_1,\ldots,v_n$ be linearly independent in $V$.
Then $n\leq m$. \\

\noindent {\bf 1.17 Corollary}

If $\{u_1,\ldots,u_m\}$ and $\{v_1,\ldots,v_n\}$ are two bases
of $V$, then $m=n$. \\

\noindent {\bf 1.18 Definition (Dimension)}

The dimension of a finite-dimensional vector space
$V$ is the number of vectors in any basis of $V$.
It is denoted by dim$\, V$.

The trivial vector space $\{0\}$, the one consisting of a
single zero vector, has no bases, and we define
dim$\{0\}=0$. \\

\noindent {\bf 1.19 Examples}

a) dim$\, F^n=n$

b) dim$\, P_n(\IR)=n+1$

c) dim$\, F^{m\times n}=mn$

d) $P(\IR)$ is not a finite-dimensional space

e) Let $A\in \IR^{m\times n}$, $S=\{X\in \IR^{n\times 1}:\ AX=0\}$
(the solution space of $AX=0$), and $R$ is the row echelon matrix
equivalent to $A$. Then dim$\, S= n-r$, where $r$ is the number of
non-zero rows of $R$. \\

\noindent {\bf 1.20 Theorem}

Let $S$ be a linearly independent subset of $V$.
Suppose that $u\in V$ is not contained in span$\, S$.
Then the set $S\cup \{u\}$ is linearly independent. \\

\noindent {\bf 1.21 Theorem}

Let $V$ be finite dimensional, $W\subset V$ a subspace,
and $S$ a linearly independent subset of $W$. Then
$S$ can be extended to a finite basis of $W$. \\

\noindent {\bf 1.22 Corollary}

Let $V$ be a finite dimensional vector space.

a) If $W$ is a subspace of $V$, then dim$\, W\leq$dim$\, V$,
in particular $W$ is finite dimensional.

b) If $W$ is a proper subspace of $V$, then dim$\, W<\,$dim$\, V$.

c) Every nonempty linearly independent subset of $V$
is a part of a basis of $V$. \\

\noindent {\bf 1.23 Theorem}

Let $W_1$ and $W_2$ be finite dimensional subspaces of $V$.
Then
$$
  {\rm dim}\, W_1+{\rm dim}\, W_2 =
  {\rm dim}\, (W_1\cap W_2)+{\rm dim}\, (W_1+W_2)
$$
In particular, $W_1+W_2$ is finite dimensional. \\

\noindent {\bf 1.24 Lemma}

If $\{u_1,\ldots,u_n\}$ is a basis for $V$, then
for any $v\in V$ there exist unique scalars
$c_1,\ldots,c_n$ such that
$$
   v=c_1u_1+\cdots +c_nu_n
$$

\noindent {\bf 1.25 Definition (Coordinates)}

Let $B=\{u_1,\ldots,u_n\}$ be an ordered basis of $V$.
If $v=c_1u_1+\cdots +c_nu_n$, then $(c_1,\ldots,c_n)$
are the {\em coordinates} of the vector $v$ with respect
to the basis $B$. Notation:
$$
   (v)_B=\left (\begin{array}{c} c_1\\ \vdots \\ c_n\end{array}\right )
$$
is the coordinate (row) vector of $v$ relative $B$. \\

\noindent {\bf 1.26 Examples}

a) The canonical coordinates of a vector $v=(x_1,\ldots,x_n)\in F^n$
in the standard (canonical) basis $\{e_1,\ldots,e_n\}$ are
its components $x_1,\ldots,x_n$, since $v=x_1e_1+\cdots +x_ne_n$.

b) The coordinates of a polynomial $p\in P_n(\IR)$ given by
$$
    p=a_0+a_1x+a_2x^2+\cdots +a_nx^n
$$ in the basis $\{1,x,\ldots,x^n\}$ are its coefficients
$a_0,a_1,\ldots,a_n$.  \\

\noindent {\bf 1.27 Coordinate mapping}

Let dim$\, V=n$ and $B=\{u_1,\ldots,u_n\}$ be an ordered
basis of $V$. Then the mapping
$$
    M_B:\ V\to F^n\ \ \ \ {\rm given}\ {\rm by}\ \ v\mapsto (v)_B
$$
is a bijection. For any $u,v\in V$ and $c\in F$ we have
\begin{eqnarray*}
    M_B(u+v)&=&M_B(u)+M_B(v)\\
    M_B(cv)&=&cM_B(v)
\end{eqnarray*}
\\

\noindent
Note: The mapping $M_B:\, V\to F^n$ not only is a bijection,
but also preserves the vector operations. Since there is
nothing else defined in $V$, we have a complete identity
of $V$ and $F^n$. Any property of $V$ can be proven by
first substituting $F^n$ for $V$ and then using the
mapping $M_B$. \\

\noindent {\bf 1.28 Theorem (Change of coordinates)}

Let $B=\{u_1,\ldots,u_n\}$ and $B'=\{u_1',\ldots,u_n'\}$
be two ordered bases of $V$. Denote by $P_{B',B}$ the
$n\times n$ matrix with $j$th column given by
$$
     (P_{B',B})_j=(u_j')_B
$$
for $j=1,\ldots,n$. Then the matrix $P_{B',B}$ is invertible with
$P_{B',B}^{-1}=P_{B,B'}$ and
$$
    (v)_B=P_{B',B}(v)_{B'}
$$
for every $v\in V$.\\

\noindent {\bf 1.29 Definition (Row space, row rank)}

Let $A\in F^{m\times n}$. Denote by $v_i=(A_{i1},\ldots,A_{in})
\in F^n$ the $i$th row vector of $A$. Then the subspace
span$\{v_1,\ldots,v_m\}$ of $F^n$
is called the {\em row space} of $A$, and dim(span$\{v_1,\ldots,v_m\})$
is called the {\em row rank} of $A$. \\

\noindent {\bf 1.30 Theorem}

Row equivalent matrices have the same row space. \\

\noindent Note: Theorem 1.30 has a converse: if two matrices have
the same row space, then they are row equivalent (a proof may be
found in textbooks). We will not need this fact. \\

\noindent {\bf 1.31 Theorem}

If $R$ is a row echelon matrix, then the non-zero
row vectors of $R$ make a basis of the row space of $R$. \\

\noindent Note: Every matrix is row equivalent to a row echelon
matrix. Thus, Theorems 1.30 and 1.31 show how to find a basis of
span$\{v_1,\ldots,v_m\}$ for a given set of vectors
$v_1,\ldots,v_m\in F^n$. In particular, this gives the dimension
of that subspace. \\

\noindent {\bf 1.32 Definition (Independent subspaces, direct
sums)}

Let $W_1,\ldots,W_k$ be subspaces of a vector space $V$.
We say that they are independent if, whenever
$w_1\in W_1,\ldots,w_k\in W_k$ with $w_1+\cdots +w_k=0$,
then $w_1=\cdots =w_k=0$.

In this case, the sum $W_1+\cdots+W_k$ is called
a {\em direct sum} and denoted by $W_1\oplus\cdots\oplus W_k$.

If $k=2$ and $W_1\oplus W_2=V$, then the subspaces
$W_1$ and $W_2$ are called {\em complementary subspaces}
of $V$. \\

\noindent
Note: For every $w\in W_1\oplus\cdots\oplus W_k$
there exists a unique collection of vectors $w_i\in W_i$, $1\leq i\leq k$,
such that $w=w_1+\cdots +w_k$. \\

\noindent {\bf 1.33 Theorem}

Let $V$ be finite dimensional. Let $W_1,\ldots,W_k$
be subspaces of $V$. Then the following are equivalent:

(i) $W_1,\ldots,W_k$ are independent.

(ii) $W_i\cap(W_1+\cdots +W_{i-1}+W_{i+1}+\cdots +W_k)=\{0\}$
for every $i=1,\ldots,k$.

(iii) If $B_i$ is a basis of $W_i$, then $B_1\cup\cdots\cup B_k$
is a basis of $W_1+\cdots +W_k$. \\

\noindent Note: If $k=2$, then $W_1$ and $W_2$ are independent if
and only if $W_1\cap W_2=\{0\}$.\\

\noindent {\bf 1.34 Examples}

a) Three lines in the ordinary space are independent if they do
not belong in one plane. A plane and a line are independent if the
line does not lie in the plane. Two planes are always dependent.

b) Let $V=C[0,1]$. Let $W_1=\{f\in V:\, \int_0^1 f(x)\, dx=0\}$
and $W_2=\{f\in V:\, f\equiv{\rm const}\}$. Then $V=W_1\oplus
W_2$.

\newpage

\section{Linear transformation}

\noindent
{\bf 2.1 Definition (Linear transformation)}

Let $V$ and $W$ be vector spaces over a field $F$.
A {\it linear transformation} from $V$ to $W$
is a mapping $T:\, V\to W$ such that

(i) $T(u+v)=Tu+Tv$ for all $u,v\in V$;

(ii) $T(cu)=c\, Tu$ for all $u\in V$, $c\in F$.\\

\noindent
Note: if $V=W$ then $T$ is often called a {\it linear operator} on $V$. \\

\noindent
{\bf 2.2 Elementary properties}

$T(0)=0$, $T(-u)=-Tu$, $T(\sum c_iu_i)=\sum c_iTu_i$,

Im$\, T=\{Tu:\, u\in V\}$ is a subspace of $W$ (also denoted by $R(T)$),

Ker$\, T=\{u\in V:\, Tu=0\}$ is a subspace of $V$ (also denoted by $N(T)$),

$T$ is injective (one-to-one) if and only if Ker$\, T=\{0\}$.\\

\noindent
{\bf 2.3 Examples}

(a) A matrix $A\in F^{m\times n}$ defines a linear transformation
$T: F^n\to F^m$ by $Tu=Au$ (multiplication). We denote this
transformation by $T_A$.

Conversely, one has: if $T:\, F^n\to F^m$ is a linear
transformation, then there is a matrix $A\in F^{m\times n}$ such
that $T=T_A$.

(b) $T:\, C^1(0,1)\to C(0,1)$ defined by $Tf=f'$, where $f'$ is
the derivative of the function $f$.

(c) $T:\, P_n(\IR)\to P_{n-1}(\IR)$ defined by $Tf=f'$, as above.

(d) $T:\, C[0,1]\to\IR$ defined by $Tf=\int_0^1f(x)\, dx$.\\

\noindent {\bf 2.4 Theorem}

Let $V$ and $W$ be vector spaces, where $V$ is finite dimensional
with basis $\{u_1,\ldots,u_n\}$. Let $\{v_1,\ldots,v_n\}$ be a
subset of $W$. Then there exists a unique linear transformation
$T:\, V\to W$ such that $Tu_i=v_i$ for all $1\leq i\leq n$.\\

\noindent {\bf 2.5 Definition (Rank, nullity)}

Let $T:\, V\to W$ be a linear transformation. Then
\begin{eqnarray*}
  {\rm rank}(T):&=&{\rm dim}\,{\rm Im}(T)\ \ \ \ {\rm if}\ {\rm
  Im}(T)\ {\rm is}\ {\rm finite}\ {\rm dimensional}\\
  {\rm nullity}(T):&=&{\rm dim}\,{\rm Ker}(T)\ \ \ \ {\rm if}\ {\rm
  Ker}(T)\ {\rm is}\ {\rm finite}\ {\rm dimensional}
\end{eqnarray*}

\noindent{\bf 2.6 Theorem}

Let $T:\, V\to W$ be a linear transformation, $V$ finite
dimensional. Then $${\rm rank}(T)\, +\, {\rm nullity}(T)=\, {\rm
dim}\, V$$

\newpage

\noindent{\bf 2.7 Definition (Column rank)}

Let $A\in F^{m\times n}$, then the {\em column rank} of $A$ is the
dimension of the column space of $A$ as a subspace of $F^m$.\\

\noindent{\bf 2.8 Theorem + Definition (Rank of a matrix)}

Let $A\in F^{m\times n}$. Then $${\rm row}\ {\rm rank}(A)\, =\,
{\rm column}\ {\rm rank}(A)\, =:\,{\rm rank}(A)$$

\noindent{\bf 2.9 Notation}

Let $V$ and $W$ be vector spaces over $F$. The set of all linear
transformations from $V$ to $W$ is denoted by $L(V,W)$.

$L(V,W)$ is a vector space (over $F$), with ordinary addition and
multiplication by scalars defined for functions (from $V$ to $W$). \\

\noindent{\bf 2.10 Theorem}

If dim$\, V=n$ and dim$\, W=m$, then dim$\, L(V,W)=mn$, in
particular, $L(V,W)$ is finite dimensional. \\

\noindent{\bf 2.11 Theorem}

Let $V,W,Z$ be vector spaces over $F$. For any $T\in L(V,W)$ and
$U\in L(W,Z)$ the composition $U\circ T$, also denoted by $UT$, is a linear
transformation from $V$ to $Z$, i.e. $UT\in L(V,Z)$.\\

\noindent{\bf 2.12 Example}

Let $A\in F^{m\times n}$, $B\in F^{k\times m}$ and $T_A$, $T_B$ be
defined as in example 2.3(a). Then the composition $T_BT_A$ is a
linear transformation from $F^n$ to $F^k$ given by the product
matrix $BA$, i.e. $T_BT_A=T_{BA}$. \\

\noindent{\bf 2.13 Definition (Isomorphism)}

A transformation $T\in L(V,W)$ is called an {\em isomorphism} if
$T$ is bijective. If an isomorphism $T\in L(V,W)$ exists, the
vector spaces $V$ and $W$ are called {\em isomorphic}.

Note: $T\in L(V,W)$ is an isomorphism if and only if there is a
$U\in L(W,V)$ such that $UT=I_V$ (the identity on $V$) and
$TU=I_W$ (the identity on $W$). In other words, $T$ is invertible
and $U=T^{-1}$, the inverse of $T$. Note that $T^{-1}$ is also
an isomorphism. \\

\noindent{\bf 2.14 Theorem}

Let $V$ and $W$ be finite dimensional, and $T\in L(V,W)$.

(i) $T$ is injective (one-to-one) if and only if whenever
$\{u_1,\ldots,u_k\}$ is linearly independent, then
$\{Tu_1,\ldots,Tu_k\}$ is also linearly independent.

(ii) $T$ is surjective (onto, i.e. Im$(T)=W$) if and only if
rank$(T)\, =\, $dim$\, W$

(iii) $T$ is an isomorphism if and only if whenever
$\{u_1,\ldots,u_n\}$ is a basis in $V$, then
$\{Tu_1,\ldots,Tu_n\}$ is a basis in $W$.

(iv) If $T$ is an isomorphism, then dim$\, V\,=\,$dim$\, W$.\\

\noindent{\bf 2.15 Theorem}

Let $V$ and $W$ be finite dimensional, dim$\, V\, =\,$dim$\, W$,
and $T\in L(V,W)$. Then the following are equivalent:

(i) $T$ is an isomorphism

(ii) $T$ is injective (one-to-one)

(iii) $T$ is surjective (onto)\\

\noindent{\bf 2.16 Definition (Automorphism, $GL(V)$)}

An isomorphisms $T\in L(V,V)$ is called an {\em automorphism} of
$V$. The set of all automorphisms of $V$ is denoted by $GL(V)$,
which stands for {\em general linear group}. In the special case $V=F^n$
one sometimes writes $GL(V)=GL(n,F)$.

Note: $GL(V)$ is not a subspace of $L(V,V)$ (it does not contain
zero, for example), but it is a group with respect to composition.
This group is not abelian, i.e. $TU\neq UT$ for some $T,U\in
GL(V)$, unless dim$\, V=1$.\\

\noindent{\bf 2.17 Example}

Let $T:\, P_n(\IR)\to P_n(\IR)$ defined by $Tf(x)=f(x+a)$, where
$a\in\IR$ is a fixed number. Then $T$ is an isomorphism. \\


\noindent{\bf 2.18 Theorem}

If dim$\, V=n$, then $V$ is isomorphic to $F^n$. \\

\noindent{\bf 2.19 Definition (Matrix representation)}

Let dim$\, V=n$ and dim$\, W=m$. Let $B=\{u_1,\ldots,u_n\}$ be a
basis in $V$ and $C=\{v_1,\ldots,v_m\}$ be a basis in $W$. Let
$T\in L(V,W)$. The unique matrix $A$ defined by $$
Tu_j=\sum_{i=1}^mA_{ij}v_i$$ is called the {\em matrix of} $T$
{\em relative to} $B,C$ and denoted by $[T]_{B,C}$.\\

\noindent{\bf 2.20 Theorem}

In the notation of 2.18, for each vector $u\in V$
$$(Tu)_C=[T]_{B,C}\, (u)_B$$

\newpage

\noindent{\bf 2.21 Theorem}

the mapping $T\mapsto [T]_{B,C}$ defines an isomorphisms of
$L(V,W)$ and $F^{m\times n}$.\\

\noindent{\bf 2.22 Theorem}

Let $B,C,D$ be bases in vector spaces $V,W,Z$, respectively. For
any $T\in L(V,W)$ and $U\in L(W,Z)$ we have $$
[ST]_{B,D}=[S]_{C,D}\, [T]_{B,C}$$

\noindent{\bf 2.23 Corollary}

$T\in L(V,W)$ is an isomorphism if and only if $[T]_{B,C}$ is an
invertible matrix. \\

\noindent{\bf 2.24 Corollary}

Let $B=\{u_1,\ldots,u_n\}$ and $B'=\{u_1',\ldots,u_n'\}$ be two bases
in $V$. Then $$ [I]_{B',B}=P_{B',B}$$where $P_{B',B}$ is the
transition matrix defined in 1.28.\\

\noindent{\bf 2.25 Theorem}

Let $V$ and $W$ be finite dimensional, and $T\in L(V,W)$.
Let $B$ and $B'$ be bases in $V$, and $C$ and $C'$ be
bases in $W$. Then
$$
   [T]_{B',C'}=Q\, [T]_{B,C}\, P
$$
where
$$
    P=[I]_{B',B}\ \ \ \ \ {\rm and}\ \ \ \ \ Q=[I]_{C,C'}
$$
Note: in the special case $V=W$, $B=C$ and $B'=C'$ one has
$$
   [T]_{B',B'}=P^{-1}\, [T]_{B,B}\, P
$$
where $P=[I]_{B',B}$. \\

\noindent{\bf 2.26 Definition (Similar matrices)}

Two matrices $A,A'\in F^{n\times n}$ are said to be {\em similar}
if there is an invertible matrix $P\in F^{n\times n}$ such that
$$
    A'=P^{-1}A\, P
$$
The similarity is denoted by $A\sim A'$.\\

\noindent
Note: similarity is an equivalence relation.\\

\noindent{\bf 2.27 Theorem}

Two matrices $A$ and $A'$ are similar if and only if they
are matrix representations of one linear operator. \\

\noindent{\bf 2.28 Theorem}

Let $V$ and $W$ be finite dimensional and $T\in L(V,W)$. Let
$B$ be a basis in $V$ and $C$ a basis in $W$. Then
$$
   {\rm rank}(T)\, =\, {\rm rank}\, [T]_{B,C}
$$

\noindent{\bf 2.29 Corollary}

If $A$ and $A'$ are similar, then rank$(A)\, =\,$rank$(A')$. \\

\noindent{\bf 2.30 Definition (Linear functional, Dual space)}

Let $V$ be a vector space over $F$. Then $V^{\ast}:=L(V,F)$
is called the {\em dual space} of $V$. The elements $f\in V^{\ast}$
are called {\em linear functionals} on $V$ (they are linear
transformations from $V$ to $F$). \\

\noindent{\bf 2.31 Corollary}

$V^{\ast}$ is a vector space. If $V$ is finite dimensional,
then dim$\, V^{\ast}=\, $dim$\, V$. \\

\noindent{\bf 2.32 Examples}

(a) see Example 2.3(d): $T:\, C[0,1]\to\IR$ defined by $Tf=\int_0^1f(x)\, dx$

(b) The trace of a square matrix $A\in F^{n\times n}$ is defined
by tr$\, A=\sum_i A_{ii}$. Then tr:$\, F^{n\times n}\to F$ is
a linear functional

(c) Every linear functional $f$ on $F^n$ is on the form
$$
  f(x_1,\ldots,x_n)=\sum_{i=1}^na_ix_i\ \ \ \ \ {\rm for}\ {\rm some}\ a_i\in F
$$

\noindent{\bf 2.33 Theorem + Definition}

Let $V$ be finite dimensional and $B=\{u_1,\ldots,u_n\}$
be a basis of $V$. Then there is a unique basis
$B^{\ast}=\{f_1,\ldots,f_n\}$ of $V^{\ast}$ such that
$$
    f_i(u_j)=\delta_{ij}
$$
where $\delta_{ij}=1$ if $i=j$ and $0$ if $i\neq j$
(`Kronecker delta symbol').

The basis $B^{\ast}$ is called the {\em dual basis} of $B$. It
has the property that
$$
    f=\sum_{i=1}^n f(u_i)f_i
$$
for all $f\in V^{\ast}$. \\

\noindent
Note: In Example 2.32(c) the dual basis of the standard
basis $B=\{e_1,\ldots,e_n\}$ is given by
$f_i(x_1,\ldots,x_n)=x_i$.

\newpage

\section{Determinants}


\noindent {\bf 3.1 Definition (Permutation, Transposition, Sign)}

A {\em permutation of a set} $S$ is a bijective mapping $\sigma:\,
S\rightarrow S$. If $S=\{1,\ldots,n\}$ we call $\sigma$ a {\em
permutation of degree} $n$ (or {\em permutations of} $n$ {\em
letters}).

Notation: $\sigma=(\sigma(1),\ldots,\sigma(n))$.

$S_{n}$ is the set of all permutations of degree $n$.

A permutation which interchanges two numbers and leaves all the
others fixed is called a {\em transposition}. Notation:
$\tau(j,k)$.

If $\sigma\in S_n$, then the {\em sign} of $\sigma$ is defined as
follows: sg$(\sigma)=1$ if $\sigma$ can be written as a product of
an even number of transpositions, and sg$(\sigma)=-1$ if $\sigma$
can be written as a product of an odd number of transpositions.

Note: The sign of permutation is well-defined, see MA634.\\

\noindent
{\bf 3.2 Definition (Determinant)}

Let $A\in F^{n\times n}$. Then the {\em determinant} of $A$ is $$
\det(A)= \sum_{\sigma\in S_n}{\rm
sg}(\sigma)a_{1\sigma(1)}a_{2\sigma(2)}\cdots a_{n\sigma(n)}. $$

\noindent
Note: every term in this sum contains exactly one element from
each row and exactly one element from each column. \\

\noindent
{\bf 3.3 Examples}

(1) If $A\in F^{2\times 2}$, then det$(A)=a_{11}a_{22}
-a_{12}a_{21}$

(2) Let $A=$diag$(a_{11},\ldots,a_{nn})$ be a diagonal matrix
(i.e., $A$ is the $n\times n$-matrix
with diagonal elements  $a_{11},\ldots,a_{nn}$ and zeros off the
diagonal). Then det$(A)=a_{11}\cdots a_{nn}$.\\

\noindent
{\bf 3.4 Theorem}

Let $A,B,C \in F^{n\times n}$.

a) If $B$ is obtained from $A$ by multiplying one row of $A$ by
$k$,then $$ \det(B)=k\,\det(A)$$

b) If $A$,$B$ and $C$ are identical, except for the $i$-th row,
where $$ c_{ij}=a_{ij}+b_{ij}\ \ \ \  1\leq j\leq n$$ then $$
\det(C)=\det(A)+\det(B)$$ (Note that in general $\det(A+B) \neq
\det(A)+\det(B)$.)

c) If $B$ is obtained from $A$ by interchange of two rows, then $$
\det(B)= -\det(A)$$

d) If $A$ has two equal rows, then $\det(A)=0$.

e) If $B$ is obtained from $A$ by adding a multiple of one row to
another row, then $$ \det(B)=\det(A) $$

\noindent
{\bf 3.5 Algorithm}

Let $A\in F^{n\times n}$. By using two elementary row operations
-- row interchange and adding a multiple of one row to another
row -- we can transform $A$ into a row echelon matrix $R$,
whose leading entries in non-zero rows are non-zero numbers
(not necessarily ones). By the above theorem, $\det(A)=(-1)^p\det(R)$,
where $p$ is the number of row interchanges used.

In particular, let $A\in F^{n\times n}$ be invertible. Then
$R$ above will be upper triangular, i.e. $R_{ii}\neq 0$ for
all $1\leq i\leq n$, and $R_{ij}=0$ for all $i>j$. By performing
some more row operations one can trandform $R$ into a diagonal
matrix $D={\rm diag}(d_1,\ldots,d_n)$ with non-zero diagonal
entries $d_i\neq 0$. \\

\noindent
{\bf 3.6 Theorem}

$A\in F^{n\times n}$ is invertible if and only if $\det(A)\neq
0$.\\

\noindent
{\bf 3.7 Lemma}

Let $A,B\in F^{n\times n}$ and $A$ invertible. Then $$ \det(AB)
=\det(A)\,\det(B) $$

\noindent
{\bf 3.8 Theorem}

Let $A,B\in F^{n\times n}$, then $$ \det(AB) = \det(A)\,\det(B)$$


\noindent
{\bf 3.9 Corollary}

(i)  If $A\in F^{n\times n}$ is invertible, then $\det\, A^{-1} =
1/\det(A)$.

(ii) If $A$ and $B$ are similar, then $\det(A) = \det(B)$.\\


\noindent {\bf 3.10 Theorem + Definition (Transpose)}

The {\em transpose} $A^{t}$ of $A\in
F^{n\times n}$ is defined by $A^{t}_{ij}:= A_{ji}$. Then $$
\det(A) = \det(A^{t})$$ Note: This implies that all parts of
Theorem 3.4 are valid with ``row" replaced by ``column".\\


\noindent {\bf 3.11 Theorem}

If $A_{11}\in F^{r\times r}$, $A_{21}\in F^{(n-r)\times r}$, and
$A_{22}\in F^{(n-r)\times (n-r)}$, then
$$\det\left(\begin{array}{cc}A_{11} & 0\\ A_{21} &
A_{22}\end{array}\right )= \det(A_{11})\,\det(A_{22})$$ Note: By
induction it follows that $$\det\left (\begin{array}{cccc} A_{11}
& 0 & \cdots & 0 \\ \vdots & \ddots & \ddots & \vdots \\ \vdots &
\ddots & \ddots & 0 \\ A_{m1} & \cdots & \cdots & A_{mm}
\end{array}\right ) = \det (A_{11})\cdots \det(A_{mm})$$
In particular, for a {\em lower triangular} matrix one has
$$\det\left (\begin{array}{cccc} a_{11} & 0 & \cdots & 0 \\ \vdots
& \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & 0 \\
a_{n1} & \cdots & \cdots & a_{nn}
\end{array}\right ) = a_{11}\cdots a_{nn}$$
By Theorem 3.10 this also holds for {\em upper triangular}
matrices.\\


\noindent {\bf 3.12 Definition (Cofactors)}

Let $A\in F^{n\times n}$ and $i,j\in \{1,\ldots,n\}$. Denote by
$A(i|j)\in F^{(n-1)\times (n-1)}$ the matrix obtained by deleting
the $i$-th row and $j$-th column from $A$. Then $$c_{ij} :=
(-1)^{i+j}\det(A(i|j))$$ is called the $i,j$-{\em cofactor} of
$A$.\\


\noindent {\bf 3.13 Theorem (Cofactor expansion)}

(a) For every $i\in\{1,\ldots,n\}$ one has the $i$-th {\em row
cofactor expansion} $$ \det(A) = \sum_{j=1}^n a_{ij}c_{ij}$$

(b) For every $j\in\{1,\ldots,n\}$ one has the $j$-th {\em column
cofactor expansion} $$ \det(A) = \sum_{i=1}^n  a_{ij}c_{ij}$$


\noindent
{\bf 3.14 Theorem}

If $A$ is invertible, then $$ A^{-1}= \frac{1}{\det(A)}{\rm
adj}(A)$$ where adj$(A)\in F^{n\times n}$ is the {\em adjoint
matrix} of $A$ defined by $$ ({\rm adj}(A))_{ij} = c_{ji}$$

\newpage

\noindent {\bf 3.15 Theorem (Cramer's rule)}

If $A\in F^{n\times n}$ is invertible and $b\in F^{n}$, then the
unique solution $x\in F^{n}$ of the equation $Ax = b$ is given by
$$ x_{j} = \frac{\det(B_{j})}{\det(A)}\ \ \ \ \ j=1,\ldots,n$$
where $B_{j}$ is the matrix obtained by replacing the $j$-th
column of $A$ by the vector $b$.\\

\noindent
Note: Using adj$(A)$ to compute $A^{-1}$ or Cramer's rule to solve
the equation $Ax = b$ is numerically impractical, since the
computation of determinants is ``too expensive" compared to other
methods. However, 3.12 and 3.13 have theoretical value: they show
the continuous dependence of entries of $A^{-1}$ on entries of $A$
and, respectively, of $x$ on the entries of $A$ and $b$.\\

\noindent
{\bf 3.16 Definition}

A matrix $A\in F^{n\times n}$ is said to be {\em upper triangular}
if $A_{ij}=0$ for all $i>j$. If, in addition, $A_{ii}=1$ for all
$1\leq i\leq n$, the matrix $A$ is said to be {\em unit upper
triangular}. Similarly, lower triangular matrices and unit
lower triangular matrices are defined.\\

\noindent
{\bf 3.17 Theorem}

The above four classes of matrices are closed under
multiplication. For example, if $A,B\in F^{n\times n}$
are unit lower triangular matrices, then so is $AB$. \\

\noindent
{\bf 3.18 Theorem}

The above four classes of matrices are closed under
taking inverse. For example, if $A\in F^{n\times n}$
is unit lower triangular matrices, then so is $A^{-1}$. \\

\newpage

\section{The LU Decomposition Method}

\noindent{\bf 4.1 Algorithm (Gauss Elimination)}

Let ${A} = (a_{ij})$ be an $n\times n$ matrix with $a_{11} \ne 0$.
Denote $A^{(1)}=A$ and $a_{ij}^{(1)}=a_{ij}$. We define multipliers
$$
     m_{i1} = a^{(1)}_{i1}/a^{(1)}_{11}\ \ \ \  {\rm for}\ \ i=2,\ldots,n
$$
and replace the $i$-th row $R_i$ of the matrix $A$ with
$R_i - m_{i1}R_1$ for all $i=2,\ldots,n$. This creates zeros in
the first column of ${A}^{(1)}$, which then takes the form
$$
{A}^{(2)} =
\left(
\begin{array}{cccc}
a_{11}^{(1)}&\cdots&&a_{1n}^{(1)}\\
0&a_{22}^{(2)}&\cdots&a_{2n}^{(2)}\\
\vdots&\vdots&&\vdots\\
0&a_{n2}^{(2)}&\cdots&a_{nn}^{(2)}
\end{array}
\right)
$$
where
$$
a_{ij}^{(2)} = a_{ij}^{(1)}-m_{i1} a_{1j}^{(1)}\ \ \ \
{\rm for} \ \  2\le i,j \le n
$$
Next, assume that $a_{22}^{(2)} \ne 0$.
Then one can continue this process and define
multipliers
$$
   m_{i2} = a_{i2}^{(2)}/a_{22}^{(2)}\ \ \ \ {\rm for}\ \ i=3,\ldots,n
$$
and replace the $i$-th row
$R_i$ of the matrix $A^{(2)}$ with $R_i - m_{i2}R_2$
for all $i=3,\ldots,n$. This creates a matrix, ${A}^{(3)}$,
with zeros in the second column below the main diagonal, and so on.
If all the numbers $a_{ii}^{(i)}$, $1\le i \le n-1$, are not zero, then one
ultimately obtains an upper triangular matrix
$$
A^{(n)}=U =
\left(
\begin{array}{ccccc}
a_{11}&\cdots&&&a_{1n}\\
0&a_{22}^{(2)}&\cdots&&a_{2n}^{(2)}\\
0&0&a_{33}^{(3)}&\cdots&a_{3n}^{(3)}\\
\vdots&\vdots&&\ddots&\vdots\\
0&0&\cdots&0&a_{nn}^{(n)}
\end{array}
\right)
$$
The elements $a_{ii}^{(i)}$, $1\le i \le n$, are called {\em pivots}; the
method fails if (and only if) one of the pivots
$a_{ii}^{(i)}$, $1\le i \le n-1$,  is zero.\\

\noindent{\bf 4.2 Definition (Principal minors)}

Let $A\in F^{n\times n}$. For $1\le k \le n$,
the $k$-th principal minor of $A$ is the matrix
$k\times k$ formed by intersecting the first $k$ rows and the
first $k$ columns of $A$ (i.e., the top left $k\times k$
block of $A$). We denote the $k$-th principal
minor of $A$ by $A_k$. \\

\newpage

\noindent{\bf 4.3 Criterion of failure in the Gauss elimination process}

The method of Gauss elimination fails if and only if
det$\, A_k=0$ for some $k=1,\ldots,n-1$. This follows
because for each $k=1,\ldots, n$
$$
    \det A_k=a^{(1)}_{11}\cdots a^{(k)}_{kk}
$$

\noindent{\bf 4.4 Gauss matrices}

Assume that $A\in F^{n\times n}$ has non-singular principal
minors up to the order $n-1$, so that the Gauss elimination works.
For each $j=1,\ldots,n-1$ the Gauss matrix $G_j$ is defined by
$$
{G}_j =
\left(
\begin{array}{cccclcc}
1&0&\cdots&&&&0\\
0&1&&&&&\\
\vdots&0&\ddots&&&&\\
&\vdots&&1&&&\\
&&&-m_{j+1,j}&\ddots&&\vdots\\
&&&\vdots&&1&0\\
0&0&&-m_{nj}&&0&1
\end{array}
\right)
$$
Note that $G_j = I - m^{(j)} e_j^t$ where
$$
m^{(j)} =
\left(
\begin{array}{c}
0\\
\vdots \\
0\\
m_{j+1,j}\\
\vdots \\
m_{nj}
\end{array}
\right)
$$

\noindent{\bf 4.5 Lemma}

For each $j=1,\ldots,n-1$ we have
${G}_j {A}^{(j)} = {A}^{(j+1)}$. \\

\noindent{\bf 4.6 Corollary}

We have
$$
U=A^{(n)}={G}_{n-1} \cdots {G}_2 {G}_1 {A}
$$

\noindent{\bf 4.7 Lemma}

For each $j=1,\ldots,n-1$ we have
$$
L_j:={G}^{-1}_j =I + m^{(j)} e_j^t
$$
so that
$$
L_j=
\left(
\begin{array}{cccclcc}
1&0&\cdots&&&&0\\ 0&1&&&&&\\ \vdots&0&\ddots&&&&\\ &\vdots&&1&&&\\
&&&m_{j+1,j}&\ddots&&\vdots\\ &&&\vdots&&1&0\\ 0&0&&m_{nj}&&0&1
\end{array}
\right)
$$

\noindent{\bf 4.8 Lemma}

We have
$$
L: = (I+m^{(1)} e_1^t)(I+m^{(2)} e_2^t) \cdots
                (I+m^{(n-1)} e_{n-1}^t)
= I + \sum_{k=1}^{n-1} m^{(k)} e_k^t $$ so that $$ L = \left(
\begin{array}{ccccl}
1&0&\cdots&&0\\
m_{21}&1&0&\cdots&0\\
\vdots&\ddots&\ddots&&\\
&&&1&0\\
m_{n1}&m_{n2}&\cdots&m_{n,n-1}&1
\end{array}
\right) ,
$$
is a unit lower triangular matrix. \\

\noindent{\bf 4.9 Corollary}

Assume that $A\in F^{n\times n}$ has non-singular principal
minors up to the order $n-1$, so that the Gauss elimination works.
Then
$$
   A=LU
$$
i.e. $A$ is the product of a unit lower triangular
matrix and an upper triangular matrix. In that case
$$
   \det A=\det U=a^{(1)}_{11}\cdots a^{(n)}_{nn}
$$

\noindent{\bf 4.10 Theorem (LU Decomposition)}

Assume that $A\in F^{n\times n}$ has non-singular principal
minors up to the order $n-1$, so that the Gauss elimination works.
Then there exists a factorization for $A$ of the form
$A=LU$, where $U$ is upper triangular and $L$ is unit lower
triangular. If in addition, $A$ is non-singular, then such
a factorization is unique.\\

\noindent
{\em Proof}. It remains to prove uniqueness.
By way of contradiction, let $A=\tilde{L} \tilde{U} = L U$.
As $A$ is non-singular, it follows that $\tilde{U}$ is also
non-singular, and hence
${L}^{-1} \tilde{L} = U\tilde{U}^{-1}$.
Now, ${L}^{-1}$ is  unit lower triangular, so that
${L}^{-1} \tilde{L}$ is also unit lower triangular. On the
other hand, $U\tilde{U}^{-1}$ is upper triangular.
The only matrix with this property is the
identity matrix $I$, and thus $\tilde{L} = L$ and $\tilde{U}=U$.
\\

\noindent{\bf 4.11 Algorithm (Forward and backward substitution)}

Assume that $A\in F^{n\times n}$ is nonsingular and is
decomposed as $A=LU$, where $L$ is lower triangular and
$U$ upper triangular. To solve a system $A x = b $,
one writes it as $LUx=b$, calls $Ux=y$,
then solves the lower triangular system $Ly = b $ for $y$
using ``forward substitution'' (finding $y_1,\ldots,y_n$
subsequently), then solves the system $Ux=y$ for $x$
via a ``back substitution'' (finding $x_n,\ldots,x_1$
subsequently). \\

\noindent
{\bf 4.12 Cost of computation}

The cost of computation is usually measured in ``flops'', where
a flop ({\em fl}oating point {\em op}eration) is
a multiplication or division together with one  addition or subtraction.
(There is also a different definition of ``flop'' in the literature,
but we use this one.) Let us estimate the cost of the
LU decomposition.
The cost of arithmetic in computation of $A^{(2)}$
is $n-1$ divisions to compute the
multipliers and $n(n-1)$ flops ($n-1$ rows with $n$ flops per row)
to make the zeros in the first column, i.e. total of
approximately $n^2$ flops. The computation of $A^{(3)}$
then takes $(n-1)^2$ flops, and so on.
Thus the total computational cost for the LU factorization is
$$
n^2+(n-1)^2 + \cdots + 2^2 = \frac{n(n+1)(2n+1)}{6} \approx \frac{n^3}{3}
$$
flops.

If one solves a system $Ax=b$, then the LU decomposition
is followed by solving two triangular systems.
The cost to solve one triangular system
is about $n^2/2$ flops. Hence, the total cost is
still $\approx n^3/3$. \\

\noindent
Note that most of the computational expense is incurred in
finding the factors $L$ and $U$. Thus, this method is particularly well
suited to situations in which one is solving systems
$Ax = b$ for more that one vector $b$: each additional
$b$ will require $\approx n^2$ flops. \\

\noindent{\bf 4.13 Algorithm for finding $A^{-1}$}

Assume that $A\in F^{n\times n}$ is non-singular
and has non-singular principal
minors up to the order $n-1$, so that the Gauss elimination works.
One can find the matrix $X=A^{-1}$ by solving the system
$AX=I$ for $X\in F^{n\times n}$,
where $I$ is the identity matrix. This amounts
to solving $n$ systems of linear equations $Ax_k=e_k$,
for $k=1,\ldots,n$, where $x_k$ stands for the $k$-th
column of the matrix $X$. The computational
cost of this procedure is $n^3/3+n\times n^2=4n^3/3$. \\

\noindent
Note that, in principle, one can solve the system
$Ax=b$ by $x=A^{-1}b$, finding $A^{-1}$ as above.
However, this is {\em very} inefficient, it costs
approximately four times more flops than the the
LU decomposition followed by forward and backward
substitutions. \\

\noindent
{\bf 4.14 Definition (Diagonally dominant matrix)}

An $n\times n$ matrix $A = (a_{ij})$ for which we have
$$
|a_{ii}| > \sum_{j \ne i} |a_{ij}|
$$
for all $i$ is said to be {\em strictly row diagonally dominant}. If
$$
|a_{jj}| > \sum_{i \ne j} |a_{ij}|
$$
for all $j$ the matrix is said to be {\em strictly column diagonally dominant}.
\\

\noindent{\bf 4.15 Theorem}

If a matrix $A$ is strictly row (or column)
diagonally dominant, then det$\, A_k\neq 0$
for all $1\leq k\leq n$. Hence, no
zero pivots will be encountered during
Gaussian elimination. \\
%Furthermore, in the column diagonally dominant case
%Gaussian elimination with no pivoting is equivalent to Gaussian elimination
%with partial pivoting.

\noindent
Note that if $A$ is strictly column diagonally
dominant, then all the multipliers (i.e., the elements of $L_j$)
have absolute value less than one. \\

\noindent
The above theorem give some conditions under which
the Gauss elimination method works. It is easy to find
matrices to which the method does not apply. For example,
if $A=\left (\begin{array}{cc}0 & 1\\ 1 & 0\end{array}\right )$,
then the method fails instantly. (Furthermore, for this $A$
there is no decomposition $A=LU$ with $L$ lower triangular
and $U$ upper triangular.) In practice, however,
due to the effects of round-off error, one rarely
encounters a pivot that is exactly zero. Does this
mean that the Gauss elimination is practically perfect?
By no means. In practice, one can easily encounter
a pivot that is very small, and this is equally
disastrous. You can read \cite[\S 2.7, p.~123]{watkins1991}
carefully to appreciate the phenomenon of {\em swamping}.
One tries to avoid this
type of problem by using an appropriate pivoting strategy.\\

\noindent{\bf 4.16 Algorithm of partial pivoting -- general}

The idea is to avoid small (in absolute value) pivots
by interchanging rows, if necessary. At any stage of
Gauss elimination, one looks for the largest (in
absolute value) element in the pivot column
(at or below the main diagonal). For a non-singular matrix
it cannot happen that all of these numbers are zero.
Then the row containing that element is interchanged
with the current row. Now the largest element is
on the main diagonal. After that the usual elimination
step is performed. \\

\noindent
It is important to note that partial pivoting implies that
all the multipliers (i.e., the elements of $L_j$)
have absolute value less than or equal to one.\\

\noindent{\bf 4.17 Theorem}

If a matrix $A$ is strictly column
diagonally dominant, then the Gaussian elimination
with no pivoting is equivalent to Gaussian elimination
with partial pivoting (i.e., no row interchanges
are necessary). \\

\noindent{\bf 4.18 Definition (Permutation matrix)}

Let $1\leq i,j\leq n$. The {\em permutation matrix} $E(i,j)$
is obtained from the identity matrix $I$ by interchanging the
$i$-th and $j$-th rows. \\

\noindent{\bf 4.19 Lemma}

Let $A\in F^{n\times n}$. Then the matrix $E(i,j)A$ is obtained
from $A$ by interchanging the rows $i$ and $j$.
Similarly, the matrix $AE(i,j)$ is obtained from $A$ by
interchanging the columns $i$ and $j$.
Also, $E(i,j)^{-1}=E(i,j)$. \\

\noindent{\bf 4.20 Algorithm of partial pivoting -- formalism}

Let us analyze the partial pivoting procedure. At every stage
$j\in [1,n-1]$, we find the row, $r_j$, containing the
largest element in the $j$-th (pivot) column at or below
the main diagonal. Then we interchange the rows $j$ and $r_j$,
note that $r_j\geq j$.
This will be better described by the permutation matrix $E(j,r_j)$,
which we denote for brevity by $E_j$. Hence, we have
$$
   A^{(j+1)}={G}_j E_j{A}^{(j)}
$$
(Note that if we do not interchange rows then simply $r_j=j$ and $E_j=I$,
and we recover our old Gauss elimination procedure.) Therefore,
$$
U=A^{(n)}={G}_{n-1}E_{n-1} \cdots {G}_1 E_1 {A}
$$
By construction, $U$ is an upper triangular matrix.
Now, taking inverses gives
$$
A=E_1{L}_{1} \cdots {E}_{n-1} L_{n-1} U
$$
The next question is, what can we say about the matrix
$E_1{L}_{1} \cdots {E}_{n-1} L_{n-1}$?\\

\noindent
{\bf 4.21 Theorem}

Let $A\in F^{n\times n}$ be non-singular. Then we can apply
the partial pivoting algorithm. Also, let
$$
  P=E_{n-1}\cdots E_{1}
$$
Then the matrix
$$
\tilde{L}:=P^{-1}E_1{L}_{1} \cdots {E}_{n-1} L_{n-1}
$$
is unit lower triangular, and so we have
$$
   PA=\tilde{L}U
$$

\noindent
{\em Proof}. First, observe that for any $m > j$ the
matrix $E_m L_j E_m$ is obtained from the (old) Gauss matrix
$L_j$ by interchanging the $m$-th and $r_m$-th
elements in the $j$-th column below the main diagonal.
So, the matrix
$$
\tilde{L}_j= E_{n-1}\cdots E_{j+1} L_j E_{j+1}\cdots E_{n-1}
$$
is obtained from the (old) Gauss matrix
$L_j$ by some permutation of its
elements in the $j$-th (pivot) column below the main diagonal.
In particular, $\tilde{L}_j$ is also unit lower triangular.

Now, in the expression
$$
E_1{L}_{1} \cdots {E}_{n-1} L_{n-1}
$$
we fill in as many $E$'s as necessary (remembering
that $E_i^2=I$) to convert all $L_j$'s into $\tilde{L}_j$'s, and obtain
$$
    PA =\tilde{L}_1\cdots \tilde{L}_{n-2} L_{n-1} U
$$
where
$$
  P=E_{n-1}\cdots E_{1}
$$
is called a permutation matrix. The matrix
$$
  \tilde{L}=\tilde{L}_1\cdots \tilde{L}_{n-2} L_{n-1}
$$
is unit lower triangular, and we get
$$
PA = \tilde{L}U
$$

\noindent{\bf 4.22 Algorithm of partial pivoting -- implementation}

In practice, one wants to solve a system of equations $Ax=b$
with a nonsingular $A$.
Applying the algorithm of partial pivoting gives $PA=\tilde{L}U$.
Therefore, $\tilde{L}Ux=Pb=:c$. Then $x$ can be found by the
standard forward and backward substitution, one only needs to
obtain $c$ from $b$. In computer implementation,
one does not actually interchange values in memory
locations for the elements of $A$ or $b$,
but the row interchanges are recorded
in a special permutation vector $S=(s_1,\ldots,s_n)$.
It holds initially the values $s_1=1, \cdots, s_n=n$.
The interchange of rows 2 and 5, for example, is recorded by interchanging
the integers 2 and 5 in this vector. Thus if one finds the permutation vector
$S$ (which is returned when the LU factorization is completed) then
the components of the vector $c=Pb$
can be retrieved from $b$ via the vector $S$, which is used
as a `pointer'. (see \cite[p.~64]{watkins1991}). The method then
proceeds in the usual manner.\\

\noindent{\bf 4.23 Complete pivoting -- a sketch}

The method of {\em complete pivoting} involves both row
and column interchanges to make use of the largest pivot
available. By a  similar argument to that used above this is
equivalent to effecting the factorization
$$
PAQ = LU ,
$$
where
$P$ and $Q$ are permutation matrices. This method, which provides
additional insurance against round-off error buildup is useful if
the method of partial pivoting proves to be unstable. The
main disadvantage of the method is that it is expensive in that an
extra $n^3/3$ comparisons are required, compared to a cost on the
order of $n^2$ comparisons for the partial pivoting algorithm.

\section{Diagonalization}

Throughout this section, we use the following notation: $V$ is a
finite dimensional vector space, dim$\, V=n$, and $T\in L(V,V)$.
Also, $B$ is a basis in $V$ and $[T]_B:=[T]_{B,B}\in F^{n\times
n}$ is a matrix representing $T$.

Our goal in this and the following sections is to find a basis in
which the matrix $[T]_B$ is ``as simple as possible''. In this
section we study conditions under which the matrix $[T]_B$ can be
made diagonal. \\

\noindent
{\bf 5.1 Definition (Eigenvalue, eigenvector)}

A scalar $\lambda\in F$ is called an {\em eigenvalue}
of $T$ if there is a non-zero vector $v\in V$ such
that
$$
     Tv=\lambda v
$$
In this case, $v$ is called an {\em eigenvector} of $T$
corresponding to the eigenvalue $\lambda$. (Sometimes these are
called {\em characteristic value, characteristic vector}.) \\

\noindent
{\bf 5.2 Theorem + Definition (Eigenspace)}

For every $\lambda\in F$ the set
$$
   E_{\lambda}=\{v\in V:\, Tv=\lambda v\}=\,{\rm Ker}(\lambda I-T)
$$
is a subspace of $V$. If $\lambda$ is an eigenvalue, then
$E_{\lambda}\neq\{0\}$, and it is called the {\em eigenspace}
corresponding to $\lambda$. \\

\noindent
Note that $E_{\lambda}$ always contains 0, even though 0
is never an eigenvector. At the same time, the zero scalar $0\in
F$ may be an eigenvalue. \\

\noindent
{\bf 5.3 Remark}

0 is an eigenvalue $\Leftrightarrow$ Ker$\, T\neq\{0\}$
$\Leftrightarrow$ $T$ is not invertible $\Leftrightarrow$ $[T]_B$
is singular $\Leftrightarrow$ $\det [T]_B=0$ . \\

\noindent
{\bf 5.4 Definition (Eigenvalue of a matrix)}

$\lambda\in F$ is called an {\em eigenvalue} of a matrix
$A\in F^{n\times n}$ if there is a nonzero $v\in F^n$
such that
$$
    Av=\lambda v
$$
{\em Eigenvectors} and {\em eigenspaces} of matrices
are defined accordingly. \\

\noindent
{\bf 5.5 Simple properties}

(a) $\lambda$ is an eigenvalue of $A\in F^{n\times n}$
$\Leftrightarrow$ $\lambda$ is an eigenvalue of $T_A\in L(F^n,F^n)$.

(b) $\lambda$ is an eigenvalue of $T$
$\Leftrightarrow$ $\lambda$ is an eigenvalue of $[T]_B$
for any basis $B$.

(c) if $A={\rm diag}(\lambda_1,\ldots,\lambda_n)$, then
$\lambda_1,\ldots,\lambda_n$ are eigenvalues of $A$
with eigenvectors $e_1,\ldots,e_n$.

(d) dim$\, E_{\lambda}=\,$nullity$(\lambda I-T)=n-\,$rank$(\lambda I-T)$.\\

\noindent
{\bf 5.6 Lemma}

The function $p(x):=\det (xI-[T]_B)$ is a polynomial
of degree $n$. This function is independent of the
basis $B$. \\

\noindent
{\bf 5.7 Definition (Characteristic polynomial)}

The function
$$
   C_T(x):=\det (xI-[T]_B)
$$
is called the {\em characteristic polynomial} of $T$.

For a matrix $A\in F^{n\times n}$, the function
$$
   C_A(x):=\det (xI-A)
$$
is called the {\em characteristic polynomial} of $A$. \\

\noindent
Note that $C_T(x)=C_{[T]_B}(x)$ for any basis $B$. \\

\noindent
{\bf 5.8 Lemma}

$\lambda$ is an eigenvalue of $T$ if and only if $C_T(\lambda)=0$. \\

\noindent
{\bf 5.9 Corollary}

$T$ has at most $n$ eigenvalues. If $V$ is complex ($F=\IC$), then
$T$ has at least one eigenvalue. In this case, according to the
Fundamental Theorem of Algebra, $C_T(x)$ is decomposed into linear
factors. \\

\noindent
{\bf 5.10 Corollary}

If $A\sim B$ are similar matrices, then $C_A(x)\equiv C_B(x)$,
hence $A$ and $B$ have the same set of eigenvalues. \\

\noindent
{\bf 5.11 Examples}

(a) $A=\left (\begin{array}{rr}3 & 2\\-1 & 0\end{array}\right )$.
Then $C_A(x)=x^2-3x+2=(x-1)(x-2)$, so that $\lambda=1,2$.
Also, $E_1=$span$(1,-1)$ and $E_2=$span$(2,-1)$, so that
$E_1\oplus E_2=\IR^2$.

(b) $A=\left (\begin{array}{rr}1 & 1\\0 & 1\end{array}\right )$.
Then $C_A(x)=(x-1)^2$, so that $\lambda=1$ is the only eigenvalue,
$E_1=$span$(1,0)$.

(c) $A=\left (\begin{array}{rr}0 & 1\\-1 & 0\end{array}\right )$.
Then $C_A(x)=x^2+1$, so that there are no eigenvalues in the real
case and two eigenvalues ($i$ and $-i$) in the complex case.

(d) $A=\left (\begin{array}{rrr}3 & 3 & 2\\1 & 2 & 2\\ -1 & -1 & 0
\end{array}\right )$.
Then $C_A(x)=(x-1)(x-2)^2$, so that $\lambda=1,2$.
$E_1=$span$(-1,1,0)$ and $E_2=$span$(2,0,-1)$.
Here $E_1\oplus E_2\neq\IR^3$ (``not enough eigenvectors'').

(e) $A=\left (\begin{array}{rrr}1 & 0 & 0\\0 & 2 & 0\\ 0 & 0 & 2
\end{array}\right )$.
Then $C_A(x)=(x-1)(x-2)^2$, so that $\lambda=1,2$.
$E_1=$span$\{e_1\}$ and $E_2=$span$\{ e_2,e_3\}$.
Now $E_1\oplus E_2=\IR^3$. \\

\noindent
{\bf 5.12 Definition (Diagonalizability)}

$T$ is said to be {\em diagonalizable} if there is a
basis $B$ such that $[T]_B$ is a diagonal matrix.

A matrix $A\in F^{n\times n}$ is said to be
{\em diagonalizable} if there is a similar matrix
$D\sim A$ which is diagonal. \\

\noindent
{\bf 5.13 Lemma}

(i) If $v_1,\ldots,v_k$ are eigenvalues of $T$ corresponding
to distinct eigenvalues $\lambda_1,\ldots,\lambda_k$,
then the set $\{v_1,\ldots,v_n\}$ is linearly independent.

(ii) If $\lambda_1,\ldots,\lambda_k$ are distinct
eigenvalues of $T$, then
$E_{\lambda_1}+\cdots+E_{\lambda_n}=
E_{\lambda_1}\oplus\cdots\oplus E_{\lambda_n}$. \\

\noindent
{\em Proof} of (i) goes by induction on $k$.\\

\noindent
{\bf 5.14 Corollary}

If $T$ has $n$ distinct eigenvalues, then $T$ is
diagonalizable. (The converse is not true.)\\

\noindent
{\bf 5.15 Theorem}

$T$ is diagonalizable if and only if there is a basis $B$
consisting entirely of eigenvectors of $T$. (In this case
we say that $T$ has a complete set of eigenvectors.) \\

\noindent
Not all matrices are diagonalizable, even in the complex
case, see Example 5.11(b). \\

\noindent
{\bf 5.16 Definition (Invariant subspace)}

A subspace $W$ is said to be {\em invariant} under $T$
if $TW\subset W$, i.e. $Tw\in W$ for all $w\in W$.

The {\em restriction} of $T$ to a $T$-invariant subspace $W$
is denoted by $T|_W$. It is a linear transformation of $W$
into itself. \\

\noindent
{\bf 5.17 Examples}

(a) Any eigenspace $E_{\lambda}$ is $T$-invariant.
Note that any basis in $E_{\lambda}$ consists
of eigenvectors.

(b) Let $A=\left (\begin{array}{rrr}0 & -1 & 0\\1 & 0 & 0\\ 0 & 0 & 1
\end{array}\right )$. Then the subspaces $W_1=\,$span$\{e_1,e_2\}$
and $W_2=\,$span$\{e_3\}$ are $T_A$-invariant. The restriction
$T_A|_{W_1}$ is represented by the matrix $\left
(\begin{array}{rr}0 & -1\\1 & 0\end{array}\right )$, and the
restriction $T_A|_{W_2}$ is the identity. \\

\noindent
{\bf 5.18 Lemma}

Let $V=W_1\oplus W_2$, where $W_1$ and $W_2$ are
$T$-invariant subspaces. Let $B_1$ and $B_2$ be
bases in $W_1$, $W_2$, respectively. Denote
$[T|_{W_1}]_{B_1}=A_1$ and $[T|_{W_2}]_{B_2}=A_2$.
Then
$$
   [T]_{B_1\cup B_2}=
\left (\begin{array}{cc} A_1 & 0 \\ 0 & A_2\end{array}\right )
$$
Matrices like this are said to be {\em block-diagonal}. Note: by
induction, this generalizes to $V=W_1\oplus\cdots\oplus W_k$. \\

\noindent
{\bf 5.19 Definition (Algebraic multiplicity, geometric multiplicity)}

Let $\lambda$ be an eigenvalue of $T$. The {\em algebraic
multiplicity} of $\lambda$ is its multiplicity as a root
of $C_T(x)$, i.e. the highest power of $x-\lambda$ that
divides $C_T(x)$. The {\em geometric multiplicity}
of $\lambda$ is the dimension of the eigenspace $E_{\lambda}$.

The same definition goes for eigenvalues of matrices. \\

\noindent
Both algebraic and geometric multiplicities are at least one. \\

\noindent
{\bf 5.20 Theorem}

$T$ is diagonalizable if and only if the sum of
geometric multiplicities of its eigenvalues
equals $n$. In this case, if $\lambda_1,\ldots,
\lambda_s$ are all distinct eigenvalues, then
$$
   V=E_{\lambda_1}\oplus\cdots\oplus E_{\lambda_s}
$$
Furthermore, if $B_1,\ldots,B_s$ are arbitrary bases in
$E_{\lambda_1},\ldots,E_{\lambda_s}$ and
$B=B_1\cup\cdots\cup B_s$, then
$$
   [T]_B=\,{\rm diag}\,(\lambda_1,\ldots,\lambda_1,
   \lambda_2,\ldots,\lambda_2,\ldots,
   \lambda_s,\ldots,\lambda_s)
$$
where each eigenvalue $\lambda_i$ appears $m_i=\dim E_{\lambda_i}$
times. \\

\noindent
{\bf 5.21 Corollary}

Assume that
$$
  C_T(x)=(x-\lambda_1)\cdots (x-\lambda_n)
$$
where $\lambda_i$'s are not necessarily distinct.

(i) If all the eigenvalues have the same algebraic and
geometric multiplicities, then $T$ is diagonalizable.

(ii) If all the eigenvalues are distinct, then $T$
is diagonalizable. \\

\newpage

\noindent
{\bf 5.22 Corollary}

Let $T$ be diagonalizable, and $D_1$, $D_2$ are two diagonal
matrices representing $T$ (in different bases). Then $D_1$ and
$D_2$ have the same the diagonal elements, up to a permutation. \\

\noindent
{\bf 5.23 Examples (continued from 5.11)}

(a) The matrix is diagonalizable, its diagonal
form is $D=\left (\begin{array}{rr}1 & 0\\0 & 2\end{array}\right )$.

(b) The matrix is not diagonalizable.

(c) The matrix is not diagonalizable in the real case,
but is diagonalizable in the complex case. Its
diagonal form is $D=\left (\begin{array}{rr}i & 0\\0 & -i\end{array}\right )$.

(d) The matrix is not diagonalizable.

\newpage

\section{Generalized eigenvectors, Jordan decomposition}

Throughout this and the next sections, we use the following notation:
$V$ is a finite dimensional {\em complex} vector space, dim$\, V=n$,
and $T\in L(V,V)$.
%Also, $B$ is a basis in $V$ and $[T]_B:=[T]_{B,B}\in F^{n\times n}$.

In this and the next sections we focuse on
nondiagonalizable transformations. Those, as
we have seen by examples, do not have `enough
eigenvectors'. \\

\noindent
{\bf 6.1 Definition (Generalized eigenvector, Generalized eigenspace)}

Let $\lambda$ be an eigenvalue of $T$. A vector $v\neq 0$ is
called a {\em generalized eigenvector} of $T$ corresponding
to $\lambda$ if
$$
(T-\lambda I)^{k}v = 0
$$
for some positive integer $k$.

The {\em generalized eigenspace} corresponding to $\lambda$ is
the set of all generalized eigenvectors corresponding to $\lambda$
plus the zero vector. We denote that space by $U_{\lambda}$. \\

\noindent
{\bf 6.2 Example}

Let $A=\left (\begin{array}{rr} \lambda & 1\\ 0 & \lambda\end{array}\right )$
for some $\lambda\in\IC$. Then $\lambda$ is the (only) eigenvalue of $A$,
and $E_{\lambda}=\,{\rm span}\,\{e_1\}$. Since $(A-\lambda I)^2$
is the zero matrix, $U_{\lambda}=\IC^2$. \\

\noindent
{\bf 6.3 Notation}

For each $k\geq 1$, denote $U_{\lambda}^{(k)}=\,{\rm Ker}\, (T-\lambda I)^k$.
Clearly, $U_{\lambda}^{(1)}=E_{\lambda}$ and $U_{\lambda}^{(k)}
\subset U_{\lambda}^{(k+1)}$ (i.e.,
$\{ U_{\lambda}^{(k)}\}$ is an {\em increasing} sequence
of subspaces of $V$). Note that if
$U_{\lambda}^{(k)}\neq U_{\lambda}^{(k+1)}$, then
$\dim U_{\lambda}^{(k)} < \dim U_{\lambda}^{(k+1)}$.

Observe that $U_{\lambda} = \cup^{\infty}_{k=1} U_{\lambda}^{(k)}$.
Since each $U_{\lambda}^{(k)}$ is a subspace of $V$,
their union $U_{\lambda}$ is a subspace, too. \\

\noindent
{\bf 6.4 Lemma}

There is an $m=m_{\lambda}$ such that
$U_{\lambda}^{(k)}\neq U_{\lambda}^{(k+1)}$
for all $1\leq k\leq m-1$, and
$$
   U_{\lambda}^{(m)}=
   U_{\lambda}^{(m+1)}=
   U_{\lambda}^{(m+2)}=\cdots
$$
In other words, the sequence of subspaces $U_{\lambda}^{(k)}$
strictly increases up to $k=m$ and
stabilizes after $k\geq m$.
In particular, $U_{\lambda}=U_{\lambda}^{(m)}$.
\\

\noindent
{\em Proof}.
By way of contradiction, assume that
$$
   U_{\lambda}^{(k)}=
   U_{\lambda}^{(k+1)}\neq
   U_{\lambda}^{(k+2)}
$$
Pick a vector $v\in U_{\lambda}^{(k+2)}\setminus U_{\lambda}^{(k+1)}$
and put $u:=(T-\lambda I)v$.
Then $(T-\lambda I)^{k+2}v=0$, so $(T-\lambda I)^{k+1}u=0$,
hence $u\in U_{\lambda}^{k+1}$. But then
$u\in U_{\lambda}^{k}$, and so
$(T-\lambda I)^{k}u=0$, hence $(T-\lambda I)^{k+1}v=0$,
a contradiction. $\Box$\\

\noindent
{\bf 6.5 Corollary}

$m_{\lambda}\leq n$, where $n = \dim V$.
In particular, $U_{\lambda}=U_{\lambda}^{(n)}$.
\\

\noindent
{\bf 6.6 Definition (Polynomials in $T$)}

By $T^k$ we denote $T\circ\cdots\circ T$ ($k$ times), i.e.
inductively $T^kv=T(T^{k-1}v)$. A polynomial in $T$ is $$a_{k}T^k
+\cdots +a_1 T + a_{0}I$$ where $a_0,\ldots,a_k\in \IC$.
Example: $(T-\lambda I)^k$ is a polynomial in $T$
for any $k\geq 1$.\\

\noindent Note: $T^k\circ T^m=T^m\circ T^k$.
For arbitrary polynomials $p,q$ we have $p(T)q(T)
= q(T)p(T)$.\\

\noindent
{\bf 6.7 Lemma}.

The generalized eigenvectors of $T$ span $V$. \\

\noindent
{\em Proof} goes by induction on $n={\rm dim}V$.
For $n=1$ the lemma follows from 5.9.
Assume that the lemma holds for all vector spaces of dimension $< n$.
Let $\lambda$ be an eigenvalue of $T$.
We claim that $V=V_{1}{\oplus}V_{2}$,
where $V_1 := \,{\rm Ker}\,(T-{\lambda}I)^n=U_{\lambda}$ and
$V_2 := \,{\rm Im}\,(T-{\lambda}I)^n$.

Proof of the claim:\\
(i) Show that $V_1{\cap}V_2 = {0}$.
Let $v {\in} V_1{\cap}V_2$. Then
$(T-{\lambda}I)^{n}v = 0$ and $(T-{\lambda}I)^{n}u = v$ for some
$u {\in}V$. Hence $(T-{\lambda}I)^{2n}u = (T-{\lambda}I)^{n}v=0$,
i.e. $u{\in} U_{\lambda}$. Now 6.5 implies that
$0 = (T-{\lambda}I)^{n}u = v$.\\
(ii) Show that $V=V_{1} + V_{2}$. In view of 2.6
we have ${\rm dim}\, V_{1}+\, {\rm dim}\, V_{2}=\, {\rm dim}\, V$.
Since $V_1$ and $V_2$ are independent by (i),
we have $V_{1} + V_{2} = V$. \\
The claim is proven.

Since, $V_1=U_{\lambda}$, it is already spanned by generalized
eigenvectors. Next,
$V_2$ is $T$-invariant, because for any $v{\in}V_2$
we have $v=(T-{\lambda}I)^{n}u$
for some $u{\in}V$, so $Tv=T(T-{\lambda}I)^{n}U=
(T-{\lambda}I)^{n}Tu{\in} V_2$.
Since dim$\, V_2<n$ (remember that dim$\, V_1\geq 1$),
by the inductive assumption
$V_2$ is spanned by generalized eigenvectors of $T|_{V_2}$,
which are, of course, generalized eigenvectors for $T$.
This proves the lemma.$\Box$\\

\noindent
{\bf 6.8 Lemma}

Generalized eigenvectors corresponding to distinct eigenvalues
of $T$ are linearly independent. \\

\noindent
{\em Proof}.
Let $v_1,{\ldots},v_m$ be generalized eigenvectors
corresponding to distinct eigenvalues ${\lambda}_1,
{\ldots},{\lambda}_m$. We need to show that if
$v_1+{\cdots}+v_{m}=0$, then $v_1=\cdots =v_m=0$.
It is enough to show that $v_1=0$.

Let $k$ be the smallest positive integer
such that $(T-\lambda_1 I)^{k}v_1 = 0$.
We now apply the transformation
$$
 R:=(T-{\lambda}_{1}I)^{k-1}(T-\lambda_2I)^n\cdots(T-{\lambda}_{m}I)^n
$$
to the vector $v_1+\cdots +v_m$
(if $k=1$, then the first factor in $R$ is missing).
Since all the
factors in $R$ commute (as polynomials in $T$),
$R$ kills all the vectors $v_2,\ldots,v_m$,
and we get $Rv_1=0$. Next, we replace $T-\lambda_iI$
by $(T-\lambda_1I)+(\lambda_1-\lambda_i)I$ for all
$i=2,\ldots,m$ in the product formula for $R$.
We then expand this formula by Binominal Theorem.
All the terms but one will contain $(T-\lambda_1I)^r$
with some $r\geq k$, which kills $v_1$,
due to our choice of $k$. The equation $Rv_1=0$
is then equivalent to
$$
(\lambda_1-\lambda_2)^n\cdots (\lambda_1-\lambda_m)^n
(T-{\lambda}_{1}I)^{k-1}v_1=0
$$
This contradicts our choice of $k$ (remember that
the eigenvalues are distinct, so that $\lambda_i\neq\lambda_1$).
$\Box$\\

\noindent
{\bf 6.9 Definition (Nilpotent transformations)}

The transformation $T:V\to V$ is said to be
{\em nilpotent}, if $T^k=0$ for some positive
integer $k$. The same definition goes for matrices. \\

\noindent
{\bf 6.10 Example}

If $A\in \IC^{n\times n}$ is an upper triangular matrix
whose diagonal entries are zero, then it is nilpotent. \\

\noindent
{\bf 6.11 Lemma}

$T$ is nilpotent if and only if $0$ is its only eigenvalue.\\

\noindent
{\em Proof}.
Let $T$ be nilpotent and $\lambda$ be its eigenvalue
with eigenvector $v\neq 0$. Then $T^kv=\lambda^kv$ for
all $k$, and then $T^kv=0$ implies $\lambda^k=0$, so $\lambda=0$.

Conversely, if $0$ is the only eigenvalue, then
by 6.7, $V=U_0=\,$Ker$\, T^n$, so $T^n=0$. $\Box$\\

\noindent
{\bf 6.12 Theorem (Structure Theorem)}

Let ${\lambda}_{1},{\ldots},{\lambda}_{m}$ be all
distinct eigenvalues of $T:V\to V$
with corresponding generalized eigenspaces $U_1,{\ldots},U_m$.
Then\\
(i)   $V=U_1{\oplus}{\cdots}{\oplus}U_m$\\
(ii)  Each $U_j$ is $T$-invariant\\
(iii) $(T-{\lambda}_{j}I)|_{U_j}$ is nilpotent for each $j$\\
(iv)  Each $T|_{U_j}$ has exactly one eigenvalue, ${\lambda}_{j}$\\
(v)   dim$\, U_{j}$ equals the algebraic multiplicity of ${\lambda}_{j}$\\

\noindent
{\em Proof}.
(i)   Follows from 6.7 and 6.8.\\
(ii)  Recall that $U_{j}=\, {\rm Ker}\,(T-{\lambda}_{j}I)^n$  by 6.5.
      Hence, for any $v{\in}U_{j}$ we have
$$
   (T-{\lambda}_{j}I)^{n}Tv \stackrel{{\rm by}\ 6.6}{=}T(T-{\lambda}_{j}I)^{n}v = 0
$$
so that $Tv{\in}U_j$. \\
(iii) Follows from 6.5. \\
(iv)  From 6.11 and (iii),
    $(T-{\lambda}_{j}I)|_{U_j}$ has exactly one
    eigenvalue, 0. Therefore, $T_{U_j}$ has
    exactly one eigenvalue, ${\lambda}_{j}$.
(A general fact: ${\lambda}$ is an eigenvalue
of $T$ if and only if $\lambda-\mu$ is an eigenvalue of $T-{\mu}I$.)\\
(v)   Pick a basis $B_{j}$ in each $U_{j}$,
      then $B:={\cup}^{m}_{j=1} B_{j}$ is a basis of $V$ by (i).
Due to 5.18 and (i), the matrix $[T]_B$ is block-diagonal,
whose diagonal blocks are $[T|_{U_j}]_{B_j}$, $1\leq j\leq m$.
Then
\begin{eqnarray*}
C_T(x) &=& \det(xI-[T]_B)\\
&=& C_{[T|_{U_1}]_{B_1}}(x){\cdots}C_{[T|_{U_m}]_{B_m}}(x)\\
&=& C_{T|_{U_1}}(x){\cdots}C_{T|_{U_m}}(x)
\end{eqnarray*}
due to 3.11. Since $T|_{U_j}$ has the only eigenvalue
$\lambda_j$, we have $C_{T|_{U_j}}(x)=(x-\lambda_j)^{\dim U_j}$, hence
$$
C_T(x) =
(x-\lambda_1)^{\dim U_1}\cdots (x-\lambda_m)^{\dim U_m}
$$
Theorem is proven. $\Box$\\

\noindent
{\bf 6.13 Corollary}

Since $E_{\lambda}\subset U_{\lambda}$, the geometric
multiplicity of $\lambda$ never exceeds its algebraic
multiplicity.\\

\noindent
{\bf 6.14 Definition (Jordan block matrix)}

An $m{\times}m$ matrix $J$ is called a {\em Jordan block matrix} for
the eigenvalue ${\lambda}$ if
$$
J=\left( \begin{array}{cccccc}
\lambda & 1 & 0 & \cdots & 0 & 0\\
0 & \lambda & 1 & 0 & \ddots & 0\\
0 & 0 & \lambda & 1 & \ddots & \vdots\\
\vdots & \ddots & \ddots & \ddots & \ddots & 0\\
\vdots & \ddots & \ddots & 0 & \lambda & 1 \\
0 & \cdots & \cdots & 0 & 0 & \lambda  \end{array} \right)
$$

\noindent
{\bf 6.15 Properties of Jordan block matrices}

\noindent
(i)   $C_J(x)=(x-{\lambda})^m$, hence ${\lambda}$ is the only
      eigenvalue of $J$, its algebraic multiplicity is $m$\\
(ii)  $(J-{\lambda}I)^m=0$, i.e. the matrix
      $J-{\lambda}I$  nilpotent \\
(iii) rank$\, (J-{\lambda}I)=m-1$, hence nullity$\,(J-{\lambda}I)=1$,
      so the geometric multiplicity of ${\lambda}$ is 1.\\
(iv)  $Je_1={\lambda}e_1$, hence $(J-\lambda I)e_1=0$,
      i.e. $E_{\lambda}=\,$span$\{e_1\}$\\
(v)   $Je_k={\lambda}e_k + e_{k-1}$, hence
      $(J-{\lambda}I)e_k=e_{k-1}$ for $2\leq k\leq m$\\
(vi)  $(J-\lambda I)^ke_k=0$ for all $1\leq k\leq m$.\\
Note that the map $J-\lambda I$ takes
$$
    e_m\mapsto e_{m-1}\mapsto\cdots \mapsto e_1\mapsto 0
$$

\noindent
{\bf 6.16 Definition (Jordan chain)}

Let $\lambda$ be an eigenvalue of $T$. A {\em Jordan chain}
is a sequence of non-zero vectors $\{v_1,\ldots,v_m\}$ such that
$(T-\lambda I)v_1=0$ and $(T-\lambda I)v_k=v_{k-1}$
for $k=2,\ldots,m$. The {\em length} of the Jordan
chain is $m$. \\

\noindent
Note that a Jordan chain contains exactly one eigenvector ($v_1$),
and all the other vectors in the chain are generalized eigenvectors. \\

\noindent
{\bf 6.17 Lemma}

Let $\lambda$ be an eigenvalue of $T$. Suppose we have
$s\geq 1$ Jordan chains corresponding to $\lambda$, call them
$\{v_{11},\ldots,v_{1m_1}\}$, $\ldots$,
$\{v_{s1},\ldots,v_{sm_s}\}$. Assume that
the vectors $\{v_{11},v_{21},\ldots,v_{s1}\}$
(the eigenvectors in these chains) are
linearly independent. Then all the vectors
$\{v_{ij}:\ i=1,\ldots,s,\ j=1,\ldots,m_j\}$
are linearly independent.\\

\noindent
{\em Proof}. Let $M=\max\{m_1,\ldots,m_s\}$
be the maximum length of the chains. The proof goes
by induction on $M$. For $M=1$ the claim is trivial.
Assume the lemma is proved for chains of lengths $\leq M-1$.
Without loss of generality, assume
that $m_1\geq m_2\geq\cdots\geq m_s$, i.e. the
lengths are decreasing, so $M=m_1$.

By way of contradiction, let
$$
   \sum_{i,j}c_{ij}v_{ij}=0
$$
Applying $(T-\lambda I)^{m_1-1}$ to the vector
$\sum c_{ij}v_{ij}$ kills all the terms except
the last vectors $v_{im_1}$ in the chains of
maximum length (of length $m_1$). Those vectors
will be transformed to
$(T-\lambda I)^{m_1-1}v_{im_1}=v_{i1}$, so we get
$$
   \sum_{i=1}^pc_{im_1}v_{i1}=0
$$
where $p\leq s$ is the number of chains of length $m_1$.
Since the vectors $\{v_{i1}\}$ are linearly
independent, we conclude that $c_{im_1}=0$ for all $i$.
That reduces the problem to the case of chains of
lengths $\leq M-1$. $\Box$\\

\noindent
{\bf 6.18 Corollary}

Let $B=\{v_1,\ldots,v_m\}$ be a Jordan chain corresponding
to an eigenvalue $\lambda$. Then $B$ is linearly independent, i.e.
it is a basis in the subspace $W:=\,$span$\{v_1,\ldots,v_m\}$. Note that
$W$ is $T$-invariant, and the matrix $[T|_W]_B$ is exactly
a Jordan block matrix. \\

\noindent
{\bf 6.19 Definition (Jordan basis)}

A basis $B$ of $V$ is called a {\em Jordan basis} for $T$ if it
is a union of some Jordan chains. \\

\noindent
{\bf 6.20 Remark}

If $B$ is a Jordan basis of $V$, then $[T]_B$ is a block diagonal
matrix, whose diagonal blocks are Jordan block matrices. \\

\newpage

\noindent
{\bf 6.21 Definition (Jordan matrix)}

A matrix $Q$ is called a {\em Jordan matrix corresponding
to an eigenvalue} $\lambda$ if
$$
  Q=\left (\begin{array}{ccc}J_1 & \cdots & 0\\
     \vdots & \ddots & \vdots\\ 0 & \cdots & J_s
      \end{array}\right )
$$
where $J_1,\ldots,J_s$ are Jordan block matrices corresponding
to $\lambda$, and their lengths decrease: $|J_1|\geq\cdots\geq |J_s|$.

A matrix $A$ is called a {\em Jordan matrix} if
$$
  A=\left (\begin{array}{ccc}Q_1 & \cdots & 0\\\vdots & \ddots & \vdots\\
     0 & \cdots & Q_r  \end{array}\right )
$$
where $Q_1,\ldots,Q_r$ are Jordan matrices corresponding
to distinct eigenvalues $\lambda_1,\ldots,\lambda_r$. \\

\noindent
{\bf 6.22 Example}

Let $T:\IC^4\to\IC^4$ have only one eigenvalue, $\lambda$.
We can find all possible Jordan matrices for $T$; there
are 5 distinct such matrices. \\

\noindent
{\bf 6.23 Theorem (Jordan decomposition)}

Let $V$ be a finite dimensional complex vector space.\\
(i) For any $T:V\to V$ there is a Jordan basis $B$ of $V$,
so that the matrix $[T]_B$ is a Jordan matrix. The latter is
unique, up to a permutation of eigenvalues.\\
(ii) Every matrix $A\in \IC^{n\times n}$ is similar to
a Jordan matrix. The latter is
unique, up to a permutation of eigenvalues
(i.e., $Q_j$'s in 6.21).\\

\noindent
Note: the uniqueness of the matrices $Q_j$ is achieved
by the requirement $|J_1|\geq\cdots\geq |J_s|$ in 6.21. \\

\noindent
Note: the Jordan basis $B$ is not unique, not even after
fixing the order of eigenvalues. \\

\noindent
{\em Proof} of Theorem 6.23. \\
(ii) follows from (i).\\
It is enough to prove (i) assuming that $T$ has just one
eigenvalue $\lambda$, and then use 6.12. We can even assume that
the eigenvalue of $T$ is zero, by switching from $T$ to $T-\lambda I$.
Hence, we assume that $T$ is nilpotent.

The proof of existence goes by induction on $n=\dim V$. The case $n=1$ is
trivial. Assume the theorem is proved for all spaces of
dimension $<n$. Consider $W:=\,{\rm Im}\, V$. If $\dim W=0$,
then $T=0$, so the matrix $[T]_B$ is diagonal (actually, zero)
in any basis. So, assume that $m:=\dim W\geq 1$.

Note that $W$ is $T$-invariant, and $m<n$, because
$n-m=\,$nullity$\, T\neq 0$. So, by the inductive
assumption there is a basis $B$ in $W$ that is the
union of Jordan chains. Let $k$ be the number of
those chains.

The last vector in each Jordan chain has a pre-image
under $T$ (because it belongs in $W=\,$Im$\, T$).
So, we can extend each of those $k$ Jordan chains by
one more vector. Now we get $k$ Jordan chains for
the transformation $T:V\to V$. By 6.17 all the
vectors in those chains are linearly independent,
so they span a subspace of dimension $m+k$.

Next, consider the space $K:=\, {\rm Ker}\, T$.
Note that $K_0:=\,$Ker$\, T|_W$ is a subspace of $K$.
The first vectors in our Jordan chains make a basis
in $K_0$, so $k=\dim K_0=\,$nullity$\, T|_W$. This
basis can be extended to a basis in $K$, and thus
we can get $r:=\dim K-\dim K_0$ new vectors. Note that
$\dim K-\dim K_0=n-m-k$. Hence, the total number of
vectors we found is $n$. The last $r$ vectors are
eigenvectors, so they make $r$ Jordan chains of
length $1$.

Finally, note that all our vectors are independent,
therefore they make a basis in $V$.

To prove the uniqueness, note that for any $k\geq 1$
the number of Jordan chains in the Jordan basis that
have length $\geq k$ equals rank$\,T^{k-1}-\,$rank$\, T^k$,
so it is independent of the basis. This easily proves
the uniqueness. $\Box$\\

\noindent
{\bf 6.24 Strategy to find the Jordan matrix}

Given a matrix $A\in\IC^{n\times n}$ you can
find a similar Jordan matrix $J\sim A$ as
follows. First, find all the eigenvalues.
Then, for every eigenvalue $\lambda$ and
$k\geq 1$ find the number $r_k=\,$rank$\,
(T-\lambda I)^k$. You will get a sequence
$n>r_1>r_2>\cdots >r_p=r_{p+1}=\cdots$
(in view of 6.4). Then $r_{k-1}-r_k$ is
the number of Jordan blocks of length
$\geq k$ corresponding to $\lambda$. \\

\noindent
Example:
$A=\left (\begin{array}{rrr}1 & 0 & 1\\0 & 1 & 1\\ 0 & 0 & 1
\end{array}\right )$. Here $\lambda=1$ is the only
eigenvalue, and $r_1=\,$rank$\, (A-I)=1$. Then $(A-I)^2$
is a zero matrix, so $r_2=0$. Therefore,
$J=\left (\begin{array}{rrr}1 & 1 & 0\\0 & 1 & 0\\ 0 & 0 & 1
\end{array}\right )$.

In addition, we can
find a Jordan basis in this example, i.e. a basis
in which the transformation is represented by a Jordan
matrix. The strategy: pick a vector $v_1\in\,$Im$\,(A-I)$, then
take one of its preimages $v_2\in (A-I)^{-1}v_1$,
and an arbitrary eigenvector $v_3\in\,$Ker$\, (A-I)$
independent of $v_1$. Then $\{v_1,v_2\}$ and $\{v_3\}$
are two Jordan chains making a basis.

\newpage

\section{Minimal Polynomial and Cayley-Hamilton Theorem}

We continue using the notation $V,n,T$ of Section~6.
The statements 7.1--7.4 below hold for any field $F$,
but in the rest of the section 7 we work in the complex field.\\

\noindent
{\bf 7.1 Lemma}

For any $T:V\to V$ there exists a nonzero polynomial $f{\in}P(F)$
such that $f(T)=0$. If we require that the leading coefficient
equal 1 and the degree of the polynomial be minimal, then
such a polynomial is unique. \\

\noindent
{\em Proof}: Recall that $L(V,V)$ is a vector space of
a finite dimension, dim$\,L(V,V)=n^2$. The transformations
$I,T,T^2,{\ldots}$ belong in $L(V,V)$, so there is
a $k\geq 1$ such that $I,T,\ldots,T^k$ are linearly
dependent, i.e. ${\exists}\, c_0,{\ldots},c_k{\in} F$:
$$
   c_0I+c_1T+\cdots +c_{k}T^k=0
$$
and we can assume that $c_k{\neq}0$. Dividing
through by $c_k$ gives $c_k=1$. Lastly, if there
are two distinct polynomials of degree $k$ and with
$c_k=1$ satisfying the above equation, then their
difference is a polynomial $g$ of degree $<k$
such that $g(T)=0$. This proves the uniqueness. $\Box$\\

\noindent {\bf 7.2 Definition (Minimal polynomial)}

The unique polynomial found in Lemma 7.1 is called the {\em
minimal polynomial} $M_T(x)$ of $T:\, V\to V$.
If $A$ is an $n{\times}n$-matrix then the minimal polynomial
of $T_A$ is denoted by $M_A(x)$.\\

\noindent
{\bf 7.3 Examples}

(a) $A=\left (\begin{array}{rr}0 & 1\\0 & 0\end{array}\right )$.
Here $A^2=0$, so that the minimal polynomial is $M_A(x)=x^2$.
(It is easy to check that $cI+A\neq 0$ for any $c$, so
the degree one is not enough.) Compare this to the
characteristic polynomial $C_A(x)=x^2$.

(b) It is an easy exercise to prove $C_A(A)=0$ for any
$2\times 2$ matrix $A$ (over any field $F$). Hence $M_A(x)$
either coincides with $C_A(x)$ or is of degree one. In the
latter case $A-cI=0$ for some $c\in F$, hence $A=cI$,
in which case $C_A(x)=(x-c)^2$ and $M_A(x)=x-c$.

(c) $A=\left (\begin{array}{rrr}2 & 3 & 1\\0 & 2 & 0\\ 0 & 0 & 2
\end{array}\right )$. Here $A-2I$ is an upper triangular
matrix with zero main diagonal, so it is nilpotent, see 6.10.
It is easy to check that $(A-2I)^2=0$, hence the minimal
polynomial is $M_A(x)=(x-2)^2=x^2-4x+4$. Compare this to the
characteristic polynomial $C_A(x)=(x-2)^3$. Note that
$C_A(x)$ is a multiple of $M_A(x)$. \\

\newpage

\noindent
{\bf 7.4  Corollary}

\noindent (i)   Let $B$ be a basis of $V$, then $M_T(x) =
M_{[T]_B}(x)$. \\ (ii)  Similar $n{\times}n$-matrices have the
same minimal polynomial. \\

From now on, $F=\IC$ again. \\

\noindent
{\bf 7.5  Theorem}

Let ${\lambda}_1,{\ldots},{\lambda}_r$ be all distinct eigenvalues
of $T$ and $U_j$ the corresponding generalized eigenspaces. Let
$m_j$ is the maximum size of Jordan blocks corresponding to
the eigenvalue $\lambda_j$. Consider the polynomial
$$
  p(x)=(x-{\lambda}_1)^{m_1}{\cdots}(x-{\lambda}_r)^{m_r}
$$
Then:\\
(i)   deg$\, p{\leq}\,$dim$\, V$\\
(ii) if $f(x)$ is a nonzero polynomial such that $f(T)=0$, then $f$
     is a multiple of $p$\\
(iii) $p(x) = M_{T}(x)$\\

\noindent {\em Note}: $m_j$ is the length of the longest Jordan
chain in $U_j$. Also, $m_j$ is the smallest positive integer s.t.
$(T-{\lambda}_{j}I)^{m_j}v = 0 $ for all $v{\in}U_j$. \\

\noindent {\em Proof}:\\ (i)   Follows from 6.23. \\ (ii)  Let
$f(T)=0$. We will show that $f(x)$ is a multiple of
$(x-{\alpha}_j)^m_j$ for all $j$. Fix a $j$ and write $f(x) =
c(x-c_{1})^{t_1}\cdots(x-c_s)^{t_s}(x-{\lambda}_j)^t$ where
$c_1,{\ldots}c_s$ denote the roots of $f$ other than $\lambda_j$
(if $\lambda_j$ is not a root of $f$, we simply put $t=0$). If
$t<m_j$, then there is a vector $v\in U_j$ such that
$u:=(T-\lambda_jI)^tv\neq 0$. Recall that $U_j$ is $T$-invariant,
so it is $(T-cI)$-invariant for any $c$. Hence, $u\in U_j$.
Furthermore, each transformation $T-c_iI$ leaves $U_j$ invariant,
and is a bijection of $U_j$ because $c_i\neq\lambda_j$. Therefore,
the transformation $c(T-c_{1}I)^{t_1}\cdots(T-c_sI)^{t_s}$ is a
bijection of $U_j$, so it takes $u$ to a nonzero vector $w$. Thus,
$w=f(T)v\neq 0$, hence $f(T)\neq 0$, a contradiction. This proves
(ii). \\ (iii) By (ii), $M_T(x)$ is a multiple of $p(x)$. It
remains to prove that $p(T)=0$, then use 7.1. To prove that
$p(T)=0$, recall that $V=U_1\oplus\cdots\oplus U_r$, and for every
$v\in U_j$ we have $(T-\lambda_jI)^{m_j}v=0$. $\Box$\\

\noindent
{\bf 7.6. Example}

Let $J$ be an $m{\times}m$ Jordan block matrix for eigenvalue
${\lambda}$, see 6.14. Then $U_{\lambda}=\IC^m$ and $(T-\lambda I)^m=0$
(and $m$ is the minimal such power). So, $M_J(x)=(x-\lambda)^m$.
Note that $C_J(x)=M_J(x)$. In general, though, $C_A(x)\neq M_A(x)$. \\

\noindent
{\bf 7.7 Theorem (Cayley-Hamilton)}

The characteristic polynomial
$C_{T}(x)$ is a multiple of
the minimal polynomial $M_{T}(x)$.
In particular, $C_{T}(T)=0$,
i.e. any linear operator satisfies
its own characteristic equation.\\

\noindent
{\em Proof}:
Let
${\lambda}_{1},{\ldots},{\lambda}_r$ be all distinct eigenvalues of $T$,
and $p_1,\ldots,p_r$ their algebraic multiplicities. Then
$C_T(x) = (x-{\lambda}_1)^{p_1}{\cdots}(x-{\lambda}_r)^{p_r}$.
Note that $p_j=\dim U_j\geq m_j$, where $m_j$ is the maximum
size of Jordan blocks corresponding to $\lambda_j$. So,
by 7.5 the minimal polynomial
$M_T(x) = (x-{\lambda}_1)^{m_1}{\cdots}(x-{\lambda}_r)^{m_r}$
divides $C_T(x)$. $\Box$\\

\noindent
{\bf 7.8 Corollary}

\noindent
(i) $C_T(x)$ and $M_T(x)$ have the same linear factors.\\
(ii) $T$ is diagonalizable if and only if $M_T(x)=
(x-\lambda_1)\cdots (x-\lambda_r)$, i.e. $M_T(x)$
has no multiple roots. \\

\noindent
{\bf 7.9 Examples}

(a) $A=\left (\begin{array}{rrr}1 & 0 & 0\\-1 & 0 & 1\\ -1 & -1 & -2
\end{array}\right )$. Here $C_A(x)=(x+1)^2(x-1)$. Therefore,
$M_T(x)$ may be either $(x+1)^2(x-1)$ or $(x+1)(x-1)$.
To find it, it is enough to check if $(A+I)(A-I)=0$,
i.e. if $A^2=I$. This is not true, so $M_T(x)=(x+1)^2(x-1)$.
The Jordan form of the matrix is
$J=\left (\begin{array}{rrr}-1 & 1 & 0\\0 & -1 & 0\\ 0 & 0 & 1
\end{array}\right )$.

(b) Assume that $C_A(x)=(x-2)^4(x-3)^2$ and $M_A(x)=(x-2)^2(x-3)$.
Find all possible Jordan forms of $A$. Answer: there are two
Jordan blocks of length one for $\lambda=3$ and two or three Jordan
blocks of lengths 2+2 or 2+1+1 for $\lambda=2$.

\end{document}
\end
