\documentclass[11pt]{amsart} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{eucal} \usepackage{yfonts} \usepackage[all]{xy} \usepackage{amsxtra} \usepackage{appendix} \usepackage[pdftex, breaklinks, linktocpage=true, bookmarksopen=true,bookmarksopenlevel=0,bookmarksnumbered=true]{hyperref} \hypersetup{ pdfauthor = {\textcopyright\ Bryden Cais}, pdfcreator = {\LaTeX\ with package \flqq hyperref\frqq}, colorlinks = {true} } \topmargin=-0.5in \oddsidemargin=-0.3in \evensidemargin=-0.3in \textwidth=7.1in \textheight=8.5in %\xymatrixcolsep{2.8pc} \CompileMatrices \entrymodifiers={+!!<0pt,\fontdimen22\textfont2>} %\def\objectstyle{\displaystyle} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Introduce a nice script font for sheaves \DeclareFontFamily{OT1}{rsfs}{} \DeclareFontShape{OT1}{rsfs}{n}{it}{<-> rsfs10}{} \DeclareMathAlphabet{\mathscr}{OT1}{rsfs}{n}{it} \DeclareFontFamily{OT1}{pzc}{} \DeclareFontShape{OT1}{pzc}{n}{it}{<->s*[2.2]pzc}{} \DeclareMathAlphabet{\mathpzc}{OT1}{pzc}{b}{sl} %\DeclareFontFamily{OT1}{pzc}{} %\DeclareFontShape{OT1}{pzc}{m}{it}{<-> s * [0.900] pzcmi7t}{} %\DeclareMathAlphabet{\mathpzc}{OT1}{pzc}{m}{it} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % These commands allow one to make roman numerals \makeatletter \newcommand{\rmnum}[1]{\romannumeral #1} \newcommand{\Rmnum}[1]{\expandafter\@slowromancap\romannumeral #1@} \makeatother %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Math Operators \DeclareMathOperator{\Ann}{Ann} \DeclareMathOperator{\depth}{depth} \DeclareMathOperator{\zar}{zar} \DeclareMathOperator{\Cat}{Cat} \DeclareMathOperator{\Cov}{Cov} \DeclareMathOperator{\can}{can} \DeclareMathOperator{\tot}{tot} \DeclareMathOperator{\gr}{gr} \DeclareMathOperator{\id}{id} \DeclareMathOperator{\spc}{sp} \DeclareMathOperator{\Frac}{Frac} \DeclareMathOperator{\ord}{ord} \DeclareMathOperator{\nil}{nil} \DeclareMathOperator{\bij}{bij} \DeclareMathOperator{\Sym}{Sym} \DeclareMathOperator{\Stab}{Stab} \DeclareMathOperator{\sgn}{sgn} % %\DeclareMathOperator{\pr}{pr} \newcommand*{\pr}{\rho} % \DeclareMathOperator{\Div}{Div} \DeclareMathOperator{\Hom}{Hom} \DeclareMathOperator{\End}{End} \DeclareMathOperator{\Ext}{Ext} \DeclareMathOperator{\Gal}{Gal} \DeclareMathOperator{\GL}{GL} \DeclareMathOperator{\SL}{SL} \DeclareMathOperator{\PSL}{PSL} \DeclareMathOperator{\PGL}{PGL} \DeclareMathOperator{\Aut}{Aut} \DeclareMathOperator{\Spec}{Spec} \DeclareMathOperator{\Spf}{Spf} \DeclareMathOperator{\Sp}{Sp} \DeclareMathOperator{\Proj}{Proj} \DeclareMathOperator{\coker}{coker} \DeclareMathOperator{\et}{\acute{e}t} \DeclareMathOperator{\rig}{rig} \DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\dR}{dR} \DeclareMathOperator{\Cris}{Cris} \DeclareMathOperator{\cris}{cris} \DeclareMathOperator{\MW}{MW} \DeclareMathOperator{\tr}{tr} \DeclareMathOperator{\Tr}{Tr} \DeclareMathOperator{\an}{an} \DeclareMathOperator{\Ner}{N\acute{e}r} \DeclareMathOperator{\Pic}{Pic} \DeclareMathOperator{\Alb}{Alb} \DeclareMathOperator{\sm}{sm} \DeclareMathOperator{\Extrig}{Extrig} \DeclareMathOperator{\Lie}{Lie} \DeclareMathOperator{\Inf}{Inf} %\DeclareMathOperator{\BT}{BT} \DeclareMathOperator{\reg}{reg} \DeclareMathOperator{\Ab}{Ab} \DeclareMathOperator{\tors}{tors} \DeclareMathOperator{\free}{fr} \DeclareMathOperator{\red}{red} \DeclareMathOperator{\smooth}{sm} \DeclareMathOperator{\Char}{char} \DeclareMathOperator{\nr}{nr} \DeclareMathOperator{\Mod}{Mod} \DeclareMathOperator{\Fil}{Fil} \DeclareMathOperator{\MF}{MF} \DeclareMathOperator{\rk}{rk} \DeclareMathOperator{\cork}{co-rk} \DeclareMathOperator{\st}{st} \DeclareMathOperator{\Rep}{Rep} \DeclareMathOperator{\tor}{tor} \DeclareMathOperator{\sep}{s} \DeclareMathOperator{\perf}{p} \DeclareMathOperator{\un}{un} \DeclareMathOperator{\projdim}{projdim} \DeclareMathOperator{\res}{res} \DeclareMathOperator{\Def}{Def} \DeclareMathOperator{\Ht}{ht} \DeclareMathOperator{\GD}{GD} \DeclareMathOperator{\Ig}{Ig} \DeclareMathOperator{\len}{length} \DeclareMathOperator{\cone}{cone} \DeclareMathOperator{\supp}{supp} \DeclareMathOperator{\im}{im} \DeclareMathOperator{\rad}{rad} \DeclareMathOperator{\Con}{Conn} \DeclareMathOperator{\Irr}{Irr} \DeclareMathOperator{\bal}{bal.} \DeclareMathOperator{\Ell}{Ell} \DeclareMathOperator{\Sets}{Sets} \DeclareMathOperator{\univ}{univ} \DeclareMathOperator{\MC}{M} \DeclareMathOperator{\Rad}{Rad} \DeclareMathOperator{\abs}{abs} \DeclareMathOperator{\Cot}{Cot} \DeclareMathOperator{\pdiv}{pdiv} \DeclareMathOperator{\ModFI}{ModFI} \DeclareMathOperator{\inv}{IF} \DeclareMathOperator{\mult}{m} \DeclareMathOperator{\loc}{ll} \DeclareMathOperator{\Jac}{Jac} \DeclareMathOperator{\Frob}{F} \DeclareMathOperator{\Ver}{V} \DeclareMathOperator{\proj}{proj} \DeclareMathOperator{\Mat}{Mat} \DeclareMathOperator{\Span}{span} \DeclareMathOperator{\Gr}{Gr} \DeclareMathOperator{\surj}{surj} \DeclareMathOperator{\Bilin}{Bilin} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %New Commands %%% The usual rings %%% \newcommand*{\R}{\ensuremath{\mathbf{R}}} \renewcommand*{\c}{\ensuremath{\mathbf{C}}} \newcommand*{\Z}{\ensuremath{\mathbf{Z}}} \newcommand*{\Q}{\ensuremath{\mathbf{Q}}} \newcommand*{\N}{\ensuremath{\mathbf{N}}} \newcommand*{\Qbar}{\overline{\Q}} \renewcommand*{\k}{\kappa} \newcommand*{\kbar}{\overline{k}} \newcommand*{\Kbar}{\overline{K}} %%% The usual schemes %%% \renewcommand*{\P}{\ensuremath{\mathbf{P}}} \newcommand*{\Gm}{\ensuremath{{\mathbf{G}_m}}} \newcommand*{\Ga}{\ensuremath{{\mathbf{G}_a}}} %%% Gothic letters (ideals) %%% \newcommand*{\m}{\mathfrak{M}} \newcommand*{\n}{\mathfrak{N}} \newcommand*{\p}{\mathfrak{p}} \newcommand*{\q}{\mathfrak{q}} \renewcommand*{\r}{\mathfrak{r}} \newcommand*{\s}{\mathfrak{S}} %%% Capital scripts (sheaves etc) \newcommand*{\A}{\ensuremath{\mathcal{A}}} \newcommand*{\B}{\mathcal{B}} \newcommand*{\scrC}{\mathscr{C}} \newcommand*{\C}{\mathbf{C}} \newcommand*{\E}{\mathscr{E}} \newcommand*{\F}{\mathbf{F}} \newcommand*{\scrF}{\mathscr{F}} \newcommand*{\scrS}{\mathscr{S}} \newcommand*{\scrW}{\mathscr{W}} \newcommand*{\G}{\mathcal{G}} \newcommand*{\scrG}{\mathscr{G}} \newcommand*{\h}{\mathscr{H}} \newcommand*{\I}{\mathscr{I}} \newcommand*{\J}{\mathcal{J}} \renewcommand*{\L}{\mathscr{L}} \newcommand*{\scrM}{\mathscr{M}} \newcommand*{\calM}{\mathcal{M}} \renewcommand*{\O}{\mathscr{O}} \newcommand*{\U}{\mathscr{U}} \newcommand*{\X}{\mathcal{X}} \newcommand*{\Y}{\mathcal{Y}} %%% script capitals %%% \newcommand*{\scrJ}{\mathscr{J}} \newcommand*{\calL}{\mathcal{L}} \newcommand*{\calS}{\mathcal{S}} \newcommand*{\scrP}{\mathscr{P}} %%% Various sheaves %%% \newcommand*{\scrHom}{\mathscr{H}\mathit{om}} \newcommand*{\scrExtrig}{\mathscr{E}\mathit{xtrig}} \newcommand*{\scrExt}{\mathscr{E}\mathit{xt}} \newcommand*{\scrLie}{\mathscr{L}\mathit{ie}} \newcommand*{\scrD}{\mathscr{D}} %%% Misc %%% \newcommand*{\barrho}{\overline{\rho}} \newcommand*{\invlim}{\varprojlim} \newcommand*{\tensorhat}{\widehat{\otimes}} \newcommand*{\D}{\ensuremath{\mathbf{D}}} \newcommand*{\M}{\ensuremath{\mathbf{M}}} \newcommand*{\calD}{\ensuremath{\mathcal{D}}} \renewcommand*{\H}{\ensuremath{\mathfrak{H}}} \newcommand*{\z}{\zeta} \newcommand*{\dual}{\vee} \renewcommand*{\qedsymbol}{\ensuremath{\blacksquare}} % end of proof \newcommand*{\eqdef}{\stackrel{\text{def}}{=}} % definition \newcommand*{\wa}[1]{{}^{\mathrm{w.a.}}\hspace{-0.4ex}{#1}} \newcommand*{\mfun}{\underline{\M}} \newcommand*{\Mfun}{\underline{\m}} \newcommand*{\Dfun}{\underline{D}} \newcommand*{\Gfun}{\underline{G}} \newcommand*{\Dual}[1]{\widehat{#1}} %\newcommand*{\R}{\ensuremath{\mathscr{R}}} \renewcommand*{\b}{\ensuremath{\mathrm{b}}} \renewcommand*{\int}{\ensuremath{\mathrm{int}}} \newcommand*{\bnd}{\ensuremath{\mathrm{bnd}}} \newcommand*{\e}{\ensuremath{\mathbf{e}}} \newcommand*{\Dst}{\ensuremath{{\underline{D}_{\st}}}} \renewcommand*{\div}{\ensuremath{\mathrm{div}}} \renewcommand*{\SS}{\ensuremath{\underline{\mathrm{ss}}}} \renewcommand*{\u}[1]{\underline{#1}} \renewcommand*{\o}[1]{\overline{#1}} \newcommand*{\wh}[1]{\widehat{#1}} \newcommand*{\nor}[1]{{#1}^{\mathrm{n}}} \newcommand*{\T}{\ensuremath{\mathbf{T}}} \newcommand*{\tens}{\mathop{\otimes}\limits} %\newcommand*{\Win}{\ensuremath{\mathscr{W}\!\mathit{in}}} %\newcommand*{\Win}{\textswab{Win}} %\newcommand*{\BT}{\textswab{BT}} \DeclareMathOperator{\Win}{Win} \DeclareMathOperator{\BT}{BT} \DeclareMathOperator{\Null}{null} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Define environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{thmdef}[theorem]{Theorem-Definition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{notation}[theorem]{Notation} \newtheorem{hypotheses}[theorem]{Hypotheses} \newtheorem{question}[theorem]{Question} \newtheorem{problem}[theorem]{Problem} \newtheorem{technique}[theorem]{Technique} \theoremstyle{remark} \newtheorem{example}[theorem]{Example} \newtheorem{remark}[theorem]{Remark} \newtheorem{remarks}[theorem]{Remarks} \newtheorem{exercise}[theorem]{Exercise} \newtheorem{warning}[theorem]{Warning} \newtheorem{convention}[theorem]{Convention} \include{header} \numberwithin{theorem}{subsection} \numberwithin{equation}{subsection} \newenvironment{dotlist} { \begin{list} {$\cdot$} { \setlength{\itemsep}{.5ex} \setlength{\parsep}{0ex} \setlength{\leftmargin}{1em} \setlength{\parskip}{0ex} \setlength{\topsep}{0ex} } } { \end{list} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %This command creates a footnote and an indicator mark in the margin pointing to problems, questions, or unresolved (small) issues %To use type \edit{ insert text here } \newcommand{\marginalfootnote}[1]{% \footnote{#1} \marginpar[\hfill{\sf\thefootnote}]{{\sf\thefootnote}}} \newcommand{\edit}[1]{\marginalfootnote{#1}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %This command creates a box marked ``To Do'' around text. %To use type \todo{ insert text here }. \newcommand{\todo}[1]{\vspace{5 mm}\par \noindent \marginpar{\textsc{ToDo}} \framebox{\begin{minipage}[c]{0.95 \textwidth} \tt #1 \end{minipage}}\vspace{5 mm}\par} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \bibliographystyle{plain} \title{Linear Algebra Outline\\ {\rm University of Arizona Integration Workshop, August 2011}} %\author{Bryden Cais} \address{University of Arizona, Tucson} \email{cais@math.arizona.edu} \thanks{These notes are heavily influenced by versions from previous years, especially those written by Nick Rogers, Dinesh Thakur, and Doug Ulmer.} %\subjclass[2000]{Primary: Secondary: } %\keywords{} \date{\today} %\begin{abstract} % %\end{abstract} \maketitle These notes are intended only as a rough summary of the background in linear algebra expected of incoming graduate students. With brevity as our guiding principle, we include virtually no proofs of the results stated in the text below. The reader is encouraged to fill in as many of the arguments and details as possible. \section{Lecture 1}\label{lec1} Throughout these notes, we fix a field $k$. \subsection{First definitions and properties} \begin{definition} A {\bf vector space} over $k$ is a set $V$ equipped with maps $+:V\times V\rightarrow V$ (addition) and $\cdot: k\times V\rightarrow V$ (scalar multiplication) which satisfy: \begin{enumerate} \item The pair $(V,+)$ forms an abelian group. That is: \begin{enumerate} \item $+$ is {\em commutative}: $v+w=w+v$ for all $v,w\in V$. \item $+$ is {\em associative}: $u+(v+w) = (u+v)+w$ for all $u,v,w\in V$. \item There {\em exists an additive identity} $0\in V$ such that $0+v=v$ for all $v\in V$. \item There {\em exist additive inverses}: for all $v\in V$, there exists $-v\in V$ such that $v+(-v)=0$. \end{enumerate} \item Scalar multiplication gives an action of the group $k^{\times}$ on $V$. That is \begin{enumerate} \item $a\cdot(b\cdot v) = (ab)\cdot v$ for all $a,b\in k$ and all $v\in V$. \item $1\cdot v=v$ for all $v\in V$. \end{enumerate} \item Scalar multiplication distributes over addition. That is \begin{enumerate} \item $a\cdot(v+w) = a\cdot v + a\cdot w$ for all $a\in k$ and all $v,w\in V$ \item $(a+b)\cdot v=a\cdot v+b\cdot v$ for all $a,b\in k$ and all $v\in V$. \end{enumerate} \end{enumerate} As is customary, we write the scalar product $a\cdot v$ simply as $av$, we will not mention $k$ when it is clear from context, and we will call elements of the set $V$ vectors. \end{definition} \begin{definition} Let $V$ be a vector space over $k$. A subset $W\subseteq V$ is called a {\bf subspace} of $V$ if $W$ is also a vector space over $k$ under the addition and scalar multiplication on $V$. \end{definition} \begin{remark} It is easy to see that a subset $W\subseteq V$ of a vector space $V$ is a subspace if and only if: \begin{enumerate} \item $W$ is nonempty. \item $W$ is closed under addition: $u+w\in W$ for all $u,w\in W$. \item $W$ is closed under scalar multiplication: $aw\in W$ for all $a\in k$ and all $w\in W$. \end{enumerate} Note that the subsets of a fixed vector space $V$ are partially ordered with respect to inclusion. \end{remark} \subsection{Constructions} We now discuss some fundamental constructions of new vector spaces and subspaces from old ones. \begin{example} The following are fundamental examples: \begin{enumerate} \item For any $k$, we have the {\bf zero vector space}, $0$, consisting of the single vector $0$. \item $k$ is a vector space over itself with respect to the canonical addition and multiplication. \item More generally, $k^n:=\{(a_1,\ldots,a_n)\ :\ a_i\in k\}$ is a vector space over $k$ with respect to coordinate-wise addition and scalar multiplication. \item For any vector space $V$, both $V$ and $0$ are subspaces of $V$. \end{enumerate} \end{example} \begin{definition} Let $V$ be a vector space over $k$ and let $\{W_i\}_{i\in I}$ a collection of subspaces of $V$. \begin{enumerate} \item The {\bf sum} of the $\{W_i\}$ is $$\sum_{i\in I} W_i:= \{\sum_{\substack{i\in J\\ J\subseteq I\ \text{finite}}}w_i\ :\ w_i\in W_i\ \text{for all}\ i\}.$$ It is a subspace of $V$, and is the smallest subspace of $V$ containing $W_i$ for all $i$. \item The {\bf intersection} of the $\{W_i\}$ is the set $$\bigcap_{i\in I} W_i:=\{v\in V\ :\ v\in W_i\ \text{for all}\ i\}.$$ It is a subspace of $V$, and is the largest subspace of $V$ contained in $W_i$ for all $i$. \end{enumerate} \end{definition} \begin{definition} Let $I$ be an index set and $\{V_i\}_{i\in I}$ a collection of vector spaces over $k$. \begin{enumerate} \item The {\bf direct product} of the $V_i$ is the cartesian product $$\prod_{i\in I} V_i:=\{(v_i)\ :\ v_i\in V_i\}$$ with coordinate-wise addition and scalar multiplication. \item The {\bf direct sum} of the $V_i$ is $$\bigoplus_{i\in I} V_i:= \{(v_i)\in \prod_{i\in I} V_i\ :\ v_i=0\ \text{for all but finitely many}\ i\}$$ with coordinate-wise addition and scalar multiplication. \end{enumerate} These are both vector spaces over $k$, and $\bigoplus V_i$ is a subspace of $\prod V_i$ with equality if and only if $I$ is a finite set or $V_i=0$ for all but finitely many $i$. \end{definition} \begin{definition} Let $V$ be a vector space over $k$ and $W$ a subspace of $V$. The {\bf quotient} of $V$ by $W$, written $V/W$, is the vector space whose underlying set is the set $\{v+W\ :\ v\in V \}$ of (left) cosets of $W$ in $V$, with addition and scalar multiplication given by \begin{equation*} (u+W) + (v+W) := (u+v) + W \qquad{respectively}\qquad a\cdot(v+W) := av + W. \end{equation*} One checks that this really is a vector space over $k$. \end{definition} \subsection{Span and linear independence, bases and dimension} \begin{definition} Let $V$ be a vector space over $k$. \begin{enumerate} \item Let $v\in V$ be any vector. The {\bf span} of $v$ is the subsace $k\cdot v:=\{av\ :\ a\in k\}$ of all $k$-multiples of $v$. \item Let $S\subseteq V$ be any subset of $V$. The {\bf span} of $S$ is the subspace $$\Span(S):=\sum_{v\in S} k\cdot v$$ of $V$ \end{enumerate} \end{definition} \begin{definition} Let $V$ be a vector space over $k$. \begin{enumerate} \item Let $v_1,\ldots, v_n\in V$ be arbitrary. We say that $v_1,v_2,\ldots, v_n$ are {\bf linearly independent} if the only solution to the equation \begin{equation*} \sum a_i v_i = 0 \end{equation*} is $a_1=a_2=\cdots = a_n = 0$. \item Let $S\subseteq V$ be any subset of $V$. We say that $S$ is a {\bf linearly independent} set of vectors if every finite subset of $S$ is linearly independent. Otherwise we say that $S$ is {\bf lineraly dependent}. \end{enumerate} \end{definition} \begin{definition} Let $V$ be a vector space over $k$ and $S$ a subset of $V$. We say that $S$ is a {\bf basis} of $V$ provided: \begin{enumerate} \item $S$ spans $V$, i.e. $\Span(S)=V$. \item $S$ is linearly independent. \end{enumerate} \end{definition} \begin{theorem}\label{fun} The following facts are fundamental: \begin{enumerate} \item Every vector space over $k$ has a basis (requires the axiom of choice). \item Any two bases of a given vector space have the same cardinality. \item Any maximal (with respect to inclusion) linearly independent subset of $V$ is a basis. \item Any minimal (with respect to inclusion) spanning subset of $V$ is a basis. \end{enumerate} \end{theorem} \begin{example} The {\bf standard basis} of $k^n:=\bigoplus_{i=1}^n k$ is the basis $\{e_i\}_{i=1}^n$ with $e_i:=(0,\ldots,0,1,0,\ldots,0)$ the vector whose entries are all 0 except for a 1 in the $i$ th position. Using this, it is easy to see that a choice of basis $S$ of a vector space $V$ is equivalent to an isomorphism $\bigoplus_{s\in S} k\simeq V$. \end{example} \begin{definition} Let $V$ be a vector space over $k$ and $S$ a basis of $V$. The {\bf dimension of $V$} is the cardinality of $S$, i.e.: $\dim_k(V):=\#S$. \end{definition} \begin{remark} As with every definition in these notes, it is possible to give an {\em intrinsic} definition of $\dim(V)$; i.e. one that does not use bases. It is not, however, possible to avoid the axiom of choice in showing that dimension is well defined in general (one ends up needing to know existence of maximal chains of subspaces). \end{remark} \begin{technique}[Coordinates]\label{coods} If $V$ is a vector space over $k$ and $S$ is a basis of $V$, then every nonzero $v\in V$ can be written as an {\em unique} linear combination of elements of $S$. That is, $v$ determines a unique tuple $\{a_s\}_{s\in S}\in k^S$ such that $a_s=0$ for all but finitely many $s\in S$ and $v=\sum_{s\in S} a_s s$. Note that this sum makes sense, as only finitely many of its summands are nonzero. We say that $\{a_s\}_{s\in S}$ are the {\bf coordinates of $v$ with respect to the basis $S$}. \end{technique} \subsection{Linear maps} \begin{definition} Let $V$ and $W$ be vector spaces over $k$. \begin{enumerate} \item A {\bf linear map} or a {\bf linear transformation} is a map of sets $T:V\rightarrow W$ which respects addition and scalar multiplication: \begin{enumerate} \item $T(u+v) = T(u)+T(v)$ for all $u,v\in V$. \item $T(av) = aT(v)$ for all $v\in V$ and all $a\in k$. \end{enumerate} \item Let $T:V\rightarrow W$ be a linear map. \begin{enumerate} \item The {\bf kernel of $T$} is $$\ker(T):=\{v\in V\ :\ T(v)=0\}.$$ It is a subspace of $V$. \item The {\bf image of $T$} is $$\im(T):=\{w\in W\ :\ w=T(v)\ \text{for some}\ v\in V\}.$$ It is a subspace of $W$. \end{enumerate} \end{enumerate} \end{definition} \begin{definition} Let $V$ and $W$ be vector spaces over $k$. We define \begin{equation*} \Hom(V,W):=\{\text{linear maps}\ T:V\rightarrow W\}. \end{equation*} This set is naturally a vector space over $k$ with addition with addition $(S+T)(v):=S(v)+T(v)$ and scalar multiplication $(aT)(v):=aT(v)$. In the special case that $W=k$, we obtain the {\bf dual} of $V$ given by $V^*:=\Hom(V,k)$. \end{definition} \begin{theorem}\label{dualisom} Let $V$ be a vector space over $k$. Then there is a canonical linear map \begin{equation} V\rightarrow V^{**}\qquad \text{given by}\qquad v\mapsto (f\mapsto f(v))\label{dbldual} \end{equation} which is injective. When $V$ has finite dimension $n$, then $V^*$ also has dimension $n$ and so $V$ and $V^*$ are {\em non-canonically} isomorphic.\footnote{Meaning that one must {\em choose} a basis of $V$ to exhibit an isomorphism $V\simeq V^*$} In particular, when $V$ has finite dimension, the map $(\ref{dbldual})$ is a canonical isomorphism of $V$ with $V^{**}$. \end{theorem} \begin{definition} Let $T:V\rightarrow W$ be a linear map of vector spaces over $k$. \begin{enumerate} \item The {\bf rank} of $T$ is $\rk(T):=\dim_k\im(T)$. \item The {\bf nullity} of $T$ is $\Null(T):=\dim_k\ker(T)$. \end{enumerate} \end{definition} \begin{theorem}\label{kerim} Let $V$ and $W$ be vector spaces over $k$ and $T:V\rightarrow W$ a linear map. There is a canonical isomorphism of $k$-vector spaces $$V/\ker(T)\simeq \im(T).$$ In particular, if $V$ and $W$ are finite dimensional then $$\rk(T)+\Null(T) = \dim(V)$$ \end{theorem} \begin{technique}[Matrix of a linear map]\label{cob} Let $V$ and $W$ be vector spaces over $k$ of finite dimension and $T:V\rightarrow W$ a linear transformation. Let $\mathbf{v}:=\{v_1,\ldots, v_n\}$ and $\mathbf{w}:=\{w_1,\ldots,w_m\}$ be bases of $V$ and of $W$, respectively. By Technique \ref{coods}, there are unique $a_{ij}\in k$ such that \begin{equation*} T(v_j) = \sum_{i=1}^m a_{ij} w_i\qquad\text{for}\ 1\le j\le n. \end{equation*} The {\bf matrix of $T$ with respect to the bases $\mathbf{v}$, $\mathbf{w}$} is the $m\times n$ matrix ${}_{\mathbf{w}}[T]_{\mathbf{v}}:=(a_{ij})$. If $v\in V$ has coordinates $(b_1,\ldots, b_n)$ with respect to the basis $\mathbf{v}$, then the coordinates of $T(v)$ with respect to $\mathbf{w}$ are given by the matrix product \begin{equation} \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix} \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{pmatrix}\label{matprod} \end{equation} Conversely, if $M$ is an arbitrary $m\times n$-matrix, then $M$ may be viewed as the linear transformation $M:k^n\rightarrow k^m$ whose associated matrix in the standard bases on source and target is $M$. In other words, choosing bases for $V$ and $W$ gives a bijection $$\Hom(V,W)\simeq \Mat_{m\times n}(k).$$ We will frequently utilize this perspective, and treat $m\times n$ matrices as linear transformations $k^n\rightarrow k^m$. \end{technique} \begin{remark} The set $\Mat_{m\times n}(k)$ is a $k$-vector space via addition and scalar multiplication of matrices. The bijection $\Hom(V,W)\simeq \Mat_{m\times n}(k)$ is readily checked to respect the natural vector space structure on both sides. In particular, $\Hom(V,W)$ has dimension $\dim(V)\cdot\dim(W)$. \end{remark} \begin{technique}[Change of basis] As a special case of Technique \ref{cob}, we have the following. Let $V$ be a finite-dimensional vector space over $k$ with fixed basis $\mathbf{e}=\{e_i\}_{i=1}^n$. Let $\mathbf{v}=\{v_i\}_{i=1}^n$be another basis of $V$. The {\bf change of basis matrix from $\mathbf{e}$ to $\mathbf{v}$} is the $n\times n$ matrix $A=(a_{ij}):={}_{\mathbf{v}}[\id_V]_{\mathbf{e}}$. \begin{enumerate} \item It follows easily from definitions that if $B:={}_{\mathbf{e}}[\id_V]_{\mathbf{v}}$ is the change of basis matrix from $\mathbf{v}$ to $\mathbf{e}$ then \begin{equation*} AB = BA = \id_{n}, \end{equation*} with $\id_n$ the $n\times n$ identity matrix. In particular, $A$ is invertible and $B=A^{-1}$. \item If $v\in V$ has coordinates $(b_1,\ldots, b_n)$ with respect to $\mathbf{e}$, then the coordinates of $v$ with respect to $\mathbf{v}$ are given by the matrix product as in (\ref{matprod}). \item Let $W$ be another finite dimensional vector space with fixed basis $\mathbf{f}=\{f_i\}_{i=1}^m$. Let $\mathbf{w}=\{w_i\}_{i=1}^m$ be another basis of $W$ and let $T:V\rightarrow W$ be a linear transformation. If $A:={}_{\mathbf{v}}[\id_V]_{\mathbf{e}}$ and $B:={}_{\mathbf{w}}[\id_W]_{\mathbf{f}}$ are the change of basis matrices, then the equality of matrices \begin{equation*} {}_{\mathbf{w}}[T]_{\mathbf{v}}= B ({}_{\mathbf{f}}[T]_{\mathbf{e}}) A^{-1} \end{equation*} holds. \end{enumerate} \end{technique} \subsection{Systems of equations and Gaussian elimination} \begin{technique}[Elementary row and column operations]\label{rowop} Let $M$ be any $m\times n$ matrix over $k$. \begin{enumerate} \item The following operations on $M$ are called {\bf elementary row operations} \begin{enumerate} \item Swap rows $i$ and $j$: $R_i\leftrightarrow R_j$. \item Multiply row $i$ by a {\em nonzero} scalar: $R_i\rightarrow aR_i$. \item Add {\em any} scalar multiple of row $j$ to row $i$: $R_i\rightarrow R_i+aR_j$. \end{enumerate} If $E$ is any one of these operations (so the $E(M)$ is the matrix obtained from $M$ by performing the row operation $E$ to $M$), then a little thought with change of basis matrices (or with explicit matrix multiplication) shows that the matrix equation \begin{equation*} E(M) = E(\id_m) M \end{equation*} holds. It is clear that each of these operations can be undone by an operation of the same type, so that $E(\id_m)$ is an invertible matrix. In particular, {\bf any (finite) succession of elementary row operations corresponds to left multiplication by an invertible matrix}. In fact, the converse is true as well. \item The following operations on $M$ are called {\bf elementary column operations} \begin{enumerate} \item Swap columns $i$ and $j$: $C_i\leftrightarrow C_j$. \item Multiply column $i$ by a {\em nonzero} scalar: $C_i\rightarrow aC_i$. \item Add {\em any} scalar multiple of column $j$ to column $i$: $C_i\rightarrow C_i+aC_j$. \end{enumerate} If $E$ is any one of these operations then as above one has the matrix equation \begin{equation*} E(M) = M E(\id_n) \end{equation*} holds. In particular, {\bf any (finite) succession of elementary column operations corresponds to right multiplication by an invertible matrix}, and the converse holds as well. \end{enumerate} \end{technique} \begin{technique}[Gaussian Elimination]\label{gauss} We say that a matrix $M$ is in {\bf row-echelon form} prvovided the following hold: \begin{itemize} \item All nonzero rows are above any row with all zeroe entries. \item The {\bf leading coefficient} (or {\bf pivot}) of any row (i.e. the first nonzero entry) is to the left of the pivot in every row beneath it. \end{itemize} We say that $M$ is in {\bf reduced row-echelon form} if, in addition, we have: \begin{itemize} \item Every pivot of $M$ is equal to $1$ and all entries above (and below) any pivot are equal to 0. \end{itemize} Let $M=(a_{ij})$ be an $m\times n$ matrix with entries in $k$. The following procedure (called Gaussian Elimination) uses only elementary row operations to bring $M$ to reduced row-echelon form: \begin{enumerate} \item Find the first column of $M$ (say column $j$) containing a nonzero entry in some row (row $i$). \item Swap row $i$ and row 1. \item Multiply row 1 by $1/a_{ij}$. The first nonzero entry in this row is now $1$. \item Subtract the appropriate multiple of row 1 from every row below it to obtain all zeroes in column $j$ below the first row. \item While $m > 1$, repeat the above procedure with $M$ replaced by the $(m-1)\times n$ submatrix of $M$ obtained from deleting the first row and $m$ replaced by $m-1$. \item For each pivot of the new matrix, subtract the appropriate multiple of the row containing that pivot from all rows above it so that the pivot is the only nonzero entry in its column. \end{enumerate} There is of course a variant of Gaussian elimination for columns; we leave this to the reader to work out as an exercise. \end{technique} \begin{technique} Let $T:V\rightarrow W$ be a linear transformation of finite dimensional vector spaces and let $\mathbf{v}$ and $\mathbf{w}$ be bases of $V$ and $W$, respectively. Set $M:={}_{\mathbf{w}}[T]_{\mathbf{v}}$. It follows from Technique \ref{rowop} that: \begin{enumerate} \item Any elementary row operation on $M$ is equivalent to left multiplying $M$ by a change of basis matrix on $V$. In particular, {\bf elementary row operations do not change $\ker(T)$}. \item Any elementary column operation on $M$ is equivalent to right multiplying $M$ by a change of basis matrix on $W$. In particular, {\bf elementary column operations do not change $\im(T)$}. \end{enumerate} In particular, if $M'$ is the reduced row-echelon form of $M$, then $\ker(M)=\ker(M')$ and we conclude that {\bf the nullity of $M$ is the number of zero-rows of $M'$}. Thanks to Theorem \ref{kerim}, {\bf the rank of $M$ is the number of leading entries of $M'$} (all of which are 1). \end{technique} \begin{technique}[Solving systems of linear equations]\label{solve} A {\bf system of $m$ linear equations in $n$ unknowns} is any collection of equations \begin{equation} \begin{alignedat}{5} a_{11}x_1 &+ a_{12}x_2 &+ \cdots &+ a_{1n}x_n &= b_1 \\ a_{21}x_1 &+ a_{22}x_2 &+ \cdots &+ a_{2n}x_n &= b_2 \\ \vdots & & \cdots & & \vdots \\ a_{m1}x_1 &+ a_{m2}x_2 &+ \cdots &+ a_{mn}x_n &= b_m \end{alignedat} \label{sys} \end{equation} in which the $a_{ij}$ and $b_i$ are fixed scalars and the $x_j$ are unknowns. A {\bf solution} of (\ref{sys}) is any vector $(x_1,\ldots,x_n)\in k^n$ satisfying every one of these equations. Let $A=(a_{ij})\in \Mat_{m\times n}(k)$ and let $b:=(b_1,\ldots,b_n)\in k^n$ and $\mathbf{x}:=(x_1,\ldots, x_n)$, viewed as column vectors. Then the system (\ref{sys}) is equivalent to the matrix equation $A\mathbf{x} = b.$ This may be solved by forming the {\bf augmented matrix} \begin{equation*} M:=\left(\begin{array}{cccc|c} a_{11} & a_{12} & \cdots & a_{1n} & b_1 \\ a_{21} & a_{22} & \cdots & a_{2n} & b_2 \\ \vdots & \vdots & \cdots & \vdots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} & b_m \end{array}\right) \end{equation*} and applying Gaussian elimination to bring it to reduced row-echelon form. The resulting augmented matrix corresponds to an equivalent system of equations whose solutions are easily determined inductively, starting with the equation corresponding to the bottom row and proceeding upwards via ``back-substitution". In the special case where $b=0$, this allows us to determine a basis of $\ker(A)$ for any $m\times n$ matrix $A$. \end{technique} \section{Lecture 2}\label{lec2} In this section, we assume that $k$ is algebraically closed, as it simplifies our treatment of eigenvalues. \subsection{Determinants and characteristic polynomial} \begin{definition} Let $n$ be a positive integer.% and set $V:=k^n$. %We identify $\Mat_{n\times n}(k)$ with $V^n$ by assigning to each $(v_1,\ldots, v_n)\in V^n$ %the $n\times n$ matrix whose $i$-th column is $v_i$. A {\bf determinant function} is a map $D:\Mat_{n\times n}(k) \rightarrow k$ satisfying \begin{enumerate} \item $D$ is multilinear. That is, for each $i$ with $1\le i\le n$, the function $D$ is a linear map on the $i$-th row when the other $n-1$ rows are fixed. %each $i$ with $1\le i\le n$ and any (fixed) $n-1$-vectors %$v_1,\ldots,v_{i-1},v_{i+1},\ldots, v_n\in V$, %the function %\begin{equation*} % D_i:V\rightarrow k\qquad v\mapsto D(v_1,v_2,\ldots, v_{i-1},v,v_{i+1},\ldots, v_n) %\end{equation*} %is a linear map. \item $D(A)=0$ whenever $A$ has two equal rows. %$D$ is alternating: If $A\in \Mat_{n\times n}(k)$ and $A'$ is obtained %from $A$ by switching two rows, then $D(A)=-D(A')$.\footnote{If $k$ has characteristic $2$, %then we require moreover that $D(A)=0$ whenever $A$ has two equal rows. This latter %requirement is automatic outside of characteristic 2.} \item $D(\id_n)=1$. \end{enumerate} \end{definition} \begin{theorem} For any positive integer $n$, a determinant function exists and is unique. It is given by \begin{equation} \det((a_{ij})) := \sum_{\sigma\in S_n} \sgn(\sigma)\prod_{i=1}^n a_{i\sigma(i)} \label{detdef} \end{equation} Here, the sum is over all permutations $\sigma$ of the set $\{1,2,\ldots, n\}$ and $\sgn(\sigma)$ is the {\em sign} of $\sigma$.\footnote{One possible definition is that $\sgn(\sigma)$ is $(-1)^{d(\sigma)}$, where $d(\sigma)$ is the number of transpositions in (any) product decomposition of $\sigma$ into transpositions.} In addition to the characterizing properties listed above, $\det$ satisfies: \begin{enumerate} \item $\det(AB)=\det(A)\det(B)$. \item $\det(A)=\det(A^t)$, where $A^t$ is the transpose of $A$. \item $A$ is an invertible matrix if and only if $\det(A)\in k^{\times}$. \item If $A,B\in \Mat_{n\times n}(k)$ with $A$ invertible, then $\det(ABA^{-1})=\det(B)$. \end{enumerate} \end{theorem} \begin{technique} There are a number of useful computational techniques for computing determinants, the most common of which is {\em Laplace's Formula}. Let $A=(a_{ij})$ be an $n\times n$ matrix and define $M_{ij}$ to be the {\bf $(i,j)$-minor} of $A$, i.e. the determinant of the $(n-1)\times (n-1)$ submatrix of $A$ obtained by deleting the $i$-th row and $j$-th column. By definition, the {\bf $(i,j)$-cofactor} of $A$ is $(-1)^{i+j}M_{ij}$. Then for any fixed $i$ (respectively $j$) one has \begin{equation*} \det(A)= \sum_{j=1}^n(-1)^{i+j}a_{ij}M_{ij}\qquad\text{respectively}\qquad \det(A)= \sum_{i=1}^n(-1)^{i+j}a_{ij}M_{ij} \end{equation*} These formulae allow one to inductively compute the determinant of any square matrix. \end{technique} \begin{thmdef} Let $V$ be a finite dimensional vector space over $k$ and $T:V\rightarrow V$ a linear map. For each basis $\mathbf{e}$ of $V$, the number $\det({}_{\mathbf{e}}[T]_{\mathbf{e}})$ is independent of $\mathbf{e}$; we call this number the {\bf determinant of $T$} and denote it $\det(T)$. \end{thmdef} \begin{remark} There is of course an {\em intrinsic} way to define the determinant of a linear map which avoids the crutch of bases and matrices. This method involves exterior algebra, which we do not discuss in these notes. However, we {\em highly encourage} the reader to study tensor and wedge products. In what follows, we will phrase things in terms of linear maps; the corresponding definitions and theorems for matrices follow immediately from the discussion in Technique \ref{cob}. \end{remark} In what follows, we fix an $n$-dimensional vector space $V$ and a linear map $T:V\rightarrow V$. \begin{definition} %Let $T:V\rightarrow V$ be a linear map on an $n$-dimensional vector space $V$. The {\bf characteristic polynomial of $T$} is % Let $M\in \Mat_{n\times n}(k)$ and let $x$ be a variable. We may view $M-x\cdot\id_n$ % as an element of $\Mat_{n\times n}(k(x))$, where $k(x)$ is the field of rational functions % in $x$. The {\bf characteristic polynomial of $M$} is \begin{equation*} \Char_T(x):=\det(T-x\cdot \id). \end{equation*} % Although this is {\em a priori} an element of $k(x)$, it is easy to see Using the definition (\ref{detdef}) of the determinant and its basic properties, it is easy to see that the following hold: \begin{enumerate} \item $\Char_T(x)$ is a monic degree $n$ polynomial in $x$ with coefficients in $k$. \item The constant term of $\Char_T(x)$ is $(-1)^n\det(T)$. %\item The roots of $\Char_M(x)$ are precisely the eigenvalues of $M$. \end{enumerate} % The characteristic polynomial of a linear map $T:V\rightarrow V$ on a finite-dimensional % vector space is the characteristic polynomial of the matrix of $T$ in any basis of $V$, % and is denoted $\Char_T(x)$. \end{definition} \begin{theorem}[Cayley--Hamilton] Every linear map satisfies its characteristic polynomial: %Let $T:V\rightarrow V$ be a linear map on an $n$-dimensional vector space $V$. $\Char_T(T) = 0$. \end{theorem} It follows from the Cayley--Hamilton Theorem that there {\em exists} a polynomial (of degree $n$, in fact) satisfied by $T$, and hence that the set of {\em all} monic polynomials satisfied by $T$ is nonempty. The well-ordering principle (using the degree of a polynomial) then guarantees the existence of a monic polynomial of least degree satisfied by $T$. Using the fact that $k[x]$ is a principal ideal domain and monicity, one shows that any two such polynomials are equal: \begin{definition} % Let $T:V\rightarrow V$ be a linear map on an $n$-dimensional vector space $V$. The {\bf minimal polynomial} of $T$, written $\min_T(x)$, is the monic polynomial of least degree satisfied by $T$. \end{definition} \begin{theorem} % Let $T:V\rightarrow V$ be a linear map on an $n$-dimensional vector space $V$ and let Let $p(x)\in k[x]$ be any polynomial with $p(T)=0$. Then $\min_T$ divides $p$. In particular, $\min_T$ divides $\Char_T$. Furthermore, $\Char_T$ divides some power of $\min_T$; in other words, the roots of $\Char_T$ are precisely the roots of $\min_T$ $($although the multiplicities may be different$)$. \end{theorem} \subsection{Eigenvalues and eigenvectors} \begin{definition} % Let $V$ be a vector space over $k$ and $T:V\rightarrow V$ a linear map. A scalar $\lambda\in k$ is said to be an {\bf eigenvalue of $T$} if there exists a {\em nonzero} vector $v\in V$ such that \begin{equation} Tv=\lambda v.\label{evec}\qquad\text{or equvalently}\qquad (T-\lambda)v=0 \end{equation} Any vector $v$ satisfying (\ref{evec}) is called an {\bf eigenvector of $T$ corresponding to $\lambda$}. %Equivalently, an eigenvector corresponding to $\lambda$ is any element of $\ker(T-\lambda)$. A {\bf generalized eigenvector corresponding to $\lambda$} is any $v\in V$ satisfying \begin{equation*} (T-\lambda)^j v = 0\qquad\text{for some}\ j>0.\label{genevec} \end{equation*} For an eigenvalue $\lambda$ of $T$, the associated {\bf generalized eigenspace} is the set $U_{\lambda}$ of all $u\in V$ which satisfy (\ref{genevec}). It is easy to see that $U_{\lambda}$ is a subspace of $V$. The {\bf multiplicity} of an eigenvalue $\lambda$ of $T$ is by definition $\dim(U_{\lambda})$. We define eigenvalues, (generalized) eigenvectors, and eigenspaces of $n\times n$ matrices to be the corresponding objects of the associated linear maps on $k^n$. \end{definition} \begin{theorem}\label{eigenthm} %Let $T:V\rightarrow V$ be a linear map on an $n$-dimensional vector space $V$. Let $V$ and $T$ be as above. \begin{enumerate} \item The eigenvalues of $T$ are precisely the roots of $\Char_T(x)$ $($equivalently $\min_T(x)$$)$. \item The multiplicity of an eigenvalue of $T$ is equal to its multiplicity as a root of $\Char_T(x)$. \item Each $U_{\lambda}$ is stable by $T$; i.e. the restriction $T\big|_{U_{\lambda}}$ of $T$ to $U_{\lambda}$ has image in $U_{\lambda}$. \item If $\lambda\neq \lambda'$ are distinct eigenvalues of $T$ then $U_{\lambda}\cap U_{\lambda'}=0$. \item Let $\lambda_1,\ldots, \lambda_r$ be the distinct eigenvalues of $T$ The inclusion mapping $\sum_{i=1}^r U_{\lambda_i}\rightarrow V$ induces an isomorphism \begin{equation*} \bigoplus_{i=1}^r U_{\lambda_i} \simeq V\label{eigendecomp} \end{equation*} \label{eigendecomp} % \item For any eigenvalue $\lambda$, we have $U_{\lambda}=\ker\left((M-\lambda\id_n)^{n}\right).$ \end{enumerate} \end{theorem} \begin{technique}[Finding eigenvalues and vectors] Let $M\in \Mat_{n\times n}(k)$. To find the eigenvalues of $M$, we simply find all roots of $\Char_M(x)$. For each eigenvalue $\lambda$, we can then determine a basis of the space of eigenvectors with eigenvalue $\lambda$ by using Technique \ref{solve} to find a basis of $\ker(M-\lambda\cdot \id_n)$. \end{technique} %Consider the restriction $T\big|_{U_{\lambda}}:U_{\lambda}\rightarrow U_{\lambda}$. By definition %of $U_{\lambda}$, there is a positive integer $r$ (depending on $\lambda$) such that %\begin{equation*} % (T-\lambda)\big|_{U_{\lambda}}^r = 0\qquad\text{on}\ U_{\lambda}; %\end{equation*} %in other words, $(T-\lambda)\big|_{U_{\lambda}}$ is {\bf nilpotent}. If $r$ is the minimal %integer with this property, then there exists $u\in U_{\lambda}$ with %\begin{equation*} % (T\big|_{U_{\lambda}}-\lambda)^{r-1}(u)\neq 0. %\end{equation*} \begin{definition} We say that $T$ is: \begin{enumerate} \item {\bf nilpotent} if $T^s=0$ for some positive integer $s$, or equivalently: \begin{enumerate} \item In Theorem \ref{eigenthm} (\ref{eigendecomp}) we have $r=1$ and $\lambda_1=0$. \item $\min_T$ and $\Char_T$ are both powers of $x$. \end{enumerate} \item {\bf semisimple} if any $T$-stable subspace $W\subseteq V$ admits a $T$-stable complement, % $W'$ (i.e. $W\oplus W'\simeq V$), or equivalently \begin{enumerate} \item $\min_T$ is square-free. \item $V$ admits a basis of eigenvectors. \item Every generalized eigenvector is an eigenvector. \item There exists a basis of $V$ in which the matrix of $T$ is diagonal. \end{enumerate} \end{enumerate} \end{definition} \begin{technique}[Diagonalizing] Let $M\in \Mat_{n\times n}(k)$. We describe an algorithm to determine whether or not $M$ is diagonalizable, and when it is, to find a matrix $P$ with $P^{-1}MP$ a diagonal matrix. \begin{enumerate} \item Compute $\Char_M(x)$. \item For each root $\lambda$ of $\Char_M(x)$, use Technique \ref{solve} to determine a basis $B_{\lambda}$ of $\ker(M-\lambda\cdot\id_n)$. \item If $\sum_{\lambda} \#B_{\lambda} < n$, then $M$ is not diagonalizable. \item Otherwise, let $B=\bigcup_{\lambda} B_{\lambda}$; it is a basis of $V$ $k^n$ consisting of eigenvectors of $M$. Let $P$ be the $n\times n$ matrix whose columns are the elements of $B$; it is an invertible matrix satisfying \begin{equation*} P^{-1}MP = D \end{equation*} where $D$ is a diagonal matrix whose diagonal entries are the eigenvalues of $M$ (with multiplicity). \end{enumerate} \end{technique} \subsection{Jordan canonical form} \begin{definition} The {\bf Jordan block} of size $s$ associated to $\lambda\in k$ is the $s\times s$ matrix \begin{equation*} J_{\lambda,s}:=\begin{pmatrix} \lambda & 1 & 0 & \cdots & 0 \\ 0 & \lambda & 1 & \cdots & 0 \\ \vdots & & \ddots & & \vdots \\ 0 & & \cdots & & \lambda \end{pmatrix} \end{equation*} with $\lambda$'s on the diagonal, $1$'s on the super-diagonal, and $0$'s elsewhere. \end{definition} By studying the nilpotent operators $(T-\lambda)\big|_{U_{\lambda}}$, one proves: \begin{theorem}[Jordan Canonical Form] Let $T:V\rightarrow V$ be a linear map on an $n$-dimensional vector space. There exists a basis of $V$ with respect to which the matrix of $T$ is in the block diagonal form $($called {\bf Jordan form}$)$ \begin{equation} \begin{pmatrix} J_{\lambda_1,s_1} & & & \\ & J_{\lambda_2,s_2} & & \\ & & \ddots & \\ & & & J_{\lambda_t,s_t} \end{pmatrix}\label{Jform} \end{equation} Here, $\lambda_1,\ldots,\lambda_t$ are (not necessarily distinct) eigenvalues of $T$. For any eigenvalue $\lambda$, the dimension of $U_{\lambda}$ is equal to the sum of the sizes all Jordan blocks above that are associated to $\lambda$. The Jordan form of $T$ is uniquely determined by $T$, up to permutations of the Jordan blocks. Said differently, there exists an invertible matrix $P\in \Mat_{n\times n}(k)$ such that $PMP^{-1}$ is equal to a matrix of the form $(\ref{Jform})$. \end{theorem} \begin{theorem}[Abstract Jordan form] Let $T:V\rightarrow V$ be a linear map on a finite dimensional vector space. Then $T$ can be written as a sum $T=S+N$ with $S:V\rightarrow V$ semisimple and $N:V\rightarrow V$ nilpotent, with $SN=NS$. \end{theorem} \begin{technique}[Computing Jordan form] Let $M\in \Mat_{n\times n}(k)$. To find the Jordan form of $M$, we proceed as follows: \begin{enumerate} \item Compute $\Char_M(x)$. \item Determine all distinct roots $\{\lambda_1,\ldots,\lambda_r\}$ of $\Char_M(x)$ and their multiplicities $\{m_1,\ldots, m_r\}$. \item For each $i$, compute $n_j:=\Null((M-\lambda_i\cdot\id_{n})^j)$ for $1\le j\le m_i/2$ using Gaussian elimination. \item For each partition $p:=(a_1,\ldots, a_v)$ of $m_i$ into nonnegative integers, and each $j$ above, compute \begin{equation*} z_j:=\sum_{i:\ a_i \ge j} j + \sum_{i:\ a_i < j} a_i. \end{equation*} \item For each $i$, there will be an unique partition $(a_1,\ldots,a_v)$ with $n_j=z_j$ for all $j$. The Jordan blocks in the Jordan form of $M$ corresponding to $\lambda_i$ are then $J_{\lambda_i,a_{\ell}}$ for $1\le\ell\le v$. \end{enumerate} \end{technique} \begin{remark} For each distinct eigen value $\lambda_i$ of $M$, let $s_i$ be the size of the largest Jordan block associated to $\lambda_i$. Then $\sum s_i$ is equal to the degree of $\min_M$. This fact is often useful in speeding up the computation of the Jordan form of $M$. \end{remark} \section{Lecture 3}\label{lec3} \subsection{Bilinear forms} \begin{definition} Let $V$ be a vector space over $k$. A {\bf bilinear form on $V$} is a map $f: V\times V\rightarrow k$ satisfying \begin{enumerate} \item $f(au+v,w) = af(u,w) + f(v,w)$ \item $f(u,av+w) = af(u,v)+ f(u,w)$ \end{enumerate} for all $u,v,w\in V$ and any $a\in k$. That is, $f$ is a linear map in each argument when the other argument is held fixed. We will sometimes write $\langle u,v\rangle$ for $f(u,v)$ if $f$ is clear form context. We denote by $\Bilin(V,V)$ the set of all bilinear forms on $V$. \end{definition} It is easy to see that any scalar multiple of a bilinear form or any sum of two bilinear forms is again a bilinear form. This gives $\Bilin(V,V)$ the structure of a vector space over $k$. Moreover, any bilinear form $f$ on $V$ gives rise to {\em two} canonical linear maps \begin{align*} &L_f: V\rightarrow V^*\qquad\text{given by}\qquad L_f(v) (w) := f(v,w)\\ &R_f: V\rightarrow V^*\qquad\text{given by}\qquad R_f(v) (w) := f(w,v)\\ \end{align*} \begin{definition} Let $f:V\times V\rightarrow k$ be a bilinear form. We say that $f$ is: \begin{enumerate} \item {\bf Left (respectively right) nondegenerate} if $L_f$ (respectively $R_f$) is injective. \item {\bf Nondegenerate} if it is both left and right nondegenerate. \item {\bf Symmetric} if $f(u,v)=f(v,u)$ for all $u,v\in V$ (equivalently $L_f=R_f$). \item {\bf Skew symmetric} if $f(u,v)=-f(v,u)$ for all $u,v\in V$ (equivalently $L_f = -R_f$). \item {\bf Alternating} if $f(v,v) = 0$ for all $v\in V$. \item {\bf Reflexive} if $f(u,v)=0 \iff f(v,u)=0$ for all $u,v\in V$. \end{enumerate} \end{definition} \begin{remark} Every alternating form $f$ satisfies $f(u,v)=-f(v,u)$ and hence is skew-symmetric. If $\Char(k)\neq 2$ then the converse holds and every skew-symmetric form is alternating. In characteristic 2, the notions of skew-symmetric and symmetric coincide, and there are alternating forms which are not (skew-) symmetric. \end{remark} \begin{theorem} Let $f:V\times V\rightarrow V$ be a bilinear form. If $\Char(k)\neq 2$ then there exist unique bilinear forms $f^{\pm}$ on $V$ with $f^+$ symmetric and $f^{-}$ alternating $($equivalently skew-symmetric$)$ such that $f=f^+ + f^-$. \end{theorem} It is easy to see that any alternating or symmetric bilinear form is reflexive. In fact, the converse holds: \begin{theorem} A reflexive bilinear form on a vector space $V$ is either symmetric or alternating. \end{theorem} \begin{definition} Let $f$ be a reflexive (i.e. symmetric or alternating) bilinear form on a vector space $V$. \begin{enumerate} \item We say that $u,v\in V$ are {\bf orthogonal} with respect to $f$ if $f(u,v)=0$. Thanks to the reflexivity of $f$, orthogonality is a symmetric condition; i.e. $u$ and $v$ ore orthogonal if and only if $v$ and $u$ are orthogonal. \item A vector $v\in V$ is {\bf isotropic} with respect to $f$ if $f(v,v)=0$. \item A vector $v\in V$ is {\bf anisotropic} with respect to $f$ if $f(v,v)\neq 0$. \item If $W\subseteq V$ is a subspace of $V$, we define the {\bf orthogonal complement of $W$ in $V$} to be $$W^{\perp}:=\{v\in V\ :\ f(v,w)=0\ \text{for all}\ w\in W\}.$$ \item The {\bf radical} of a subspace $W\subseteq V$ with respect to $f$ is $$\rad(W):=W\cap W^{\perp}.$$ \item A subspace $W\subseteq V$ is \begin{enumerate} \item {\bf Isotropic} with respect to $f$ if $\rad(W)=W$. \item {\bf Coisotropic} with respect to $f$ if $\rad(W)=W^{\perp}$. \item {\bf Lagrangian} with respect to $f$ if it is isotropic and coisotropic, or equivalently if $W=W^{\perp}$. \item {\bf Nondegenerate} with respect to $f$ if $\rad(W)=0$. \end{enumerate} \end{enumerate} \end{definition} \begin{theorem} Let $f$ be a reflexive bilinear form on a vector space $V$ and $W\subseteq V$ a nondegenerate subspace of $V$. Then $V=W\oplus W^{\perp}$. \end{theorem} \begin{definition}[Quadratic form associated to a symmetric bilinear form] Let $f$ be a symmetric bilinear form on a vector space $V$. The {\bf quadratic form} associated to $f$ is the map $$q:=q_f : V\rightarrow k \qquad\text{given by}\qquad q_f(v) = f(v,v).$$ If $\Char(k)\neq 2$ then $q_f$ determines $f$ via the identity $$f(u,v) = \frac{1}{2}(q_f(u+v) - q_f(u)-q_f(v))$$ \end{definition} \begin{technique}[Matrix of a bilinear form] Let $V$ be a vector space over $k$ of dimension $n$ and $f$ a bilinear form on $V$. If $\mathbf{e}=\{e_1,\ldots,e_n\}$ is any basis of $V$, then the {\bf matrix of $f$ with respect to $\mathbf{e}$} is the matrix $[f]_{\mathbf{e}}:=(f(e_i,e_j))$. \end{technique} Since $f$ is bilinear, the matrix $[f]_{\mathbf{e}}$ determines $f$. More precisely, if $u,v\in V$ have coordinates $X:=(u_1,\ldots,u_n)$ and $Y:=(v_1,\ldots,v_n)$ with respect to $\mathbf{e}$, then one checks that we have \begin{equation*} f(u,v) = X[f]_{\mathbf{e}}Y^t. \end{equation*} In fact, for any basis $\mathbf{e}$ of $V$, the resulting map of sets \begin{equation*} \Bilin(V,V)\rightarrow \Mat_{n\times n}(k)\qquad\text{given by}\qquad f\mapsto [f]_{\mathbf{e}} \end{equation*} is an isomorphism of vector spaces over $k$. \begin{technique}[Change of basis for a bilinear form] Let $V$ be an $n$-dimensional vector space over $k$ and $f$ a bilinear form on $V$. Let $\mathbf{e}$ and $\mathbf{e}'$ be two bases of $V$ and denote by $P:={}_{\mathbf{e}}[\id_V]_{\mathbf{e'}}$ the change of basis matrix from $\mathbf{e}$-coordinates to $\mathbf{e}'$-coordinates. Then \begin{equation*} [f]_{\mathbf{e}'} = P^t [f]_{\mathbf{e}} P \end{equation*} \end{technique} Let $V$ be a finite dimensional vector space and $f$ a bilinear form on $V$. The map $L_f:V\rightarrow V^*$ induces, by pullback, a linear mapping \begin{equation} V^{**}\rightarrow V^*\qquad\text{given by}\qquad \theta\mapsto \theta\circ L_f. \label{LfDual} \end{equation} On the other hand, as $V$ is of finite dimension we have a canonical isomorphism $V\simeq V^{**}$ given as in Theorem dualisom. We thus obtain a map \begin{equation*} L_f^*: V\simeq V^{**}\xrightarrow{(\ref{LfDual})} V^* \end{equation*} \begin{theorem} Let $V$ and $f$ be as above. Then $L_f^*=R_f$. In particular, $\rk(R_f)=\rk(L_f)$. \end{theorem} \begin{definition} Let $f$ be a bilinear form on a finite dimensional vector space $V$. The {\bf rank} of $f$ is the number $\rk(f):=\rk(R_f)=\rk(L_f)$. \end{definition} \begin{corollary}\label{equivs} Let $f$ be a bilinear form on an $n$-dimensional vector space $V$. The following are equivalent: \begin{enumerate} \item $f$ is left nondegenerate. \item $L_f:V\rightarrow V^*$ is an isomorphism. \item $f$ is right nondegenerate. \item $R_r:V\rightarrow V^*$ is an isomorphism. \item $f$ is nondegenerate. \item $\rk(f)=n$ \item The matrix $[f]_{\mathbf{e}}$ of $f$ in any basis $\mathbf{e}$ has rank $n$. \end{enumerate} \end{corollary} %\begin{theorem}\label{strthm} % Let $V$ be a finite dimensional vector space over a field $k$ of characteristic zero, % and $f$ a symmetric bilinear form on $V$. Then there exists a basis of $V$ % with respect to which the matrix of $f$ is diagonal. %\end{theorem} \subsection{The cases $k=\R$ and $k=\C$} In the special case that $k=\R$ (the real numbers) or $k=\C$ (complex numbers), we may use the ordering on $\R$ combined with the absolute value on $\C$ to further develop the theory of pairings on vector spaces. We begin with a slight variant on the notion of symmetric bilinear form which is adapted to the case when the base field is $\C$. \begin{definition} Let $V$ be a vector space over $\C$. A {\bf Hermitian form} on $V$ is a map $f: V\times V\rightarrow V$ satisfying \begin{enumerate} \item $f(au+v,w) = af( u,w) + f( v, w)$ \item $f( u,v) = \o{f( v,u)}$ \end{enumerate} for all $u,v,w\in V$ and all $a\in \C$. These conditions force \begin{enumerate} \stepcounter{enumi} \stepcounter{enumi} \item $f(v,au+w) = \o{a}f( v,u) + f( v, w)$ \item $f(v,v)\in \R$ \end{enumerate} for all $u,v,w\in V$ and $a\in \C$. \end{definition} \begin{technique}[Matrix of an Hermitian form] Let $V$ be a vector space over $\C$ of dimension $n$ and $f$ an Hermitian form on $V$. If $\mathbf{e}=\{e_1,\ldots,e_n\}$ is any basis of $V$, then the {\bf matrix of $f$ with respect to $\mathbf{e}$} is the matrix $[f]_{\mathbf{e}}:=(f(e_i,e_j))$. If $u,v\in V$ have coordinates $X:=(u_1,\ldots,u_n)$ and $Y:=(v_1,\ldots,v_n)$ with respect to $\mathbf{e}$, then one checks that we have \begin{equation*} f(u,v) = X[f]_{\mathbf{e}}\o{Y}^t. \end{equation*} \end{technique} %This induces a bijection between the set of Hermitian forms on $V$ and the set of %$n\times n$ matrixes We have the following general structure theorem: \begin{theorem}\label{str} Let $V$ be a finite dimensional vector space over $k$. \begin{enumerate} \item If $k$ has characteristic zero and $f$ is a symmetric bilinear form on $V$ of rank $r$ then there exists a basis of $V$ with respect to which the matrix of $f$ is diagonal, with exactly $r$ nonzero $($diagonal$)$ entries. \item If $k=\R$ and $f$ is a symmetric bilinear form on $V$ of rank $r$ then there exists a basis $\mathbf{e}$ of $V$ with respect to which the matrix of $f$ is diagonal, with diagonal entries $$f(e_i,e_i)=\pm 1\qquad\text{for}\ 1\le i\le r\qquad\text{and}\ f(e_i,e_i)=0\ \text{for}\ r < i\le n.$$ Furthermore, the number of $-1$'s on the diagonal depends only on $f$, and not on any choice of basis.\label{realstr} \item If $k=\C$ and $f$ is an Hermitian form on $V$ then then there exists a basis $\mathbf{e}$ of $V$ with respect to which the matrix of $f$ is diagonal, with all diagonal entries equal to $1$ or $0$. \end{enumerate} \end{theorem} \begin{remark} The result of Theorem \ref{str} (\ref{realstr}) allows us to define the {\bf signature} of a symmetric bilinear form on a vector space $V$ over the real numbers as the triple $(r^{-},r^+, s)$ where $r^{-}$ (respectively $r^+$) is the number of $-1$'s (respectively $+1$'s) on the diagonal and $s$ is the number of zeroes. Clearly $r=r^-+ r^+$ and $r+s=\dim(V)$. The signature of a bilinear form depends only on the form. \end{remark} The method of proof of Theorem \ref{str} is interesting and important. Rather than prove the theorem, however, we discuss the Gram-Schmidt algorithm, which gives a constructive proof in a special case. It is straightforward to adapt these ideas to the general case. \begin{definition} Let $V$ be a vector space over $\R$ or $\C$. An {\bf inner product} on $V$ is a map $\langle,\rangle: V\times V\rightarrow \C$ satisfying \begin{enumerate} \item $\langle v, v\rangle$ lies in $\R$ and is nonnegative. \item $\langle v,v \rangle=0$ if and only if $v=0$. \item $\langle au+v,w\rangle = a\langle u,w\rangle + \langle v, w \rangle$. \item $\langle u,v \rangle = \o{\langle v,u\rangle}$. \end{enumerate} for all $u,v,w\in V$ and any $a\in k$. The first two conditions are called {\bf positivity} and {\bf definiteness}, respectively. Note that when the base field is $\R$, an inner product is the same as a positive definite symmetric bilinear form (automatically nondegenerate), and when the base field is $\C$, an inner product is a positive definite Hermitian form. We define the {\bf norm} of a vector $v\in V$ to be $|\!| v|\!| := \sqrt{\langle v,v\rangle}$; the square root makes sense due to positivity. An {\bf inner product space} is a vector space $V$ equipped with an inner product. \end{definition} \begin{technique}[Gram-Schmidt] Let $V$ be an $n$-dimensional inner product space (over $\R$ or $\C$) and let $\{v_1,\ldots, v_n\}$ be a basis of $V$. We will construct an {\bf orthogonal basis} of $V$, i.e. a basis $\{u_1,\ldots, u_n\}$ with $\langle u_i,u_j\rangle $ nonzero if and only if $i=j$. It is clear that in this basis, the matrix of $\langle,\rangle$ is diagonal. %For convenience, we write $|\!| v |\!|:=\sqrt{\langle v,v\rangle}$ %for any $v\in V$; the square root makes sense due to positive definiteness of $\langle, \rangle$. We inductively define \begin{align*} u_1 &:= v_1 \\ u_2 &:= v_2 - \frac{\langle v_2, u_1\rangle}{\langle u_1,u_1 \rangle} u_1 \\ \vdots & \\ u_n &:= v_n - \frac{\langle v_n, u_1\rangle}{\langle u_1,u_1 \rangle} u_1 - \frac{\langle v_n, u_2\rangle}{\langle u_2,u_2 \rangle} u_2 -\cdots - \frac{\langle v_n, u_{n-1}\rangle}{\langle u_{n-1},u_{n-1} \rangle} u_{n-1} \end{align*} As the $v_i$ may be recovered from the $u_i$, we see that $\{u_i\}$ is a basis of $V$, and one easily checks that it is an orthogonal basis. Given an orthogonal basis $\{u_i\}$ of $V$, we can construct an {\bf orthonormal basis} of $V$, i.e. a basis $\{w_i\}$ satisfying $\langle w_i,w_j\rangle = \delta_{ij}$ with $\delta$ the Dirac delta function by setting $w_i:= \frac{1}{|\!| u_i |\!|} u_i$. \end{technique} \subsection{Operators on inner product spaces} Let $V$ be a finite dimensional inner product space. The inner product on $V$ gives a map \begin{equation} V\rightarrow V^*\qquad\text{via}\qquad v\mapsto \langle \cdot, v \rangle,\label{inprodisom} \end{equation} which is injective (see Corollary \ref{equivs}) as any inner product is nondegenerate. It follows that (\ref{inprodisom}) is an isomorphism, though be warned that when the base field is $\C$, the complex structure on the target must be twisted by complex conjugation (so the isomorphism in this case is ``semilinear over complex conjugation"). \begin{definition} Let $V$ and $W$ be inner product spaces and $T:V\rightarrow W$ a linear map. The {\bf adjoint of $T$} is the linear map $T^*:W\rightarrow V$ defined by the composition \begin{equation*} \xymatrix@C=35pt{ W \ar[r]^{(\ref{inprodisom})}_-{\simeq} & {W^*} \ar[r]^-{T^{\vee}} & {V^*} \ar[r]^-{(\ref{inprodisom})^{-1}}_-{\simeq} & V } \end{equation*} By definition, $T^*$ is the unique mapping $W\rightarrow V$ satisfying $$\langle Tv, w\rangle_W = \langle v, T^*w\rangle_V$$ for all $v\in V$ and $w\in W$. One checks that the mapping \begin{equation*} \xymatrix@C=35pt{ {\Theta:\Hom(V,W)} \ar[r]^{T\mapsto T^*} & {\Hom(W,V)} } \end{equation*} is semi-linear over complex conjugation (i.e. it is additive and satisfies $\Theta(af)=\o{a}\Theta(f)$). Moreover, one has $T^{**}=T$ for any $T\in \Hom(V,W)$, and if $U$ is a third inner product space then $(ST)^*=T^*S^*$ for any $S\in \Hom(W,U)$ and $T\in \Hom(V,W)$. \end{definition} \begin{remark} Let $\mathbf{e}$ be a basis of $V$ and $\mathbf{f}$ a basis of $W$. For $T\in \Hom(V,W)$ one checks that $${}_{\mathbf{f}}[T]_{\mathbf{e}} = {}_{\mathbf{e}}\o{[T^*]}^t_{\mathbf{f}}.$$ That is, the matrix of the adjoint of $T$ is the conjugate transpose of the matrix of $T$. \end{remark} \begin{definition} Let $T:V\rightarrow V$ be a linear map on an inner product space $V$. We say that $T$ is: \begin{enumerate} \item {\bf Self adjoint} if $T^*=T$. If we wish to emphasize that the ground field is $\R$, we will say that $T$ is {\bf symmetric}, while in the case that the ground field is $\C$, we will say that $T$ is {\bf Hermitian}. \item {\bf Normal} if $T$ commutes with its adjoint; i.e. if $TT^* = T^*T$. Observe that every self adjoint operator is normal. There are, however, normal operators which are not self adjoint. \item An {\bf Isometry} if $|\!| Tv|\!| = |\!|v|\!|$ for all $v\in V$. If we wish to emphasize that the ground field is $\R$, we will say in this case that $T$ is {\bf orthogonal}; in the complex case we will say {\bf unitary}. \end{enumerate} \end{definition} \begin{remark} It is easy to see that any eigenvalue of an Hermitian operator must be real, while any eigenvalue of a unitary operator must have absolute value 1. \end{remark} \begin{theorem}[Spectral Theorem] Let $V$ be an inner product space and $T:V\rightarrow V$. \begin{enumerate} \item If the base field is $\C$, then $V$ has an orthonormal basis consisting of eigenvectors for $T$ if and only if $T$ is normal.\label{spec1} \item If the base field is $\R$, then $V$ has an orthonormal basis consisting of eigenvectors for $T$ if and only if $T$ is self adjoint. \end{enumerate} \end{theorem} From part (\ref{spec1}) of the Spectral Theorem we deduce: \begin{corollary} Let $T:V\rightarrow V$ be a normal linear transformation on a complex inner product space. Then $T$ is Hermitian if and only if all eigenvalues are real and unitary if and only if all eigenvalues have absolute value $1$. \end{corollary} \bibliography{mybib} \end{document}