\documentclass[hidelinks, 16pt]{report}

\usepackage{amssymb,amsmath,amsthm,enumitem}
\usepackage{mathtools}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{color}
%\usepackage{fullpage}

\usepackage{tikz}
\usepackage{tikz-3dplot}
\usetikzlibrary{calc,trees,positioning,arrows,fit,shapes,calc}

\usetikzlibrary{positioning,decorations.pathreplacing,matrix,arrows,calc,shapes,arrows}


\usepackage{multirow,multicol}



\newtheorem{theorem}{Theorem}[chapter]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem*{ZL}{Zorn's Lemma}

\theoremstyle{definition}
\newtheorem*{definition}{Definition}
\newtheorem*{definitions}{Definitions}
\newtheorem*{exs}{Examples}
\newtheorem*{ex}{Example}



\DeclareMathOperator{\CG}{\mathbb{C}G}
\DeclareMathOperator{\C}{\mathbb{C}}
\DeclareMathOperator{\cts}{\mathcal{C}}
\DeclareMathOperator{\Q}{\mathbb{Q}}
\DeclareMathOperator{\R}{\mathbb{R}}
\DeclareMathOperator{\D}{\mathcal{D}}
\DeclareMathOperator{\A}{\mathcal{A}}
\DeclareMathOperator{\F}{\mathbb{F}}
\DeclareMathOperator{\G}{\mathcal{G}}
\DeclareMathOperator{\B}{\mathcal{B}}
\DeclareMathOperator{\J}{\mathcal{J}}
\DeclareMathOperator{\Cc}{\mathcal{C}}
\DeclareMathOperator{\lin}{\mathcal{L}}
\DeclareMathOperator{\poly}{\mathcal{P}}
\DeclareMathOperator{\fcts}{\mathcal{F}}


\newcommand{\myand}{\qquad\mbox{and}\qquad}
\newcommand{\spn}{\operatorname{span}}
\newcommand{\tr}{\operatorname{trace}}
\newcommand{\nul}{\operatorname{null}}
\newcommand{\ran}{\operatorname{ran}}

\newcommand{\makeset}[2]{ \left\{#1\;|\;#2\right\} }
\newcommand{\myvec}[1]{ \left[\begin{array}{c}#1\end{array}\right] }


\newcommand{\todo}[1]{\vspace{2 mm}\par\noindent
   \marginpar{\textsc{ToDo}}\framebox{\begin{minipage}[c]{0.95 \textwidth}
   \tt #1 \end{minipage}}\vspace{2 mm}\par}
   


\begin{document}

\title{Abstract Linear Algebra\\ Math 350}
\author{}
\date{\today}

\maketitle
\tableofcontents
%\vfill


\chapter{An introduction to vector spaces}

Abstract linear algebra is one of the pillars of modern mathematics.  Its theory is used in every branch of mathematics and its applications can be found all around our everyday life.  Without linear algebra, modern conveniences such as the Google search algorithm, iPhones, and microprocessors would not exist.  But what is abstract linear algebra?  It is the study of vectors and functions on vectors from an abstract perspective.  
To explain what we mean by an abstract perspective, let us jump in and review our familiar notion of vectors.  Recall that a \emph{vector} of length $n$ is a $n\times 1$ array
$$\left[
\begin{array}{c}
a_1\\
a_2\\
\vdots\\
a_n
\end{array}
\right],$$
where $a_i$ are real numbers, i.e., $a_i\in\R$.  It is also customary to define 
$$\R^n = \makeset{\left[
\begin{array}{c}
a_1\\
a_2\\
\vdots\\
a_n
\end{array}
\right]}{a_i\in\R},$$
which we can think of as the set where all the vectors of length $n$ live.  Some of the usefulness of vectors stems from our ability to draw them (at least those in $\R^2$ or $\R^3$).  Recall that this is done as follows: 


\begin{center}
\begin{tikzpicture}
\begin{scope}[shift={(0,0)}]
		\node at(-3,.5) {$\left[
\begin{array}{c}
a\\
b
\end{array}
\right]$};
\draw[implies-implies,double equal sign distance] (-2.25,.5) -- (-.75,.5);
        % x-axis
        \draw [thick,->] (-.5, 0) -- (2.5, 0) node[right] {$x$};
        % y-axis
        \draw [thick,->] (0, -.5) -- (0, 1.5) node[above] {$y$};
		\draw [blue,->] (0,0) -- (2,1);
		\draw [dotted] (2,0) --(2,1) node[midway,right] {\tiny $b$};
		\node at (1.2,-.2) {\tiny $a$};	
\end{scope}

\begin{scope}[shift = {(8,0)}]
	\node at(-3,.5) {$\left[
\begin{array}{c}
a\\
b\\
c
\end{array}
\right]$};
\draw[implies-implies,double equal sign distance] (-2.25,.5) -- (-.75,.5);
\end{scope}

\tdplotsetmaincoords{60}{120}
\begin{scope}[shift={(8,0)},
		axis/.style={->,black},
		tdplot_main_coords,
		vector/.style={-stealth,blue,},
		vector guide/.style={dashed,red}]
	
%draw the axes
	\draw[axis] (0,0,0) -- (3,0,0) node[anchor=west]{$x$};
	\draw[axis] (0,0,0) -- (0,3,0) node[anchor=west]{$y$};
	\draw[axis] (0,0,0) -- (0,0,3) node[anchor=west]{$z$};
	
	
	%standard tikz coordinate definition using x, y, z coords
	\coordinate (O) at (0,0,0);
	\coordinate (P) at (1,1,1);
	
	%tikz-3dplot coordinate definition using r, theta, phi coords
	\tdplotsetcoord{P}{3}{40}{45}
	
	%draw a vector from O to P
	\draw[vector] (O) -- (P);
	
	%draw guide lines to components


	\draw[vector guide] (Px) -- (Pxy) node[midway,below, black] {\tiny $b$};
	\draw[vector guide] (Py) -- (Pxy)  node[midway,below, black] {\tiny $a$};
	\draw[vector guide] (Pxy) -- (P) node[midway,right, black] {\tiny $c$};
\end{scope}
\end{tikzpicture}	
\end{center}

Basic algebraic operations on vectors correspond nicely with our picture of vectors.  In particular, if we scale a vector $v$ by a number $s$ then in the picture we either stretch or shrink our arrow.  

\begin{center}
\begin{tikzpicture}
\begin{scope}[shift={(0,0)}]
		\node at(-3,.5) {$s\cdot \left[
\begin{array}{c}
a\\
b
\end{array}
\right]$};
\draw[implies-implies,double equal sign distance] (-2.25,.5) -- (-.75,.5);
        % x-axis
        \draw [thick,->] (-.5, 0) -- (4.5, 0) node[right] {$x$};
        % y-axis
        \draw [thick,->] (0, -.5) -- (0, 2) node[above] {$y$};
		\draw [red,->] (0,0) -- (4,2);		
		\draw [blue,->] (0,0) -- (2,1);

		\draw [dotted] (2,0) --(2,1) node[midway,right] {\tiny $b$};
		\draw [dotted] (4,0) --(4,2) node[midway,right] {\tiny $sb$};
		\node at (1.2,.2) {\tiny $a$};
		\draw [decoration={
        brace,
        mirror, raise = .05cm},decorate] (0,0) -- (4,0);
        \node at (2,-.2) {\tiny $sa$};
\end{scope}
\end{tikzpicture}	
\end{center}


The other familiar thing we can do with vectors is add them.  This corresponds to placing the vectors ``head-to-tail" as shown in the following picture.    


\begin{center}
\begin{tikzpicture}
\begin{scope}[shift={(0,0)}]
		\node at(-4.5,1) {$\left[
\begin{array}{c}
a\\
b
\end{array}
\right] + 
\left[
\begin{array}{c}
c\\
d
\end{array}
\right]$};
\draw[implies-implies,double equal sign distance] (-2.75,1) -- (-1.25,1);
        % x-axis
        \draw [thick,->] (-.5, 0) -- (4.5, 0) node[right] {$x$};
        % y-axis
        \draw [thick,->] (0, -.5) -- (0, 2.5) node[above] {$y$};
		\draw [blue,->] (0,0) -- (3,2);
		\draw [blue,->] (3,2) -- (4,1);
		\draw [blue,->] (0,0) -- (3.95,.95);
		
		\draw (.1, 2) -- (-.1, 2) node[left] {\tiny $b$};
		\draw (3, .1) -- (3, -.1) node[below] {\tiny $a$};
		
		\draw (.1, 1) -- (-.1, 1) node[left] {\tiny $b+d$};
		\draw (4, .1) -- (4, -.1) node[below] {\tiny $a+c$};

		\draw [dotted] (3,2) -- (4,2) node[midway, above] {\tiny $c$};
		\draw [dotted] (4,2) -- (4,1) node[midway, right] {\tiny $d$};

\end{scope}
\end{tikzpicture}	
\end{center}

In summary, our familiar notion of vectors can be captured by the following description.   Vectors of length $n$ live in the set  $\R^n$ that is equipped with two operations.  The first operation takes any pair of vectors $u,v\in \R^n$ and gives us a new vector $u+v\in\R^n$.  The second operation takes any pair $a\in \R$ and $v\in \R^n$ and gives us a new vector $a\cdot v\in \R^n$.  

With this summary in mind we now give a definition which generalizes this familiar notion of a vector.  It will be very helpful to read the following in parallel with the above summary.   

\section{Basic definitions \& preliminaries}
Throughout we let $\F$ represent either the rational numbers $\Q$, the real numbers $\R$ or the complex numbers $\C$.

\begin{definition}
A \textbf{vector space over $\F$} is a set $V$ along with two operation.  The first operation is called \textbf{addition}, denoted $+$, which assigns to each pair $u,v\in V$ an element $u+v\in V$.  The second operation is called \textbf{scalar multiplication} which assigns to each pair $a\in\F$ and $v\in V$ an element $av\in V$.  Moreover, we insist that the following properties hold, where $u,v,w\in V$ and $a,b\in \F$:

\begin{itemize}
\item \textbf{Associativity}
$$u+(v+w) = (u+v)+w \qquad\textrm{and}\qquad a(bv) = (ab)v.$$
\item \textbf{Commutativity of $+$}
$$u+v = v+u.$$

\item \textbf{Distributivity}
$$a(u+v) = au + av \qquad\textrm{and}\qquad (a+b)v = av+ bv$$
\item \textbf{Multiplicative Identity}

The number $1\in \F$ is such that
$$1v = v\qquad\textrm{for all } v\in V.$$
\item \textbf{Additive Identity \& Inverses}

There exists an element $0\in V$, called an \textbf{additive identity} or a \textbf{zero},  with the property that
$$0+v = v\qquad\textrm{for all } v\in V.$$
Moreover, for every $v\in V$ there exists some $u\in V$, called an \textbf{inverse of $v$}, such that $u+v= 0$.
\end{itemize}
\end{definition}


It is common to refer to the elements of $V$ as \textbf{vectors} and the elements of $\F$ as \textbf{scalars}.  Additionally, if $V$ is a vector space over $\R$ we call it a \textbf{real vector space} or an \textbf{$\R$-vector space}.  Likewise, a vector space over $\C$ is called  \textbf{a complex vector space} or a \textbf{$\C$-vector space}. 


Although this definition is intimidating at first, you are more familiar with these ideas than you might think.  In fact, you have been using vector spaces in your previous math courses without even knowing it!  The following examples aim to convince you of this.

\bigskip

\begin{exs}\ \\
	\begin{enumerate}
	
		\item $\R^n$ is a vector space over $\R$ under the usual vector addition and scalar multiplication as discussed in the introduction.  
		\item $\C^n$, the set of column vectors of length $n$ whose entries are complex numbers,  is a a vector space over $\C$. 
		\item $\C^n$ is also a vector space over $\R$ where addition is standard vector addition and scalar multiplication is again the standard operation but in this case we limit our scalars to real numbers only.  This is NOT the same vector space as in the previous example; in fact, it is as different as a line is to a plane! 
		\item Let $\mathcal{P}(\F)$ be the set of all polynomials with coefficients in $\F$.  That is
			$$\mathcal{P}(\F) = \makeset{a_0+a_1x+\cdots + a_nx^n}{n\geq 0, a_0,\ldots,a_n\in \F}.$$  
			Then $\mathcal{P}(\F)$ is a vector space over $\F$.  In this case our ``vectors" are polynomials where addition is the standard addition on polynomials.  For example, if 
			$v = 1+ x+3x^2$ and $u = x+7x^2+x^5$, then 
			$$u + v = (1+ x+3x^2) + (x+7x^2+x^5) = 1+2x+10x^2+x^5.$$
			Scalar multiplication is defined just as you might think.  
			If $v = a_0+a_1x+\cdots + a_nx^n$, then 
			$$s\cdot v = s a_0+s a_1x+\cdots +s a_nx^n.$$
		\item Let $\cts(\R)$ be the set of continuous functions 
		$$f:\R\to \R.$$
		Then $\cts(\R)$ is a vector space over $\R$ where addition and scalar multiplication is given as follows. For any functions $f,g\in \cts(\R)$ we define
		$$(f+g)(x) = f(x) + g(x).$$ Likewise, for scalar multiplication we define
		$$(s\cdot f) (x) = sf(x).$$
		The reader should check that these definitions satisfy the axioms for a vector space. 
		\item Let $\fcts$ be the set of all functions $f:\R\to \R$. Then the set $\fcts$ is a vector space over $\R$ where addition and scalar multiplication are as given in Example 5.  
	\end{enumerate}

\end{exs}
  
  
You might be curious why we use the term ``over" when saying that a vector space $V$ is  \emph{over} $\F$.  The reason for this is due to a useful way to visualize abstract vector spaces.   In particular, we can draw the following picture

\begin{center}
\begin{tikzpicture}
\begin{scope}[shift={(0,0)}]
		\draw (0,0) circle (1cm);
		\node at (1,1) {$V$};
%		\node at (0,0) {$0_V$};
%		\draw[->] (0,0)--(.6,.6) node[left] {$v$};
%		\node[circle,fill,inner sep=1pt, label=below:$0_V$] at (0,0) {};
		\draw[very thick] (-3,-2) -- (3,-2) node[right] {$\F$};
\end{scope}
\end{tikzpicture}	
\end{center}
where our set $V$ is sitting \emph{over} our scalars $\F$.  
%Just like in the familiar $\R^n$ setting, we represent the the zero vector $0_V$ by a point in the center and any nonzero vector $v$ as an arrow originating from the origin.  Consequently, we can still think of scalar multiplication, in the abstract setting, as stretching or shrinking our vectors.  This perspective will continue to be useful as we move forward.  
 
\section{Basic algebraic properties of vector spaces}
There are certain algebraic properties that we take for granted in $\R^n$.  For example, the zero vector  
$$\left[\begin{array}{c}0\\ \vdots\\  0\end{array}\right]\in \R^n$$
is the unique additive identity in $\R^n$.   Likewise, in $\R^n$ we do not even think about the fact that $-v$ is the (unique) additive inverse of $v$.   These algebraic properties are so fundamental that we certainly would like our general vector spaces to have these same properties as well.  As the next several lemmas show, this is happily the case.    

Assume throughout this section that $V$ is a vector space over $\F$.  

\begin{lemma}
$V$ has a unique additive identity. 
\end{lemma}
\begin{proof}
Assume $0$ and $0'$ are both additive identities in $V$. To show $V$ has a unique additive identity we show that $0 = 0'$.  Playing these two identities off each other we see that
$$0' = 0+0' = 0,$$
where the first equality follows as $0$ is an identity and the second follows since $0'$ is also an identity.  
\end{proof}

An immediate corollary of this lemma is that now we can talk about \emph{the} additive identity or \emph{the} zero of a vector space.  To distinguish between zero, the number in $\F$ and the zero the additive identity in $V$ we will often denote the latter as $0_V$.




\begin{lemma}\label{lem:unique_additive_inv}
Every element $v\in V$ has a unique additive inverse denoted ${-v}$.    
\end{lemma}

\begin{proof}
Fix $v\in V$.  As in the proof of the previous lemma, it will suffice to show that if $u$ and $u'$ are both additive inverses of $v$, then $u=u'$.  Now consider
$$u' = 0_V + u' = (u+v)+u' = u+(v+u') = u + 0_V = u,$$
where associativity gives us the third equality.   
\end{proof}


\begin{lemma}[Cancellation Lemma]
If $u,v,w$ are vectors in $V$ such that 
\begin{align*}
u+w = v+w,\tag{*}
\end{align*}
then $u = v$
\end{lemma}
\begin{proof}
To show this, add $-w$ to both sides of (*) to obtain $(u+w) + -w = (v+w) +-w$.
By associativity, 
$$u+(w + -w) =  v+ (w+-w)$$
$$u + 0_V = v+0_V$$
$$u=v.$$	
\end{proof}


\begin{lemma}
For any $a\in \F$ and $v\in V$, we have
$$0\cdot v = 0_V$$
and
$$a\cdot0_V = 0_V.$$ 
\end{lemma}

\begin{proof}
The proof of this is similar to the Cancellation Lemma.  We leave its proof to the reader.   
\end{proof}



The next lemma asserts that  $-1\cdot v = -v$.  A natural reaction to this statement is: Well isn't this obvious, what is there to prove?  Be careful!  Remember $v$ is just an element in an abstract set $V$ endowed with some specific axioms.  From this vantage point, it is not clear that the vector defined by the abstract rule $-1\cdot v$  should necessarily be the additive inverse of $v$.    

\begin{lemma}
${-1}\cdot v = {-v}$.
\end{lemma}


\begin{proof}
    Observe that $-1\cdot v$ is an additive inverse of $v$ since
$$v + {-1}\cdot v = 1\cdot v + -1\cdot v = (1-1)\cdot v = 0 v = 0_V,$$
where the last two equalities follow from the distributive law and the previous lemma respectively.  As $v$ has only one additive inverse by Lemma~\ref{lem:unique_additive_inv}, then  $-1\cdot v = -v$.  
\end{proof}


\section{Subspaces}
\begin{definition}
Let $V$ be a vector space over $\F$.  We say that a subset $U$ of $V$ is a \textbf{subspace} (of $V$), provided that $U$ is a vector space over $\F$ using the same operations of addition and scalar multiplication as given on $V$.
\end{definition}

Showing that a given subset $U$ is a subspace of $V$ might at first appear to involve a lot of checking.  Wouldn't one need to check Associativity, Commutativity, etc?  Fortunately, the answer is no.  Think about it, since these properties hold true for all the vectors in $V$ they certainly also hold true for some of the vectors in $V$, i.e., those in $U$. (The fancy way to say this is that $U$ \textbf{inherits} all these properties from $V$.)   Instead we need only check the following:
\begin{enumerate}
\item $0_V\in U$
\item $u+v\in U,\textrm{ for all } u,v\in U$ (\textbf{Closure under addition})



\item $av \in U,\textrm{ for all } a\in\F,\textrm{ and } v\in U$ (\textbf{Closure under scalar multiplication})


\end{enumerate}

\begin{exs}\ \\
	\begin{enumerate}
		\item For any vector space $V$ over $\F$, the sets $V$ and $\{0_V\}$ are both subspaces of $V$.  The former is called a \textbf{nonproper} subspace while the latter is called the \textbf{trivial} or \textbf{zero} subspace.  Therefore a proper nontrivial subspace of $V$ is one that is neither $V$ nor $\{0_V\}$.
		\item Consider the real vector space $\R^3$.  Fix real numbers $a,b,c$.  Then we claim that the subset
			$$U = \makeset{(x,y,z)\in\R^3}{ax+by+cz=0}$$
		is a subspace of $\R^3$.  	To see this we just need to check the three closure properties.  First, note that $0_{\R^3} = (0,0,0) \in U$, since $0 = a0+b0+c0$.   To see that $U$ is closed under addition let $u=(x_1,y_1,z_1),v=(x_2,y_2,z_2)\in U$.  
		Since 
		$$a(x_1+x_2)+b(y_1+y_2)+c(z_1+z_2) = (ax_1+by_1+cz_1) +(ax_2+by_2+cz_2) = 0+0 =0$$
		we see that $u+v=(x_1+x_2,y_1+y_2,z_1+z_2)\in U$.  Lastly, a similiar check shows that $U$ is closed under scalar multiplication.  Let $s\in\R$, then
		$$0 = s0 = s(ax_1+by_1+cz_1) = asx_1+bsy_1+csz_1.$$
		This means that $su = (sx_1,sy_1,sz_1)\in U$.
		\item\label{ex:poly_subspace}  Recall that $\poly(\R)$ is the vector space over $\R$ consisting of all polynomials whose coefficients are in $\R$.  In fact, this vector space is also a subspace of $\cts(\R)$.  To see this note that $\poly(\R) \subset \cts(\R)$.  Since the zero function and the zero polynomial are the same function, then $0_{\cts(\R)} \in \poly(\R)$.  Since we already showed that $\poly(\R)$ is a vector space then it is certainly closed under addition and scalar multiplication, so $\poly(\R)$ is a subspace of $\cts(\R)$.  
		\item This next examples demonstrates that we can have subspaces within subspaces.  Consider the subset $\poly_{\leq n}(\R)$ of $\poly(\R)$ consisting of all those polynomials with degree $\leq n$.  Then, $\poly_{\leq n}(\R)$ is a subspace of $\poly(\R)$.  As the degree of the zero polynomial is (defined to be) $-\infty$, then $\poly_{\leq n}(\R)$.  Additionally, if $u,v\in \poly_{\leq n}(\R)$, then clearly the degree of $u+v$ is $\leq n$, so $u+v\in \poly_{\leq n}(\R)$.  Likewise $\poly_{\leq n}(\R)$ is certainly closed under scalar multiplication.  Combining this example with the previous one shows that we actually have the following sequence of subspaces
		$$\poly_{\leq 0}(\R) \subset \poly_{\leq 1}(\R)\subset \poly_{\leq 2}(\R)\subset\cdots \subset \poly(\R)\subset\cts(\R).$$
		\item The subset $\mathcal{D}$ of all differentiable functions in $\cts(\R)$, is a subspace of the $\R$-vector space $\cts(\R)$.  Since the zero function $f(x) =0$ is differentiable, and the sum and scalar multiple of differentiable functions is differentiable, it follows that $\mathcal{D}$ is a subspace.  
		\item Let $U$ be the set of solutions to the differential equation $f''(x) = -f'(x)$, i.e.,
		$$U= \makeset{f(x)}{f''(x) = -f'(x)}.$$
		Then $U$ is a subspace $\mathcal{D}$, the space of differentiable functions.  To see this, first note that the zero function is a solution to our differential equation.  Therefore $U$ contains our zero vector.  To check the closure properties let $f,g\in U$.  Therefore $f''(x) = -f'(x)$ and that $g''(x) = -g(x)$ and moreover,
		$$(f+g)''(x) = f''(x)+g''(x) = -f'(x) + -g'(x) = -(f+g)'(x).$$
		In other words, $f+g\in U$.  To check closure under scalar multiplication let $s\in \R$.  Now
		$$(s\cdot f)''(x) = sf''(x) = -sf'(x) = -(sf)'(x),$$
		and so $s\cdot f\in U$.  
	\end{enumerate}
\end{exs}


\chapter{Dimension}

\section{Linear combination}

\begin{definition}
A \textbf{linear combination} of the vectors $v_1,\ldots, v_m$ is any vector of the form 
$$a_1 v_1+\cdots + a_m v_m,$$
where $a_1,\ldots, a_m\in \F$.   For a nonempty subset $S$ of $V$,  we define 
$$\spn(S) = \makeset{a_1 v_1+\cdots + a_m v_m}{v_1,\ldots,v_m\in S, a_1,\ldots, a_m\in \F},$$
and call this set the \textbf{span of $S$}.  If $S=\emptyset$, we define $\spn(\emptyset)=\{0_V\}$.  Lastly, if $\spn(S) = V$, we say that \textbf{$S$ spans $V$} or that $S$ is a \textbf{spanning set} for $V$.
\end{definition}

For example, consider the vector space $\R^n$ and let $S = \{e_1,\ldots, e_n\}$, where 
$$e_i = \left[\begin{array}{c}0\\ \vdots\\  1\\ \vdots\\ 0\end{array}\right],$$
that is, the vector whose entries are all 0 except the $i$th, which is 1.  Then $\R^n =\spn(S)$, since we can express any vector $\left[\begin{array}{c}a_1\\ \vdots\\   a_n\end{array}\right]\in \R$ as 
$$\left[\begin{array}{c}a_1\\ \vdots\\   a_n\end{array}\right]= a_1e_1+\cdots a_ne_n.$$  
The vectors $e_1,\ldots,e_n$ play a fundamental role in the theory of linear algebra.  As such they are named the \textbf{standard basis vectors} for $\R^n$. 

Now consider the vector space of continuous functions $\cts(\R)$.  For brevity let us write the function $f(x) = x^n$ as $x^n$ and let $S=\{1,x,x^2,\ldots\}$.  
	Certainly 
	$$\spn(S) = \makeset{a_0 1 +a_1x+a_2x^2+\cdots + a_n x^n}{n\geq 0, a_0,\ldots, a_n\in \R} = \poly(\R).$$
	This example raises a subtle point we wish to make explicit.  Although our set $S$ has \emph{infinite} cardinality, each element in $\spn(S)$ is a linear combination of a \emph{finite} number of vectors in $S$.  We do not allow something like $1+x+x^2+\cdots$ to be an element in $\spn(S)$.  A good reason for this restriction is that, in this case, such an expression is not defined for $|x| \geq 1$, so it could not possibly be an element of $\cts(\R)$.  
	
	Example~\ref{ex:poly_subspace} in Section 1.3 shows that $\poly(\R)$ is a subspace of $\cts(\R)$.  The next lemma provides an alternate way to see this fact where we take $S = \{1,x,x^2,\ldots\}$ and $V =\cts(\R)$.  Its proof is left to the reader.  

\begin{lemma}\label{lem:span_is_space}
For any $S\subseteq V$, we have that $\spn(S)$ is a subspace of $V$.
\end{lemma}



To motivate the next definition, consider the set of vectors from $\R^2$:
$$S = \left\{ \myvec{1\\1},\myvec{1\\0},\myvec{3\\2} \right\}.$$
Since 
$$\myvec{a\\b} = b\myvec{1\\1} + (a-b)\myvec{1\\0}$$
we see that $\spn(S) = \R^2$.  That said, the vector $\myvec{3\\2}$ is not needed in order to span $R^2$.  It is in this sense that $\myvec{3\\2}$ is an ``unnecessary" or ``redundant" vector in $S$. The reason this occurs is that $\myvec{3\\2}$ is a linear combination of the other two vectors in $S$.  In particular, we have
 $$\myvec{3\\2} =\myvec{1\\0}+2\myvec{1\\1},$$
 or
 $$\myvec{0\\0} = \myvec{1\\0}+2\myvec{1\\1} - \myvec{3\\2}.$$
Consequently, the next definition makes precise this idea of ``redundant" vectors.  


\begin{definition}
We say a set $S$ of vectors is \textbf{linearly dependent} if there exists distinct vectors $v_1,\ldots, v_m\in S$ and scalars $a_1,\ldots, a_m\in \F$, \emph{not} all zero, such that 
$$a_1 v_1+\cdots + a_m v_m=0_V.$$ 
If $S$ is \emph{not} linearly dependent we say it is \textbf{linearly independent}.  
\end{definition}




As the empty set  $\emptyset$ is a subset of every vector space,  it is natural to ask if $\emptyset$ is linearly dependent or linearly independent.  The only way for $\emptyset$ to be dependent is if there exists some vectors $v_1,\ldots,v_m$ in $\emptyset$ whose linear combination is $0_V$.  But we are stopped dead in our tracks since there are NO vectors in $\emptyset$.  Therefore $\emptyset$ cannot be linearly dependent, hence, $\emptyset$ is linearly independent. 



\begin{lemma}[Linear Dependence Lemma]
If $S$ is a linearly dependent set, then there exists some element $v\in S$ so that 
$$\spn(S-v) = \spn(S).$$
Moreover, if $T$ is a linear independent subset of $S$, we may choose $v\in S-T$.  
\end{lemma}
\begin{proof}
As $S$ is linearly dependent  we know there exist distinct vectors 
$$\underbrace{v_1,\ldots,v_i}_{\in T},\underbrace{v_{i+1},\ldots,v_m}_{\in S- T}$$
and scalars  $a_1,\ldots,a_m$, not all zero, such that 
$$a_1v_1+\cdots+a_mv_m=0_V.$$  
As $T$ is linearly independent and $v_1,\ldots, v_i$ are distinct, we cannot have $a_{i+1}=\cdots=a_m = 0$.  (Why?)  Without loss of generality we may assume that $a_m \neq 0$. At this point choose $v=v_m$ and observe that $v\notin T$.  Rearranging the above equation we obtain
	$$v=v_{m}=-\left(\frac{a_1}{a_{m}}v_1+\ldots + \frac{a_i}{a_{m}}v_i+ \frac{a_{i+1}}{a_{m}}v_{i+1} +\ldots + \frac{a_{m-1}}{a_{m}}v_{m-1} \right),$$
which implies that $v\in \spn(S-v)$.  Moreover, since $S-v\subseteq \spn(S-v)$, we see that $S\subset \spn(S-v)$.  Lemma~\ref{lem:span_is_space} now implies that 
$$\spn(S) \subseteq\spn(S-v)\subseteq \spn(S),$$
which yields our desired result.     
\end{proof}


\begin{lemma}[Linear Independence Lemma]
Let $S$ be linearly independent.  If $v\in V$ but not in $\spn(S)$, then $S\cup\{v\}$ is  also linearly independent.
\end{lemma}
\begin{proof}
If $V- \spn(S)=\emptyset$, then there is nothing to prove.  Otherwise, let $v \in V$ such that $v\notin\spn(S)$ and assume for a contradiction that $S\cup \{v\}$ is linearly dependent. This means that there exists distinct vectors $v_1,\ldots, v_m\in S\cup\{v\}$ and scalars $a_1,\ldots,a_m$, not all zero, such that $a_1v_1+a_1v_1+\cdots + a_mv_m= 0_V$.  First, observe that $v = v_i$ for some $i$ and that $a_i\neq 0$.  (Why?)  Without loss of generality we may choose $i = m$.   Just like the calculation we performed in the proof of the Linear Dependence Lemma, we also have
$$ v = v_m = -\left(\frac{a_1}{a_m}v_1+\cdots + \frac{a_{m-1}}{a_m}v_{m-1}\right)\in \spn(S),$$
which contradicts the fact that $v\notin \spn(S)$.  We conclude that $S \cup \{v\}$ is linearly independent.   
\end{proof}


\section{Bases}
\begin{definition}
	A (possibly empty) subset $\B$ of $V$ is called a \textbf{basis} provided it is linearly independent and spans $V$.
\end{definition}


\begin{exs}\ \\
\begin{enumerate}
	\item The set of standard basis vectors $e_1,\ldots, e_n$ are a basis for $\R^n$ and $\C^n$.  (This explains their name!)
\item The set $\{1,x,x^2,\ldots,x^n\}$ form a basis for $\poly_{\leq n}(\F)$.
\item The infinite set $\{1,x,x^2,\ldots\}$ form a basis for $\poly(\F)$.
\item The emptyset $\emptyset$ forms a basis for the trivial vectors space $\{0_V\}$.  This might seem odd at first but consider the definitions involved.  First $\emptyset$ was defined to be linearly independent.  Additionally, we defined $\spn(\emptyset) = \{0_V\}$.   Therefore $\emptyset$ must be a basis for $\{0_V\}$.  
\end{enumerate}


\end{exs}

The proof of the next lemma is left to the reader.  
\begin{lemma}
	The subset $\B$ is a basis for $V$ if and only if every vector $u\in V$ is a unique linear combination of the vectors in $\B$.  
\end{lemma}


\begin{theorem}[Basis Reduction Theorem]\label{thm:basis_reduction}
	Assume $S$ is a finite set of vectors such that $\spn(S)=V$.  Then there exists some subset $\B$ of $S$ that is a basis for $V$.
\end{theorem}

\begin{proof}
If $S$ happens to be linearly independent we are done.  On the other hand, if $S$ is linearly dependent, then, by the Linear Dependence Lemma, there exists some $v\in S$ such that 
$$\spn(S- v) = \spn(S)$$  
If $S-v$ is not independent, we may continue to remove vectors until we obtain a subset $\B$ of $S$ which is independent.  (Note that since$S$ is finite we cannot continue removing vectors forever, and since $\emptyset$ is linearly independent this removal process must result in an independent set.) Additionally, 
$$\spn(\B) = V,$$
since the Linear Dependence Lemma guarantees that the subset of $S$ obtained after each removal spans $V$.  We conclude that $\B$ is a basis for $V$.  
\end{proof}

\begin{theorem}[Basis Extension Theorem]\label{thm:basis_extension_thm}
	Let $L$ be a linearly independent subset of $V$.  Then there exists a basis $\B$ of $V$ such that $L\subset \B$.  
\end{theorem}
We postpone the proof of this lemma to Section~\ref{subsec:ZornsLemma}.

\begin{corollary}
	Every vector space has a basis.  
\end{corollary}
\begin{proof}
	As the empty set $\emptyset$ is a linearly independent subset of any vector space $V$, the Basis Extension Theorem implies that $V$ has a basis.
\end{proof}

\section{Dimension}

\begin{lemma}\label{lem:indp_lessthan_span}
	If $L$ is any finite independent set and $S$ spans $V$, then  $|L| \leq |S|$.
\end{lemma}
\begin{proof}
	Of all the sets that span $V$ and have cardinality $|S|$ choose $S'$ so that it maximizes $|L\cap S'|$.  If we can prove that  $L\subset S'$ we are done, since 
	$$|L|\leq |S'|=|S|.$$
	For a contradiction, assume $L$ is not a subset of $S'$.  Fix some vector $u \in L -S'$.  As $S'$ spans $V$ and does not contain $u$, then $D=S'\cup\{u\}$ is linearly dependent. Certainly, $\spn(D) = V$.  Now define the linearly independent subset
	$$T = L\cap D,$$
	and observe that $u\in T$. By the Linear Dependence Lemma there exists some $v\in D-T$   so that 
	$$\spn(D-v) = \spn(D)=V.$$
	Observe $u\neq v$.  This immediately yields our contradiction since $|D-v| = |S'|=|S|$ and $D-v$ has one more vector from $L$ (the vector $u$) than $S'$ does.  As this contradicts our choice of $S'$, we conclude that $L\subset S'$ as needed.    
\end{proof}


\begin{theorem}\label{thm:dimension}
	Let $V$ be a vector space with at least one finite basis $\B$.  Then every basis of $V$ has cardinality $|\B|$.  
\end{theorem}
\begin{proof}
	  Fix any other basis $\B_0$ of $V$.  As $\B_0$ spans $V$, Lemma~\ref{lem:indp_lessthan_span}, with $S= \B_0$ and $L=\B$, implies that $|\B|\leq |\B_0|$.  Our proof will now be complete if we can show that  $|\B| \nless |\B_0|$.  For a contradiction, assume that  $n=|\B| < |\B_0|$ and let $L$ be any $n+1$ element subset of $\B_0$ and $S=\B$.  (As $\B_0$ is a basis, $L$ is linearly independent.)  Lemma~\ref{lem:indp_lessthan_span} then implies that $n+1=|L|\leq |S|=n$, which is absurd.  
\end{proof}

	

\begin{definition}
	A vector space $V$ is called \textbf{finite-dimensional} if it has a finite basis $\B$.  As all bases in this case have the same cardinality, we call this common number the \textbf{dimension} of $V$ and denote it by $\dim(V)$.    
\end{definition}

A beautiful consequence of Theorem~\ref{thm:dimension}, is that in order to find the dimension of a given vector space we need only find the cardinality of some basis for that space.  Which basis we choose doesn't matter!

\begin{exs}\ \\
	\begin{enumerate}
		\item The dimension of $\R^n$ is $n$ since $\{e_1,\ldots, e_n\}$ is a basis for this vector space.  
		\item Recall that $\{1,x,x^2,\ldots, x^n\}$ is a basis for $\poly_{\leq n} (\R)$.  Therefore $\dim\poly_{\leq n}(\R) = n+1$.  
		\item Consider the vector space $\C$ over $\C$.  A basis for this space is $\{1\}$ since every element in $\C$ can be written uniquely as $s\cdot 1$ where $s$ is a scalar in $\C$.  Therefore, we see that this vector space has dimension 1. We can write this as $\dim_{\C}(\C)=1$, where the subscript denotes that we are considering $\C$ as a vector space over $\C$. 
		
		On the other hand, recall that $\C$ is also a vector space over $\R$.  A basis for this space is $\{1,i\}$ since, again, every element in $\C$ can be uniquely expressed as
		$$a\cdot 1 + b\cdot i$$
		where $a,b\in\R$.  It now follows that this space has dimension 2.  We write this as $\dim_{\R}(\C)=2$.
		\item What is the dimension of the trivial vector space $\{0_V\}$?  A basis for this space is the emptyset $\emptyset$, since by definition it is linearly independent and $\spn(\emptyset) = \{0_V\}$.  Therefore, this space has dimension $|\emptyset| = 0$.  
	\end{enumerate}

\end{exs}

We now turn our attention to proving some basic properties about dimension.  


\begin{theorem}\label{thm:dimIndepSet}
	Let $V$ be a finite-dimensional vector space.  If $L$ is any linearly independent set in $V$, then $|L|\leq\dim(V)$.
	Moreover, if $|L|= \dim(V)$, then $L$ is a basis for $V$.  
\end{theorem}
\begin{proof}
By the Basis Extension Theorem,  we know that there exists a basis $\B$ such that 
\begin{align*}
L\subseteq \B.\tag{*}
\end{align*}
This means that $|L|\leq |\B| = \dim(V)$.	In the special case that $|L| = \dim(v) = |\B|$, then $(*)$ implies $L=\B$, i.e., $L$ is a basis.   
\end{proof}

A useful application of this theorem is that whenever we have a set $S$ of $n+1$ vectors sitting inside an $n$ dimensional space, then we instantly know that $S$ must be dependent.  The following corollary, is another useful consequence of this theorem.

\begin{corollary}
	If $V$ is a finite-dimensional vector space, and $U$ is a subspace, then $\dim(U)\leq \dim(V)$.  
\end{corollary}


It might occur to the reader that an analogous statement for spanning sets should be true.  That is, if we have a set $S$ of $n-1$ vectors which sits inside an $n$-dimensional vectors space $V$ can we conclude that $\spn S\neq V$?  As the next theorem shows, the answer is yes.

\begin{theorem}
	Let $V$ be a finite-dimensional vector space.  If $S$ is any spanning set for $V$, then $\dim(V)\leq |S|$. Moreover, if $|S| = \dim(V)$ then $S$ is a basis for $V$.
\end{theorem}

To prove this theorem, we would like to employ similar logic as in the proof of the previous theorem but with Theorem~\ref{thm:basis_reduction} in place of Theorem~\ref{thm:basis_extension_thm}.  The problem with this is that $S$ is not  necessarily finite.  Instead, we may use the following lemma in place of Theorem~\ref{thm:basis_extension_thm}.  Both its proof, and the proof of this lemma are left as exercises for the reader.  

\begin{lemma}\label{lem:ReduceToBasisFiniteDimension}
	Let $V$ be a finite-dimensional vector space.  If $S$ is any spanning set for $V$, then there exists a subset $\B$ of $S$, which is a basis for $V$.
\end{lemma}




  







\section{Zorn's lemma \& the basis extension theorem}\label{subsec:ZornsLemma}

\begin{definition}
	Let $\mathfrak{X}$ be a collection of sets. We say a set $B\in\mathfrak{X}$ is \textbf{maximal} if there exists no other set $A\in\mathfrak{X}$ such that $B\subset A$.  A \textbf{chain} in $\mathfrak{X}$ is a subset $\mathfrak{C}\subseteq\mathfrak{X}$ such that for any two sets $A,B\in \mathfrak{C}$ either 
	$$A\subseteq B\qquad\textrm{ or }\qquad B\subseteq A.$$
	Lastly, we say $C\in\mathfrak{X}$ is an \textbf{upper bound} for a chain $\mathfrak{C}$ if $A\subseteq C$, for all $A\in \mathfrak{C}$.
\end{definition}

Observe that if $\mathfrak{C}$ is a chain and $A_1,\ldots,A_m\in\mathfrak{C}$, then there exists some $1\leq k\leq m$, such that
$$A_k=A_1\cup A_2\cup\cdots\cup A_m.$$
This observation follows by a simple induction, which we leave to the reader.


\begin{ZL}
	Let $\mathfrak{X}$ be a collection of sets such that every chain $\mathfrak{C}$ in $\mathfrak{X}$ has an upper bound.  Then $\mathfrak{X}$ has a maximal element.  
\end{ZL}

\begin{lemma}\label{lem:maximal_is_basis}
	Let $V$ be a vector space and fix a linearly independent subset $L$.  Let $\mathfrak{X}$ be the collection of all linearly independent sets in $V$ that contain $L$.  If $B$ is a maximal element in $\mathfrak{X}$, then $B$ is a basis for $V$.  
\end{lemma}
\begin{proof}
	By definition of the set $\mathfrak{X}$, we know that $B$ is linearly independent.  It only remains to show that $\spn(B) = V$.  Assume for a contradiction that it does not.  This means there exists some vector $v\in V-\spn(B)$.  By the Linear Independence Theorem, $B\cup\{v\}$ is linearly independent and hence must be an element of $\mathfrak{X}$.  This contradicts the maximality of $B$. We conclude that $\spn(B) = V$ as desired.  
\end{proof}


\begin{proof}[Proof of Theorem~\ref{thm:basis_extension_thm}]
	Let $L$ be a linearly independent subset of $V$ and define $\mathfrak{X}$ to be the collection of all linearly independent subsets of $V$ containing $L$.  In light of Lemma~\ref{lem:maximal_is_basis}, it will suffice to prove that $\mathfrak{X}$ contains a maximal element.  An application of Zorn's Lemma, assuming its conditions are met, therefore completes our proof.  
	To show that we can use Zorn's Lemma, we need to check that every chain $\mathfrak{C}$ in $\mathfrak{X}$ has an upper bound.  If $\mathfrak{C} = \emptyset$, then $L\in\mathfrak{X}$ is an upper bound.  Otherwise, we claim that the set
	\begin{align*}
	C = \bigcup_{A\in \mathfrak{C}}A,	
	\end{align*}
	is an upper bound for our chain $\mathfrak{C}$. Clearly, $A\subset C$, for all $A\in\mathfrak{C}$.  It now remains to show that  $C\in \mathfrak{X}$, i.e., $L\subset C$ and $C$ is independent.  As $\mathfrak{C} \neq \emptyset$, then for any $A\in \mathfrak{C}$, we have 
	$$L\subseteq A \subseteq C.$$   
	To show $C$ is independent, assume
	$$a_1v_1+\cdots+ a_mv_m = 0_V,$$
	for some (distinct) $v_i\in C$ and  $a_1\in \F$.  By construction of $C$ each vector $v_i$ must be an element of some $A_i$.  As $\mathfrak{C}$ is a chain the above remark implies that 	$$A_k=A_1\cup A_2\cup\cdots\cup A_m,$$
	for some $1\leq k\leq m$.  	Therefore all the vectors $v_1,\ldots,v_m$ lie inside the linearly independent set $A_k\in \mathfrak{X}$.   This means our scalars $a_1,\ldots,a_m$ are all zero.  We conclude that $C$ is an independent set.    
\end{proof}


\chapter{Linear transformations}

In this chapter, we study functions from one vector space to another.  So that the functions of study are linked, in some way, to the operations of vector addition and scalar multiplication we restrict our attention to a special class of functions called linear transformations.   
Throughout this chapter $V$ and $W$ are always vector spaces over $\F$.  

\section{Definition \& examples}

\begin{definition}
We say a function $T:V\to W$ is a \textbf{linear transformation} or a \textbf{linear map} provided 
$$T(u+v) = T(u) + T(v)$$ 
and 
$$T(av) = aT(v)\textrm{ for all } v\in V, a\in \F$$
for all $u,v\in V$ and $a\in\F$. We denote the set of all such linear transformations, from $V$ to $W$, by $\lin(V,W)$ .  
\end{definition}

To simplify notation we often write $Tv$ instead of $T(v)$.  It is not a coincidence that this simplified notation is reminiscent of matrix multiplication; we expound on this in Section~\ref{sec:linearmap_matrix}.




\begin{exs}\ \\
	\begin{enumerate}
		\item The function $T:V\to W$ given by $Tv = 0_W$ for all $v\in V$ is a linear map.  Appropriately, this is called the \textbf{zero map}.
		\item The function $I:V\to V$, given by $Iv = v$, for all $v\in V$ is a linear map.  It is called the \textbf{identity map}.
		\item Let $A$ be an $m\times n$ matrix with real coefficients.  Then $A:\R^n\to \R^m$ given by matrix-vector product is a linear map.  In fact, we show in Section~\ref{sec:linearmap_matrix}, that, in some sense, all linear maps arise in this fashion.  
		\item Recall the vector space $\poly_{\leq n}(\R)$.  Then the map $T:\poly_{\leq n}(\R)\to \R^n$ defined by
		$$T(a_0+a_1x+\cdots a_nx^n) = \left[\begin{array}{c}a_0\\a_1\\ \vdots\\ a_n\end{array}\right]$$
		is a linear map. 
		\item Recall the space of continuous functions $\cts$.  An example of a linear map on this space is the function $T:\cts \to \cts$ given by $Tf = xf(x)$.    
		\item Recall that $\D$ is the vector space of all differentiable function $f:\R\to\R$ and $\fcts$ is the space of all function $g:\R\to \R$.    Define the map $\partial:\D \to \fcts$, so that $\partial f = f'$.  We see that $\partial$ is a linear map since 
		$$\partial(f+g) = (f+g)' = f'+g' = \partial f+ \partial g$$
		and 
		$$\partial(af) = (af)' = af'=a\partial f.$$
		\item From calculus, we obtain another linear map $T: \cts\to \R$ given by 
		$$Tf = \int_0^1 f\ dx.$$ 
		The reader should convince himself that this is indeed a linear map.
		
		
		
	\end{enumerate}

\end{exs}

Although the above examples draw from disparate branches of mathematics, all these maps have the property that they map the zero vector to the zero vector.   As the next lemma shows, this is not a coincidence.  

\begin{lemma}\label{lem:zero}
	Let $T\in\lin(V,W)$.  Then $T(0_V) = 0_W$.  
\end{lemma}
\begin{proof}
To simplify notation let $0 = 0_V$.  Now 
$$T(0) = T(0+0) = T(0)+T(0).$$
Adding $-T(0)$ to both sides yields
$$T(0) + -T(0)= T(0)+T(0) + -T(0).$$
Since all these vectors are elements of $W$, simplifying gives us $0_W = T(0)$. 
\end{proof}

It is often useful to ``string together" existing linear maps to obtain a new linear map.  In particular, let $S\in\lin(U,V)$ and $T\in\lin(V,W)$ where $U$ is another $\F$-vector space.  Then the function defined by
$$ST(v) = S(Tv)$$
is clearly a linear map in $\lin(U,W)$. (The reader should verify this!) We say that $TS$ is the \textbf{composition} or \textbf{product} of $S$ with $T$.  The reader may find the following figure useful for picturing the product of two linear maps.  

\begin{center}
\begin{tikzpicture}
 
\draw (0,3.5) ellipse (1cm and 1.5cm);  
\draw (4,3.5) ellipse (1cm and 1.5cm);  
\draw (8,3.5) ellipse (1cm and 1.5cm);  

  \node at (0,1.5) {$U$};
    \node at (4,1.5) {$V$};  
        \node at (8,1.5) {$W$};
        
  \node[fill=black,circle,minimum width=1.5pt,inner sep=1pt,label=below:$v$] at (0,3.5) {};        
    \node[fill=black,circle,minimum width=1.5pt,inner sep=1pt,label=below:$Sv$] at (4,3.5) {};        
      \node[fill=black,circle,minimum width=1.5pt,inner sep=1pt,label=below:$T(Sv)$] at (8,3.5) {};        
  \draw[->,thick,shorten <=5pt,shorten >=5pt] (0,3.5) to [bend left=30] node[midway,above] {$S$}(4,3.5);
  \draw[->,thick,shorten <=5pt,shorten >=5] (4,3.5) to [bend left=30] node[midway,above] {$T$} (8,3.5) ;
 \end{tikzpicture}	
\end{center}

There is another important way to combine two existing linear maps to obtain a third. If $S,T\in \lin(V,W)$ and $a,b\in \F$, then we may define the function
$$(aS+bT)(v) = aSv + bTv$$
for any $v\in V$.  Again we encourage the reader to check that this function is a linear map in $\lin(V,W)$.  


 
 

Before closing out this section, we first pause to point out a very important property of linear maps.  First, we need to generalize the concept of a line in $\R^n$ to a line in an abstract vector space.  Recall, that any two vector $v,u\in\R^n$ define a line via the expression $av+u$, where $a\in \R$.  As this definition requires only vector addition and scalar multiplication we may ``lift" it to the  abstract setting.  Doing this we have the following definition.  
\begin{definition}
	Fix vectors $u,v\in V$.  We define a \textbf{line} in $V$ to be all points of the form $$av+u,\quad\textrm{where}\quad a\in \F.$$
\end{definition}
Now consider applying a linear map $T\in\lin(V,W)$  to the line $av+u$.  In particular, we see that
$$T(av+u) = aT(v)+T(v).$$
In words, this means that the points on our line in $V$ map to points on a new line in $W$, defined by the vectors $T(v),T(u)\in W$.   In short we say that linear transformations have the property that they map lines to lines.  

In light of the preceding lemma, even more is true.  Observe that any line containing $0_V$ is of the form $av+0_V$.  (We think of such lines as analogues to lines through the origin in $\R^n$.)  Lemma~\ref{lem:zero} now implies that such lines are mapped to lines of the form
$$T(av+0_V) = aT(v) +T(0_W) = aT(v) + 0_W.$$
In other words, linear transformations actually map lines through the origin in $V$ to lines through the origin in $W$.  



\section{Rank-nullity theorem}
The aim of this section is to prove the Rank-Nullity Theorem.  This theorem describes a fundamental relationship between linear maps and dimension.  An immediate consequence of this theorem, will be an beautiful proof to the fact that a homogeneous system of equations with more variables than equations must have an infinite number of solutions.

We begin with the following definition.  
 
\begin{definition}
Let $T:V\to W$ be a linear map.  We say $T$ is \textbf{injective} if  $Tv = Tu$ implies that $u=v$.  On the other hand, we say that $T$ is \textbf{surjective} provided that for every $w\in W$, there exists some $v\in V$ such that $Tv = w$.  A function that is both injective and surjective is called \textbf{bijective}.
\end{definition}

It might help to think of $T$ as a canon that shoots shells (elements in $V$) at targets (elements of $W$)\footnote{D. Saracino, A first course in abstract algebra.}.  From this perspective there is an easy way to think about surjectivity and injectivity.  
\begin{itemize}
	\item Surjectivity means that the canon $T$ hits every element in $W$.
	\item Injectivity means that every target in $W$ is hit at most once.
	\item Bijectivity means that every target is hit exactly once.  In this case we can think of $T$ as ``matching up" the elements in $T$ with the elements in $W$.  
\end{itemize}


\begin{figure}[h!]
 \centering
 \begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt},every fit/.style={ellipse,draw,inner sep=10pt}]
  \node[ele,label=left:$u$] (a1) at (0,4) {};    
  \node[ele,label=left:$v$] (a2) at (0,3) {};    


  \node[ele,label=right:$Tu$] (b1) at (4,4) {};
  \node[ele,label=right:$Tv$] (b2) at (4,3) {};


  \node[draw,fit= (a1) (a2),minimum width=2cm] {} ;
  \node[draw,fit= (b1) (b2),minimum width=2cm] {} ;
  
  \node at (0,1.5) {$V$};
    \node at (4,1.5) {$W$};  
  \draw[->,thick,shorten <=2pt,shorten >=2pt] (a1) to [bend left=30] (b1);
  \draw[->,thick,shorten <=2pt,shorten >=2] (a2) to [bend right=30] (b2);

 \end{tikzpicture}
\end{figure}






As is always the case in mathematics, it will be beneficial to have more than one description of a single idea.  Our next lemma provides this alternative description of injectivity and surjectivity.

\begin{definition}
	Fix $T\in\lin(V,W)$.  Define the \textbf{null space} of $T$ to be
	$$\nul T = \makeset{v\in V}{Tv = 0_W}$$
	and the \textbf{range} of $T$ to be 
	$$\ran T = \makeset{Tv}{v\in V}.$$  
\end{definition}

Observe that the null space is a subset of $V$ where as the range is a subset of $W$.  

\begin{lemma}\label{lem:inj_nul}
	Let $T\in \lin(V,W)$.  
	\begin{enumerate}
		\item $T$ is surjective if and only if $\ran T = W$.
		\item $T$ is injective if and only if $\nul T = \{0_V\}$.
		
	\end{enumerate}
\end{lemma}

\begin{proof}
Saying that $T$ is surjective is equivalent to saying that
for any $w\in W$ there exists some $v\in V$ such that $Tv = w$.  In other words, 
$$\ran T = \makeset{Tv}{v\in V} = W,$$
as claimed.  For the second claim, begin by assume $T$ is injective.  This means that $u=v$ whenever $Tu = Tv$.  Consequently,
$$\nul T = \makeset{v\in V}{Tv = 0_W=T(0_V)} = \{0_V\},$$
as desired.  For the other direction, assume $\{0_V\}= \nul T$ and consider any two vectors $u,v\in V$ such that $Tu = Tv$.  To prove  $T$ is injective we must show that $u=v$.  To this end, the linearity of $T$ yields 
$$T(u-v) = 0_W.$$
This means that $u-v\in \nul T = \{0_V\}$. Hence $u-v = 0_V$ or $u=v$ as desired.    
\end{proof}


The next lemma, whose proof we leave to the reader, states that our two sets $\nul T$ and $\ran T$ are no ordinary sets; they are vector spaces in their own right.  

\begin{lemma}
	Let $T\in\lin(V,W)$.  Then $\nul(T)$ is a subspace of $V$ and $\ran(T)$ is a subspace of $W$.  
\end{lemma}

\begin{exs}\ \\
	\begin{enumerate}
		\item Consider the linear map $T:\R^{n+1} \to \poly_{\leq n}$ given by
		$$T(a_0,\ldots,a_{n+1}) = a_0 + a_1x+\cdots a_nx^n.$$
		Then $\nul T = \{(0,\ldots,0)\} = \{0_{\R^2}\}$ and $\ran T = \poly_{\leq n}$.  
		\item The $T:\poly\to\poly$ given by $T(f)(x) = f'(x)$ is linear with  $\nul T=$ constant polynomials and $\ran T = \poly$.
		Therefore, $T$ is surjective but not injective. 
		\item Consider the map $T:\R^2 \to \R^3$ given by 
		$$T\left(\myvec{x\\y}\right) = \myvec{x\\y\\-(x+y)}.$$
		Then $\nul T = \{0_{\R^2}\}$, but $\ran T \neq \R^3$.  In fact, 
		$$\ran T = \makeset{\myvec{x\\y\\z}\in\R^3}{x+y+z=0}$$
		which is the equation of a plane in $\R^3$.  So this map if injective but not surjective.  
%		\item Let $U$ be 2-dimensional subspace of $\R^3$ and let $\{u_1, u_2\}$ be a basis for this space.  (Note $U$ is just a plane in $\R^3$.) By the Basis Extension Theorem we know there exists a basis $\{u_1,u_2, v\}$ for all of $\R^3$.  Now, define the map $P:\R^3 \to U$ by 
%		$$P(a u_1+ bu_2 + cv) = a u_1+ bu_2.$$
%
%		Then $\nul P = \spn(v)$ and $\ran T = U$.  Observe that $P$ ``projects" vectors in $\R^3$ onto $U$.  Linear maps defined in this manner are called \textbf{projections}.
	\end{enumerate}

\end{exs}


Before reading any further, can you spot a relation among the dimensions of the domain, range and null space in example 3)?   

As the next theorem shows, there is one and an important one at that!  The reader should check that in fact, both examples 1) and 3) do indeed satisfy this theorem.  

\begin{theorem}[Rank-Nullity]
	Assume $V$ is finite-dimensional.  For any $T\in\lin(V,W)$, 
	$$\dim V = \dim(\nul T ) + \dim(\ran T).$$
\end{theorem}

\begin{proof}
	As $\nul T$ is a subspace of $V$, and hence a vector space in its own right, it has a basis.  Let $\{e_1,\ldots, e_k\}$ be such a basis for $\nul T$.  By the Basis Extension Theorem (Theorem~\ref{thm:basis_extension_thm}), there exists vectors $f_1,\ldots,f_m$ so that 
	$$\B=\{e_1,\ldots e_k,f_1,\ldots, f_m\}$$
	is a basis for $V$.  Since
	$$\dim V=k+m =  \dim \nul T + m,$$
	we must show $\dim \ran T = m$.  To this end, it suffices to show that  $S=\{Tf_1,\ldots, Tf_m\}$ is a basis for $\ran T$.  We do this in two parts. 
	
	We first show that $\spn(S) = \ran T$.  This readily follows from the following:
	\begin{align*}
	\ran T &= \makeset{Tv}{v\in V}\\
	&=\makeset{T(a_1e_1+\cdots +a_ke_k + b_{1}f_1+\cdots +b_{m}f_m)}{a_i,b_i\in \F}\\
	&=\makeset{a_1Te_1+\cdots +a_kTe_k + b_{1}Tf_1+\cdots +b_{m}Tf_m)}{a_i,b_i\in \F}\\
	&=\makeset{b_{1}Tf_1+\cdots +b_{m}Tf_m)}{b_i\in \F} \\
	&= \spn(S),
	\end{align*}
	where the second equality uses the fact that $\B$ is a basis for $V$ and the third equality follows since $e_1,\ldots,e_k\in \nul T$.   

We now turn our attention to showing that $S$ is linearly independent.  To do this we must show that if $a_1Tf_1+\cdots + a_mTf_m = 0_W$, then all the scalars are zero.   By the linearity of $T$ we have
$$0_W = T(a_1f_1+\cdots+a_mf_m),$$
which means that $a_1f_1+\cdots+a_mf_m\in \nul T$.  As $e_1,\ldots, e_k$ are a basis for $\nul T$ it follows that 
$$b_1e_1 +\cdots + b_ke_k = a_1f_1+\cdots+a_mf_m,$$
for some scalars $b_i$.  Rearranging we see that
$$0_V = -(b_1e_1 +\cdots + b_ke_k) +a_1f_1+\cdots+a_mf_m.$$
The linear independence of $\B=\{e_1,\ldots e_k,f_1,\ldots, f_m\}$ forces all the scalars to be zero.  In particular, $a_1=a_2=\cdots	=0$ as needed.  
As we have shown that $S$ is independent and spans $\ran T$, we may conclude that it is a basis for $\ran T$ as desired.
\end{proof}


To motivate our first corollary recall the following fact about plain old sets.  If $X$ and $Y$ are sets and $f:X\to Y$ is injective then $|X|\leq |Y|$.  On the other hand if $f$ is surjective, then  $|X|\geq |Y|$.  As dimension measures the ``size" of a  vector space, the following is the vector space analogue to this set theory fact.  

\begin{corollary}\label{cor:ranknullity}
	Let $V$ and $W$ be finite-dimensional vector spaces and let  $T$ be an arbitrary linear map in $\lin(V,W)$.
	\begin{enumerate}
		\item If $\dim V > \dim W$, then $T$ is not injective.
		\item If $\dim V < \dim W$, then $T$ is not surjective.  
	\end{enumerate}
\end{corollary}

\begin{proof}
	Fix $T\in \lin(V,W)$.  To prove the first claim, assume $\dim V>\dim W$.  By the Rank-Nullity Theorem we see that 
	$$\dim(\nul T) = \dim V - \dim(\ran T) \leq \dim V - \dim W  > 0,$$
	where the second inequality follows since $\ran T$ is a subspace of $W$.  Consequently, $\nul T$ is not the trivial space, so by  Lemma~\ref{lem:inj_nul} $T$ is not injective.
	Likewise, if $\dim V <\dim W$, then 
	$$\dim(\ran T) = \dim V - \dim(\nul T) \leq \dim V < \dim W.$$
	Consequently, $\ran T$ cannot be all of $W$, i.e., $T$ is not surjective.  
\end{proof}

In general mathematical function can be injective without being surjective and vice versa.  For example consider the functions  $f,g:\mathbb{Z}\to \mathbb{Z}$ given by $f(n) = 2n$ and 
$$g(n) = \begin{cases} n+1 &\mbox{if } n > 0 \\ 
0 & \mbox{if } n = 0\\
n+2 & \mbox{if } n <0. \end{cases}.
$$
Then $f$ is injective but not surjective and $g$ is surjective but not injective  since $g(-2) = 0 = g(0)$.  Consequently the next theorem is quiet amazing.  It states that if two vector spaces have the same dimension, then a linear map between them is surjective if and only if it is injective!  

\begin{corollary}\label{thm:onto_iff_1to1}
	Let $V$ and $W$ be finite-dimensional vector spaces with the same dimension.  For any linear map $T\in\lin(V,W)$ we have that $T$ is surjective if and only if $T$ is injective.  
\end{corollary}

\begin{proof}
	By the Rank-Nullity Theorem states we always have 
	$$\dim V = \dim( \nul T) + \dim( \ran T).$$
Now, observe that 
\begin{align*}
T\mbox{ is surjective }& \Longleftrightarrow \ran T = W \\&\Longleftrightarrow \dim(\ran T) = \dim W \\
&\Longleftrightarrow \dim(\ran T) = \dim V \\
&\Longleftrightarrow \dim(\nul T) = 0 \\
&\Longleftrightarrow \nul T = \{0_V\} \\
&\Longleftrightarrow T\mbox{ is injective}, 	
\end{align*}
where the third equivalence is the fact that $\dim V = \dim W$ and the fourth equivalence follows from the Rank-Nullity Theorem.

\end{proof}




Before closing this section, let demonstrate two beautiful applications of the Rank-Nullity Theorem.  First, consider a homogeneous system of linear equations
\begin{align*}
	a_{11} x_1 + \ldots +a_{1n}x_n &=0\\
	a_{21} x_1 + \ldots +a_{2n}x_n &=0\\
	&\vdotswithin{=}\\
	a_{m1} x_1 + \ldots +a_{1n}x_n &=0.  
\end{align*}
A standard result from any elementary linear algebra course is that if this system has more variable than equations ($n>m$), then a non-trivial solution to the system exists, i.e., one other than $x_1=\cdots x_n = 0$.   We are now in a position to give an elegant proof of this fact.  First, rewrite this system in matrix form as $A\textbf{x} = \textbf{0}$, where 
$$A = \left[\begin{array}{ccc}
a_{11}&\cdots & a_{1n}\\
\vdots&\ddots&\vdots\\
a_{m1}&\cdots & a_{mn}
\end{array}\right]\qquad\textrm{and}\qquad\textbf{x} = \myvec{x_1\\ \vdots\\ x_n}.$$
Recall that  $A:\R^n\to \R^m$ is a linear map given by matrix vector multiplication. As $n>m$,  Corollary~\ref{cor:ranknullity} states that $T$ is not injective and hence $\{0_V\} \subsetneq \nul T$.  Therefore there exists some nonzero $\textbf{x}\in \nul T$.  As $\textbf{x}$ is nonzero and $A\textbf{x} =\textbf{0}$, we see that our system has a nontrivial solution as claimed.  

For our second application, consider a system of (not necessarily homogeneous) linear equations
\begin{align*}
	a_{11} x_1 + \ldots +a_{1n}x_n &=b_1\\
	a_{21} x_1 + \ldots +a_{2n}x_n &=b_2\\
	&\vdotswithin{=}\\
	a_{m1} x_1 + \ldots +a_{1n}x_n &=b_m.  
\end{align*}
In matrix form this becomes $A\textbf{x}= \textbf{b}$.
Another standard result from elementary linear algebra is that if our system has more equations than unknowns, i.e., $n<m$, then there exists some choice of $\textbf{b}\in \R^m$ so that our system is inconsistent (has no solutions).  To prove this, again think of $A:\R^n\to \R^m$ as a linear map.  Corollary~\ref{cor:ranknullity} tell us that $A$ is not surjective.  This means there exists some $\textbf{b}\in\R^m$ so that no choice of $\textbf{x}\in \R^n$ gives $A\textbf{x}=\textbf{b}$.  In other words, for this $\text{b}$, our system is inconsistent.  







\section{Vector space isomorphisims}

Our next goal is to identify when two vectors spaces are essential the same.  Mathematically, we say they are \emph{isomorphic} which is latin for ``same shape". To see what we mean by this, imagine you are given an $\F$-vector space $V$ and you paint all its elements red to obtain a new space $W$.  Although this new space $W$ ``looks" different (all its vectors are red!), it still has the same algebraic structure as $V$.    

A more concrete example of isomorphic vector spaces has been in front of us almost since page one!  In fact, it might have already occurred to you that as vector spaces $\R^{n+1}$ and $\poly_{\leq n}$ were strikingly similar.  Certainly as sets they are very different -- one is a set of vectors while the other is a set of polynomials!  In terms of their vector space structure this is just a cosmetic difference.  To convince you note that an arbitrary vector in $\R^{n+1}$ looks like
$$\myvec{a_0\\\vdots\\a_n}$$
while an arbitrary vector in $\poly_{\leq n}$ looks like $a_0 + a_1x +\cdots + a_nx^n$.
In either case, a vector is just a list of $n+1$ numbers $\{a_0,\ldots, a_n\}$.  Moreover, the operation of addition and scalar multiplication are essentially the same in both spaces too.  For example, addition in $\R^{n+1}$ is given by
$$\myvec{a_0\\\vdots\\a_n}+\myvec{b_0\\\vdots\\b_n} = \myvec{a_0+b_0\\\vdots\\a_n+b_n}$$
which is really no different then addition in $\poly_{\leq n}$ which looks like
\begin{align*}
(a_0 + a_1x +\cdots + a_nx^n) &+ (b_0 + b_1x +\cdots + b_nx^n)\\ 
&=(a_0+b_0) + (a_1+b_1)x +\cdots + (a_n+b_n)x^n.
\end{align*}.  
Intuitively, these two spaces are the ``same".  With this example in mind consider the formal definition for vector spaces to be isomorphic.  

\begin{definition}
We say  two vector spaces $V$ and $W$ are \textbf{isomorphic} and write $V\cong W$, if there exists $T\in\lin(V,W)$ which is both injective and surjective. We call such a $T$ an \textbf{isomorphism}.
\end{definition}



\begin{theorem}
Two finite-dimension vector spaces $V$ and $W$ are isomorphic if and only if they have the same dimension.  	
\end{theorem}
\begin{proof}
	Assume $V$ and $W$ are isomorphic.  This means there exists a linear map $T:V\to W$ that is both surjective and injective.  Corollary~\ref{cor:ranknullity} immediately implies that $\dim V = \dim W$.  
	For the reverse direction, let $\B_V=\{v_1,\ldots, v_n\}$ be a basis for $V$ and $\B_W=\{w_1,\ldots, w_n\}$ be a basis for $W$.  As every vector $v\in V$ can be written (uniquely) as 
	$$v=a_1v_1+\cdots +a_n v_n$$
	for $a_i \in \F$, we may define a function $T:V\to W$ by 
	$$Tv = a_1w_1+\cdots + a_n w_n.$$
	Observe that the uniqueness of our representation of $v$ implies that $T$ is a well-defined function.  Moreover, a straightforward check reveals that $T$ is indeed a linear map. 
	It only remains to show that $T$ is an isomorphism.  To see that $T$ is injective, let that $v \in \nul T$ and let  $b_i\in\F$ be such that $v=b_1v_1+\cdots +b_n v_n$. This means 
	$$0_W = Tv = b_1w_1+\cdots + b_n w_n.$$
	Since $\B_W$ is an independent set, it follows that all our scalars $b_i$ must be 0 and, in turn, $v = 0$. This shows that $\nul T = \{0_V\}$, i.e., $T$ is injective.    
	
	 To see that $T$ is also surjective, note that any vector $w\in W$ can be written as 
	$$w = c_1w_1+\cdots+c_mw_m,$$
	for some choice of scalars $c_i$ (why?).  Now consider the vector $c_1v_1 + \cdots + c_m v_m \in V$ and observe that  
	$$T(c_1v_1 + \cdots + c_m v_m) = c_1w_1+\cdots+c_mw_m = w.$$
	This shows that $T$ is surjective.   
\end{proof}




\begin{definition}
Let $T\in\lin(V,W)$.  We say $T$ is \textbf{invertible} provided there exists some $S\in \lin(W,V)$ so that $ST:V\to V$ is the identity map on $V$ and $TS:W\to W$ is the identity map on $W$.  We call $S$ an \textbf{inverse} of $T$.   
\end{definition}

As a consequence of the next lemma, we are able to refer to \emph{the} inverse of $T$ which we denote by $T^{-1}$.

\begin{lemma}
Let $T\in\lin(V,W)$.  If $T$ is invertible, then its inverse is unique.  	
\end{lemma}

\begin{proof}
	Assume $S$ and $S'$ are both inverses for $T$.  Then
	$$S = SI_W = STS'= I_VS' =S'$$
	where $I_V$ and $I_W$ are the identity maps on $V$ and $W$ respectively.  
\end{proof}



\begin{lemma}
Let $T\in\lin(V,W)$.  Then $T$ is invertible if and only if $T$ is an isomorphism.  
\end{lemma}
\begin{proof}
	Let us first assume that $T$ is invertible. We must prove that $T$ is both injective and surjective.  To see injectivity, let $u\in\nul T$, then 
	$$u = I_Vu = T^{-1}Tu = T^{-1}0_W = 0_V,$$
	where $I_V$ is the identity map on $V$.  
	We conclude that $\nul T = \{0_V\}$ and hence $T$ is injective.  To see that $T$ is also surjective fix $w\in W$.  Observe that $T$ maps the vector $T^{-1}w\in V$ onto $w$ since  
	$$T(T^{-1}w) = TT^{-1}w = I_Ww = w.$$
	We conclude that $T$ is surjective.
	
	Now assume $T:V\to W$ is an isomorphism.  As $T$ is both injective and surjective, then for every $w\in W$ there exists exactly one $v\in V$ so that $Tv = w$.  Now define the function $S:W\to V$ by $S(w) = v$.  We claim $T^{-1}=S$.  By definition we have $S(Tv) = v$ for all $v\in V$ and $TS(w) = w$ for all $w\in W$.  It only remains to show that $S$ is linear.  Let $w_1,w_2\in W$ and let $v_1,v_2$ be the unique vectors in $V$ so that $Tv_i = w_i$.  As $T$ is linear then $T(v_1+v_2) = w_1+w_2$.  By definition of $S$ we now have 
	$$S(w_1+w_2) = v_1+v_2 = S(w_1) + S(w_2).$$
	Likewise,
	$$S(aw_1) = aw_1 = aS(w_1).$$
	We may now conclude that $T^{-1} = S$ and hence $T$ is invertible.  
\end{proof}




\section{The matrix of a linear transformation}\label{sec:linearmap_matrix}

In this section we study a striking connection between linear transformations and matrices.  In fact, we will see that linear transformations and matrices are really two sides of the same coin!  
Before beginning let us review the basics of matrix multiplication.  
Let $A = [\vec{a}_1\cdots \vec{a}_n]$ where $\vec{a}_i\in\R^m$, so that $A$ is an $m\times n$ matrix whose $i$th column is the vector $\vec{a}_i$.  For any $\vec{b}\in\R^n$ we define
$$A\vec{b} := [\vec{a}_1\cdots \vec{a}_n]\myvec{b_1\\\vdots\\b_n} = b_1\vec{a}_1 + \cdots + b_n \vec{a}_n.$$
So $A\vec{b}$ is the linear combintion of the columns of $A$ using the coefficients in $\vec{b}$.  
\begin{ex}
$$
\begin{bmatrix}
	1&4&5\\
	2&3&6
\end{bmatrix}\myvec{a\\b\\c} = a\myvec{1\\2}+b\myvec{4\\3}+c\myvec{5\\6}$$
\end{ex}
Moreover, if $B =  [\vec{b}_1\cdots \vec{b}_k]$ where each $\vec{b}_i\in \R^n$, then we define
$$AB = A[\vec{b}_1\cdots \vec{b}_k] = [A\vec{b}_1\cdots A\vec{b}_k],$$
so that the $i$th column of $AB$ is $A\vec{b}_i$. 

With this review under our belt, let us begin our study.  As usual, fix finite-dimensional $\F$-vector spaces  $V$ and $W$ with bases $\B=\{v_1,\ldots, v_n\}$  for $V$ and  $\Cc=\{w_1,\ldots, w_m\}$ for $W$.  

\begin{definition}
	For any $v\in V$, we define 
	$$[v]_{\B} = \myvec{b_1\\\vdots\\b_n}$$
	where $v =b_1v_1+\cdots + b_nv_n$.	We call this vector the \textbf{coordinates} of $v$ with respect to the basis $\B$.  
\end{definition}

The next fact follows directly from the definition of coordinates.  We leave its proof to the reader. 
\begin{lemma}[Linearity of Coordinates]
	For any $u,v\in V$ and $a,b\in \F$, we have 
	$$[au+bv]_{\B} = a[u]_{\B}+ b[v]_{\B}$$
\end{lemma}



Now fix $T\in\lin(V,W)$ and consider the action of $T$ on some $v\in V$. First let
$$[v]_{\B} = \myvec{b_1\\\vdots\\b_n}.$$
Now we see that
\begin{align*}
Tv &= T(b_1v_1+\cdots + b_nv_n)\\ 
&= b_1Tv_1+\cdots + b_nTv_n. 
\end{align*}  
As $Tv_i\in W$ and $\Cc$ is a basis for $W$ we must have 
$$Tv_i = b_{1i}w_1 +\cdots + b_{mi}w_m$$
for some scalars $b_{ij}\in \F$ where $1\leq i\leq m$ and $1\leq j\leq n$.  Solving for the coordinates of $Tv$ with respect to $\Cc$ we have

By the linearity of coordinates we now have
$$[Tv]_{\Cc} = [b_1Tv_1+\cdots + b_nTv_n]_{\Cc} =  b_1[Tv_1]_{\Cc} +\cdots + b_n[Tv_n]_{\Cc}.$$
If we set 
$$[Tv_i]_{\Cc} = \myvec{c_{1i}\\\vdots\\ c_{mi}}$$
then we see that 
\begin{align*}
[Tv]_{\Cc}&= b_1\myvec{c_{11}\\ \vdots\\ c_{m1}}+b_2\myvec{c_{12}\\ \vdots \\c_{m2}}+\cdots + b_n\myvec{c_{1n}\\ \vdots\\ c_{mn}}\\\\
&=\quad\begin{bmatrix}
	c_{11} & \cdots &c_{1n}\\
	\vdots & & \vdots \\
	c_{m1} & \cdots & c_{mn}
\end{bmatrix}\myvec{b_1\\\vdots\\ b_n}.
\end{align*}

This discussion proves the following theorem.

\begin{theorem}\label{thm:trans_as_matrix}
Fix $T\in\lin(V,W)$.  Then 
$$[Tv]_{\Cc	} = [T]_{\B}^{\Cc}\ [v]_{\B},$$
where $[T]_{\B}^{\Cc}$ is the matrix whose columns are $[Tv_i]_{\Cc}$.  That is 
$$[T]_{\B}^{\Cc} = \begin{bmatrix}
	c_{11} & \cdots &c_{1n}\\
	\vdots & & \vdots \\
	c_{m1} & \cdots & c_{mn}
\end{bmatrix}\quad\mbox{where}\quad [Tv_i]_{\Cc} = \myvec{c_{1i}\\\vdots\\c_{mi}}.$$

\end{theorem}

The reader should take note that $[T]_{\B}^{\Cc}$ is an $m\times n$ matrix and $T$ is a linear map from an $n$-dimensional space $V$ to an $m$-dimensional space $W$. 




	
	
 

Having developed this connection let consider the following concrete example.

\begin{exs}\ \\

\begin{enumerate}
	\item Define the linear map  
$$T:\R^3 \to \poly_{\leq 2}$$
by $T\left(\myvec{a\\b\\c}\right) = (a+b)x + (a+c)x^2$.  Now let 
$$\B=\left\{\myvec{1\\1\\0},\myvec{1\\0\\1},\myvec{0\\1\\1}\right\}$$ 
be our basis for $\R^3$ and take $\Cc=\{1,x,x^2\}$ as our basis for $\poly_{\leq 2}$. As
$$
T\left(\myvec{1\\1\\0}\right) = 2x+x^2, \quad
T\left(\myvec{1\\0\\1}\right) = x+2x^2, \quad
T\left(\myvec{0\\1\\1}\right) = x+x^2,
$$
we have 
$$[T]_{\B}^{\Cc} = \begin{bmatrix}
	0 & 0 & 0\\
	2 & 1& 1\\
	1& 2 & 1
\end{bmatrix}.$$   
Next, consider the vector $v=\myvec{3\\4\\5}\in\R^3$  so that $[v]_{\B} = \myvec{1\\2\\3}$.  By Theorem~\ref{thm:trans_as_matrix} we have
$$[Tv]_{\Cc} = \begin{bmatrix}
	0 & 0 & 0\\
	2 & 1& 1\\
	1& 2 & 1
\end{bmatrix} \myvec{1\\2\\3} = \myvec{0\\7\\8},$$
which is consistent as $Tv = 7x + 8x^2$.
\item For any $n$-dimensional vector space $V$, let $I:V\to V$ be the identity map.  If $\B$ is any basis for $V$, the reader should check that 
$$[I]_{\B}^{\B} = \begin{bmatrix}
 1 & & 0\\
 &\ddots &\\
 0 && 1	
 \end{bmatrix}$$
 where the matrix on the right has size $n\times n$.  For obvious reasons this matrix is often called the \textbf{identity} matrix and is denoted  by $I_n$.  
\end{enumerate}

\end{exs}


 In the past, you may have wondering why matrix multiplication is defined in the way it is.   Why not just multiply corresponding entries? Why is this definition so great?  We are now in a position to answer this question!   Consider our next theorem.

\begin{theorem}\label{thm:matrix_mult}
Let $U$ be another finite-dimensional vector space with basis $\D$.  For any $T\in\lin(V,W)$ and $S\in\lin(W,U)$, we have
$$[ST]_{\B}^{\D}  =[S]_{\Cc}^{\D} \cdot [T]_{\B}^{\Cc}$$
where the operation $\cdot$ on the left is the usual matrix multiplication.  
\end{theorem}

In other words, matrix multiplication is precisely the operation needed in order to obtain the matrix $[ST]_{\B}^{\D}$ from the matrices $[S]_{\Cc}^{\D}$ and $[T]_{\B}^{\C}$.  Another way to look at this is that composition of functions on the linear transformation side corresponds to matrix multiplication on the matrix side.  Let us now prove this pretty result.  

\begin{proof}
	To simplify notation let us denote $[T]_{\B}^{\Cc}$ by $[T]$ and $[S]_{\Cc}^{\D}$ by $[S]$.   Theorem~\ref{thm:trans_as_matrix} tells us that 
	$$[STv_i]_{\D} = [S][Tv_i]_{\Cc}.$$
	As $ST\in\lin(U,W)$, then
	$$[ST]_{\B}^{\D} = \Big[[STv_1]_{\D}\cdots [STv_n]_{\D}\Big]= \Big[[S][Tv_1]_{\Cc}\cdots [S][Tv_n]_{\Cc}\Big]	 = [S][T],$$
	where the last equality is our definition of matrix multiplication.   
\end{proof}


%\begin{definition}
%	We say an $n\times n$ matrix $A$ is \textbf{invertible} provided there exists another $n\times n$ matrix $B$ so that 
%	$$AB = I_n = BA.$$
%	The matrix $B$ is called an inverse of $A$.
%\end{definition}
%
%\begin{lemma}
%	If $A$ is invertible, then its inverse is unique.  Moreover, we denote this unique matrix by $A^{-1}$.  
%\end{lemma}
%
%
%\begin{lemma}
%	If $T:\lin(V,W)$ is an isomorphism of vector spaces, then $[T]_{\B}^{\Cc}$ is invertible.   
%\end{lemma}

We are now in a position to answer our last fundamental question regarding this correspondence between linear transformations and matrices.  Assume $\B'$ and $\Cc'$ are also bases for $V$ and $W$ respectively.  For any $T\in\lin(V,W)$ how are the matrices $[T]_{\B}^{\Cc}$ and $[T]_{\B'}^{\Cc'}$ related to each other?

\begin{theorem}[Change of Basis]
	$$[T]_{\B'}^{\Cc'} = [J]_{\Cc}^{\Cc'}\ [T]_{\B}^{\Cc}\ [I]_{\B'}^{\B},$$  
	where $J$ and $I$ are the identity maps on $V$ and $W$ respectively.  
\end{theorem}
\begin{proof}
	Certainly we have the following equality
	$$T = J T I.$$
	Several applications of Theorem~\ref{thm:matrix_mult} now yields
$$
[T]_{\B'}^{\Cc'} = [J T I]_{\B'}^{\Cc'}= [J]_{\Cc}^{\Cc'}\  [TI]_{\B'}^{\Cc} = [J]_{\Cc}^{\Cc'}\ [T]_{\B}^{\Cc}\ [I]_{\B'}^{\B}.	
$$
\end{proof}


You might be mislead into thinking that $[I]_{\B'}^{\B}$ must be the identity matrix since $I$ is the identity map plus we know this to be true when $\B=\B'$ (see Example 2 above).  The following simple example shows that this is NOT generally true.  Consider the identity map $I:\R^3 \to \R^3$ where $\B'$ is the standard basis and $\B=\left\{\myvec{1\\1\\0},\myvec{1\\0\\1},\myvec{0\\1\\1}\right\}$.  Since 
$$
	e_1 = \frac{1}{2}\left(\myvec{1\\1\\0}+\myvec{1\\0\\1}-\myvec{0\\1\\1}\right),\quad  e_2 = \frac{1}{2}\left(\myvec{1\\1\\0}-\myvec{1\\0\\1}+\myvec{0\\1\\1}\right),$$
and
$$e_3 = \frac{1}{2}\left(-\myvec{1\\1\\0}+\myvec{1\\0\\1}+\myvec{0\\1\\1}\right)$$
We see that 
$$[I]_{\B'}^{\B} =\Big[[e_1]_{\B}\ [e_2]_{\B}\ [e_3]_{\B}\Big]= \begin{bmatrix}
	1/2 & 1/2 &-1/2 \\
	1/2 &-1/2 & 1/2 \\
	-1/2 & 1/2 & 1/2 \\
\end{bmatrix}$$
is certainly not the identity matrix.  We hope this example dispels any possible confusion. 
















\chapter{Complex operators}
In this chapter we study linear transformations that map a vector space $V$ into itself. Such maps, formally called operators, are the foundation for a rich theory.  This chapter aims to provide an introduction to this theory.
    
\section{Operators \& polynomials}


\begin{definition}
	We call a linear map $T$ from $V$ to $V$ an \textbf{operator}.  If $V$ is a complex vector space we say $T$ is a \textbf{complex operator}. Likewise, if $V$ is a real vector space we say $T$ is a \textbf{real operator}.  We denote the set of operators $\lin(V)$ instead of $\lin(V,V)$. 
\end{definition}


As the domain and range of an operator $T\in\lin(V)$ is the same, we may compose such function with themselves an arbitrary number of times.  In particular, we write
$$T^i = \underbrace{TT\cdots T}_{i},$$
for integers $i>0$ and define $T^0=I_V$ to be the identity map on $V$. If $p(x) = a_0 + a_1x+\cdots a_nx^n$ is any polynomial with coefficients in $\F$ we  define the function  $p(T):V\to V$ given by
$$p(T)u = a_0u + a_1Tu + \cdots + a_nT^nu,$$ 
for any $u\in V$.  A straightforward check, which we leave to the reader, shows that $p(T)$ is an operator. For example consider the operator $T:\C\to \C$ given by 
$$T\left(\myvec{a\\b}\right) =\myvec{2a\\3b}.$$ 
If $p(x) = 2+3x+x^2$, then 
\begin{align*}
p(T)\myvec{a\\b} = (2+3T+T^2)\myvec{a\\b} &= 2\myvec{a\\b} + 3T\myvec{a\\b} + T^2\myvec{a\\b}\\
&= \myvec{2a\\2b} + 3\myvec{2a\\3b}+\myvec{4a\\9b}\\
&= \myvec{12a\\20b}.
\end{align*}
Continuing in this vain we note that if $f(x), g(x)$, and $h(x)$ are polynomials such that $f(x) = g(x)h(x)$, then $f(T) = g(T)h(T)$.  We encourage the reader to check this fact for themselves.  Moreover, since $f(x) = g(x)h(x) = h(x)g(x)$ we see that 
\begin{equation}\label{eq:poly_commute}
g(T)h(T) = h(T)g(T).	
\end{equation}

Returning to the example above, observe that $p(x) = (1+x)(2+x)$.  Computing we obtain
\begin{align*}
p(T)\myvec{a\\b} = (1+T)(2+T)\myvec{a\\b} &= (1+T)\left(2\myvec{a\\b}+\myvec{2a\\3b}\right)\\
&= (1+T)\myvec{4a\\5b}\\
&= \myvec{4a\\5b} +  \myvec{8a\\15b} = \myvec{12a\\20b},
\end{align*}
which agrees with our computation above.  The reader is encouraged to check that one gets the same answer by computing 
$$(2+T)(1+T)\myvec{a\\b}.$$

For the remainder of this section we review some basic facts about polynomials that will be needed throughout the remainder of this chapter. We start with one of the most famous theorems in algebra.  

\begin{theorem}(Fundamental Theorem of Algebra)
Every non-constant $p(z)\in \poly(\C)$ has at least one root.  Consequently, $p(z)$ factors completely into linear terms as
$$p(z) = a(z-\lambda_1)\cdots(z-\lambda_n),$$
for some $c,\lambda_i\in \C$.  \end{theorem}

Recall that for integers $a,b$, we say $a$ divides $b$, and write $a|b$ provided there exists some integer $c$ such that $b=ac$.  We now give an analogous definition for polynomials.


\begin{definitions}
	For polynomials $p(x),q(x)$ we say $q(x)$ \textbf{divides} $p(x)$  and write $q(x) | p(x)$, provided there exists some polynomials $s(x)$ such that $p(x) = q(x)s(x)$. 
	
	We define the \textbf{greatest common divisor} or \textbf{GCD} of $p(x)$ and $q(x)$ to be the monic polynomials of greatest degree, written $(p,q)$, that divides both $p$ and $q$. We can easily extend this definition to  a finite number of polynomials $p_1,\ldots, p_k$ by defining their GCD $(p_1,\ldots, p_k)$ to be the monic polynomials of largest degree that divides each $p_i$.   
	
	Lastly, we say $p_1,\ldots, p_k$ are \textbf{relatively prime} provided their GCD is 1.  
\end{definitions}

For example, observe that $x-1 | x^3-1$ since $(x-1)(x^2+x+1) = x^3-1$.  We also have that that the polynomials $(x-a)^n$ and $(x-b)^m$ are relatively prime provided $a\neq b$ and if $a=b$ then  their GCD is $(x-a)^k$, where $k = \min(n,m)$.

The next lemma, whose proof can be readily found in many algebra books, will serve as a critical ingredient in Section~\ref{sec:generlized_eigenvectors}.

\begin{lemma}[B\'ezout]
	Let $p_1(x),\ldots, p_k(x)\in\poly(\C)$ with GCD $d(x)$.  Then there exists polynomials, $a_1(x),\ldots, a_k(x)\in\poly(\C)$ such that 
	$$a_1(x)p_1(x)+\cdots + a_k(x)p_k(x) = d(x).$$
\end{lemma}

%For example, if $p_1(x) = (x-1)(x-2)$, $p_2(x) = (x-3)(x-4)$, then their GCD is 1, i.e., they are relatively prime.  As guaranteed by B\'ezout's lemma we have 
%$$1 = (x-1)(x-2) - (x-3)(x-4)$$


  


 
  
\section{Eigenvectors \& eigenvalues}\label{sec:eigenvalues}
%With the preliminaries out of the way, we now  begin studying the ``structure" of complex operators. At first this may seem incredibly open-ended.  Where does one even start?  By analogy, recall that in Number Theory one studies integers by decomposing them into prime numbers.  Our approach in this context will be similar -- we study how complex operators, in general, ``decompose" into smaller operators.   In light of this the following definition is a good place to start.  

\begin{definition}
	Let $T\in \lin(V)$.  We say a subspace $U$ of $V$ if \textbf{$T$-invariant} provided that $T(U) =\makeset{Tu}{u\in U}\subseteq U$.  
\end{definition}

The utility of this definition is that if $U$ is $T$-invariant, then we can restrict $T$ to the ``smaller" linear map
$$T:U\to U.$$



A particularly, important $T$-invariant subspace is given by the following definition.   

\begin{definition}
	Let $T\in \lin(V)$.  A scalar $\lambda\in\F$ is said to be an \textbf{eigenvalue}, if there is a nonzero vector $v\in V$,  such that 
	$$Tv = \lambda v.$$
	In this case, we say $v$ is an \textbf{eigenvector} for $\lambda$ and refer to the tuple $(\lambda,v)$ as an \textbf{eigenpair} for $T$.    
\end{definition}
Observe that if $(\lambda,v)$ is an eigenpair for $T$ then $\spn(v)$ is $T$-invariant and
$$T:\spn(v) \to \spn(v)$$ 
is given by multiplication by $\lambda$. Geometrically, this means that along the line generated by $v$, i.e., $\spn(v)$, $T$ acts by simply stretching the line by a factor of $\lambda$ as if the line were made of rubber.    To illustrate consider the following picture where the dashed line is $\spn(v)$.
 

\begin{center}
\begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt}]



\begin{scope}[shift={(0,0)}]
		\draw [dashed] (-2.5,-1.25) --(2.5,1.25);
%		\draw[black,fill=black] (0,0) circle (.5mm);
%		\node[below] at (0,0) {$0_V$};
	  \node[ele,label=below:$0_V$] at (0,0) {}; 
		\draw [red,->,thick] (0,0) -- (2,1) node[black,below] {$\lambda v$};	
		\draw [blue,->,thick] (0,0) -- (1,.5) node[black,midway, above] {$v$};	
		\draw[black] (0,0) ellipse (4cm and 2cm);
		\node at (-1.5,1) {$V$};
\end{scope}

\end{tikzpicture}	
\end{center}
The significance of this is that although $T$ may be wildly complicated in general, the existence of an eigenpair $(\lambda,v)$ means that at least in the $v$ direction $T$ acts in a very simple way -- it just stretches the line by a factor of $\lambda$. 

\begin{exs}\ \\
\begin{enumerate}
	\item For the identity operator, $I_V$, every nonzero vector $v$ is an eigenvector with corresponding eigenvalue $1$.  What are the eigenvalues/vectors for the zero map on $V$?  
	\item Let $A=\begin{bmatrix}
		2&0\\
		0&-1
	\end{bmatrix}$.  As an operator $A:\R^2\to\R^2$ we see (by inspection) that 
	$$\left(2,\myvec{1\\0}\right)\quad\mbox{and}\quad\left(-1,\myvec{0\\1}\right)$$  
	are its two eigenpairs.  

	\item Now define the operator $T$ on $\R^2$ by $T\left(\myvec{x\\y}\right) = \myvec{x+2y\\ 4y-x}$. Unlike the previous example, it is a bit harder to just spot the eigenpairs for this operator.  Instead, let us appeal to some simple algebra.  We seek values $x,y$ and $\lambda$ such that
$$ \myvec{x+2y\\ 4y-x} = \lambda\myvec{x\\y}.$$
Equating the first and second coordinates we obtain two equations:
\begin{equation}
x+2y = \lambda x \qquad\mbox{and}\qquad 4y-x =\lambda y.\tag{$\star$}
\end{equation}


Using the second equation to obtain an expression for $x$ we then plug this expression into the first equation to obtain (after simplifying) 
\begin{equation}
0=y(\lambda^2 -5\lambda +6)=y(\lambda-3)(\lambda-2).
\end{equation}

Therefore $y=0$ or $\lambda = 3,2$.  We see from above that when $y=0$,  $x$ is also $0$.  Since the zero vector cannot be an eigenvector we are not interested in this solution.   If $\lambda = 2$, then solving $(\star)$ yields $x=2, y=1$.  Hence $\left(2,\myvec{2\\1}\right)$ is an eigenpair for $T$.  Likewise, when $\lambda =3$, we get the eigenpair $\left(3,\myvec{1\\1}\right)$.  

\item Let $T$ be the operator on the space of continuous function $\cts(\R)$ given by 
$$Tf = \int f(x)\ dx.$$
Now consider the function $e^{\lambda x }$ with $\lambda\neq 0$.  Since 
$$T(e^{\lambda x }) = \int e^{\lambda x }\ dx = \frac{1}{\lambda} e^{\lambda x }$$
we see that $\left(\frac{1}{\lambda}, e^{\lambda x }\right)$ is an eigenpair for this operator.  
\end{enumerate}

\end{exs}
 



\begin{lemma}
	Let $T\in \lin(V)$ and $\lambda\in\F$.  Then the nonzero vectors in $\nul(T-\lambda)$ are precisely the eigenvectors for $T$ corresponding to $\lambda$. 
\end{lemma}
\begin{proof}
	To prove this lemma we must show that $0_V\neq v\in\nul(T-\lambda)$ if and only if  $(\lambda,v)$ is an eigenpair for $T$.  This follows directly from the definitions involved.  In particular, we have 
	\begin{align*}
		0_V\neq v\in\nul(T-\lambda) &\Leftrightarrow (T-\lambda)v = 0_V \mbox{ and } v\neq 0_V\\
		&\Leftrightarrow Tv-\lambda v = 0_V \mbox{ and } v\neq 0_V\\
		&\Leftrightarrow Tv = \lambda v \mbox{ and } v\neq 0_V\\
		&\Leftrightarrow (\lambda, v) \mbox{ is an eigenpair for } T.
	\end{align*}

\end{proof}
We first remark that a straightforward consequence of this lemma is that $\lambda$ is an eigenvalue for $T$ if and only if $\nul (T-\lambda)$ is not trivial.  

This lemma also suggests that the subspace $\nul(T-\lambda)$ is intimately connected to the eigenvectors for $\lambda$. As such, it makes sense to formally name this subspace.  

\begin{definition}
Let $T\in\lin(V)$ and $\lambda\in\F$ be an eigenvalue for $T$.  Then $\nul(T-\lambda)$ is called the \textbf{eigenspace} of $T$ corresponding to $\lambda$.    
\end{definition}






\begin{theorem}\label{thm:eigenvectors_exist}
	Let $T\in \lin(V)$.  Suppose $\lambda_1,\ldots, \lambda_m$ are distinct eigenvalues of $T$ with corresponding eigenvectors $v_1,\ldots, v_m$.  Then the vectors $v_1,\ldots, v_m$ are linearly independent.  
\end{theorem}
\begin{proof}
	Let $a_i$ be scalars such that 
	$$a_1v_1+\cdots + a_mv_m = 0_V.$$
Next define the new operator
	$$T_j = (T-\lambda_1)\cdots (T-\lambda_{j-1})(T-\lambda_{j+1})\cdots (T-\lambda_m).$$  
	As we can write the factors of $T_j$ in any order, it follows that  $T_jv_i = 0_V$, provided $i\neq j$.  Next we determine the value of $T_jv_j$.  To compute this, first observe that
	$$(T-\lambda_k)v_j = Tv_j -\lambda_k v_j = \lambda_jv_j-\lambda_k v_j = (\lambda_j-\lambda_k)v_j.$$
	Using this repeatedly, we obtain
	\begin{align*}
T_jv_j &=  (T-\lambda_1)\cdots (T-\lambda_{j-1})(T-\lambda_{j+1})\cdots (T-\lambda_m)v_j\\
&= \underbrace{(\lambda_j-\lambda_1)\cdots (\lambda_j-\lambda_{j-1})(\lambda_j-\lambda_{j+1})\cdots(\lambda_j-\lambda_m)}_{\Lambda}v_j.
	\end{align*}
	It now follows that  
$$0_V= T_j(a_1v_1+\cdots + a_mv_m)=a_j\Lambda v_j.$$
	As our eigenvalues are distinct, then $\Lambda\neq 0$. Dividing through by $\Lambda$ now yields $0_V = a_jv_j$.  Therefore $a_j=0$, since $v_j$ is an eigenvector and cannot be the zero vector.  As $j$ was arbitrary, this shows that all our scalars must indeed be zero, completing our proof.  
\end{proof}


\begin{corollary}
	Any operator on a finite-dimensional vector space $V$ has at most    $\dim V$ distinct eigenvalues.  
\end{corollary}
\begin{proof}
	If $V$ has dimension $n$, then any set of linearly independent vectors must have at most $n$ vectors.  The result now follows immediately from the preceding theorem.  
\end{proof}


What can we say if $T$ has exactly $\dim V$ linearly independent eigenvectors.  In fact, we can say a lot!   To motivate consider the operator $T$ on $\R^3$ given by $T\left(\myvec{a\\b\\c}\right) = \myvec{a+2b\\ 4b-a\\ 3c}$.  Straightforward calculations show that  $T$  has eigenpairs 
$$\left(2,\myvec{2\\1\\0}\right),\quad \left(3,\myvec{1\\1\\0}\right)\myand \left(3,\myvec{0\\0\\1}\right),$$
where we denote the $i$th vector by $v_i$.  In other words, $T$ simply stretches the lines given by $v_1$, $v_2$, and $v_3$ as shown in the following illustration.
\begin{center}
\begin{tikzpicture}
\tdplotsetmaincoords{60}{100}
\begin{scope}[shift={(0,0)},
		axis/.style={->,black},
		tdplot_main_coords,
		vector/.style={-stealth,blue,},
		vector guide/.style={dashed,red}]
	
%draw the axes
	\draw[axis] (0,0,0) -- (4,0,0) node[anchor=west]{$x$};
	\draw[axis] (0,0,0) -- (0,3,0) node[anchor=west]{$y$};
	\draw[axis] (0,0,0) -- (0,0,4) node[anchor=west]{$z$};
	
	
	%standard tikz coordinate definition using x, y, z coords
	\coordinate (O) at (0,0,0);
	\coordinate (v1) at (2,1,0);
	\coordinate (v2) at (1,1,0);
	\coordinate (v3) at (0,0,1);
	
	\coordinate (Tv1) at (4,2,0);
	\coordinate (Tv2) at (3,3,0);
	\coordinate (Tv3) at (0,0,3);


	\coordinate (e1) at (5,2.5,0);
	\coordinate (e2) at (4,4,0);
	\coordinate (e3) at (0,0,2);			
	
	%tikz-3dplot coordinate definition using r, theta, phi coords
	\tdplotsetcoord{P}{3}{40}{45}
	
	%draw a vector from O to P
	\draw[dashed] (O) -- (e1);
	\draw[dashed] (O) -- (e2);
	
	\draw[vector, thick,red] (O) -- (Tv1) node[right,black] {$Tv_1$};
	\draw[vector, thick,red] (O) -- (Tv2) node[right, black] {$Tv_2$};
	\draw[vector, thick,red] (O)-- (Tv3) node[left, black] {$Tv_3$};
	
	\draw[vector, thick] (O) -- (v1) node[right,black] {$v_1$};
	\draw[vector, thick] (O) -- (v2) node[right, black] {$v_2$};
	\draw[vector, thick] (O)-- (v3) node[left, black] {$v_3$};
	

\end{scope}
\end{tikzpicture}	
\end{center}


%\begin{center}
%\begin{tikzpicture}
%\draw[-stealth, thick](-3,0)--(3,0) node[below]{$x$};
%\draw[-stealth, thick](0,-2)--(0,2) node[left]{$y$};
%
%
%\draw [dashed] (-3,-1.5) --(3,1.5);
%\draw [blue,->,thick] (0,0) -- (2,1) node[black,midway, above] {};
%
%\draw [dashed] (-2,-2) --(2,2);
%\draw [red,->,thick] (0,0) -- (1,1) node[black,midway, above] {};
%
%\draw (1,.1) -- (1,-.1) node[below] {1};
%\draw (2,.1) -- (2,-.1) node[below] {2};
%\draw (.1,1) -- (-.1,1) node[left] {1};	
%
%
%\end{tikzpicture}	
%\end{center}
Since that these three eigenvectors are linearly independent, they form a basis  $$\B=\left\{\myvec{2\\1\\0},\myvec{1\\1\\0},\myvec{0\\0\\1}\right\}$$ for $\R^3$.  Consequently, $T$ is completely determined by these eigenvectors. Moreover, observe that 
$$[T]_{\B} = \begin{bmatrix}
	2&0&0\\
	0&3&0\\
	0&0&3
\end{bmatrix}.$$


As we have just seen, operators that have ``enough" eigenvectors are easy to understand -- they essentially just stretch space.  Such operators also have a very nice description in terms of their matrix representations as described by our last theorem.  We leave the details to the reader.  

\begin{definition}
	Let $T$ be any operator on an $\F$-vector space.  We say $T$ is \textbf{diagonalizable} provided there exists a basis $\B$ for $V$ such that $[T]_{\B}$ is a diagonal matrix, i.e., 
	$$[T]_{\B} = \left[\begin{array}{cccc}
		\lambda_1 & 	  &       \multicolumn{2}{c}{\multirow{2}{*}{\huge $0$}}\\
		    & \lambda_2 &       &	 \\
	\multicolumn{2}{c}{\multirow{2}{*}{\huge $0$}}	  & \ddots & \\
	&  &		  & \lambda_n			     
	\end{array}\right],$$
	for some scalars $\lambda_1,\ldots, \lambda_n\in \F$.  
\end{definition}


\begin{theorem}\label{thm:diagonlize}
	Let $T\in \lin(V)$.  Then $T$ is diagonalizable if and only if $V$  has a basis consisting entirely of eigenvectors for $T$.  
\end{theorem}





We now turn our attention to the following question:  When do operators have eigenvectors?  We would hope that all operators have eigenvectors but, as the next example shows, this is unfortunately not true!  To illustrate such an operator consider $T\in\lin(\R^2)$ given by $T(x,y) = (-y,x)$.  If $T$ had eigenvectors, then we would be able to find values $x$, $y$, and $\lambda$ such that
\begin{equation}
(-y,x) =  T(x,y) = \lambda(x,y)\tag{$\star$}	
\end{equation}
Equating the first and second coordinates yields
$$-y = \lambda x \qquad\mbox{and}\qquad x =\lambda y.$$
Combining we obtain $y(\lambda^2+1) = 0$.  Since $y=0$ cannot be a solution (why?) and the equation
\begin{equation}
(\lambda^2+1) = 0\tag{$\dagger$}	
\end{equation}
has no real solutions, we conclude that $T$ has no eigenvectors.  

As you might already suspect, what if we work over $\C$ instead of over $\R$?  In that case, the equation $(\dagger)$ has a solution, namely, $\lambda=\pm i$. If we indeed do this by considering $T$ as an operator on $\C^2$ then we obtain the eigenpairs:
 $$\left(i, (i,1)\right)\myand \left(-i, (-i,1)\right),$$
 since 
 $$T(i,1) = (-1, i) = i(i,1)\myand T(-i,1) = (-1, -i) = -i(-i,1).$$

More generally, since polynomials always have roots over $\C$, then it stands to reason that any complex operator should have at least one eigenvector.  Not only does the next theorem assert this but its proof relies solely on  the Fundamental Theorem of Algebra! 


\begin{theorem}\label{thm:EigenvectorsExist}
	Every operator $T$ on a non-trivial finite-dimensional complex vector space $V$ has at least one eigenvalue.  
\end{theorem}
\begin{proof}
	Set $n=\dim V$ and fix any nonzero vector $u\in V$.  Now consider the $n+1$ vectors 
	$$u, Tu,\ldots, T^n u.$$
	As the dimension of $V$ is $n$, these $n+1$ vectors must be dependent and so there exists scalars $a_i\in\C$ not all zero such that
	\begin{align*}
		0_V &= a_0u + a_1Tu + \cdots + a_nT^nu\\
		&=	(a_0 + a_1T + \cdots + a_nT^n)u\\
		&= p(T)u,
	\end{align*}
	where $p(z) = a_0 + a_1z + \cdots + a_nz^n$.   Let $m$ be the largest index such that $a_m\neq 0$.  As $u$ is a nonzero vector we must have $0<m\leq n$.  In particular, $p(z)$ is a nonconstant polynomial.  By the Fundamental Theorem of Algebra $p(z)$ factors as $p(z) = a_m(z-\lambda_1)(z-\lambda_2)\cdots(z-\lambda_m)$, where $\lambda_1,\ldots,\lambda_m\in\C$. 
	Plugging this into the above equation yields, 
	$$0_V = a_m(T-\lambda_1)(T-\lambda_2)\cdots(T-\lambda_m)u.$$
It now follows that one of the factors $(T-\lambda_i)$ must have a nontrivial null space.  In other words, $\lambda_i$ is an eigenvalue for $T$.  
\end{proof}








The above theorem only guarantees that a complex operator has at least one eigenvalue.  It does not guarantee that we have lots of distinct eigenvalues, say $\dim V$ of them!  To see an example of this, consider the matrix $A=\begin{bmatrix}
	0&1\\
	0&0
\end{bmatrix}$ thought of as an operator
 $A:\C^2\to \C^2$.  To find its eigenpairs we set up the usual eigenvector/value equation
 $$\myvec{w\\0}=A\myvec{z\\w} = \lambda\myvec{z\\w},$$
 to obtain the equations  $w = \lambda z$ and $0 = \lambda w$.  We see that the only eigenpairs for $A$ are $\left(0, \myvec{z\\0}\right)$ where $z\neq 0$.  Additionally, this example demonstrates that complex operators may not even have $\dim V$ linearly independent eigenvectors.  (In this case all the eigenvectors for $A$ are multiplies of $(1,0)$.)  This means, thanks to Theorem~\ref{thm:diagonlize}, that not every complex-operator is diagonalizable.  
 
 That said, all is not lost!  The next theorem demonstrates that, for the right choice of basis, every complex operator can be represented by an ``upper-triangular" matrix.  We start with a few definitions.  

\begin{definition}
	Let $T\in\lin(V)$.  We say an  basis $\B=\{v_1,\ldots,v_n\}$ for $V$ is \textbf{$T$-triangularizing} provided that 
	$$Tv_k \in \spn(v_1,\ldots, v_k),$$
	for each $k\leq n$.  
\end{definition}

The next definition and lemma reveal why the term ``triangularizing" is used. 

\begin{definition}
	We say a square matrix $M$ is  \textbf{upper triangular} provided it is of the form
	$$\left[\begin{array}{cccc}
		\lambda_1 & 	  &       \multicolumn{2}{c}{\multirow{2}{*}{\huge $*$}}\\
		    & \lambda_2 &       &	 \\
			\multicolumn{2}{c}{\multirow{2}{*}{\huge $0$}}	  & \ddots & \\
			&	  &		  & \lambda_n			     
	\end{array}\right],$$
	so that the values weakly above the diagonal are arbitrary (indicated by the $*$) but the values  strictly below the diagonal must be zero.  
\end{definition}


\begin{lemma}
Let $T$ be an operator on $V$ with  basis $\B=\{v_1,\ldots,v_n\}$.  Then the following are equivalent.
\begin{enumerate}[label=(\alph*)]
	\item The basis $\B$ is $T$-triangularizing.
	\item For all $k\leq n$, the subspaces $\spn(v_1,\ldots, v_k)$ are $T$-invariant.
	\item The matrix $[T]_{\B}$ is upper triangular.
\end{enumerate}
\end{lemma}
\begin{proof}\ \\
{\tt Case:} (a) $\Rightarrow$ (b)

\medskip	
Assume $\B$ is $T$-triangularizing and fix $k\leq n$.   Now for any $i\leq k$ we have
$$Tv_i\in \spn(v_1,\ldots,v_i)\subset \spn(v_1,\ldots,v_k).$$
To see that this implies $T$-invariance, consider an arbitrary $u\in \spn(v_1,\ldots, v_k)$. We know that $u = a_1v_1+\cdots+a_kv_k$ for some scalars $a_i$.  Thus
$$Tu = T(a_1v_1+\cdots+a_kv_k) = a_1Tv_1+\cdots+a_kTv_k\in \spn(v_1,\ldots,v_k),$$
where the last step follows since subspaces are closed under linear combinations. This shows  $\spn(v_1,\ldots,v_k)$ is $T$-invariant.

\bigskip

{\tt Case:} (b) $\Rightarrow$ (c)

\medskip	

Assume $\spn(v_1,\ldots,v_k)$ is $T$-invariant for each $k\leq n$.  
To show that 
$$[T]_{\B}=\{[Tv_1]_{\B} \cdots[Tv_k]_{\B}\cdots [Tv_n]_{\B} \}$$ 
is upper triangular, it will suffice to show that the bottom $n-k$ rows of the $k$th column $[Tv_k]_{\B}$ are all zeros.  To see this, observe that $Tv_k\in \spn(v_1,\ldots, v_k)$, as $\B$ is $T$-triangularizing.  This means there exists scalars $a_1,\ldots, a_k$ so that
$$Tv_k = a_1v_1+\cdots + a_kv_k+0v_{k+1}+\cdots + 0v_n.$$
Hence the coordinates of this vector and hence the $k$th column of our matrix is 
$$[Tv_k]_{\B} = \myvec{a_1\\ \vdots \\ a_k \\ 0 \\ \vdots \\ 0}\raisebox{5pt}{$\leftarrow k\mbox{th row}$}.$$
As the bottom $n-k$ rows are indeed all zero, we conclude that $[T]_{\B}$ is upper triangular.  

\bigskip

{\tt Case:} (c) $\Rightarrow$ (a)

\medskip

In this case we know that $[T]_{\B}$ is an upper triangular of the form
	$$\begin{bmatrix}
a_{1,1} & a_{1,2} & a_{1,3} & \ldots & a_{1,n}  \\
        & a_{2,2} & a_{2,3} & \ldots & a_{2,n}  \\
        &         & a_{3,3}  &  &    \\
        &		&	& \ddots & \vdots\\
  0     &         &         &        & a_{n,n}
\end{bmatrix}.$$
We must show that $Tv_k\in \spn(v_1,\ldots, v_k)$.  To do this lets consider the coordinates of $Tv_k$ (with respect to $\B$) first.  
$$[Tv_k]_{\B} = [T]_{\B}\ [v_k]_{\B} = [T]_{\B}\ \mathbf{e}_k = \myvec{a_{1,k}\\ \vdots \\ a_{k,k}\\ \vdots \\ 0},$$
where the first equality follows from Theorem~\ref{thm:trans_as_matrix} and $\mathbf{e}_k$ is the $k$th standard vector.  By definition we thus have
$$Tv_k = a_{1,k}v_k + \cdots + a_{k,k}v_k\in \spn(v_1,\ldots, v_k).$$  So $\B$ is $T$-triangularizing as needed.
\end{proof}




\begin{theorem}
	Let $T$ be a complex operator on $V$.  Then there exists a $T$-triangularizing basis $\B$ for $V$. 
\end{theorem}
\begin{proof}
	We proceed by induction on $\dim V$.  The result is clear when $\dim V =1$ since basis in this case is $T$-triangularizing. 
	
Now let $T$ be an operator on an $n>1$ dimensional space $V$.  By Theorem~\ref{thm:EigenvectorsExist}, we know there exists some eigenpair $(\lambda,v_1)$ for $T$. As $v_1$ is nonzero (why?) then we can extend this single vector to a basis  $\{v_1, u_2, \ldots, u_n\}$ for all of $V$.  Set $U = \spn(u_2,\ldots, u_n)$.  Observe $\dim U = n-1$ and $v_1\notin U$.  Next, define the function $S:U\to U$ by
	$$Su = a_2u_2 + \cdots a_nu_n$$
	where $Tu = a_1v_1+a_2u_2 + \cdots +a_nu_n$.  A straightforward check shows that $S$ is indeed an operator.  By induction we know that $U$ has a $S$-triangularizing basis $\B_U=\{v_2,\ldots, v_n\}$.  
	
	We now claim that 
	$$\B= \{v_1\}\cup\{v_2,\ldots, v_n\}$$
	is a $T$-triangularizing basis for all of $V$.  Certainly, $\B$ is a basis for $V$ as it is linearly independent (why?) and $|\B| =n =\dim V$.    
It only remains to  see that $\B$ is $T$-triangularizing.  When $k=1$, we see that  $Tv_1=\lambda v_1\in \spn(v_1)$, since $(\lambda,v_1)$ is an eigenpair for $T$.  

For $k\geq 2$ we observe that as $\B_U$ is $S$-triangularizing, then $$Sv_k \in \spn(v_2,\ldots,v_k)$$
	where $Tv_k = a_1v_1+Sv_k$.  So, $Tv_k \in \spn(v_1,\ldots, v_k)$. This concludes our proof.
\end{proof}

%\begin{lemma}
%	Let $T$ be an operator on a finite-dimensional vector space $V$ with $T$-triangularizing basis $\B$.  Then $T$ is not injective if and only if there is at least one zero on the diagonal in $[T]_{\B}$.  
%\end{lemma}
%
%\begin{proof}
%To set notation let $\B=\{v_1,\ldots,v_n\}$ and 
%$$
%[T]_{\B} =	 \begin{bmatrix}
%a_{1,1} & a_{1,2} & a_{1,3} & \ldots & a_{1,n}  \\
%        & a_{2,2} & a_{2,3} & \ldots & a_{2,n}  \\
%        &         & a_{3,3}  &  &    \\
%        &		&	& \ddots & \vdots\\
%  0     &         &         &        & a_{n,n}
%\end{bmatrix}
%$$
%so that $Tv_k = a_{1,k}v_1 + \cdots + a_{k,k}v_k$. First, assume $a_{k,k}=0$ for some $k$.  As $\B$ is $T$-triangularizing we know that   
%$$T v_i = Tv_i \in \spn(v_1,\ldots,v_i)\subset \spn(v_1,\ldots,v_k),$$
%provided $i<k$.  When $i=k$, we see that
%$$Tv_k = a_{1,k}v_1 + \cdots + a_{k-1,k}v_{k-1} \in \spn(v_1,\ldots, v_{k-1}),$$
%since $a_{k,k} = 0$.  Consequently, $T$ maps the space $\spn(v_1,\ldots, v_k)$ into the space $\spn(v_1,\ldots, v_{k-1})$.  In other words, we have a (resticted) map
%$$T:\spn(v_1,\ldots, v_k) \to \spn(v_1,\ldots, v_{k-1}),$$
%from a $k$-dimensional space to a $k-1$-dimensional space.   By Corollary~\ref{cor:ranknullity} we see that $T$ is not injective.  
%
%For the other direction, assume $T$ is not injective and let $v\neq 0_V$ be such that $Tv =0_V$.  (Why must such a $v$ exist?)  For a contradiction assume $0$ does not lie on the diagonal of $[T]_{\B}$.  It now follows that the columns of $[T]_{\B}$ are linearly independent.  This implies that 
%$$\vec{0}=[0_V]_{\B} =[Tv]_{\B} = [T]_{\B}[v]_{\B}$$
%In other words, the linear combination of the columns of $[T]_{\B}$ using the scalars in $[v]_{\B}$ is zero.  As the columns are linearly independent, then all the scalars in $[v]_{\B}$ must be zero and hence $v=0_V$, a contradiction.  
%\end{proof}










\section{Direct sums} 
To motivate this section consider the vector space $\R^2$ thought of as the $xy$-plane.  From this perspective the two subspaces 
$$X = \makeset{(x,0)}{x\in\R}\myand Y=\makeset{(0,y)}{y\in \R}$$
of $\R^2$ have a more familar description -- they are just the  $x$- and $y$-axes. The fact that these axes only intersect at the origin is reflected in the fact that 
$$X\ \cap\ Y = \{(0,0)\}.$$  
We also know that every vector in $\R^2$ can be written (uniquely) as vector in the $x$-axis plus a vector in the $y$-axis.  This is mirrored by the fact that 
$$\R^2 = \makeset{u+v}{u\in X, v\in Y}.$$
It now makes sense to denote the set on the right by $X+Y$, in which case we write $\R^2 = X+Y$.  That is $\R^2$ is the ``sum" of two of its subspaces.   We can perform a similar decomposition to $\R^3$ as well.  Redefining  
$X$, $Y$ and $Z$ to be the subspaces given by the $x$-, $y$-, and $z$-axis, then we certainly have
$$\R^3 = X+Y+Z.$$

Our first definition formalizes these ideas.  

\begin{definition}
	Let $U_1,\ldots, U_m$ be subspaces of $V$.  We define their \textbf{sum} to be the set
	$$U=U_1+\cdots + U_m = \makeset{u_1+\cdots + u_m}{u_i\in U_i}.$$
	We say $U$ is the \textbf{direct sum} of the $U_i$ provided that the only choice of $u_i\in U_i$ that gives
	$$u_1+\cdots + u_m=0_V,$$ 
	is $u_i = 0_V$.  In this case we write,
	 $$U=U_1\oplus\cdots \oplus U_m.$$  
\end{definition}


A straightforward check shows that  $U$ is a subspace of $V$.  As it is clear that $U_i$ is a subset of $U$ (check!), it now follows that $U_i$ is a  subspace of $U$.  There is also an important analogy that is not to be missed.   The subspaces $U_i$ are behaving a lot like vectors.  Saying that $U =U_1+\cdots + U_m$ is reminiscent of a spanning set of vectors, while the definition of a direct sum is reminiscent of linear independence.  The next few lemmas make this analogy stronger. We leave the proof of the first lemma to the reader.  

\begin{lemma}
	Let $U_1,\ldots, U_m$  be subspaces of $V$ and consider the space $$U = U_1+\cdots + U_m.$$     
	Then, $U$ is a direct sum of the $U_i$'s if and only if for every $u\in U$ there is a unique choice of $u_i\in U_i$ so that vector $u =u_1+\cdots+u_m$.
\end{lemma}

\todo{make this an iff, so that we can create direct sums by partitioning a basis.}
\begin{lemma}\label{lem:basis_for_direct_sum}
Let $U_1,\ldots, U_m$  be subspaces of $V$ such that 
$$V = U_1\oplus\cdots \oplus U_m.$$
If $\B_i$ is a basis for each $U_i$, then 
$$\B = \B_1\ \bigcup\ \cdots \ \bigcup\ \B_m$$
is a basis for $V$.  Consequently, $\dim V = \dim U_1 +\cdots + \dim U_m$.
\end{lemma}

\begin{proof}
	To simplify notation we prove the claim when $m=2$.   As the reader should check, the same proof works in general.  Let $U = U_1$ and $W = U_2$ and fix bases $\B_U=\{u_1,\ldots, u_k\}$ and $\B_W=\{w_1,\ldots, w_m\}$ for $U$ and $W$ respectively.  A simple computation shows that  $\B$ spans all of $V$:
	\begin{align*}
\spn(\B) &= \makeset{(a_1u_1+\cdots +a_ku_k) +(b_1w_1+\cdots +b_mw_m) }{a_i,b_i\in \F}\\
&=\makeset{u+w}{u\in U, w\in W}\\
&=U+W\\
&=V		
	\end{align*}
	where the second equality follows since $\B_U$ spans $U$ and $\B_W$ spans $W$.  To see that $\B$ is linearly independent, assume $a_i$ and $b_i$ are such that 
	$$(a_1u_1+\cdots +a_ku_k) +(b_1w_1+\cdots +b_mw_m) = 0_V.$$
	By definition of our sum being direct, we must have 
	$$a_1u_1+\cdots +a_ku_k = 0_V \myand \ b_1w_1+\cdots +b_mw_m= 0_V.$$
By the independence of the $u_i$'s  and the $w_i$'s we see that all the $a_i$'s  and all the $b_i$'s are zero. 
\end{proof}


Continuing our analogy between direct sums and bases, the next lemma is a generalization of the Basis Extension Theorem.  In fact the main ingredient in its proof is exactly this theorem.  

\todo{FIX the wording of this lemma}
\begin{lemma}\label{lem:directsum_extension}
Fix vector space $V$ and subspace $U$.  Let $S=\{v_1,\ldots, v_k\}$ be a set of vectors such that $U\ \cap\ \spn(S) = \{0_V\}$.  Then there exists a subspace $W$ such that 
$$V=U\oplus W$$ 
and $S\subset W$.  
\end{lemma}
\begin{proof}
Let $W' = \spn(S)$.  If $V = U \oplus W'$ we are done.  Otherwise, let $\B_U$ be a basis for $U$ and $\B_{W'}$ be one for $W'$.   By the previous lemma $\B_U\ \cup\ \B_{W'}$ is a basis for $U\oplus W'$.  Now extend $\B_U\ \cup\ \B_{W'}$ to a basis for all of $V$ by adding vectors $v_1,\ldots, v_\ell$.  Then
 $$W = \spn(\B_{W'}\ \cup\ \{v_1,\ldots, v_\ell\})$$
 is the desired space. 
\end{proof}

A nice consequence of this lemma is that if $U$ is a subspace of $V$,  so that $V = U \oplus W$.  Simply choose $S=\{0_V\}$ in the lemma!



As we have already seen, direct sums decompose our vector space into (smaller) vector spaces.  Interestingly, we can also use direct sums to decompose operators as well. The one requirement is that the operator must behave ``nicely" with respect to the subspaces involved.  Our next definition makes this precise.  

\begin{definition}
	Let $T\in \lin(V)$.  We say a subspace $U$ of $V$ if \textbf{$T$-invariant} provided that $T(U) =\makeset{Tu}{u\in U}\subseteq U$.  
\end{definition}


To motive what is to come, let us consider an example.  Let $T\in\lin(\R^3)$ be given by 
$$T(x,y,z) = \left(\frac{x-y}{\sqrt{2}},\frac{x+y}{\sqrt{2}},3z\right).$$  Observe that $T$ decomposes into two parts.  The first is a rotation by $45^\circ$ in the $xy$-plane and the second is scaling by 3 along the $z$-axis.  To illustrate consider the following picture.

\begin{center}
\begin{tikzpicture}
\tdplotsetmaincoords{60}{120}
\begin{scope}[shift={(0,0)},
		axis/.style={->,black},
		tdplot_main_coords,
		vector/.style={-stealth,blue,},
		vector guide/.style={dashed,red}]
	
%draw the axes
	\draw[axis] (0,0,0) -- (4,0,0) node[anchor=west]{$x$};
	\draw[axis] (0,0,0) -- (0,4,0) node[anchor=west]{$y$};
	\draw[axis] (0,0,0) -- (0,0,4) node[anchor=west]{$z$};
	
	
	%standard tikz coordinate definition using x, y, z coords
	\coordinate (O) at (0,0,0);
	\coordinate (Z) at (0,0,2);
	\coordinate (X) at (2,0,0);
	\coordinate (TX) at (1.42,1.42,0);
	\coordinate (TZ) at (0,0,3);
	
	
	%tikz-3dplot coordinate definition using r, theta, phi coords
	\tdplotsetcoord{P}{3}{40}{45}
	
	%draw a vector from O to P
	\draw[vector, thick, red] (O) -- (TZ) node[right,black] {$Te_3$};
	\draw[vector,very thick] (O) -- (Z) node[right, black] {$e_3$};
	
	\draw[vector, very thick] (O)-- (X) node[left, black] {$e_1$};
	\draw[vector,  thick, red] (O)-- (TX) node[right, black] {$Te_1$};

	\tdplotdrawarc[->,dashed]{(O)}{1}{0}{45}{anchor=north}{$45^\circ$};
	
	%draw guide lines to components


%	\draw[vector guide] (Px) -- (Pxy) node[midway,below, black] {\tiny $b$};
%	\draw[vector guide] (Py) -- (Pxy)  node[midway,below, black] {\tiny $a$};
%	\draw[vector guide] (Pxy) -- (P) node[midway,right, black] {\tiny $c$};
\end{scope}
\end{tikzpicture}	
\end{center}

Now define the following subspaces of $\R^3$
$$U = \makeset{(x,y,0)}{x,y\in\R}\myand W = \makeset{(0,0,z)}{z\in\R}.$$
It is clear from our description of $T$ that $U$ and $W$ are both $T$-invariant subspaces.   Moreover, it is clear that $\R^3 = U\oplus W$.  Now consider $[T]_{\B}$, where $\B = \{e_1,e_2\}\ \cup\ \{e_3\}$.  That is $\B$ is the union of a basis for $U$ and a basis for $W$.  Computing we see that 
$$[T]_{\B} = \begin{bmatrix}
	\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}&0\\
	\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}&0\\
	0&0&3\\
\end{bmatrix}.$$
Looking closely, we see this matrix consists of a $2\times 2$ block (encodes the rotation) and $1\times 1$ block (encodes the scaling)  along its diagonal and all the other entries are zero.   


The significance of all this, is that if we can decompose our vector space into the direct sum of $T$-invariant subspace, then this means that our operator also decomposes into operators on smaller spaces as seen in this example.  We consider this idea in complete generality.  The reader is encouraged to keep our specific example in mind when reading the general ideas.  We begin with an expected definition.  

\begin{definition}
	We say a square matrix $M$ is \textbf{block diagonal} provided it is of the form
	$$M = \left[\begin{array}{cccccccc}
	\multicolumn{2}{c}{\multirow{2}{*}{\Large $A_1$}} &&&&&\multicolumn{2}{c}{\multirow{2}{*}{\Large $0$}} \\ 
	&&&&&&&\\
	   
	&&\multicolumn{2}{c}{\multirow{2}{*}{\Large $A_2$}}&&&&\\   
	&&&&&&&\\
	
	&&&&\multicolumn{2}{c}{\multirow{2}{*}{\Large $\ddots$}}&&\\   
	&&&&&&&\\
	
	\multicolumn{2}{c}{\multirow{2}{*}{\large $0$}}&&&&&\multicolumn{2}{c}{\multirow{2}{*}{\Large $A_m$}}\\   
	&&&&&&&\\   
\end{array}\right],$$
where each of the $A_i$ are square matrices lying along the diagonal of $M$ and all other entries in $M$ are zero.  In the case each block is just a $1\times 1$ matrix, we say $M$ is \textbf{diagonal}.
\end{definition}


  
As suggested by our motivating example, we now have the following lemma.

\begin{lemma}\label{lem:block_diag_representation}
Assume $U_1,\ldots, U_m$ are $T$-invariant subspaces of $V$ such that 
$$V = U_1\oplus \cdots \oplus U_m.$$  If $\B_i$ is a basis for $U_i$, then 
$$[T]_{\B} = \left[\begin{array}{cccccccc}
	\multicolumn{2}{c}{\multirow{2}{*}{\Large $[T|_{U_1}]_{\B_1}$}} &&&&&\multicolumn{2}{c}{\multirow{2}{*}{\Large $0$}} \\ 
	&&&&&&&\\
	   
	&&\multicolumn{2}{c}{\multirow{2}{*}{\Large $[T|_{U_2}]_{\B_2}$}}&&&&\\   
	&&&&&&&\\
	
	&&&&\multicolumn{2}{c}{\multirow{2}{*}{\Large $\ddots$}}&&\\   
	&&&&&&&\\
	
	\multicolumn{2}{c}{\multirow{2}{*}{\large $0$}}&&&&&\multicolumn{2}{c}{\multirow{2}{*}{\Large $[T|_{U_m}]_{\B_m}$}}\\   
	&&&&&&&\\   
\end{array}\right],
$$where $\B= \B_1 \cup\cdots \cup \B_m$.
Conversely, if $\B$ is any basis for $V$ such that $[T]_{\B}$ is block diagonal, then $V$ is the direct sum of $T$-invariant subspaces.  
\end{lemma}

The reader should pause to convince themselves that this lemma is a direct  generalization of Theorem~\ref{thm:diagonlize}.    In fact, it further strengthens our analogy between linear independent vectors and direct sums.  This should be somewhat expected since the 1-dimensional space spanned by an eigenvector is just an invariant subspace.  The proof of this lemma is left to the reader.













\section{Generalized eigenvectors}\label{sec:generlized_eigenvectors}

In Section~\ref{sec:eigenvalues}, we saw that the (real) operator that rotates $\R^2$ by $90^\circ$ fails to have a single eigenvector.  From this we concluded that, in general, not all real operators decompose into their eigenspaces, i.e., they are not all diagonalizable.  In the same section, we also showed that the complex operator $A:\C^3\to\C^3$, where 
$$A=\begin{bmatrix}
	1&1&0\\
	0&1&0\\
	0&0&3
\end{bmatrix},$$
only has eigenspaces 
$$\nul(A-1) = \spn\left(\myvec{1\\0\\0}\right)\myand \nul(A-3)=\spn\left(\myvec{0\\0\\1}\right).$$ 
Consequently, it follows that not all complex operators are diagonalizable either.   Since the final goal of this chapter is to decompose (complex) operators into invariant subspaces, these examples demonstrate that eigenspaces are the wrong invariant subspaces to consider.  The question now is: Which are the right invariant subspaces? To help answer this question, let us revisit the operator $A:\C^3\to\C^3$ from above.   In particular,  observe that 
$$\nul(A-1)^2 = \nul \begin{bmatrix}
	0&1&0\\
	0&0&0\\
	0&0&2\\
\end{bmatrix}^2 = \nul\begin{bmatrix}
	0&0&0\\
	0&0&0\\
	0&0&4
\end{bmatrix}.$$
It now follows that 
$$\nul(A-1)^2 = \spn(\left(\myvec{1\\0\\0},\myvec{0\\1\\0}\right),$$
and moreover, that
$$\nul(A-1)^2 \oplus \nul(A-3) = \C^3.$$
This example suggests the following definition.  

\begin{definition}
	Let $\lambda$ be an eigenvalue of $T$ and define the \textbf{generalized eigenspace} (corresponding to $\lambda$) to be the subspace 
	$$\G_\lambda = \nul(T-\lambda)^{\dim V}.$$
	We call $0_V\neq v\in \G_\lambda$ a \textbf{generalized eigenvector} (corresponding to $\lambda$).
\end{definition}


%\begin{definition}
%	Let $\lambda$ be an eigenvalue of $T$.  We say $v\in V$ is a \textbf{generalized eigenvector} corresponding to $\lambda$ if 
%	$$v\in\nul(T-\lambda)^k$$
%	for some positive integer $k$.  We denote the set of all generalized eigenvectors corresponding to $\lambda$ by $\G_\lambda$ and call this set the \textbf{generalized eigenspace} (corresponding to $\lambda$).  
%\end{definition} 
Just like eigenspaces, we next show that generalized eigenspaces are also invariant subspaces.  

\begin{lemma}\label{lem:eigenspace_invariant}
Let $\lambda$ be an eigenvalue of $T$. Then $\G_\lambda$ is a $T$-invariant. 
\end{lemma}
\begin{proof}
	Fix $n=\dim V$ and let $u\in \G_\lambda=\nul(T-\lambda)^n$.  To prove invariance, we must show that $Tu \in \nul(T-\lambda)^n$.  Computing, we see that 
	$$(T-\lambda)^n Tu = T(T-\lambda)^n u = T0_V = 0_V,$$
	where the first equality follows as $T$ commutes with itself.  Hence $Tu \in \nul(T-\lambda)^n$ as needed.
\end{proof}

As suggested by the above example, our goal now is to prove the following structure theorem for complex operators.

\begin{theorem}\label{thm:decomp_of_operators}
Let  $T$ be an operator on a finite-dimensional complex vector space $V$. If the distinct eigenvalues of $T$ are $\lambda_1,\ldots,\lambda_m$, then 
$$V = \G_{\lambda_1}\oplus \cdots \oplus \G_{\lambda_m}.$$
\end{theorem} 

In order to prove this theorem, we will need to establish a few lemmas and a deeper understanding of generalized eigenvectors.  We do this first, postponing the proof of this theorem to the end of the section.  We begin with a technical lemma.



\begin{lemma}\label{lem:invariant_space}
Assume $U$ is a  $T$-invariant subspace of $V$ with dimension $m$.  Then 
$$T^m(U) = T^{m+1}(U) = T^{m+2}(U) = \cdots.$$
\end{lemma}
\begin{proof}
	First observe that $T^i(U) \supseteq T^{i+1}(U)$.  To see this note that
	$$T^{i+1}u = T^i (Tu) \in T^i(U),$$
	since $Tu\in U$ as $U$ is $T$-invariant.  This gives us the following sequence of inclusions
$$U \supseteq T(U) \supseteq T^2(U) \supseteq \cdots.$$
Observe we must have some $i$ such that $T^i(U) = T^{i+1}(U)$.  If not then 
$$m = \dim U > \dim T(U) > \dim T^2(U) >\cdots$$ would be an infinite decreasing sequence of positive integers!  Therefore there must exist a smallest $i\leq m$ so that $T^i(U) = T^{i+1}(U)$.  (Why must $i\leq m$?)  Now observe that 
$$T^{i+1}(U) = TT^i(U)= TT^{i+1}(U)= T^{i+2}(U).$$  
Doing this again we get
$$T^{i+2}(U)= TT^{i+1}(U) = TT^{i+2}(U) = T^{i+3}(U).$$
Repeating this argument indefinitely yields 
$$T^i(U) = T^{i+1}(U) = T^{i+2}(U) = \cdots $$
and completes the proof.  
\end{proof}


%\begin{lemma}\label{lem:eigenspace} For any complex operator $T$ with eigenvalue $\lambda$ we have 
%	$$\G_\lambda = \nul(T-\lambda)^{\dim V}.$$
%\end{lemma}
%\begin{proof}
%For simplicity, let $n=\dim V$ and $S = T-\lambda$.   First, observe  
%$$\nul S^i\subseteq \nul S^{i+1},$$
%since if $u\in \nul S^i$, then $S^{i+1}u = SS^i u = S0_V = 0_V$.
%As $V$ is certainly $S$-invariant, Lemma~\ref{lem:invariant_space} shows that
%$$ S^n(V) = S^{n+1}(V)=\cdots,$$
%and hence
%$$\dim \ran S^n = \dim \ran S^{n+1}=\cdots.$$ 
%By Rank-Nullity, we have 
%$$\dim \nul S^n = \dim \nul S^{n+1} = \cdots.$$
%It now follows that 
%$$\nul(T-\lambda)\subseteq \cdots \subseteq \nul(T-\lambda)^n = \nul(T-\lambda)^{n+1} =\cdots,
%$$
%proving our claim 
%\end{proof}


We now turn our attention to exploring an important connection between $T$-triangularizing bases and generalized eigenspaces.  To warm-up, let $T$ be a complex operator on $V$ with $T$-triangularizing basis $\B=\{v_1,\ldots, v_n\}$ so that
$$[T]_{\B} =	 \begin{bmatrix}
\lambda_1 &  & \ldots &a_{1,k}&&  *  \\
        & \lambda_2 &\ldots  &a_{2,k}&& \\
        &		&\ddots &\vdots &&\\
        &		& &\lambda_k & &\\
        &		& & &\ddots &\\
  0     &         &         &&&\lambda_n
\end{bmatrix}.$$
As suggested by our choice of notation, we claim that every entry on the diagonal is actually an eigenvalue.  To see this it will suffice to show that $\nul(T-\lambda_k)$ is \textbf{not} trivial.  This follows almost immediately.  As $\B$ is $T$-triangularizing, we know that 
$$(T-\lambda_k)v_i \in \spn(v_1,\ldots, v_i)\subset \spn(v_1,\ldots, v_{k-1})$$
for all $i<k$.  Additionally, 
$$(T-\lambda_k)v_k = (a_{1,k}v_1 + \cdots a_{k-1,k}v_{k-1} + \lambda_kv_k) - \lambda_kv_k \in \spn(v_1,\ldots, v_{k-1}).$$
This means $(T-\lambda_k)$ is a map from the $k$-dimensional space $\spn(v_1,\ldots, v_k)$ to the $k-1$-dimensional space $ \spn(v_1,\ldots, v_{k-1})$.  Consequently, it must have a nontrivial nullspace. (Why?)  We now see that all the values on the diagonal of $[T]_{\B}$ are eigenvalues for $T$.  

In fact, the next lemma states an even deeper connection between eigenvalues and triangularizing bases.    

\begin{lemma}\label{lem:multiplicity}
Fix a complex operator $T$ on the $n$-dimensional vector space $V$ and  
	let $\B=\{v_1,\ldots, v_n\}$ be any $T$-triangularizing basis for $V$.  Then every scalar on the diagonal of $[T]_{\B}$ is an eigenvalue for $T$.  
	
	Moreover, if $\lambda_1,\ldots, \lambda_m$ are the distinct eigenvalues for $T$, then $\lambda_i$ appears on the diagonal of $[T]_{\B}$ precisely  $\dim \G_{\lambda_i}$ times. Consequently, 
	$$\dim V = \dim \G_{\lambda_1}+ \cdots + \dim \G_{\lambda_m}.$$
\end{lemma}

\begin{proof}
As we have already proved the first claim, we concentrate on the second.  To this end, it suffices to prove the following special case:  

\medskip

\fbox{\begin{minipage}{30em}
If $S$ is an arbitrary operator on $V$ with $S$-triangularizing basis $\B$, then zero appears on the diagonal of $[S]_{\B}$ exactly $\dim \nul S^n$ times.  
\end{minipage}}

\medskip

\noindent The general result follows from this special case as follows.  Let $\lambda$ be an eigenvalueIf 
$$d=\dim \nul(\underbrace{T-\lambda_i}_{S})^n = \dim \G_{\lambda_i},$$ 
then by the special case $d$  is the number of times zero appears on the diagonal of 
$$[S]_{\B}=[T-\lambda_i]_{\B}= [T]_{\B} - [\lambda_i]_{\B} = [T]_{\B} -\left[\begin{array}{cccc}
	\lambda_i &&\multicolumn{2}{c}{\multirow{2}{*}{\Large 0}}\\
	&\lambda_i &&\\
	\multicolumn{2}{c}{\multirow{2}{*}{\Large 0}}&\ddots &\\
	&&& \lambda_i
\end{array}\right]
$$ which,  we now see, is the same as the number of times $\lambda_i$ appears on the diagonal of $[T]_{\B}$.  This proves the general result.  

We now concentrate on proving the special case.   For concreteness, set 
$$[S]_{\B} = \begin{bmatrix}
a_{1,1} & a_{1,2} & a_{1,3} & \ldots & a_{1,n}  \\
        & a_{2,2} & a_{2,3} & \ldots & a_{2,n}  \\
        &         & a_{3,3}  &  &    \\
        &		&	& \ddots & \vdots\\
  0     &         &         &        & a_{n,n}
\end{bmatrix},$$
and let $d$ be the number of zero entries along the diagonal of $[S]_{\B}$.  The number of nonzero entries along this diagonal is then $n-d$.  
The proof will certainly be complete if we can establish that 
$$\dim \ran S^n = \dim S^n (V)  = n-d,$$
since an application of Rank-Nullity shows that
\begin{align*}
\dim \nul S^n &= \dim V - \dim \ran S^n \\
&= n - (n-d) \\
&= d, \mbox{ the number of zeros on the diagonal of } [S]_{\B},	
\end{align*}
as needed.  To this end set
$$V_i = \spn(v_1,\ldots, v_i),$$
for $0<i$, and $V_0 = \{0_V\}$.  As $V_i\subseteq V_{i+1}$, for $0\leq i$, we obtain the following sequence of inclusions
\begin{equation}
\{0_V\}\subseteq S^n(V_1)\subseteq S^n(V_2)\subseteq \cdots \subseteq S^n(V_n) = S^n(V).\tag{$\star$}
\end{equation}
Instead of proving directly that $\dim S^n(V) = n-d$, it will be easier to show that
$$\dim S^n(V) = \mbox{\# of strict inclusions in } (\star) = n-d.$$
At this point, we have reduced the problem to establishing these two equalities.   The first equality will be proved by establishing the claim that
\begin{equation}
\dim S^nV_i +1 = \dim S^n V_{i+1}\tag{$1$}	
\end{equation}
provided $S^nV_i \subsetneq S^nV_{i+1}$.  Likewise, the second equality will follow from the claim that  
\begin{equation}
S^nV_i\subsetneq S^n V_{i+1}\mbox{ if and only if } a_{i+1,i+1}\neq 0\tag{$2$}.	
\end{equation}
We now turn our attention to proving claims (1) and (2).  To prove claim (1), observe that since
$$S^n(V_i)=\spn(S^nv_1,\ldots, S^nv_i),$$
it follows that the spanning sets, for any two consecutive spaces in $(\star)$, differ by exactly one vector.  This proves claim (1). 

To prove claim (2), let us first assume that $a_{i+1,i+1}=0$.  As we already know that $S^n(V_{i})\subseteq S^n(V_{i+1})$, we need only establish the reverse inclusion.  To this end observe that since $a_{i+1,i+1}=0$, our matrix representation of $S$ implies that
$$Sv_{i+1} = a_{1,i}v_1+\cdots + a_{i,i}v_i \in V_i.$$
Additionally, as $\B$ is $S$-triangularizing, we also have $Sv_1,\ldots, Sv_i\in V_i$.
This implies that 
$$S(V_{i+1})= \spn(Sv_1,\ldots,Sv_{i+1})\subseteq V_i.$$  
Now consider,
$$S^n(V_{i+1}) = S^{n-1}S(V_{i+1}) \subseteq S^{n-1}(V_i) = S^n(V_i),$$
where the last equality follows from Lemma~\ref{lem:invariant_space} since $\dim V_i = i < n$.  It only remains to consider the case when $a=a_{i+1,i+1} \neq 0$.  In this case, we see that 
$$S^nv_{i+1} = b_1v_1 + \cdots + b_iv_i + a^n v_{i+1},$$
for some scalars $b_1,\ldots,b_i$. As $a\neq 0$ and the $v_j$ are linearly independent, we see that $S^nv_{i+1} \notin \spn(v_1,\ldots,v_i)=V_i$. Consequently, $S^nv_{i+1} \notin S^n(V_i)\subseteq V_i$, where the inclusion follows as $\B$ is $S$-triangularizing. So, $S^nV_i \subsetneq S^nV_{i+1}$, which completes our proof.  
\end{proof}

%	Let $\B=\{v_1,\ldots, v_n\}$ be any $T$-triangularizing basis for $V$.  Then the number of zeros along the diagonal of $[T]_{\B}$ is equal to $\dim T$.  
%	$$|\makeset{v_i}{Tv_i\notin \spn(v_1,\ldots, v_{i-1}), i\leq n}| = \dim T^n(V).$$
%\end{lemma}
%\begin{proof}
%	We proceed by induction on $n$.  If $n=1$, then 
%	$$\makeset{v_i}{Tv_i\notin \spn(v_1,\ldots, v_{i-1})}=\begin{cases}
%		{v_1} &\mbox{ iff } Tv_1=0  \mbox{ iff } \dim T(V) = 1\\
%		\emptyset &\mbox{ iff } Tv_1\neq 0  \mbox{ iff } \dim T(V) = 0\\
%	\end{cases},$$
%	which proves the base case.  Assuming the result for any operator on an $(n-1)$-dimensional space, consider the operator $T$ on the $n$ dimensional space $V$ with $T$-triangularizing basis $\B=\{v_1,\ldots, v_n\}$.  Define the $(n-1)$st dimensional space $U = \spn(v_1,\ldots, v_{n-1})$.  As $U$ is $T$-invariant, then $T:U\to U$ is an operator on $U$.  By induction we know that 
%	$$|\makeset{v_i}{Tv_i\in \spn(v_1,\ldots, v_{i-1}), i\leq n-1}| = \dim T^{n-1}(V).$$
%	We now consider two cases. 
%
%	\bigskip 
%
%	{\tt Case 1:} $Tv_n \in U$.
%	
%	\medskip
%	
%In this case, it suffices to prove that $T^n(V) = T^{n-1}(U)$ since then
%	\begin{align*}
%\dim T^n(V) &= \dim T^{n-1}(U)\\
%	 &= |\makeset{v_i}{Tv_i\in \spn(v_1,\ldots, v_{i-1}), i\leq n-1}|\\ 
%	 &= |\makeset{v_i}{Tv_i\in \spn(v_1,\ldots, v_{i-1}), i\leq n}|.
%	\end{align*}
%
%	To show this equality, the fact that $U\subset V$ yields 
%	$$T^{n-1}(U) = T^n(U)\subset T^n(V).$$
%	For the other inclusion, the fact that $Tv_n \in U$ implies $T(V) \subset U$.  With this, we see that
%	$$T^n(V) = T^{n-1}T(V) \subset T^{n-1}(U)$$
%	as needed.  
%	
%	\bigskip
%
%	{\tt Case 2:} $Tv_n \notin U$.
%	
%	\medskip
%	Let $\{u_1,\ldots, u_k\}$ be a basis for $T^{n-1}(U) = T^n(U)$ where the equality follows Lemma~\ref{lem:invariant_space} since $\dim U = n-1$.  As $Tv_n\notin U$ the Linear Independence Lemma guarantees that $S=\{u_1,\ldots, u_k, Tv_n\}$ is a linearly independent set.  Moreover 
%	\begin{align*}
%T^n(V) &= \spn(T^nv_1,\ldots, T^nv_n)\\ 
%&= \makeset{a_1T^nv_1+\cdots a_{n-1}T^nv_{n-1} + a_nT^nv_n}{a_i\in \C} \\
%&= \makeset{T^n(a_1v_1+\cdots a_{n-1}v_{n-1}) + a_nT^nv_n}{a_i\in \C} \\
%&= \makeset{T^nu+ a_nT^nv_n}{u\in U, a_n\in \C}\\ 
%&= \makeset{b_1u_1+\cdots b_ku_k+ a_nT^nv_n}{a_n,b_i\in \C}\\ 
%&= \spn(S).		
%	\end{align*}
%
%	It now follows that $S$ is a basis for $T^n(V)$.  Therefore $\dim T^n(V) = \dim T^{n-1}(U) +1$.  From this we get
%	\begin{align*}
%\dim T^n(V) &= \dim T^{n-1}(U) +1\\ 
%&= |\makeset{v_i}{Tv_i\notin \spn(v_1,\ldots, v_{i-1}),i\leq n-1}|+1 \\
%&= |\makeset{v_i}{Tv_i\notin \spn(v_1,\ldots, v_{i-1}), i\leq n}|.	
%	\end{align*}
%	This concludes our second case.  
%
%	
%\end{proof}





 
\todo{fix working of statement; awk}
\begin{lemma}
	Let $T$ be a complex operator whose distinct eigenvalues are  $\lambda_1,\ldots, \lambda_m$.  Assume $u_i\in \G_{\lambda_i}$ are such that 
	$$0_V= u_1+\cdots +u_m, $$
	each $u_i=0_V$.  Consequently, if $W$ is the sum of the subspaces $\G_{\lambda_i}$, then 
	$$W = \G_{\lambda_1} \oplus \cdots \oplus \G_{\lambda_m}.$$
\end{lemma}
\begin{proof}
For brevity set $n=\dim V$ and  $\G_i = \G_{\lambda_i}$.  Assume for a contradiction that there exists $u_i\in \G_i$, not all zero, so that
\begin{equation}
0_V = u_1+\cdots + u_m.\tag{$\star$}	
\end{equation}
Without loss of generality let us assume $u_1\neq 0_V$.  We now argue that we can further assume that $u_1$ is an eigenvector.   To show this observe that since $(T-\lambda_1)^n u_1 = 0_V$, then there must exists a largest $k\geq 0$ so that 
$$(T-\lambda_1)^k u_1 \neq 0_V\myand (T-\lambda_1)^{k+1} u_1 = 0_V$$
This means the $(T-\lambda_1)^k u_1$ is an eigenvector for $T$.    As each of the $\G_i$ are  $T$-invariant, and hence $(T-\lambda_1)^k$-invariant, applying the operator $(T-\lambda_1)^k$ to both sides of $(\star)$, and relabeling the $i$th vector as $u_i$,  allows us to assume $u_1$ is an eigenvector. 

We now model the remainder of our proof on the proof in  Theorem~\ref{thm:eigenvectors_exist}.  As such define the operators 
$$S = (T-\lambda_2)^n\cdots (T-\lambda_m)^n$$
As in the proof of Theorem~\ref{thm:eigenvectors_exist} we have
$$S u_i=\begin{cases}
	0_V &\mbox{ if } i\neq 1\\
	\Lambda u_1\neq 0_V & \mbox{ if } i= 1
\end{cases}
$$
for some $\Lambda\neq 0$ in $\C$.  Multiplying $(\star)$ through by $S$ now reveals that $0_V = \Lambda u_1$.  This is a contradiction since $\Lambda\neq 0$ and $u_1\neq 0_V$.

%	For a contradiction, assume $\G_{\lambda} \cap \G_{\alpha} \neq \{0_V\}$ and let $v$ be any nonzero vector in the intersection.  
%As $v$ is nonzero and $G_{\lambda} =  \nul (T-\lambda)^n$ there must be a largest $k$ so that 
%	$$u = (T-\lambda)^kv \neq 0\qquad\mbox{but}\qquad (T-\lambda)u = 0_V.$$  This means that $(\lambda,u)$ is an eigenpair for $T$.  Moreover, as $\G_\alpha$ is $T$-invariant, it follows from Lemma~\ref{lem:eigenspace_invariant} that $u\in \G_\alpha$.  Therefore 
%	$$0_V = (T-\alpha)^nu = (\lambda-\alpha)^n u.$$
%	As $u\neq 0_V$ we must have $(\lambda-\alpha)^n=0$ or $\lambda = \alpha$, contradicting our first assumption that these scalars are distinct. 
\end{proof}


%\begin{lemma}\label{lem:disjoint_eigenspaces}
%	Let $\lambda_1,\ldots, \lambda_m$, be the eigenvalues for $T$.  Now define 
%	$$p_i = (x-\lambda_1)^n\cdots(x-\lambda_{i-1})^n(x-\lambda_{i+1})^n\cdots (x-\lambda_m)^n.$$
%	Then the $p_i$ are mutually relatively prime and consequently there exists scalars $a_i$ so that 
%	$$1 = a_1p_1 + \cdots + a_mp_m.$$
%	Moreover, $p_i(T)v \in \G_i$ for all $v\in V$.  
%\end{lemma}


\begin{proof}[Proof of Theorem~\ref{thm:decomp_of_operators}]
	It follows from the previous lemma that  
	$$\G_{\lambda_1}\oplus \cdots \oplus \G_{\lambda_m} \subseteq V.$$
To complete the proof we must show this is actually an equality.  The easiest way to do this is to show the dimension of the direct sum is $n = \dim V$.  Now consider
$$\dim(\G_{\lambda_1}\oplus \cdots \oplus \G_{\lambda_m}) = \sum_{i=1}^m \dim(\G_{\lambda_i})=  \dim V,$$
where the second equality follows directly from Lemma~\ref{lem:multiplicity}.
	
\end{proof}


\section{The characteristic polynomial}

Throughout this section let $T$ be a complex operator on $V$ with distinct eigenvalues $\lambda_1,\ldots, \lambda_m$.  Additionally set $d_i = \dim \G_{\lambda_i}$.  We then have the following definition.  

\begin{definition}
	The \textbf{characteristic polynomial} of a complex operator $T$ is the polynomial
	$$\rho_T(x)=(x-\lambda_1)^{d_1}\cdots (x-\lambda_m)^{d_m}.$$
\end{definition}

For example, consider the operator $A:\C^3\to \C^3$, where
$$
A =	 \begin{bmatrix}
 1& 5&5\\
  0&1 &5\\
  0& 0&3
\end{bmatrix}.$$
Then by Lemma~\ref{lem:multiplicity}, it follows that 
$$\rho_A(x) = (x-1)^2(x-3).$$  
Now let us compute the operator $\rho_A(A)$.  We see that 
$$
\rho_A(A) = (A-1)^2(A-3) = \begin{bmatrix}
 0& 5&5\\
  0&0 &5\\
  0& 0&2
\end{bmatrix}^2\begin{bmatrix}
 -2& 5&5\\
  0&-2 &5\\
  0& 0&0
\end{bmatrix}=\begin{bmatrix}
 0& 0&0\\
  0&0 &0\\
  0& 0&0
\end{bmatrix}.$$
Our next (famous) theorem states that this always occurs.  
\begin{theorem}[Cayley-Hamilton]
Let $T$ be any complex operator, then $\rho_T(T) = 0$.
\end{theorem}
\begin{proof}
Let $\B=\{v_1,\ldots, v_n\}$ be a $T$-triangularizing basis for $V$ so that 


$$
[T]_{\B} =	 \begin{bmatrix}
\lambda_1 &  & \ldots &b_1&&  *  \\
        & \ell_2 &\ldots  &b_2&& \\
        &		&\ddots &\vdots &&\\
        &		& &\ell_k & &\\
        &		& & &\ddots &\\
  0     &         &         &&&\ell_n
\end{bmatrix}.$$
Now set $V_i = \spn(v_1,\ldots, v_i)$.  
First observe that  $Tv_1 = \ell_1 v_1$ or equivalently, 
$$(T-\ell_1):V_1\to\{0_V\}.$$
Next we claim that for any $k>1$ we have 
$$(T-\ell_k):V_k \to V_{k-1}.$$
If $i<k$, then, as $\B$ is $T$-triangularizing, we have
$$(T-\ell_k)v_i = Tv_i - \ell_k v_i \in V_k.$$
Additionally, we have 
$$(T-\ell_k)v_k= (b_1v_1+\cdots + b_{k-1}v_{k-1} + \ell_k v_k) - \ell_k v_k\in V_{k-1}.$$
We now have the following sequence of maps
$$V=V_n\xrightarrow{T-\ell_n} V_{n-1}\xrightarrow{T-\ell_{n-1}} \qquad\cdots\qquad \xrightarrow{T-\ell_2} V_1\xrightarrow{T-\ell_1} \{0_V\}.$$
For any $u\in V$ we now get
$$0 = (T-\ell_1)\cdots (T-\ell_n)u= (T-\lambda_1)^{d_1}\cdots (T-\lambda_m)^{d_m}u = \rho_T(T)u,$$ where the second equality follows from Lemma~\ref{lem:multiplicity}.  As $u\in V$ is arbitrary, $\rho_T(T)$ has to be the zero map as claimed. 
\end{proof}



%\begin{proof}[Proof of Theorem~\ref{thm:decomp_of_operators}]
%In light of Lemma~\ref{lem:disjoint_eigenspaces}, it only remains to show that 
%$$V = \G_{\lambda_1}+\cdots+\G_{\lambda_m}.$$
%In other words, we must show that any vector $v\in V$ can be expressed a 
%\begin{equation}
%v = u_1+\cdots + u_m\tag{$\star$}	
%\end{equation}
%for some $u_i\in\G_{\lambda_i}$.
%To this end define the polynomials
%$$p_i(x) = \frac{\rho_T(x)}{(x-\lambda_i)^{d_i}}=\frac{(x-\lambda_1)^{d_1}\cdots (x-\lambda_m)^{d_m}}{(x-\lambda_i)^{d_i}},$$
%where $d_i = \dim \G_{\lambda_i}$.
%First observe that for any $v\in V$ we have 
%$$(T-\lambda_i)^{d_i} p_i(T)v = \rho_T(T)v = 0_V,$$
%by Cayley-Hamilton.  This means, 
%$$p_i(T)v\in \nul (T-\lambda_i)^{d_i} \subseteq \G_{\lambda_i}.$$
%Next, observe that the GCD of the polynomials $p_1,\ldots, p_m$ is 1.  Be\'zout's Lemma now guarantees that there exist scalars $a_1,\ldots, a_m\in \C$ such that 
%$$a_1p_1(x) + \cdots + a_mp_m(x) =1.$$  Therefore
%$$v = 1v = (a_1p_1(T) + \cdots + a_mp_m(T))v = a_1p_1(T)v + \cdots + a_mp_m(T)v.$$
%Since $p_i(T)v\in \G_{\lambda_i}$, this establishes $(\star)$ and hence completes our proof. 
%
%\end{proof}


\section{Jordan basis theorem}
\begin{definition}
	We say an operator $N$ on $V$ is \textbf{nilpotent} if there exists some positive integer $k$ such that $N^k=0$.
\end{definition}

\begin{exs}
\begin{enumerate}
	\item The zero operator is nilpotent.
	\item The operator $N:\C^3\to \C^3$ given by $N(a,b,c) = (0,a,b)$ is nilpotent since $N^3 = 0$.  
	\item The matrix operator $A:\C^3\to \C^3$ where 
	$$A = \begin{bmatrix}
		0&0&0\\
		1&0&0\\
		0&1&0
	\end{bmatrix}$$ 
	is nilpotent as $A^3$ is the zero matrix.  Do the nilpotent operators $A$ and $N$ look similar?  They should since they are the same!  In fact, you should convince yourself that 
	$$[N]_{\{e_1,e_2,e_3\}} = A,$$
	so that $A$ is just the matrix representation of $N$ with respect to the standard basis for $\C^3$.  A good way to think about $N$ is that it forces the vectors $e_1,e_2, e_3$ to ``walk the plank":

\begin{center}
\begin{tikzpicture}
\begin{scope}[shift={(0,0)}]
	\coordinate (A) at (0,1);
	\coordinate (B) at (1.5,1);
	\coordinate (C) at (3,1);
	\coordinate (Z) at (4.5,1);
	 
	\node at (A) {$e_1$};
	\node at (B) {$e_2$};
	\node at (C) {$e_3$};
	\node at (Z) {$\ 0_{\C^3}$}; 
	
	\draw[->,shorten <=7pt,shorten >=7pt] (A) to [bend left=30] node[midway,above] {$N$}(B);
	\draw[->,shorten <=7pt,shorten >=7pt] (B) to [bend left=30] node[midway,above] {$N$}(C);
	\draw[->,shorten <=7pt,shorten >=7pt] (C) to [bend left=30] node[midway,above] {$N$}(Z);
\end{scope}
\end{tikzpicture}	
\end{center}
\item The operator $M:\C^5 \to \C^5$, given by 
$$M(a,b,c,d,e) = (0,a,0,c,d)$$
is nilpotent as the reader should check that $M^3=0$.  In this case $M$ forces our standard vectors to walk two planks:

\begin{center}
\begin{tikzpicture}
\begin{scope}[shift={(0,0)}]
	\coordinate (A) at (0,0);
	\coordinate (B) at (1.5,0);
	\coordinate (C) at (3,0);
	\coordinate (Z) at (4.5,0);
	 
	\node at (A) {$e_3$};
	\node at (B) {$e_4$};
	\node at (C) {$e_5$};
	\node at (Z) {$\ 0_{\C^3}$}; 
	
	\draw[->,shorten <=7pt,shorten >=7pt] (A) to [bend left=30] node[midway,above] {$M$}(B);
	\draw[->,shorten <=7pt,shorten >=7pt] (B) to [bend left=30] node[midway,above] {$M$}(C);
	\draw[->,shorten <=7pt,shorten >=7pt] (C) to [bend left=30] node[midway,above] {$M$}(Z);
	
	
	
	\coordinate (A1) at (.75,1.5);
	\coordinate (B1) at (2.25,1.5);
	\coordinate (Z1) at (3.75,1.5);
	 
	\node at (A1) {$e_1$};
	\node at (B1) {$e_2$};
	\node at (Z1) {$\ 0_{\C^3}$}; 
	
	\draw[->,shorten <=7pt,shorten >=7pt] (A1) to [bend left=30] node[midway,above] {$M$}(B1);
	\draw[->,shorten <=7pt,shorten >=7pt] (B1) to [bend left=30] node[midway,above] {$M$}(Z1);
\end{scope}
\end{tikzpicture}	
\end{center}
From this we see that $\spn(e_1,e_2)$ and $\spn(e_3,e_4,e_5)$ are $M$-invariant spaces such that $\C^5 =  \spn(e_1,e_2)\ \oplus\ \spn(e_3,e_4,e_5)$.  Consequently, Lemma~\ref{lem:block_diag_representation} gives us
$$[M]_{\{e_1,e_2\} \cup \{e_3,e_4, e_5\}} = \left[\begin{array}{cc|ccc}
	0 & 0 &   \multicolumn{3}{|c}{\multirow{2}{*}{\huge 0}}   \\
	1 & 0 &   &   &  \\
\hline
	  \multicolumn{2}{c|}{\multirow{3}{*}{\huge 0}}   & 0 & 0 & 0\\
	  &   & 1 & 0 & 0\\
	  &   & 0 & 1 & 0	  
\end{array}\right].$$

\item Let $T$ be any operator with eigenvalue $\lambda$.  Then $(T-\lambda)$ restricted to the generalized eigenspace corresponding to $\lambda$ is nilpotent.  
\end{enumerate}
	
\end{exs}


\begin{definition}
	Let $N$ be a nilpotent operator on $V$.  We say a basis $\J$ is a \textbf{Jordan basis} with respect to $N$, provided there exists vectors $v_1,\ldots, v_s\in \J$ such that 
	$$\J= \{v_1,Nv_1,\ldots, N^{k_1}v_1\}\cup \cdots \cup \{v_s,Nv_s,\ldots, N^{k_s}v_s\}$$
	and $N(N^{k_i}v_i) = 0_V$.  We say the vectors $v_i$ are  \textbf{$\J$-generating} vectors.   
\end{definition}

\begin{definition}
	Let $k\geq 0$.  We define a \textbf{Jordan block} of size $k+1$ to be the $(k+1) \times (k+1)$ matrix 
	$$J(k) = \begin{bmatrix}
		0&& &&\\
		1&0&&&\\
		 &1&\ddots & &\\
		 & &  &&\\
		 & & &1&0
	\end{bmatrix},$$
	so that $J(k)$ has $k+1$ zeros down the diagonal and $k$ ones on the off diagonal.  
\end{definition}

As a warm-up for the proof of our next lemma, assume that $N$ is a nilpotent operator on $V$ and that $\J=\{v,Nv,\ldots, N^kv\}$ is a basis for $V$ where $N^{k+1} v = 0_V$.  Before continuing, the reader should convince themselves that 
$$[N]_{\J} = J(k).$$

\begin{lemma}\label{lem:jordan_form}
	Let $N$ be a nilpotent operator on $V$ and assume $\J$ is a Jordan basis for $V$ with respect to $N$.  Then
	$$[N]_{\J} =  \left[\begin{array}{cccccccc}
	\multicolumn{2}{c}{\multirow{2}{*}{\Large $J(k_1)$}} &&&&&\multicolumn{2}{c}{\multirow{2}{*}{\Large $0$}} \\ 
	&&&&&&&\\
	   
	&&\multicolumn{2}{c}{\multirow{2}{*}{\Large $J(k_2)$}}&&&&\\   
	&&&&&&&\\
	
	&&&&\multicolumn{2}{c}{\multirow{2}{*}{\Large $\ddots$}}&&\\   
	&&&&&&&\\
	
	\multicolumn{2}{c}{\multirow{2}{*}{\large $0$}}&&&&&\multicolumn{2}{c}{\multirow{2}{*}{\Large $J(k_s)$}}\\   
	&&&&&&&\\   
\end{array}\right],$$
where $k_1,\ldots, k_s$ are as defined in our definition of a Jordan basis.   
\end{lemma}
\begin{proof}
	As 
	$$\J= \{v_1,Nv_1,\ldots, N^{k_1}v_1\}\cup \cdots \cup \{v_s,Nv_s,\ldots, N^{k_s}v_s\}$$
	we see that 
	$$V = \spn(v_1,Nv_1,\ldots, N^{k_1}v_1)\oplus\  \cdots \oplus\ \spn(v_s,Nv_s,\ldots, N^{k_s}v_s).$$
	Certainly the $i$th summand is $N$-invariant.  Moreover, denoting the $i$th summand $U_i$ and its basis $\B_i =\{v_i,Nv_i,\ldots, N^{k_i}v_i\}$, we see from our warm-up that 
	$$\big[N|_{U_i}\big]_{\B_i} = J(k_i).$$  
	An application of Lemma~\ref{lem:block_diag_representation} now yields the final result.  
\end{proof}



%\begin{lemma}\label{lem:jordan_basis_exists2}
%	Fix $T\in\lin(V)$ and let $S=\{v_1,\ldots, v_m\}\subset V$ be a linearly independent set such that $T(S) \subset S$.  Moreover, assume there exists $R=\{u_1,\ldots, u_\ell\}\subset V$ such that 
%	\begin{enumerate}
%		\item $T(R)\subset S$,
%		\item $T(R)\cap T(S) =\emptyset$, and
%		\item $Tu_i \neq Tu_j$ when $i\neq j$.  
%	\end{enumerate}
%	Then $S\cup R$ is linearly independent.  
%\end{lemma}
%\begin{proof}
%	Assume there exists scalars $a_i$ and $b_i$ such that 
%	$$a_1u_1+\cdots a_\ell u_\ell + b_1v_1+\cdots b_\ell v_\ell=0_V.$$
%	Applying $T$ to both sides yields
%	$$\underbrace{a_1Tu_1+\cdots a_\ell Tu_\ell}_{\mbox{vectors in } T(R)} + \underbrace{b_1Tv_1+\cdots b_\ell Tv_\ell}_{\mbox{vectors in } T(S)}=0_V.$$
%	By our assumptions we see that the left hand side is a linear combination (disjoint) of vectors in $S$.  Therefore the $a_i$'s and $b_i$'s must be identically zero, proving $S\cup R$ is linearly independent.  
%\end{proof}






\begin{theorem}\label{thm:jordan_basis_exists}
Let $V$ be a nontrivial finite-dimensional vector space and let $N$ be a nilpotent operator on $V$.  Then there exists a Jordan basis for $V$ with respect to $N$.
\end{theorem}
\begin{proof}

Begin by setting $V_0 = \{0_V\}$ and defining $V_{i+1} =\makeset{v\in V}{Nv\in V_i}$. A straightforward argument shows that $V_i = \nul N^i$ and 
$$V_0\subset V_1 \subset \cdots \subset V_m = V,$$ 
for some $m$. In fact, as $V$ is nontrivial we must have $m\geq 1$. 

We now aim to prove the following, slightly stronger, result.  Given any set $S$ of linearly independent vectors such that 
\begin{equation}
\spn(S)\cap V_{m-1} = \{0_V\},\tag{$\star$}	
\end{equation}
there exists a Jordan basis $\J$ for $V$ such that $S$ is a set of (not necessarily all) $\J$-generating vectors.  We proceed by induction on $m$.  If $m=1$, then $V =\nul N$, and the result follows by the Basis Extension Theorem.  Now assume $m>1$ and let $S=\{v_1,\ldots, v_k\}$ be such that $(\star)$ holds.  By Lemma~\ref{lem:directsum_extension} we see that there exists a subset $W$ such that 
$$V=V_{m-1} \oplus W$$
and $S\subset W$. Extending $S$, if necessary, we may assume it is a basis for $W$.  

Now observe that $S'=\{Nv_1,\ldots, Nv_k \}\subset V_{m-1}$.  We claim that ($\star$) holds with $S'$ in place of $S$ and $V_{m-2}$ in place of $V_{m-1}$.  For the moment, let us assume this to be true.  Applying our inductive hypothesis to the vector space $V_{m-1}$ and the set $S'$ then gives us a Jordan basis $\J'$ for $V_{m-1}$ such that $S'$ is a set of $\J'$-generating vectors.  It now follows that $\J = \J'\ \cup\ S$, is a Jordan basis for all of $V$ and $S$ is a set of $\J$-generating vectors.  In light of this, it only remains to prove our claim.  

First we show $\spn(S')\ \cap\ V_{m-2}$ is trivial.  To this end, assume $a_i$ are such that
$$a_1Nv_1+\cdots+a_k Nv_k \in V_{m-2}.$$
By linearity, we see that $N(a_1v_1+\cdots+a_k v_k) \in V_{m-2}$.  Therefore $a_1v_1+\cdots+a_k v_k\in V_{m-1}\cap W = \{0_V\}$.  As the $v_i$ are independent, we must have all $a_i=0$.  We conclude $\spn(S')\ \cap\ V_{m-2}$ is trivial as needed.  

A similar argument shows that $S'$ is independent.   If the $a_i$ are now such that 
$$0_V=a_1Nv_1+\cdots a_k Nv_k=N(a_1v_1+\cdots a_k v_k),$$
then we see that 
$$a_1v_1+\cdots + a_k v_k \in W\  \cap\  \nul N\subset W\ \cap\ V_{m-1} = \{0_V\}.$$  
As the $v_i$ are independent, then all the $a_i$'s are zero.  This shows $S'$ is a independent.	
\end{proof}



%\begin{theorem}\label{thm:jordan_basis_exists2}
%Let $N$ be a nilpotent operator on $V$.  Then there exists a Jordan basis 
%$$\{v_1,Nv_1,\ldots, N^{m_1}v_1\}\cup \cdots \cup \{v_\ell,Nv_\ell,\ldots, N^{m_\ell}v_\ell\}$$
%for $V$ such that 
%$$\{N^{m_1}v_1, \ldots, N^{m_\ell}v_\ell\}$$
%is a basis for $\nul N$.    
%\end{theorem}
%\begin{proof}
%	We proceed by induction on $\dim V$.  If this dimension is 1, then the result is clear since any nonzero vector in $V$ constitutes such a Jordan basis.  Now assume the dimension is $n>1$.  Fix 
%	$$\dim(\nul N) = k\myand \dim(\ran N) = m$$
%	and  
%	$$\dim(\nul N\ \cap\  \ran N) = \ell.$$
%	As $N$ is nilpotent, then $\dim(\nul N) >0$ and therefore (by Rank-Nullity) $\dim(\ran N) <\dim V$. Moreover, the restricted map 
%	$$N|_{\ran N}:\ran N\to \ran N$$
%	is also nilpotent.  Applying our induction hypothesis to this smaller space yields a Jordan basis 
%	$$\B'= \{x_1,Nv_1,\ldots, N^{m_1}x_1\}\cup \cdots \cup \{x_\ell,Nx_\ell,\ldots, N^{m_\ell}x_\ell\}$$
%	for $\ran N$ with respect to $N|_{\ran N}$,	where $\Cc=\{N^{m_1}x_1,\ldots, N^{m_\ell}x_\ell\}$ is a basis for 
%	$$\nul(N|_{\ran N}) = \nul N\ \cap\ \ran N.$$
%	Next, choose $\ell$ vectors  $v_1,\ldots, v_\ell\in V$ such that $Nv_i = x_i$. Additionally, extend $\Cc$ to a basis 
%	$$\Cc\ \cup\ \{v_{\ell+1},\ldots, v_k\}$$
%	for all of $\nul N$.  We claim the set 
%	$$\B = \{v_1,\ldots,v_\ell,\ldots, v_k\}\ \cup\ \B'$$
%	is a Jordan basis for all of $V$ with respect to $N$.  It is clear that if $\B$ is a basis, then it is a Jordan basis.  As $|\B| = k+  m= \dim V$, it is enough to show $\B$ is linearly independent.  
%	By Lemma???? we see that 
%	$$S = \B'\ \cup\ \{v_{\ell+1},\ldots, v_k\}$$ 
%	is linearly independent.  With this set $S$ and  $R = \{v_1,\ldots, v_\ell\}$,  a straightforward check shows that the conditions needed to apply Lemma~\ref{lem:jordan_basis_exists} are met.  Therefore $\B = R\cup S$ is indeed linearly independent.  
%	
%\end{proof}

\begin{corollary}(Jordan Form)\label{cor:jordan_decomposition}
	Let $T$ be a complex operator on an $n$-dimensional space $V$ with distinct eigenvalues $\lambda_1,\ldots, \lambda_m$. Then there exists a basis $\B$ for $V$ so that 
	$$[T]_{\B} = \left[\begin{array}{cccccccc}
	\multicolumn{2}{c}{\multirow{2}{*}{\Large $A_1$}} &&&&&\multicolumn{2}{c}{\multirow{2}{*}{\Large $0$}} \\ 
	&&&&&&&\\
	   
	&&\multicolumn{2}{c}{\multirow{2}{*}{\Large $A_2$}}&&&&\\   
	&&&&&&&\\
	
	&&&&\multicolumn{2}{c}{\multirow{2}{*}{\Large $\ddots$}}&&\\   
	&&&&&&&\\
	
	\multicolumn{2}{c}{\multirow{2}{*}{\large $0$}}&&&&&\multicolumn{2}{c}{\multirow{2}{*}{\Large $A_m$}}\\   
	&&&&&&&\\   
\end{array}\right],$$ 
and $A_i$ is some $\dim \G_i \times \dim \G_i$ block diagonal matrix whose blocks are of the form 
$$\begin{bmatrix}
		\lambda_i&& &&\\
		1&\lambda_i&&&\\
		 &1&\ddots & &\\
		 & &  &&\\
		 & & &1&\lambda_i
	\end{bmatrix}.$$
\end{corollary}
\begin{proof}
By Theorem~\ref{thm:decomp_of_operators} we know that 
$$V = \G_{\lambda_i} \oplus \cdots \oplus \G_{\lambda_m}.$$
As each $\G_i$ is $T$ invariant, it will suffice to show, thanks to Lemma~\ref{lem:block_diag_representation}, that there exists a basis $\B_i$ for $\G_i$ so that $A_i$ may be taken to be
$$\big[T|_{\G_i}\big]_{\B_i}.$$  
From Example 5 above, we know that  $T-\lambda_i$ is nilpotent when restricted to $\G_i$.  Theorem~\ref{thm:jordan_basis_exists} now provides us with a Jordan basis $\B_i$ for $\G_i$ with respect to $(T-\lambda_i)$.  This indeed finishes the proof since Lemma~\ref{lem:jordan_form} tells us that the matrix  
$$\big[T|_{\G_i}\big]_{\B_i} = \big[(T-\lambda_i)|_{\G_i}\big]_{\B_i} + \big[\lambda_i\big]_{\B_i}$$
has the desired form.  
\end{proof}












\end{document}
