%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Filename:      M216-notes.tex
%% Description:   Lecture notes for Algebra 2A
%%                
%% Author:        Francis Burstall <feb@maths.bath.ac.uk>
%% Created at:    Fri Sep 15 14:10:12 2017
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Revision History: check the git log!
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[a4paper,dvipsnames]{report}

\usepackage{lmodern}

%% lwarp for html generation
\usepackage{iftex}
\usepackage[
   HomeHTMLFilename=index,     % Filename of the homepage.
   HTMLFilename={node-},       % Filename prefix of other pages.
   mathjax                    % Use MathJax to display math.
]{lwarp}

 
\boolfalse{FileSectionNames}  % If false, numbers the files.
\setcounter{tocdepth}{2}        % Include subsections in the \TOC.
\setcounter{secnumdepth}{3}     % Number down to subsections.
\setcounter{FileDepth}{1}       % Split \HTML\ files at sections
\booltrue{CombineHigherDepths}  % Combine parts/chapters/sections
\setcounter{SideTOCDepth}{1}    % Include subsections in the side\TOC
\HTMLTitle{MA20216: Algebra 2A}       % Overrides \title for the web page.
\HTMLAuthor{Fran Burstall}        % Sets the HTML meta author tag.
\HTMLLanguage{en-UK}            % Sets the HTML meta language.
\HTMLDescription{Lecture notes for MA2016: Algebra 2A}% Sets the HTML meta description.

\title{} %Otherwise it appears on the top of every web page

\CSSFilename{M216-notes.css}
\MathJaxFilename{M216-mathjax.txt}

\renewcommand{\theHTMLTitleSection}{\theHTMLTitle}
% \renewcommand{\sidetocname}{Ramblings}

%% Usual packages
\usepackage{amssymb,amsmath,fullpage,graphicx,paralist}
\usepackage{tikz,tikz-3dplot,pgfplots}
\usepackage{tikz-cd}
\pgfplotsset{compat=1.9}
\usetikzlibrary{decorations.markings,arrows,positioning,intersections,shapes}
\usepackage{subfig}
\usepackage{tabularx} %footnotes in tables!
\usepackage{multicol}

%% Title stuff
\def\TheTitle{MA20216: Algebra 2A}
\def\TheHeroes{Callum Kemp\\Carlos Galeano Rios\\Kate Powell
  \\Tobias Beith
  \\Krunoslav Lehman Pavasovic
  \\Dan Corbie
  \\Phaidra Anastasiadou
  \\Louise Hannon
  \\Vlad Brebeanu
  \\Lauren Godfrey
  \\Elizabeth Crowley
  \\James Green
  \\Reuben Russell
  \\Ross Trigoll
  \\Emerald Dilworth
  \\George Milton
  \\Caitlin Ray
  \\Liberty Curtis
  \\Harry Todd
  \\Daniel Ng
  \\Papageorgiou Dimosthenis
  \\Kerry Finch
  \\Daniel Dodd
  \\Solla Tapping
  \\Alex Walker
  \\Charlie Hadfield
  \\Sam Cortinhas
  \\Rob Brown
}


%% I hate indented paras
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt}
%% Compact lists slightly less compact
\setlength{\plitemsep}{3pt}

\usepackage[pdftex,linktocpage,pdfstartview=FitH,colorlinks=true,linkcolor=blue,citecolor=magenta]{hyperref}
\usepackage{amsthm} % put after hyperref to turn off warnings
\usepackage[capitalise]{cleveref}
%% Theorems etc


%% Credit to AFS
\newtheoremstyle{exercise}{}{}{\normalfont}{}{\bfseries}{}{.5em}% sets optional arg in footnote
  {\thmname{#1}\thmnumber{\space#2}.\ifx#3\relax\else\footnote{#3}\fi}
\newtheorem{thm}{Theorem}[chapter]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem*{proposition*}{Proposition}
\newtheorem*{theorem*}{Theorem}
\newtheorem*{diagthm}{Diagonalisation Theorem}
\theoremstyle{definition}
\newtheorem*{xmpls}{Examples}
\newtheorem*{defns}{Definitions}
\newtheorem*{defn}{Definition}
\newtheorem*{xmpl}{Example}
\newtheorem*{notation}{Notation}
\newtheorem*{convention}{Convention}
\newtheorem*{terminology}{Terminology}
\newtheorem*{commentary}{Commentary}
\newtheorem*{facts}{Facts}
\newtheorem*{assume}{Assumption}
\newtheorem*{warning}{\textcolor{Red}{Warning}}
\theoremstyle{remark}
\newtheorem*{rem}{Remark}
\newtheorem*{rems}{Remarks}
\theoremstyle{exercise}
\newtheorem*{ex}{Exercise}
\newtheorem*{exs}{Exercises}

%% macros
%\usepackage{math-private}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\rank}{\operatorname{rank}}
\newcommand{\sol}{\operatorname{sol}}
\newcommand{\ann}{\operatorname{ann}}
\newcommand{\rO}{\operatorname{O}}
\newcommand{\rU}{\operatorname{U}}
\newcommand{\rSU}{\operatorname{SU}}
\newcommand{\ev}{\operatorname{ev}}
\newcommand{\bil}{\operatorname{Bil}}
\newcommand{\rad}{\operatorname{rad}}
\newcommand{\Span}[1]{\operatorname{span}\{#1\}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\I}{\mathrm{I}}
\newcommand{\half}{\tfrac12}
\newcommand{\rel}{\mathrel{\mathrm{rel}}}
\renewcommand{\vec}[3]{(#1_{#2},\dots,#1_{#3})}
\newcommand{\lst}[3]{#1_{#2},\dots,#1_{#3}}
\newcommand{\plst}[3]{#1_{#2}+\dots+#1_{#3}}
\newcommand{\oplst}[3]{#1_{#2}\oplus\dots\oplus#1_{#3}}
\newcommand{\pplst}[3]{#1_{#2}\times\dots\times#1_{#3}}
\newcommand{\dlst}[3]{\lst{#1^{*}}{#2}{#3}}
\newcommand{\dlc}[4]{\lc#1{#2^{*}}#3#4}
\newcommand{\hmg}[3]{[#1_{#2},\dots,#1_{#3}]} %can't recycle \lst cos
% args wrongly parsed
\newcommand{\rng}[2]{#1,\dots,#2}
\newcommand{\lc}[4]{#1_{#3}#2_{#3}+\dots+#1_{#4}#2_{#4}}
\newcommand{\plus}[2]{#1+\dots+#2}
\newcommand{\set}[1]{\{#1\}}
\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand{\ip}[1]{\langle#1\rangle}
\newcommand{\norm}[1]{\|#1\|}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\by}{\mathbf{y}}
%\newcommand{\bw}{\mathbf{w}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\cI}{\mathcal{I}}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\sub}{\subseteq}
\newcommand{\st}{\mathrel{|}}
\newcommand{\bw}[3]{#1\leq#2\leq#3}
\newcommand{\col}[3]{(#1_{#2})_{#2\in#3}}
\newcommand{\supp}{\mathrm{supp}}
\newcommand{\restr}[1]{_{|#1}}

\begin{warpHTML}
\CustomizeMathJax{\newcommand{\id}{\operatorname{id}}}
\CustomizeMathJax{\newcommand{\GL}{\operatorname{GL}}}
\CustomizeMathJax{\newcommand{\im}{\operatorname{im}}}
\CustomizeMathJax{\newcommand{\rank}{\operatorname{rank}}}
\CustomizeMathJax{\newcommand{\sol}{\operatorname{sol}}}
\CustomizeMathJax{\newcommand{\ann}{\operatorname{ann}}}
\CustomizeMathJax{\newcommand{\rO}{\operatorname{O}}}
\CustomizeMathJax{\newcommand{\rU}{\operatorname{U}}}
\CustomizeMathJax{\newcommand{\rSU}{\operatorname{SU}}}
\CustomizeMathJax{\newcommand{\ev}{\operatorname{ev}}}
\CustomizeMathJax{\newcommand{\bil}{\operatorname{Bil}}}
\CustomizeMathJax{\newcommand{\rad}{\operatorname{rad}}}
\CustomizeMathJax{\newcommand{\Span}[1]{\operatorname{span}\{#1\}}}
\CustomizeMathJax{\newcommand{\R}{\mathbb{R}}}
\CustomizeMathJax{\newcommand{\C}{\mathbb{C}}}
\CustomizeMathJax{\newcommand{\Z}{\mathbb{Z}}}
\CustomizeMathJax{\newcommand{\F}{\mathbb{F}}}
\CustomizeMathJax{\newcommand{\Q}{\mathbb{Q}}}
\CustomizeMathJax{\newcommand{\N}{\mathbb{N}}}
\CustomizeMathJax{\renewcommand{\P}{\mathbb{P}}}
\CustomizeMathJax{\newcommand{\I}{\mathrm{I}}}
\CustomizeMathJax{\newcommand{\half}{\tfrac12}}
\CustomizeMathJax{\newcommand{\rel}{\mathrel{\mathrm{rel}}}}
\CustomizeMathJax{\renewcommand{\vec}[3]{(#1_{#2},\dots,#1_{#3})}}
\CustomizeMathJax{\newcommand{\lst}[3]{#1_{#2},\dots,#1_{#3}}}
\CustomizeMathJax{\newcommand{\plst}[3]{#1_{#2}+\dots+#1_{#3}}}
\CustomizeMathJax{\newcommand{\oplst}[3]{#1_{#2}\oplus\dots\oplus#1_{#3}}}
\CustomizeMathJax{\newcommand{\pplst}[3]{#1_{#2}\times\dots\times#1_{#3}}}
\CustomizeMathJax{\newcommand{\dlst}[3]{\lst{#1^{*}}{#2}{#3}}}
\CustomizeMathJax{\newcommand{\dlc}[4]{\lc#1{#2^{*}}#3#4}}
\CustomizeMathJax{\newcommand{\hmg}[3]{[#1_{#2},\dots,#1_{#3}]}}
\CustomizeMathJax{\newcommand{\rng}[2]{#1,\dots,#2}}
\CustomizeMathJax{\newcommand{\lc}[4]{#1_{#3}#2_{#3}+\dots+#1_{#4}#2_{#4}}}
\CustomizeMathJax{\newcommand{\plus}[2]{#1+\dots+#2}}
\CustomizeMathJax{\newcommand{\set}[1]{\{#1\}}}
\CustomizeMathJax{\newcommand{\abs}[1]{\lvert#1\rvert}}
\CustomizeMathJax{\newcommand{\ip}[1]{\langle#1\rangle}}
\CustomizeMathJax{\newcommand{\norm}[1]{\|#1\|}}
\CustomizeMathJax{\newcommand{\bx}{\mathbf{x}}}
\CustomizeMathJax{\newcommand{\be}{\mathbf{e}}}
\CustomizeMathJax{\newcommand{\bq}{\mathbf{q}}}
\CustomizeMathJax{\newcommand{\bu}{\mathbf{u}}}
\CustomizeMathJax{\newcommand{\by}{\mathbf{y}}}
%\newcommand{\bw}{\mathbf{w}}
\CustomizeMathJax{\newcommand{\bv}{\mathbf{v}}}
\CustomizeMathJax{\newcommand{\E}{\mathbb{E}}}
\CustomizeMathJax{\newcommand{\cI}{\mathcal{I}}}
\CustomizeMathJax{\newcommand{\cB}{\mathcal{B}}}
\CustomizeMathJax{\newcommand{\sub}{\subseteq}}
\CustomizeMathJax{\newcommand{\st}{\mathrel{|}}}
\CustomizeMathJax{\newcommand{\bw}[3]{#1\leq#2\leq#3}}
\CustomizeMathJax{\newcommand{\col}[3]{(#1_{#2})_{#2\in#3}}}
\CustomizeMathJax{\newcommand{\supp}{\mathrm{supp}}}
\CustomizeMathJax{\newcommand{\restr}[1]{_{|#1}}}
\end{warpHTML}


%% for items with eqn envs immediately after
%% Credit: tex.stackexchange.com/questions/58141/equations-inside-enumerate-aligned-on-items-number
\newcommand\Item[1][]{%
  \ifx\relax#1\relax  \item \else \item[#1] \fi
  \abovedisplayskip=0pt\abovedisplayshortskip=0pt~\vspace*{-\baselineskip}}
%% tikz colours that geogebra uses
\definecolor{ffqqqq}{rgb}{1.,0.,0.}
\definecolor{qqqqff}{rgb}{0.,0.,1.}

\begin{document}
\pagenumbering{Alph} % to stop hyperref warnings
\begin{titlepage}
  \thispagestyle{empty}
  \vspace*{-2cm}
  \hfill\includegraphics[width=4cm,alt={Course logo.}]{logo.png}
  \vspace*{2cm}\vfill
  {\noindent\Huge\sffamily \textcolor{MidnightBlue}\TheTitle}\\
  \warpprintonly{{\color{RawSienna}\rule{\textwidth}{2pt}}\par}
  \warpHTMLonly{<hr class="titlehrule">}
  \vspace{\baselineskip} {\noindent\huge\sffamily Notes by
    Fran Burstall}\par
  \vspace{\baselineskip}
  \begin{center}\minipagefullwidth
    \begin{minipage}[t]{.9\linewidth}
      \noindent\LARGE\sffamily Corrections by:\\
      \begin{multicols}{2}
        \TheHeroes
      \end{multicols}
    \end{minipage}
  \end{center}
  \vfill\vfill
\end{titlepage} 
\pagenumbering{roman}
\tableofcontents

\chapter{Linear algebra: concepts and examples}
\label{cha:line-algebr-conc}
\pagenumbering{arabic}

Let us warm up by revising some of the key ideas from
Algebra 1B.  Along the way, we will see some new examples and prove
a couple of new results.

\section{Vector spaces}
\label{sec:vector-spaces}

Recall from Algebra 1B, \S2.1:
\begin{defn}
  A \emph{vector space $V$ over a field $\F$} is a set $V$
  with two operations:
  \begin{description}
  \item[addition] $V\times V\to V: (v,w)\mapsto v+w$ with
    respect to which $V$ is an abelian group:
    \begin{itemize}
    \item $v+w=w+v$, for all $v,w\in V$;
    \item $u+(v+w)=(u+v)+w$, for all $u,v,w\in V$;
    \item there is a \emph{zero element} $0\in V$ for which
      $v+0=v=0+v$, for all $v\in V$;
    \item each element $v\in V$ has an \emph{additive
        inverse} $-v\in V$ for which $v+(-v)=0=(-v)+v$.
    \end{itemize}
  \item[scalar multiplication] $\F\times V\to V:
    (\lambda,v)\mapsto \lambda v$ such that
    \begin{itemize}
    \item $(\lambda+\mu)v=\lambda v+\mu v$, for all $v\in
      V$, $\lambda,\mu\in\F$.
    \item $\lambda(v+w)=\lambda v+\lambda w$, for all $v,w\in
      V$, $\lambda\in\F$.
    \item $(\lambda\mu)v=\lambda(\mu v)$, for all $v\in V$,
      $\lambda,\mu\in\F$.
    \item $1v=v$, for all $v\in V$.
    \end{itemize}
  \end{description}
  We call the elements of $\F$ \emph{scalars} and those of
  $V$ \emph{vectors}.
\end{defn}

\begin{xmpls}
\item{}
  \begin{compactenum}
  \item Take $V=\F$, the field itself, with addition and
    scalar multiplication the field addition and
    multiplication.
  \item $\F^n$, the $n$-fold Cartesian product of $\F$ with
    itself, with component-wise addition and scalar
    multiplication:
    \begin{align*}
      \vec\lambda1n+\vec\mu1n&:=(\lambda_1+\mu_1,\dots,\lambda_n+\mu_n)\\
      \lambda\vec\lambda1n&:=\vec{\lambda\lambda}1n.
    \end{align*}
  \item Let $M_{m\times n}(\F)$ denotes the set of $m$ by
    $n$ matrices (thus $m$ rows and $n$ columns) with
    entries in $\F$.  This is a vector space under
    entry-wise addition and scalar multiplication.

    Special cases are the vector spaces of \emph{column vectors}
    $M_{n\times 1}(\F)$ and \emph{row vectors} $M_{1\times n}(\F)$.
    In computations, we often identify $\F^n$ with
    $M_{n\times 1}(\F)$ by associating $x=\vec{x}1n\in\F^{n}$
    with the column vector
    \begin{equation*}
      \bx=
      \begin{pmatrix}
        x_1\\\vdots\\x_n
      \end{pmatrix}.
    \end{equation*}
  \item Here is a very general example: let $\cI$ be any set
    and $V$ a vector space.  Recall that $V^{\cI}$ denotes
    the set $\set{f:\cI\to V}$ of all maps from $\cI$ to
    $V$.

    I claim that $V^{\cI}$ is a vector space under pointwise
    addition and scalar multiplication.  That is, for
    $f,g:\cI\to V$ and $\lambda\in\F$, we define
    \begin{align*}
      (f+g)(i)&:=f(i)+g(i)\\
      (\lambda f)(i)&:=\lambda(f(i)),
    \end{align*}
    for all $i\in\cI$.

    The zero element is just the constant zero function:
    \begin{equation*}
      0(i):=0,
    \end{equation*}
    and the additive inverses are defined pointwise also:
    \begin{equation*}
      (-f)(i):=-(f(i)).
    \end{equation*}
    \begin{ex}[Question 4 on sheet 1.]
      Prove the claim!  That is, show that $V^{\cI}$ is a
      vector space under pointwise addition and scalar
      multiplication.
    \end{ex}
  \end{compactenum}
\end{xmpls}

\begin{rem}
  For suitable $\cI$, this last example captures many
  familiar vector spaces.  For example:
  \begin{itemize}
  \item We identify $\F^n$ with $\F^{\set{\rng1n}}$ by
    associating $\vec{x}1n\in\F^{n}$ with the map $(i\mapsto
    x_i)$.
  \item Similarly, we identify $M_{m\times n}(\F)$ with
    $\F^{\set{\rng1m}\times\set{\rng1n}}$ by associating the
    matrix $A$ with the map $(i,j)\mapsto A_{ij}$.
  \item $\R^{\N}$ is the set of real sequences
    $\set{(a_{n})_{n\in\N}: a_n\in\R}$ that played such a
    starring role in Analysis 1.
  \end{itemize}
\end{rem}

\section{Subspaces}
\label{sec:subspaces}

\begin{defn}
  A \emph{vector} (or \emph{linear}) \emph{subspace} of a
  vector space $V$ over $\F$ is a non-empty subset $U\sub
  V$ which is closed under addition and scalar
  multiplication: whenever $u,u_1,u_2\in U$ and
  $\lambda\in\F$, then $u_1+u_2\in U$ and $\lambda u\in U$.

  In this case, we write $U\leq V$.

  Say that $U$ is \emph{trivial} if $U=\set{0}$ and
  \emph{proper} if $U\neq V$.  
\end{defn}

Of course, $U$ is now a vector space in its own right using
the addition and scalar multiplication of $V$.

\begin{ex}[Question 1 on sheet 1.]
  $U\sub V$ is a subspace if and only if $U$ satisfies the
  following conditions:
  \begin{compactenum}
  \item $0\in U$;
  \item For all $u_1,u_2\in U$ and $\lambda\in\F$,
    $u_1+\lambda u_2\in U$.
  \end{compactenum}
  This gives a efficient recipe for checking when a subset
  is a subspace.
\end{ex}

\begin{xmpls}
  A good way to see that something is a vector space is to
  see that it is a subspace of some $V^{\cI}$.  That way,
  there is no need to verify all the tedious axioms
  (associativity, distributivity and so on).
  \begin{compactenum}
  \item The set $c:=\set{\text{real convergent
        sequences}}\leq\R^{\N}$ and so is a vector space.
    This is part of the content of the Algebra of Limits
    Theorem in Analysis 1.
  \item Let $[a,b]\sub\R$ be an interval and set
    \begin{equation*}
      C^0[a,b]:=\set{f:[a,b]\to\R\st\text{$f$ is continuous}},
    \end{equation*}
    the set of continuous functions.

    Then $C^0[a,b]\leq\R^{[a,b]}$.  This is most of the
    Algebra of Continuous Functions Theorem from Analysis 1.
  \end{compactenum}
\end{xmpls}

\section{Bases}
\label{sec:bases}

\begin{defns}
  Let $\lst{v}1n$ be a list of vectors in a vector space
  $V$.
  \begin{compactenum}
  \item The \emph{span} of $\lst{v}1n$ is
    \begin{equation*}
      \Span{\lst{v}1n}:=\set{\lc\lambda{v}1n\st\lambda_i\in\F,
        1\leq i\leq n}\leq V.
    \end{equation*}
  \item $\lst{v}1n$ \emph{span $V$} (or \emph{are a spanning
      list for $V$}) if $\Span{\lst{v}1n}=V$.
  \item $\lst{v}1n$ are \emph{linearly independent} if,
    whenever $\lc\lambda{v}1n=0$, then each $\lambda_i=0$,
    $1\leq i\leq n$, and \emph{linearly dependent} otherwise.
  \item $\lst{v}1n$ is a \emph{basis} for $V$ if they are
    linearly independent and span $V$.
  \end{compactenum}
\end{defns}

\begin{defn}
  A vector space is \emph{finite-dimensional} if it admits a
  finite list of vectors as basis and
  \emph{infinite-dimensional} otherwise.

  If $V$ is finite-dimensional, the \emph{dimension} of $V$,
  $\dim V$, is the number of vectors in a (any) basis of $V$.
\end{defn}

\begin{terminology}
Let $\lst{v}1n$ be a list of vectors.
  \begin{compactenum}
  \item A vector of the form $\lc\lambda{v}1n$ is called a
    \emph{linear combination of the $v_i$}.
  \item An equation of the form $\lc\lambda{v}1n=0$ is
    called a \emph{linear relation on the $v_i$}.
  \end{compactenum}
\end{terminology}

Recall:
\begin{prop}[Algebra 1B, Section 2.4, Proposition
  5]\label{th:1}%basis via unique lin comb
  $\lst{v}1n$ is a basis for $V$ if and only if any $v\in V$
  can be written in the form
  \begin{equation}
    \label{eq:1}
    v=\lc\lambda{v}1n
  \end{equation}
  for \emph{unique} $\lst\lambda1n\in\F$. In this case,
  $\vec\lambda1n$ is called the \emph{coordinate vector} of
  $v$ with respect to $\lst{v}1n$.
\end{prop}

\subsection{Standard bases}
\label{sec:standard-bases}

In general, finite-dimensional vector spaces have many bases
and there is no good reason to prefer any particular one.
However, some lucky vector spaces come equipped with a
natural basis.

\begin{prop}
  For $\cI$ a set and $i\in\cI$, define $e_i\in\F^{\cI}$ by
  \begin{equation*}
    e_i(j)=
    \begin{cases}
      1&\text{if $i=j$}\\0&\text{if $i\neq j$},
    \end{cases}
  \end{equation*}
  for all $j\in\cI$.

  If $\cI$ is finite then $(e_i)_{i\in\cI}$ is a basis,
  called the \emph{standard basis}, of
  $\F^{\cI}$.  

  In particular, $\dim\F^{\cI}=\abs{\cI}$.
\end{prop}
\begin{proof}
  For $f\in\F^{\cI}$, we observe that
  \begin{equation*}
    f=\sum_{i\in\cI}f(i)e_i.
  \end{equation*}
  Indeed, for $j\in\cI$,
  \begin{equation*}
    \bigl(\sum_{i\in\cI}f(i)e_i\bigr)(j)=
    \sum_{i\in\cI}f(i)e_i(j)=\sum_{i\neq j}f(i)0+f(j)1=f(j).
  \end{equation*}
  In particular, $(e_i)_{i\in\cI}$ span.

  For linear independence, suppose that
  $\sum_{i\in\cI}\lambda_ie_i=0$ and evaluate both sides at
  $j\in\cI$ to get
  \begin{equation*}
    \lambda_j=0.
  \end{equation*}
\end{proof}

\begin{xmpls}
\item{}
  \begin{itemize}
  \item Identify $\F^n$ with $\F^{\set{\rng1n}}$ and then
    $e_i=(0,\dots,1,\dots,0)$ with a single $1$ in the
    $i$-th place.
  \item Similarly, the vector space of column vectors has a
    standard basis with $\be_{i}$, the column vector with a
    single $1$ in the $i$-th row:
    \begin{equation*}
      \be_{i}=
      \begin{pmatrix}
        0\\\vdots\\1\\\vdots\\0
      \end{pmatrix}.
    \end{equation*}
  \item Finally, identifying $M_{m\times n}(\F)$ with
    $\F^{\set{\rng1m}\times\set{\rng1n}}$ yields the
    standard basis $(e_{(i,j)})_{i,j}$ of $M_{m\times
      n}(\F)$ where $e_{(i,j)}$ differs from the zero matrix
    by a single $1$ in the $i$-th row and $j$-th column.
  \end{itemize}
\end{xmpls}

\subsection{Useful facts}
\label{sec:useful-facts}

A very useful fact about bases that we shall use many times
was proved in Algebra 1B:
\begin{prop}[Algebra 1B, Chapter 3,
  Theorem~6(b)]\label{th:2}%extn property
  Any linearly independent list of vectors in a
  finite-dimensional vector space can be extended to a
  basis.
\end{prop}

Here is another helpful result :
\begin{lem}[Algebra 1B, Chapter 3,
  Theorem~5]
  \label{th:32}
  % dim of subspace
  Let $V$ be a finite-dimensional vector space and $U\leq
  V$.  Then
  \begin{equation*}
    \dim U\leq\dim V
  \end{equation*}
  with equality if and only if $U=V$.
\end{lem}


\section{Linear maps}
\label{sec:linear-maps}

\begin{defns}
  A map $\phi:V\to W$ of vector spaces over $\F$ is a
  \emph{linear map} (or, in older books, \emph{linear
    transformation}) if
  \begin{align*}
    \phi(v+w)&=\phi(v)+\phi(w)\\
    \phi(\lambda v)&=\lambda\phi(v),
  \end{align*}
  for all $v,w\in V$, $\lambda\in\F$.

  The \emph{kernel} of $\phi$ is $\ker\phi:=\set{v\in
    V\st\phi(v)=0}\leq V$.

  The \emph{image} of $\phi$ is $\im\phi:=\set{\phi(v)\st
  v\in V}\leq W$.
\end{defns}

\begin{rem}
  $\phi$ is linear if and only if
  \begin{equation*}
    \phi(v+\lambda w)=\phi(v)+\lambda\phi(w),
  \end{equation*}
  for all $v,w\in V$, $\lambda\in\F$, which has the virtue of being
  only one thing to prove.
\end{rem}

\begin{xmpls}
\item{}
  \begin{compactenum}
  \item $A\in M_{m\times n}(\F)$ determines a linear map
    $\phi_A:\F^n\to\F^m$ by $\phi_A(x)=y$ where, for $1\leq
    i\leq m$,
    \begin{equation*}
      y_i=\sum_{j=1}^nA_{ij}x_j.
    \end{equation*}
    Otherwise said, $y$ is given by matrix multiplication:
    $\mathbf{y}=A\bx$.
  \item For any vector space $V$, the identity map
    $\id_V:V\to V$ is linear.
  \item If $\phi:V\to W$ and $\psi:W\to U$ are linear then
    so is $\psi\circ\phi:V\to U$.
  \item Recall that $c$ is the vector space of convergent
    sequences.

    The map
    $\lim_{n\to\infty}:(a_n)_{n\in\N}\mapsto\lim_{n\to\infty}a_n:c\to\R$
    is linear thanks to the Algebra of Limits Theorem in
    Analysis 1.
  \item $\int_a^b:f\mapsto\int_a^bf:C^0[a,b]\to\R$ is also linear.
  \end{compactenum}
\end{xmpls}

\begin{defn}
  A linear map $\phi:V\to W$ is a \emph{(linear)
    isomorphism} if there is a linear map $\psi:W\to V$ such
  that
  \begin{equation*}
    \psi\circ\phi=\id_V,\qquad\phi\circ\psi=\id_W.
  \end{equation*}

  If there is an isomorphism $V\to W$, say that $V$ and $W$
  are isomorphic and write $V\cong W$.
\end{defn}

In Algebra 1B, we saw:
\begin{lem}
  $\phi:V\to W$ is an isomorphism if and only if $\phi$ is a
  linear bijection (and then $\psi=\phi^{-1}$).
\end{lem}

\subsection{Vector spaces of linear maps}
\label{sec:vector-spaces-linear}

\begin{notation}
  For vector spaces $V,W$ over $\F$, denote by $L_{\F}(V,W)$
  (or simply $L(V,W)$) the set
  $\set{\phi:V\to W\st\text{$\phi$ is linear}}$ of linear
  maps from $V$ to $W$.
\end{notation}

\begin{thm}[Linearity is a linear condition]
  \label{th:3}
  $L(V,W)$ is a vector space under pointwise addition and
  scalar multiplication.  Otherwise said, $L(V,W)\leq W^V$.
\end{thm}
\begin{proof}
  It is enough to show that $L(V,W)$ is a vector subspace of
  $W^V$, that is, is non-empty and closed under addition and
  scalar multiplication.

  First observe that the zero map $0:v\mapsto 0\in W$ is
  linear:
  \begin{equation*}
    0(v+\lambda w)=0=0+\lambda0=0(v)+\lambda 0(w).
  \end{equation*}
  In particular, $L(V,W)$ is non-empty.

  Now let $\phi,\psi\in L(V,W)$ and show that $\phi+\psi$ is
  linear:
  \begin{align*}
    (\phi+\psi)(v+\lambda w)
    &=\phi(v+\lambda w)+\psi(v+\lambda w)\\
    &=\phi(v)+\lambda\phi(w)+\psi(v)+\lambda\psi(w)\\
    &=(\phi(v)+\psi(v))+\lambda(\phi(w)+\psi(w))\\
    &=(\phi+\psi)(v)+\lambda(\phi+\psi)(w),
  \end{align*}
  for all $v,w\in V$, $\lambda\in\F$.  Here the first and last
  equalities are just the definition of pointwise addition
  while the middle equalities come from the linearity of
  $\phi,\psi$ and the vector space axioms of $W$.

  Similarly, it is a simple exercise to see that if
  $\mu\in\F$ and $\phi\in L(V,W)$ then $\mu\phi$ is also
  linear.
\end{proof}

\subsection{Linear maps and matrices}
\label{sec:linear-maps-matrices}

Recall from Algebra 1B \S2.6:
\begin{defn}
  Let $V,W$ be finite-dimensional vector spaces over $\F$
  with bases $\cB:\lst{v}1n$ and $\cB':\lst{w}1m$
  respectively.  Let $\phi\in L(V,W)$.  The \emph{matrix of
    $\phi$ with respect to $\cB,\cB'$} is the matrix $A=(A_{ij})\in
  M_{m\times n}(\F)$ defined by:
  \begin{equation}
    \label{eq:27}
    \phi(v_j)=\sum_{i=1}^mA_{ij}w_{i},
  \end{equation}
  for all $\bw1jn$.

  In the special case where $V=W$ \emph{and} $\cB=\cB'$, we
  call $A$ the \emph{matrix of $\phi$ with respect to $\cB$}.
\end{defn}

Thus the recipe for computing $A$ is: \emph{expand
  $\phi(v_j)$ in terms of $\lst{w}1m$ to get the $j$-th
  column of $A$}.

Equivalently, $\phi(\lc{x}v1n)=\lc{y}w1m$ where
\begin{equation*}
  \by=A\bx.
\end{equation*}

There is a fancy way to say all this: recall that a basis
$\cB:\lst{v}1n$ of $V$ gives rise to a linear isomorphism
$\phi_{\cB}:\F^n\to V$ via
\begin{equation}
  \label{eq:3}
  \phi_{\cB}\vec\lambda1n=\sum_{i=1}^n\lambda_iv_i.
\end{equation}
Now the relation between $\phi$ and $A$ is that
\begin{equation*}
  \phi=\phi_{\cB'}\circ\phi_A\circ\phi_{\cB}^{-1}
\end{equation*}
or, equivalently,
$\phi_{\cB'}\circ\phi_A=\phi\circ\phi_{\cB}$ so that the
following diagram commutes:
{\displaymathother
  \begin{equation*}
     \begin{tikzcd} V \arrow{r}{\phi}& W \\
     \F^{n}\arrow{r}{\phi_A} \arrow{u}{\phi_{\cB}} &\F^m
     \arrow{u}[right]{\phi_{\cB'}}
     \end{tikzcd}
     \end{equation*}}
    (The assertion that such a diagram commutes is simply
    that the two maps one builds by following the arrows in
    two different ways coincide.  However, the diagram also
    helps us keep track of where the various maps go!)

The map $\phi\mapsto A$ is a linear isomorphism $L(V,W)\cong
M_{m\times n}(\F)$ which also plays well with composition
and matrix multiplication: if $U$ is a third vector space
with basis $\cB''$ and $\psi\in L(W,U)$ has matrix $B$ with
respect to $\cB',\cB''$ then $\psi\circ\phi$ has matrix $BA$
with respect to $\cB,\cB''$.  This gives us a compelling
dictionary between linear maps and matrices.

\subsection{Extension by linearity}
\label{sec:extension-linearity}

A linear map of a finite-dimensional vector space is
completely determined by its action on a basis.  More
precisely:
\begin{prop}[Extension by linearity]\label{th:6}
  Let $V,W$ be vector spaces over $\F$.  Let $\lst{v}1n$ be
  a basis of $V$ and $\lst{w}1n$ \emph{any} vectors in $W$.

  Then there is a \emph{unique} $\phi\in L(V,W)$ such that
  \begin{equation}
    \label{eq:2}
    \phi(v_i)=w_i,\qquad 1\leq i\leq n.
  \end{equation}
\end{prop}
\begin{proof}
  We need to prove that such a $\phi$ exists and that there
  is only one.  We prove existence first.

  Let $v\in V$.  By \cref{th:1}, we know there
  are unique $\lst\lambda1n\in\F$ for which
  \begin{equation*}
    v=\lc{\lambda}{v}1n
  \end{equation*}
  and so we define $\phi(v)$ to be the only thing it could
  be:
  \begin{equation*}
    \phi(v):=\lc\lambda{w}1n.
  \end{equation*}
  Let us show that this $\phi$ does the job.  First, with
  $\lambda_i=1$ and $\lambda_j=0$, for $i\neq j$, we see
  that
  \begin{equation*}
    \phi(v_i)=\sum_{j\neq i}0w_j+1w_i=w_i
  \end{equation*}
  so that \eqref{eq:2} holds.  Now let us see that $\phi$ is
  linear: let $v,w\in V$ with
  \begin{align*}
    v&=\lc\lambda{v}1n\\
    w&=\lc\mu{v}1n.
  \end{align*}
  Then, for $\lambda\in\F$,
  \begin{equation*}
    v+\lambda w=(\lambda_1+\lambda\mu_1)v_1+\dots+(\lambda_n+\lambda\mu_n)v_n
  \end{equation*}
  whence
  \begin{align*}
    \phi(v+\lambda w)
    &=(\lambda_1+\lambda\mu_1)w_1+\dots+(\lambda_n+\lambda\mu_n)w_n\\
    &=(\lc\lambda{w}1n)+\lambda(\lc\mu{w}1n)\\
    &=\phi(v)+\lambda\phi(w).
  \end{align*}

  For uniqueness, suppose that $\phi,\phi'\in L(V,W)$ both
  satisfy \eqref{eq:2}.  Let $v\in V$ and write
  $v=\lc\lambda{v}1n$.  Then
  \begin{align*}
    \phi(v)&=\lambda_1\phi(v_1)+\dots+\lambda_n\phi(v_n)\\
           &= \lc\lambda{w}1n\\
           &=\lambda_1\phi'(v_1)+\dots+\lambda_n\phi'(v_n)\\
    &=\phi'(v),
  \end{align*}
  where the first and last equalities come from the
  linearity of $\phi,\phi'$ and the middle two from
  \eqref{eq:2} for first $\phi$ and then $\phi'$.  We
  conclude that $\phi=\phi'$ and we are done.
\end{proof}

\begin{rem}
  In the context of \cref{th:6}, $\phi$ is an
  isomorphism if and only if $\lst{w}1n$ is a basis for $W$
  (exercise\footnote{This is question 2 on exercise sheet
    2.}!).
\end{rem}

\subsection{The rank-nullity theorem}
\label{sec:rank-nullity-theorem}

Easily the most important result in Algebra 1B is the famous
Rank-nullity theorem:
\begin{thm}[Rank-nullity]
  Let $\phi:V\to W$ be linear with $V$ finite-dimensional.
  Then
  \begin{equation*}
    \dim\im\phi+\dim\ker\phi=\dim V.
  \end{equation*}
\end{thm}

Using this, together with the observation that $\phi$ is
injective if and only if $\ker\phi=\set{0}$, we saw in
Algebra 1B:
\begin{prop}\label{th:4}
  Let $\phi:V\to W$ be linear with $V,W$ finite-dimensional
  vector spaces of the same dimension: $\dim V=\dim W$.

  Then the following are equivalent:
  \begin{compactenum}
  \item $\phi$ is injective.
  \item $\phi$ is surjective.
  \item $\phi$ is an isomorphism.
  \end{compactenum}
\end{prop}

\begin{rem}
  \cref{th:4} is flat-out false for
  infinite-dimensional $V,W$.  For example: let
  $S:\R^{\N}\to\R^{\N}$ be the \emph{shift} operator:
  \begin{equation*}
    S((a_0,a_1,\dots)):=(a_1,\dots).
  \end{equation*}
  We readily check that:
  \begin{compactitem}
  \item $S$ is linear;
  \item $S$ surjects;
  \item $S$ is not injective.  For example: $S((1,0,0,\dots))=0$.
  \end{compactitem}
\end{rem}

\chapter{Sums and quotients}
\label{cha:sums-prod-quot}

We will discuss various ways of building new vector spaces
out of old ones.
\begin{convention}
  In this chapter, all vector spaces are over the same field
  $\F$ unless we say otherwise.
\end{convention}

\section{Sums of subspaces}
\label{sec:sums-products}

\begin{defn}
  Let $\lst{V}1k\leq V$.  The \emph{sum} $\plst{V}1k$ is the
  set
  \begin{equation*}
    \plst{V}1k:=\set{\plst{v}1k\st v_i\in V_i, 1\leq i\leq k}.
  \end{equation*}
\end{defn}

$\plst{V}1k$ is the smallest subspace of $V$ that contains
each $V_i$.  More precisely:
\begin{prop}
  Let $\lst{V}1k\leq V$. Then
  \begin{compactenum}[(1)]
  \item $\plst{V}1k\leq V$.
  \item If $W\leq V$ and $\lst{V}1k\leq W$ then
    $\lst{V}1k\leq\plst{V}1k\leq W$.
  \end{compactenum}
\end{prop}
\begin{proof}
  It suffices to prove (2) since (1) then follows by taking
  $W=V$.

  For (2), first note that $\plst{V}1k$ is a subset of $W$:
  if $v_i\in V_i$ then $v_i\in W$  so that $\plst{v}1k\in W$
  since $W$ is closed under addition.

  Now observe that each $V_i\leq\plst{V}1k$ since we can
  write any $v_i\in V_i$ as
  $0+\dots+v_i+\dots+0\in\plst{V}1k$.  In particular,
  $0\in\plst{V}1k$.

  Finally, we show that $\plst{V}1k$ is a subspace.  If
  $\plst{v}1k,\plst{w}1k\in\plst{V}1k$, with $v_i,w_i\in
  V_i$, for all $i$, and $\lambda\in\F$ then
  \begin{equation*}
    (\plst{v}1k)+\lambda(\plst{w}1k)=\plus{(v_1+\lambda
      w_1)}{(v_k+\lambda w_k)}\in\plst{V}1k
  \end{equation*}
  since each $v_i+\lambda w_i\in V_i$.
\end{proof}

\begin{rem}
  The union $\bigcup_{i=1}^kV_{i}$ is almost never a
  subspace of $V$ so we use sums as a substitute for unions
  in Linear Algebra.
\end{rem}

\section{Direct sums}
\label{sec:internal-direct-sum}

Let $\lst{V}1k\leq V$.  Any $v\in\plst{V}1k$ can be written
\begin{equation*}
  v=\plst{v}1k,
\end{equation*}
with each $v_i\in V_i$.  We distinguish the case where the
$v_i$ are \emph{unique}.

\begin{defn}
  Let $\lst{V}1k\leq V$.  The sum $\plst{V}1k$ is
  \emph{direct} if each $v\in\plst{V}1k$ can be written
  \begin{equation*}
    v=\plst{v}1k
  \end{equation*}
  in only one way, that is, for unique $v_i\in V_i$,
  $\bw1ik$.

  In this case, we write $\oplst{V}1k$ instead of $\plst{V}1k$.
\end{defn}

\begin{figure}[htb]
  \centering
  \ThisAltText{A direct sum.}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=0.3cm,y=0.3cm]
\clip(-7.92,-5.551666666666653) rectangle (7.47,6.643333333333327);
\draw [color=blue,domain=-7.92:7.47] plot(\x,{(-3.5608-6.9*\x)/-3.04});
\draw [color=blue,domain=-7.92:7.47] plot(\x,{(-8.2736--1.56*\x)/7.78});
\draw [dash pattern=on 3pt off 3pt,color=blue] (0.42281833116739825,2.1310021332417923)-- (3.46,2.74);
\draw [dash pattern=on 3pt off 3pt,color=blue] (1.957181668832602,-0.6710021332417918)-- (3.46,2.74);
\draw [fill,red] (-1.08,-1.28) circle (1.0pt) node[black,below right] {$0$};
\draw (1.6875,6.103333333333328) node[left] {$V_2$};
\draw (-7.4475,-1.6816666666666595) node {$V_1$};
\draw [fill,red] (3.46,2.74) circle (1.0pt) node[black,right] {$v$};
\draw [fill,red] (1.957181668832602,-0.6710021332417918)
circle (1.0pt)  node[black,below] {$v_1$};
\draw [fill,red] (0.42281833116739825,2.1310021332417923)
circle (1.0pt) node[left,black] {$v_2$};
\end{tikzpicture}
  \caption{$\R^2=V_1\oplus V_2$}
  \label{fig:decomp}
\end{figure}

\begin{xmpl}
  Define $V_1,V_2\leq\F^3$ by
  \begin{align*}
    V_1&=\set{(x_1,x_2,0)\st x_1,x_2\in\F}\\
    V_2&=\set{(0,0,x_3)\st x_3\in\F}.
  \end{align*}
  Then $\F^3=V_1\oplus V_2$.
\end{xmpl}

When is a sum direct?  We consider the case of two summands
first where there is a very simple answer.
\begin{prop}
  \label{th:5}
  % Criterion for direct sum
  Let $V_1,V_2\leq V$.  Then $V_1+V_2$ is direct if and only
  if $V_1\cap V_2=\set0$.
\end{prop}
\begin{proof}
  First suppose that $V_1+V_2$ is direct and let $v\in
  V_1\cap V_2$.  Then we can write $v$ in two ways:
  \begin{align*}
    v&=v_1+0\\&=0+v_2,
  \end{align*}
  with $v=v_1=v_2$.  The uniqueness of the decomposition now
  forces $v=0$.

  For the converse, suppose that $V_1\cap V_2=\set0$ and
  that $v\in V_1+V_2$ can be written
  \begin{equation*}
    v=v_1+v_2=w_1+w_2
  \end{equation*}
  with $v_i,w_i\in V_i$, $i=1,2$.  Then
  \begin{equation*}
    (v_1-w_1)=(w_2-v_2)
  \end{equation*}
  with the left hand in $V_1$, the right in $V_2$ and so
  both in $V_1\cap V_2$ from which we immediately get
  $v_i=w_i$, $i=1,2$ so that $V_1+V_2$ is direct.  
\end{proof}

The special case $V=V_1+V_2$ is important and deserves some
terminology:
\begin{defn}
  Let $V_1,V_2\leq V$.  $V$ is the \emph{(internal)
    direct sum of $V_1$ and $V_2$} if $V=V_1\oplus V_2$.

  In this case, say that $V_2$ is a \emph{complement} of
  $V_1$ (and $V_1$ is a complement of $V_2$).
\end{defn}
\begin{warning}
  This notion of the complement of the subspace $V_1$ has
  \emph{nothing at all} to do with the set-theoretic
  complement $V\setminus V_1$ which is never a subspace.
\end{warning}
\begin{rems}\item[]
  \begin{compactenum}
  \item From \cref{th:5}, we see that $V=V_1\oplus V_2$ if
    and only if $V=V_1+V_2$ and $V_1\cap V_2=\set0$.  Many
    people take these latter properties as the
    \emph{definition} of internal direct sum.
  \item There is a related notion of \emph{external} direct
    sum that we will not discuss.
  \end{compactenum}
\end{rems}

\begin{figure}[ht]
  \centering
  \tdplotsetmaincoords{70}{60}
  \ThisAltText{A direct sum of a line and a plane.}
  \begin{tikzpicture}[tdplot_main_coords]
    \draw[fill=yellow!10!white,opacity=0.3] (-4,-4,0) -- (-4,4,0) --
    (4,4,0) -- (4,-4,0) -- cycle;
    \draw
    [blue,dashed] (-1.7,-1.7,-1.7) -- (0,0,0);
    \draw [blue]
    (0,0,0)--(4,4,4); \draw[blue] (-3,-3,-3)--(-1.7,-1.7,-1.7);
    \filldraw[red] (0,0,0) node[black,above left]{$0$} circle (.5mm);
    \node[black,above left] at (3,3,3) {$V_{2}$} ;
    \node[black,right] at (4,4,0) {$V_{1}$}; 
  \end{tikzpicture}
  \caption{$\R^3$ as a direct sum of a line and a plane}
  \label{fig:dsum}
\end{figure}

When there are many summands, the condition that a sum be
direct is a little more involved:
\begin{prop}
  \label{th:8}% decomp: many sumands
  Let $\lst{V}1k\leq V$, $k\geq 2$.  Then the sum
  $\plst{V}1k$ is direct if and only if for each $1\leq i\leq k$,
    $V_i\cap(\sum_{j\neq i}V_j)=\set{0}$.
\end{prop}
\begin{proof}
  This is an exercise in imitating the proof of \cref{th:5}.
\end{proof}
\begin{rem}
  This is a much stronger condition than simply asking that
  each $V_i\cap V_j=\set 0$, for $i\neq j$.
\end{rem}

\subsection{Direct sums and projections}
\label{sec:direct-sums-proj}

\begin{defn}
  Let $V$ be a vector space.  A linear map $\pi:V\to V$ is a
  \emph{projection} if $\pi\circ\pi=\pi$.
\end{defn}

\begin{ex}[Question 3 on sheet 2.]
  If $\pi$ is a projection, $V=\ker\pi\oplus\im\pi$.
\end{ex}

In fact, all direct sums arise this way:
\begin{prop}
  \label{th:79}
  % dir sums and projections
  Let $V_1,V_2\leq V$ with $V=V_1\oplus V_2$.  Then there
  are projections $\pi_1,\pi_2:V\to V$ such that:
  \begin{compactenum}[(a)]
  \item $\im\pi_i=V_i$, $i=1,2$;
  \item $\ker\pi_1=V_2$, $\ker\pi_2=V_1$;
  \item $v=\pi_1(v)+\pi_2(v)$, for all $v\in V$.  Otherwise
    said, $\id_V=\pi_1+\pi_2$.
  \end{compactenum}
\end{prop}
\begin{proof}
  Item (c) tells us how to define the $\pi_i$ so we do this
  first: for $v\in V$, we have that $v=v_1+v_2$ for unique
  $v_i\in V_i$, $i=1,2$.  So we define $\pi_i(v)$ to be
  \begin{equation*}
    \pi_i(v):=v_i,
  \end{equation*}
  for $i=1,2$.

  Our first task is to prove that the $\pi_i$ are linear:
  for $v,w\in V$ and $\lambda\in\F$, we have
  \begin{align*}
    v&=\pi_1(v)+ \pi_2(v)\\
    w&=\pi_1(w)+ \pi_2(w)\\
    v+\lambda w&=\pi_1(v+\lambda w)+ \pi_2(v+\lambda w).
  \end{align*}
  However, the first two equalities also give
  \begin{equation*}
    v+\lambda w=(\pi_1(v)+\lambda\pi_1(w))+(\pi_2(v)+\lambda\pi_2(w))
  \end{equation*}
  so the uniqueness in the third equality gives
  \begin{equation*}
    \pi_i(v+\lambda w)=\pi_i(v)+\lambda\pi_i(w),
  \end{equation*}
  $i=1,2$, so that both $\pi_i$ are linear.

  By definition, $\im\pi_i\leq V_i$.  For the converse, note
  that, for $v_1\in V_{1}$, we have $v_1=v_1+0$, with $0\in
  V_2$, so that $\pi_{1}(v_1)=v_1$.  In particular,
  $V_1\leq\im\pi_1$ so that $\im\pi_1=V_1$.  Moreover,
  taking $v_1=\pi_1(v)$, we get $\pi_1(\pi_1(v))=\pi_1(v)$,
  for any $v\in V$ so that $\pi_1$ is a projection.
  Similarly $\pi_2$ is a projection and (a) holds.

  Finally, $v=\pi_{1}(v)+\pi_2(v)\in\ker\pi_1$ if and only
  if $v=\pi_2(v)$, or, as we have just seen, $v\in V_2$.
  Thus $\ker\pi_1=V_2$ and similarly $\ker\pi_2=V_1$
  settling (b).
\end{proof}

As a corollary, we see that dimensions add in direct sums:
\begin{prop}\label{th:7}% dims add
  Let $V=V_1\oplus V_2$ with $V$ finite-dimensional.  Then
  \begin{equation*}
    \dim V=\dim V_1+\dim V_2.
  \end{equation*}
\end{prop}
\begin{proof}
  We apply the rank-nullity theorem to $\pi_1$:
  \begin{align*}
    \dim V&=\dim\im\pi_1+\dim\ker\pi_{1}\\
    &=\dim V_1+\dim V_2.
  \end{align*}
\end{proof}

\subsection{Induction from two summands}
\label{sec:induction-from-two}

A convenient way to analyse direct sums with many summands
is to induct from the two summand case.  For this, we need:
\begin{lem}
  \label{th:80}
  % induct for dir sums
  Let $\lst{V}1k\leq V$.  Then $\plst{V}1k$ is direct if and
  only if $\plst{V}1{k-1}$ is direct and
  $(\plst{V}1{k-1})+V_k$ (two summands) is direct.
\end{lem}
\begin{proof}
  Suppose first that $\plst{V}1k$ is direct.  Then any
  $v\in\plst{V}1{k-1}$ can be written
  \begin{equation*}
    v=\plst{v}1{k-1}+0
  \end{equation*}
  for unique $v_i\in V_i$, $\bw1i{k-1}$ so that
  $\plst{V}1{k-1}$ is direct.  Moreover, any $v\in
  (\plst{V}1{k-1})+V_k=\plst{V}1k$ can be written
  \begin{equation*}
    v=\plst{v}1k=(\plst{v}1{k-1})+v_k
  \end{equation*}
  with, in particular, unique $v_k\in V_k$ so that
  $(\plst{V}1{k-1})+V_k$ is direct.

  For the converse, suppose that $\plst{V}1{k-1}$  and
  $(\plst{V}1{k-1})+V_k$ are both direct.  Then any
  $v\in\plst{V}1k$
  can be written $v=w+v_k$ for unique $w\in\plst{V}1{k-1}$
  and $v_k\in V_k$.  Also, there is a unique way to write
  $w$ as
  \begin{equation*}
    w=\plst{v}1{k-1}
  \end{equation*}
  with $v_i\in V_i$, $\bw1i{k-1}$.  Putting this together,
  we get
  \begin{equation*}
    v=\plst{v}1k
  \end{equation*}
  for unique $v_i\in V_i$, $\bw1ik$ so that $\plst{V}1k$ is
  direct.
\end{proof}

Here is a sample application:
\begin{cor}
  \label{th:11}% dim of many summand dir sum
  Let $\lst{V}1k\leq V$ be subspaces of a finite-dimensional
  vector space $V$ with $\plst{V}1k$ direct.  Then
  \begin{equation*}
    \dim\oplst{V}1k=\plst{\dim V}1k.
  \end{equation*}
\end{cor}
\begin{proof}
  We induct on $k$ using \cref{th:7} and \cref{th:80} in the
  induction step.  In more detail: the induction hypothesis
  is that the formula holds for $k$ summands.  The base case
  reads
  \begin{equation*}
    \dim V_1=\dim V_1
  \end{equation*}
  which trivially holds.  For the induction step, suppose
  that the formula holds for any $k-1$ summands.  Then, if
  $\plst{V}1k$ is direct, \cref{th:80} says that
  $\plst{V}1{k-1}$ is direct and then the induction
  hypothesis says that $\dim\oplst{V}1{k-1}=\plst{\dim
    V}1{k-1}$.  Now \cref{th:80} says that
  \begin{equation*}
    \oplst{V}1k=(\oplst{V}1{k-1})\oplus V_k
  \end{equation*}
  so that \cref{th:7} applies to give
  \begin{equation*}
    \dim\oplst{V}1k=(\plst{\dim V}1{k-1})+\dim V_k.
  \end{equation*}
\end{proof}

\subsection{Direct sums and bases}
\label{sec:dirst-sums-bases}

\cref{th:7} suggests that there is a relation between the
bases of $V_1,V_2$ and the basis of $V_1\oplus V_2$.  This
is indeed the case:
\begin{prop}
  \label{th:78}
  % bases of dir sum (two summands)
  Let $V_1,V_2\leq V$ be finite-dimensional subspaces with
  bases $\cB_1:\lst{v}1k$ and $\cB_2:\lst{w}1l$.  Then
  $V_1+V_2$ is direct if and only if the
  \emph{concatenation}\footnote{The concatenation of two
    lists is simply the list obtained by adjoining all
    entries in the second list to  the first.}
  $\cB_1\cB_2:\lst{v}1k,\lst{w}1l$ is a basis of $V_1+V_2$.
\end{prop}
\begin{proof}
  Clearly $\cB_1\cB_2$ spans $V_1+V_2$ and so will be a
  basis exactly when it is linearly independent.

  Suppose that $V_1+V_2$ is direct and that we have a linear
  relation
  $\sum_{i=1}^k\lambda_{i}v_i+\sum_{j=1}^l\mu_jw_j=0$.  Then
  \begin{equation*}
    \sum_{i=1}^k\lambda_{i}v_i=-\sum_{j=1}^l\mu_jw_j\in
    V_1\cap V_2
  \end{equation*}
  which last is the zero subspace by \cref{th:5}.  Thus
  \begin{equation*}
    \sum_{i=1}^k\lambda_{i}v_i=\sum_{j=1}^l\mu_jw_j=0
  \end{equation*}
  so that all the $\lambda_i$ and $\mu_j$ vanish since
  $\cB_1$ and $\cB_2$ are linearly independent.  We conclude
  that $\cB_1\cB_2$ is linearly independent and so a basis.

  Conversely, if $\cB_1\cB_2$ is a basis and $v\in V_1\cap
  V_2$, we can write $v$ in two ways:
  $v=\sum_{i=1}^k\lambda_iv_i$, for some
  $\lst\lambda1k\in\F$, since $v\in V_1$ and, similarly,
  $v=\sum_{j=1}^l\mu_jw_j$.  We therefore have a linear
  relation
  $\sum_{i=1}^k\lambda_{i}v_i-\sum_{j=1}^l\mu_jw_j=0$ and
  so, by
  linear independence of $\cB_1\cB_2$, all $\lambda_i,\mu_j$
  vanish so that $v=0$.  Thus $V_1\cap V_2=\set0$ and
  $V_1+V_2$ is direct by \cref{th:5}.  
\end{proof}

Again, this along with \cref{th:80} and induction on $k$
yields the many-summand version:
\begin{cor}
  \label{th:81}
  % basis of dir sum (many summands)
  Let $\lst{V}1k\leq V$ be finite-dimensional subspaces with
  $\cB_i$ a basis of $V_i$, $\bw1ik$.  Then $\plst{V}1k$ is
  direct if and only if the concatenation $\cB_1\ldots\cB_k$
  is a basis for $\plst{V}1k$.
\end{cor}

\subsection{Complements}
\label{sec:complements}

For finite-dimensional vector spaces, any subspace has a complement:
\begin{prop}[Complements exist]\label{th:83}
  Let $U\leq V$, a finite-dimensional vector space.  Then
  there is a complement to $U$.
\end{prop}
\begin{proof}
  Let $\cB_1:\lst{v}1k$ be a basis for $U$ and so a linearly
  independent list of vectors in $V$.  By
  \cref{th:2}, we can extend the list to get a
  basis $\cB:\lst{v}1n$ of $V$.  Set
  $W=\Span{\lst{v}{k+1}n}\leq V$: this is a complement to $U$.

  Indeed, $\cB_2:\lst{v}{k+1}n$ is a basis for $W$ and
  $\cB=\cB_1\cB_2$ so that $V=U\oplus W$ by \cref{th:78}.
\end{proof}

In fact, as Figure \ref{fig:compl} illustrates, there are many
complements to a given subspace.
\begin{figure}[ht]
  \centering
  \ThisAltText{A subspace has many complements.}
  \begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=0.5cm,y=0.5cm]
\clip(-1.62,-2.22) rectangle (7.28,4.98);
\draw [color=blue] (-2.32,-1.16)-- (7.6,3.86) node {$U$};
\draw [dash pattern=on 2pt off 2pt,color=blue] (-0.9702881095604644,3.355165734085247)-- (5.430412939513084,-0.7437395332366683);
\draw [dash pattern=on 2pt off 2pt,color=blue] (1.4388065939899053,4.579668913988877)-- (3.3989843940668703,-2.4858303486666564);
\draw [dash pattern=on 2pt off 2pt,color=blue] (3.4882977234361667,4.597057083073897)-- (1.3086756902221568,-2.009665806041375);
\draw [fill=red] (2.3723833963827237,1.2145730493791602)
circle (1.0pt);
\end{tikzpicture}
  \caption{Each dashed line is a complement to the undashed subspace.}
  \label{fig:compl}
\end{figure}

Here is an application:
\begin{prop}[Extension of linear maps]
  \label{th:82}
  % extn of maps from subspace
  Let $V,W$ be vector spaces with $V$ finite-dimensional.
  Let $U\leq V$ be a subspace and $\phi:U\to W$ a linear
  map.  Then there is a linear map $\Phi:V\to W$ such that
  the restriction\footnote{Recall that if $f:X\to Y$ is a
    map of sets and $A\sub X$ then the \emph{restriction} of
  $f$ to $A$ is the map $f\restr{A}:A\to Y$ given by
  $f\restr{A}(a)=f(a)$, for all $a\in A$.} of $\Phi$ to $U$ is $\phi$:
  $\Phi\restr{U}=\phi$. Otherwise said: for all $u\in U$
  \begin{equation*}
    \Phi(u)=\phi(u).
  \end{equation*}
\end{prop}
\begin{proof}
  By \cref{th:83}, $U$ has a complement and so, by
  \cref{th:79}, there is a projection $\pi:V\to V$ with
  image $U$.

  Set $\Phi=\phi\circ\pi:V\to W$.  This is a linear map and
  \begin{equation*}
    \Phi\restr{U}=\phi\circ\pi\restr{U}=\phi
  \end{equation*}
  since, for $u=\pi(v)\in\im\pi=U$, $\pi(u)=\pi(\pi(v))=\pi(v)=u$.
\end{proof}

\section{Quotients}
\label{sec:quotients}

Let $U\leq V$.  We construct a new vector space from $U$ and
$V$ which is an ``abstract complement'' to $U$.  The
elements of this vector space are equivalence classes for
the following equivalence relation:
\begin{defn}
  Let $U\leq V$.  Say that $v,w\in V$ are \emph{congruent
    modulo $U$} if $v-w\in U$.  In this case, we write
  $v\equiv w\mod U$.
\end{defn}

\begin{warning}
  This is emphatically not the relation of congruence modulo
  an integer $n$ that you studied in Algebra 1A: here the
  relation is between vectors in a vector space.  However,
  both notions of congruence are examples of a general
  construction in group theory.
\end{warning}

\begin{lem}
  \label{th:16}
  Congruence modulo $U$ is an equivalence relation.
\end{lem}
\begin{proof}
  Exercise\footnote{This is question 1 on exercise sheet
    3.}!
\end{proof}
Thus each $v\in V$ lies in exactly one equivalence class
$[v]\sub V$.

What do these equivalence classes look like?  Note that
$w\equiv v\mod U$ if and only if $w-v\in U$ or,
equivalently, $w=v+u$, for some $u\in U$.

\begin{defn}
  For $v\in V$, $U\leq V$, the set $v+U:=\set{v+u\st u\in U}\sub
  V$ is called a \emph{coset of $U$} and $v$ is called a
  \emph{coset representative} of $v+U$.
\end{defn}
We conclude that the equivalence class of $v$
modulo $U$ is the coset $v+U$.
\begin{figure}[ht]
  \centering
  \ThisAltText{A subspace and one of its cosets.}
  \begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
    \clip(-1.5,-2.06) rectangle (5.5,3.84);
    \draw [color=blue] (0.,-1.)-- (5.,1.) node[black,right]{$U$};
    \draw [color=blue] (-1.,1.)-- (4.,3.) node[black,right]{$v+U$};
    \draw [fill,ffqqqq] (2.2,2.28) circle (1.0pt) node[below,black] {$v$};
    \draw [fill,ffqqqq] (2.296551724137931,-0.0813793103448276)
    circle (1.0pt) node[below,black] {$0$};
  \end{tikzpicture}
  \caption{A subspace $U\leq\R^{2}$ and a coset $v+U$.}
  \label{fig:coset}
\end{figure}

\begin{rem}
  In geometry, cosets of vector subspaces are called \emph{affine
    subspaces}.  Examples include lines in $\R^2$ and lines
  and planes in $\R^3$ irrespective of whether they contain
  zero (as vector subspaces must).
\end{rem}

\begin{xmpl}
  Fibres of a linear map: let $\phi:V\to W$ be a linear map
  and let $w\in\im\phi$.  Then the \emph{fibre of $\phi$
    over $w$} is defined by:
  \begin{equation*}
    \phi^{-1}\set{w}:=\set{v\in V\st \phi(v)=w}.
  \end{equation*}
  Unless $w=0$, this is not a linear subspace but notice
  that $v,v'$ are in the same fibre if and only if
  $\phi(v)=\phi(v')$, or, equivalently, $\phi(v-v')=0$ or
  $v-v'\in\ker\phi$.  We conclude that the fibres of $\phi$
  are exactly the cosets of $\ker\phi$:
  \begin{equation*}
    \phi^{-1}\set{w}=v+\ker\phi,
  \end{equation*}
  for any $v\in\phi^{-1}\set{w}$.
    
  We shall see below that any coset arises this way for a
  suitable $\phi$.
\end{xmpl}

\begin{defn}
  Let $U\leq V$.  The \emph{quotient space $V/U$ of $V$ by
    $U$} is the set $V/U$, pronounced ``$V$ mod $U$'', of
  cosets of $U$:
  \begin{equation*}
    V/U:=\set{v+U\st v\in V}.
  \end{equation*}
  This is a subset of the \emph{power set}\footnote{Recall
    from Algebra 1A that the power set of a set $A$ is the
    set of all subsets of $A$.} $\mathcal{P}(V)$ of $V$.
  
  The \emph{quotient map} $q:V\to V/U$ is defined by
  \begin{equation*}
    q(v)=v+U.
  \end{equation*}
\end{defn}

The quotient map $q$ will be important to us.  It has two
key properties:
\begin{compactenum}
\item $q$ is surjective.
\item $q(v)=q(v')$ if and only if $v\equiv v'\mod U$, that
  is, $v-v'\in U$.
\end{compactenum}

We can add and scalar multiply cosets to make $V/U$ into a
vector space and $q$ into a linear map:
\begin{thm}
  \label{th:17}% quotients
  Let $U\leq V$.  Then, for $v,w\in V$, $\lambda\in\F$,
  \begin{align*}
    (v+U)+(w+U)&:=(v+w)+U\\
    \lambda(v+U)&:=(\lambda v)+U
  \end{align*}
  give well-defined operations of addition and scalar
  multiplication on $V/U$ with respect to which $V/U$ is a
  vector space and $q:V\to V/U$ is a linear map.

  Moreover, $\ker q=U$ and $\im q=V/U$.
\end{thm}
\begin{proof}
  We phrase everything in terms of $q$ to keep the notation
  under control.  Since $q$ surjects, we lose nothing by
  doing this: any element of $V/U$ is of the form $q(v)$ for
  some $v\in V$.

  With this understood, the proposed addition and scalar
  multiplication in $V/U$ read
  \begin{align*}
    q(v)+q(w)&:=q(v+w)\\\lambda q(v)&:=q(\lambda v)
  \end{align*}
  so that $q$ is certainly linear so long as these
  operations make sense.  Here the issue is that
  if $q(v)=q(v')$ and $q(w)=q(w')$, we must show that
  \begin{equation}\label{eq:7}
    q(v+w)=q(v'+w'),\qquad q(\lambda v)=q(\lambda v').
  \end{equation}
  However, in this case, we have $v-v'\in U$ and $w-w'\in
  U$ so that
    \begin{gather*}
    (v+w)-(v'+w')=(v-v')+(w-w')\in U\\
    \lambda v-\lambda v'=\lambda(v-v')\in U,
  \end{gather*}
  since $U$ is a subspace, and this establishes
  \eqref{eq:7}.

  As for the vector space axioms, these follow from those of
  $V$.  For example:
  \begin{equation*}
    q(v)+q(w)=q(v+w)=q(w+v)=q(w)+q(v).
  \end{equation*}
  Here the first and third equalities are the definition of
  addition in $V/U$ and the middle one comes from
  commutativity of addition in $V$.  The zero element is
  $q(0)=0+U=U$ while the additive inverse of $q(v)$ is
  $q(-v)$.

  The linearity of $q$ comes straight from how we defined
  our addition and scalar multiplication while $v\in\ker q$
  if and only if $q(v)=q(0)$ if and only if $v=v-0\in U$ so
  that $\ker q=U$.
\end{proof}

\begin{figure}[ht]
  \centering
  \ThisAltText{Illustration of the quotient map.}
  \begin{tikzpicture}[x=1.0cm,y=1.0cm]
    \clip(-2.,0.) rectangle (7.,3.4);
    \draw [color=qqqqff] (-1.,0.5)-- (2.,0.5)
    node[black,below right]{$V$};
    \draw [color=qqqqff] (-1.,1.)-- (2.,1.);
    \draw [color=qqqqff] (-1.,1.5)node[left,black] {$U$}-- (2.,1.5);
    \draw [color=qqqqff] (-1.,2.)-- (2.,2.);
    \draw [color=ffqqqq] (-1.,2.5)node[black,left]{$v+U$}-- (2.,2.5);
    \draw [color=qqqqff] (-1.,3.)-- (2.,3.);
    \draw [->](3.,1.5)--node[above]{$q$}(3.5,1.5);
    \draw (5.,3.)-- (5.,0.5) node[below right]{$V/U$};
    \draw [fill,qqqqff] (0.5,1.5) circle (1.5pt) node[below,black] {$0$};
    \draw [fill,ffqqqq] (1.,2.5) circle (1.5pt) node[above,black] {$v$};
    \draw [fill,qqqqff] (5.,1.5) circle (1.5pt) node[right,black] {$0+U$};
    \draw [fill,ffqqqq] (5.,2.5) circle (1.5pt) node[right,black] {$v+U$};
  \end{tikzpicture}
  \caption{The quotient map $q$.}
  \label{fig:q}
\end{figure}

\begin{cor}
  Let $U\leq V$.  If $V$ is finite-dimensional then so is
  $V/U$ and
  \begin{equation*}
    \dim V/U=\dim V-\dim U.
  \end{equation*}
\end{cor}
\begin{proof}
  Apply rank-nullity to $q$ using $\ker q=U$ and $\im q=V/U$.
\end{proof}

\begin{rem}
  \Cref{th:17} shows that:
  \begin{compactenum}
  \item Any $U\leq V$ is the kernel of a linear map.
  \item Any coset $v+U$ is the fibre of a linear map: indeed
    \begin{equation*}
      v+U=q^{-1}\set{q(v)}.
    \end{equation*}
  \end{compactenum}
\end{rem}

\begin{commentary}
  Many people find the quotient space $V/U$ difficult to
  think about: its elements are (special) subsets of $V$ and
  this can be confusing.

  An alternative, perhaps better way, to proceed is to
  concentrate instead on the \emph{properties} of $V/U$ in
  much that same way that, in Analysis, we deal with real
  numbers via the axioms of a complete ordered field without
  worrying too much what a real number actually is!

  From this point of view, the quotient $V/U$ of $V$ by $U$
  is a vector space along with a linear map $q:V\to V/U$
  such that
  \begin{compactitem}
  \item $q$ surjects;
  \item $\ker q=U$
  \end{compactitem}
  and this is really all you need to know!

  The content of \cref{th:17}, from this perspective, is
  simply that quotients exist!
\end{commentary}

\begin{thm}[First Isomorphism Theorem]
  \label{th:18}%FIT
  Let $\phi:V\to W$ be a linear map of vector spaces.

  Define $\bar{\phi}:V/\ker\phi\to\im\phi$ by
  \begin{equation*}
    \bar{\phi}(q(v))=\phi(v),
  \end{equation*}
  where $q:V\to V/\ker\phi$ is the quotient map.
  
  Then $\bar{\phi}$ is a well-defined linear isomorphism.

  In particular, $V/\ker\phi\cong\im\phi$.
\end{thm}
\begin{proof}
  First we show that $\bar{\phi}$ is well-defined:
  $q(v)=q(v')$ if and only if $v-v'\in\ker\phi$ if and only
  if $\phi(v-v')=0$, or, equivalently, $\phi(v)=\phi(v')$.
  We also get a bit more: $\bar{\phi}$ injects since if
  $\bar{\phi}(q(v))=\bar{\phi}(q(v'))$ then
  $\phi(v)=\phi(v')$ which implies that $q(v)=q(v')$.

  To see that $\bar{\phi}$ is linear, we compute using the
  linearity of $q$ and $\phi$:
  \begin{equation*}
    \bar{\phi}(q(v_1)+\lambda q(v_2))=
    \bar{\phi}(q(v_1+\lambda v_2))=
    \phi(v_1+\lambda v_2)=
    \phi(v_1)+\lambda\phi(v_2)=
    \bar{\phi}(q(v_1))+\lambda\bar{\phi}(q(v_2)),
  \end{equation*}
  for $v_1,v_2\in V$, $\lambda\in\F$.

  It remains to show that $\bar{\phi}$ is surjective: but if
  $w\in\im\phi$, then $w=\phi(v)=\bar{\phi}(q(v))$, for some
  $v\in V$, and we are done.
\end{proof}

\begin{rems}
\item[]
  \begin{compactenum}
  \item Let $q:V\to V/\ker\phi$ be the quotient map and
    $i:\im\phi\to W$ the inclusion.  Then the First
    Isomorphism Theorem shows that we may write $\phi$ as
    the composition $i\circ\bar{\phi}\circ q$ of a quotient
    map, an isomorphism and an inclusion.
  \item This whole story of cosets, quotients and the First
    Isomorphism Theorem has versions in many other contexts
    such as group theory (see MA30237) and ring theory
    (MA20217).
  \end{compactenum}
\end{rems}


\chapter{Inner product spaces}
\label{cha:inner-product-spaces}

In this chapter, we equip real or complex vector spaces with
extra structure that generalises the familiar dot product.

\begin{convention}
  In this chapter, we take the field $\F$ of scalars to be
  either $\R$ or $\C$.
\end{convention}

\section{Inner products}
\label{sec:inner-products}

\subsection{Definition and examples}
\label{sec:definition-examples}

Recall the dot (or scalar) product on $\R^n$: for
$x=\vec{x}1n,y=\vec{y}1n\in\R^{n}$,
\begin{equation*}
  x\cdot y:=\lc{x}{y}1n=\bx^T\by.
\end{equation*}
Using this we define:
\begin{compactitem}
\item the \emph{length} of $x$: $\norm{x}:=\sqrt{x\cdot x}$;
\item the \emph{angle} $\theta$ between $x$ and $y$: $x\cdot
  y=\norm{x}\norm{y}\cos\theta$.
\end{compactitem}

There is also a dot product on $\C^n$: for $x,y\in\C^n$,
\begin{equation*}
  x\cdot y=\lc{\bar{x}}{y}1n=\bx^{\dagger}\by,
\end{equation*}
where $\bx^{\dagger}$ (pronounced ``x-dagger'') is the
conjugate transpose $\bar{\bx}^T$ of $\bx$.  We then have
that
\begin{equation*}
  x\cdot x=\sum_{i=1}^n\bar{x}_ix_i=\sum_{i=1}^n\abs{x_i}^2
\end{equation*}
is real, non-negative and vanishes exactly when $x=0$.

We abstract the key properties of the dot product into the
following:
\begin{defn}
  Let $V$ be a vector space of $\F$ (which is $\R$ or $\C$).

  An \emph{inner product} on $V$ is a map $V\times
  V\to\F:(v,w)\mapsto\ip{v,w}$ which is:
  \begin{compactenum}[(1)]
  \item \emph{(conjugate) symmetric}:
    $\ip{w,v}=\overline{\ip{v,w}}$, for all $v,w\in V$.  In
    particular $\ip{v,v}=\overline{\ip{v,v}}$ and so is
    real.
  \item \emph{linear in the second slot}:
    \begin{align*}
      \ip{u,v+w}&=\ip{u,v}+\ip{u,w}\\
      \ip{u,\lambda v}&=\lambda\ip{u,v},
    \end{align*}
    for all $u,v,w\in V$ and $\lambda\in\F$.
  \item \emph{positive definite:} For all $v\in V$,
    $\ip{v,v}\geq 0$ with equality if and only if $v=0$.
  \end{compactenum}
  A vector space with an inner product is called an
  \emph{inner product space}.
\end{defn}

\begin{rem}
  Any subspace $U$ of an inner product space $V$ is also an
  inner product space: just restrict $\ip{\, ,\,}$ to
  $U\times U$.
\end{rem}

Let us spell out the implications of this definition in the
real and complex cases.

Suppose first that $\F=\R$.  Then the conjugate symmetry is
just symmetry: $\ip{v,w}=\ip{w,v}$ and it follows that we
also have linearity in the first slot:
\begin{align*}
  \ip{v+w,u}&=\ip{v,u}+\ip{w,u}\\
  \ip{\lambda v,u}&=\lambda\ip{v,u}.
\end{align*}
We summarise the situation by saying that a real inner
product is a \emph{positive definite, symmetric, bilinear form}.
We shall have more to say about bilinear forms later in
chapter~\ref{cha:bilinearity}.

Now let us turn to the case $\F=\C$.  Now it is not the case
that an inner product is linear in the first slot.
\begin{defn}
  A map $\phi:V\to W$ of complex vector spaces is \emph{conjugate linear} (or
  \emph{anti-linear}) if
  \begin{align*}
    \phi(v+w)&=\phi(v)+\phi(w) \\
    \phi(\lambda v)&=\bar{\lambda}\phi(v),
  \end{align*}
  for all $v,w\in V$ and $\lambda\in\F$.
\end{defn}
We see from properties (1) and (2) that a complex inner
product has
\begin{align*}
  \ip{v+w,u}&=\ip{v,u}+\ip{w,u}\\
  \ip{\lambda v,u}&=\bar{\lambda}\ip{v,u}
\end{align*}
and so is conjugate linear in the first slot and linear in
the second.  Such a function is said to be
\emph{sesquilinear} (from the Latin \emph{sesqui} which
means one-and-a-half).  Thus an inner product on a complex
vector spaces is a \emph{positive definite, conjugate symmetric,
  sesquilinear form}.

\begin{defn}
  Let $V$ be an inner product space.
  \begin{compactenum}
  \item The \emph{norm} of $v\in V$ is
    $\norm{v}:=\sqrt{\ip{v,v}}\geq 0$.
  \item Say $v,w\in V$ are \emph{orthogonal} or
    \emph{perpendicular} if $\ip{v,w}=0$.  In this case, we
    write $v\perp w$.
  \end{compactenum}
\end{defn}

\begin{rems}\item[]
  \begin{compactenum}
  \item The norm allows us to define the \emph{distance}
    between $v$ and $w$ by $\norm{v-w}$.  We can now do
    analysis on $V$: this is one of the Big Ideas in
    MA20218.
  \item \textbf{Warning}: There is another convention for
    complex inner products which is prevalent in Analysis:
    there they ask that $\ip{\, ,\,}$ be linear in the
    \emph{first} slot and conjugate linear in the second.
    There are good reasons for either choice.
  \item Physicists often write $\ip{v\vert w}$ for
    $\ip{v,w}$. Inner product spaces (especially
    infinite-dimensional ones) are the setting for quantum
    mechanics.
  \end{compactenum}
\end{rems}

\begin{xmpls}
\item[]
  \begin{compactenum}
  \item The dot product on $\R^n$ or $\C^n$ is an inner
    product.
  \item Let $[a,b]\sub\R$ be a closed, bounded interval.
    Define a real inner product on $C^0[a,b]$ by
    \begin{equation*}
      \ip{f,g}=\int_a^bfg.
    \end{equation*}
    This is clearly symmetric, bilinear and non-negative.
    To see that it is definite, one must show that if
    $\int_a^bf^2=0$ then $f=0$.  This is an exercise in
    Analysis using the inertia property of continuous
    functions (see MA20218).
  \item The set of \emph{square summable sequences}
    $\ell_2\sub\R^{\N}$ is given by
    \begin{equation*}
      \ell_2:=\set{(a_{n})_{n\in\N}\st \sum_{n\in\N}a_n^2<\infty}.
    \end{equation*}
    \begin{exs}[Question 7 on sheet 4.]
    \item[]
      \begin{compactenum}[(a)]
      \item $\ell_2\leq\R^{\N}$.
      \item If $a,b\in\ell_2$ then $\sum_{n\in\N}a_nb_n$ is
        absolutely convergent and then
        \begin{equation*}
          \ip{a,b}:=\sum_{n\in\N}a_nb_n
        \end{equation*}
        defines an inner product on $\ell_2$.
      \end{compactenum}
      \textbf{Hint}: for $x,y\in\R$, rearrange
      $0\leq(\abs{x}-\abs{y})^2$ to get
      \begin{subequations}
        \label{eq:8}
        \begin{equation}
          \label{eq:9}
          2\abs{x}\abs{y}\leq x^2+y^2
        \end{equation}
        and then deduce
        \begin{equation}
          \label{eq:10}
          (x+y)^2\leq 2(x^2+y^2).
        \end{equation}
      \end{subequations}
      Judicious use of equations \eqref{eq:8} and the
      comparison theorem from MA10207 will bake the cake.
    \end{exs}
  \end{compactenum}
\end{xmpls}

\begin{rem}
  Perhaps surprisingly, $\ell_2$ and $C^0[a,b]$ are closely
  related: this is what Fourier series are about: see
  MA20223.
\end{rem}
\subsection{Cauchy--Schwarz inequality}

Here is one of the most important and ubiquitous
inequalities in all of mathematics:
\begin{thm}[Cauchy--Schwarz inequality]
  \label{th:19}%Cauchy--Schwarz
  Let $V$ be an inner product space.  For $v,w\in V$,
  \begin{equation}
    \label{eq:21}%CS
    \abs{\ip{v,w}}\leq\norm{v}\norm{w}
  \end{equation}
  with equality if and only if $v,w$ are linearly dependent,
  that is, either $v=0$ or $w=\lambda v$, for some
  $\lambda\in\F$.
\end{thm}
\begin{proof}
  The idea of the proof is to write $w=\lambda v+u$ where
  $u\perp v$ (see Figure~\ref{fig:CS}) and then use the fact
  that $\norm{u}^2\geq 0$.
 
  In detail, first note that if $v=0$ then both sides of the
  inequality vanish and there is nothing to prove.
  Otherwise, let us seek $\lambda\in\F$ so that
  $u:=w-\lambda v\perp v$.  We therefore need
  \begin{equation*}
    0=\ip{v,w-\lambda v}=\ip{v,w}-\lambda\ip{v,v}
  \end{equation*}
  so that
  \begin{equation*}
    \lambda=\frac{\ip{v,w}}{\norm{v}^2}.
  \end{equation*}
  The situation is shown in Figure~\ref{fig:CS}.
   \begin{figure}[ht]
     \centering
     \ThisAltText{How to construct $u$.}
     \begin{tikzpicture}[x=1cm,y=1cm]
       \draw[->] (0,0)-- (3,0) node[right]{$v$};
       \draw[->] (0,0)-- (0,3) node[left]{$u$};
       \draw[->] (0,0)-- (1,3) node[right]{$w$};
       \draw[dashed] (0,3)--(1,3);
       \draw[dashed] (1,3)--(1,0);
       \draw[thick,->] (0,0)--(1,0);
       \draw[fill] (1,0) circle [radius=1pt] node[below]{$\lambda v$};
       \draw[red,fill] (0,0) circle [radius=1pt] node[black,below]{$0$}; 
     \end{tikzpicture}
     \caption{Construction of $u$.}
     \label{fig:CS}
   \end{figure}
  
  With $\lambda$ and then $u$ so defined we have
  \begin{align*}
    0\leq\norm{u}^{2}
    &=\ip{w-\lambda v,u}=\ip{w,u}=\ip{w,w-\lambda v} \\
    &=\ip{w,w}-\lambda\ip{w,v}\\
    &=\norm{w}^2-\frac{\abs{\ip{v,w}}^{2}}{\norm{v}^2},
  \end{align*}
  where we used the sesquilinearity of the inner product to
  reach the second line and the conjugate symmetry to reach
  the third.  Rearranging this yields
  \begin{equation*}
    \abs{\ip{v,w}}^2\leq\norm{v}^2\norm{w}^2
  \end{equation*}
  and taking a square root gives us the Cauchy--Schwarz
  inequality.

  Finally, we have equality if and only if $\norm{u}=0$ or,
  equivalently, $u=0$, that is, $w=\lambda v$.
\end{proof}


\begin{xmpls}
\item[]
  \begin{compactenum}
  \item Let $(\Omega,P)$ be a finite probability space.
    Then the space $\R^{\Omega}$ of real random variables is
    an inner product space with
    \begin{equation*}
      \ip{f,g}=\E(fg)=\sum_{x\in\Omega}f(x)g(x)P(x),
    \end{equation*}
    so long as $P(x)>0$ for each $x\in\Omega$ (we need this
    for positive-definiteness).  Now the (square of) the
    Cauchy--Schwarz inequality reads
    \begin{equation*}
      \E(fg)^2\leq\E(f^2)\E(g^2).
    \end{equation*}
  \item For $a,b\in\ell_2$, the Cauchy--Schwarz inequality
    reads:
    \begin{equation*}
      \biggl\lvert\sum_{n\in\N}a_nb_n\biggr\rvert\leq
      \biggl(\sum_{n\in\N}a_n^2\biggr)^{1/2}
      \biggl(\sum_{n\in\N}b_n^2\biggr)^{1/2}.
    \end{equation*}
  \end{compactenum}
\end{xmpls}

The Cauchy--Schwarz inequality is an essentially
$2$-dimensional result about the inner product space
$\Span{v,w}$.  Here are some more that are almost as
fundamental:
\begin{prop}
  \label{th:20}% triangle and others
  Let $V$ be an inner product space and $v,w\in V$.
  \begin{compactenum}
  \item \textbf{Pythagoras Theorem}: If $v\perp w$ then
    \begin{equation}\label{eq:22}
      %Pythag
      \norm{v+w}^2=\norm{v}^2+\norm{w}^2.
    \end{equation}
  \item \textbf{Triangle inequality}:
    $\norm{v+w}\leq\norm{v}+\norm{w}$ with equality if and
    only if $v=0$ or $w=\lambda v$ with $\lambda\geq 0$.
  \item \textbf{Parallelogram identity}:
    $\norm{v+w}^2+\norm{v-w}^2=2(\norm{v}^2+\norm{w}^2)$. 
  \end{compactenum}
\end{prop}
\begin{figure}[ht]
  \centering
  \ThisAltText{Pythagoras' Theorem.}
  \subfloat[Pythagoras' Theorem]{
  \begin{tikzpicture}[x=.7cm,y=.7cm]
    \draw[->] (0,0)--(4,0) node[right]{$v$};
    \draw[->] (0,0)--(0,3) node[left]{$w$};
    \draw[->] (0,0)--(4,3) node[right]{$v+w$};
    \draw (3.75,0)--(3.75,.25)--(4,.25);
    \draw[dashed](4,0)--(4,3);
    \draw[fill,red] (0,0) circle[radius=1pt] node[below,black]{$0$};
  \end{tikzpicture}}
\hspace{2cm}
\ThisAltText{Parallelogram identity.}
  \subfloat[Parallelogram identity]{
    \begin{tikzpicture}[x=.7cm,y=.7cm]
      \draw[->] (0,0)--(4,0) node[right]{$v$};
      \draw[->] (0,0)--(1,3) node[left]{$w$};
      \draw[->] (0,0)--(5,3) node[right]{$v+w$};
      \draw[dashed](1,3)--(5,3);
      \draw[dashed] (4,0)--(5,3);
      \draw[dotted] (4,0)--(1,3);
      \node at (3,1){$v-w$};
      \draw[fill,red] (0,0) circle[radius=1pt] node[below,black]{$0$};
    \end{tikzpicture}
  }
  \caption{The identities of \cref{th:20}}
  \label{fig:pythag}
\end{figure}
\begin{proof}\item[]
  \begin{compactenum}
  \item Exercise\footnote{Question 2(a) on sheet 4.}: expand out $\norm{v+w}^2=\ip{v+w,v+w}$.
  \item We prove $\norm{v+w}^2\leq(\norm{v}+\norm{w})^2$.
    We have
    \begin{equation*}
      \norm{v+w}^2=\norm{v}^2+2\mathrm{Re}\ip{v,w}+\norm{w}^2.
    \end{equation*}
    Now,
    \begin{equation*}
      \mathrm{Re}\ip{v,w}\leq\abs{\ip{v,w}}\leq\norm{v}\norm{w}
    \end{equation*}
    by Cauchy--Schwarz so that
    \begin{equation*}
      \norm{v+w}^2\leq\norm{v}^2+2\norm{v}\norm{w}+\norm{w}^2=(\norm{v}+\norm{w})^2
    \end{equation*}
    with equality if and only if
    $\mathrm{Re}\ip{v,w}=\abs{\ip{v,w}}=\norm{v}\norm{w}$ in
    which case we first get $w=\lambda v$, for some
    $\lambda\in\F$, and then that
    $\mathrm{Re}\lambda=\abs{\lambda}$ so that $\lambda\geq
    0$.
  \item Exercise\footnote{Question 2(c) on sheet 4.}!
  \end{compactenum}
\end{proof}


\section{Orthogonality}
\label{sec:orthogonality}

\subsection{Orthonormal bases}
\label{sec:orthornormal-bases}

\begin{defn}
  A list of vectors $\lst{u}1k$ in an inner product space
  $V$ is \emph{orthonormal} if, for all $\bw1{i,j}k$,
  \begin{equation*}
    \ip{u_i,u_j}=\delta_{ij}:=
    \begin{cases}
      1&\text{if $i=j$;}\\0&\text{if $i\neq j$.}
    \end{cases}
  \end{equation*}
  If $\lst{u}1k$ is also a basis, we call it an
  \emph{orthonormal basis}.
\end{defn}

\begin{xmpl}
  The standard basis $\lst{e}1n$ of $\F^n$ is orthonormal
  for the dot product.
\end{xmpl}

Orthonormal bases are very cool.  Here is why: if
$\lst{u}1k$ is orthonormal and $v\in\Span{\lst{u}1k}$ then
we can write
\begin{equation*}
  v=\lc\lambda{u}1k.
\end{equation*}
How can we compute the coordinates $\lambda_i$?  In general,
this amounts to solving a system of linear equations and so
involves something tedious and lengthy like Gaussian
elimination.  However, in our case, things are \emph{much}
easier.  Observe:
\begin{equation*}
  \ip{u_i,v}=\ip{u_i,\sum_j\lambda_ju_j}=\sum_j\lambda_j\ip{u_i,u_j}
  =\sum_j\lambda_j\delta_{ij}=\lambda_i.
\end{equation*}
Thus
\begin{equation}
  \label{eq:11}
  \lambda_i=\ip{u_i,v}
\end{equation}
which is very easy to compute.

Let us enshrine this analysis into the following lemma:
\begin{lem}
  \label{th:35}
  % expand in on basis
  Let $V$ be an inner product space with orthonormal basis
  $\lst{u}1n$ and let $v\in V$.  Then
  \begin{equation*}
    v=\sum_{i=1}^n\ip{u_i,v}u_i.
  \end{equation*}
\end{lem}

As an immediate consequence of \eqref{eq:11}:
\begin{lem}
  \label{th:21}
  Any orthonormal list of vectors $\lst{u}1k$ is linearly independent.
\end{lem}
\begin{proof}
  If $\lc{\lambda}u1k=0$ then \eqref{eq:11} gives
  $\lambda_i=\ip{u_i,0}=0$.
\end{proof}
What is more, these coordinates $\lambda_i$ are all you need
to compute inner products.
\begin{prop}
  \label{th:22}
  % ip=dot for ortho basis
  Let $\lst{u}1n$ be an orthonormal basis of an inner
  product space $V$.

  Let $v=\lc{x}{u}1n$ and $w=\lc{y}u1n$.  Then
  \begin{equation*}
    \ip{v,w}=\sum_{i=1}^n\bar{x}_iy_i=x\cdot y.
  \end{equation*}
  Thus the inner product of two vectors is the dot product
  of their coordinates with respect to an orthonormal basis.
\end{prop}
\begin{proof}
  We simply expand out $\ip{v,w}$ by sesquilinearity:
  \begin{equation*}
    \ip{v,w}=\ip{\sum_ix_iu_i,\sum_jy_ju_j}=\sum_{i,j}\bar{x}_iy_j\ip{u_i,u_j}
    =\sum_{i,j}\bar{x}_iy_j\delta_{ij}=\sum_i\bar{x}_iy_i=x\cdot y.
  \end{equation*}
\end{proof}

To put it another way:
\begin{prop}
  \label{th:23}
  % Parseval and Bessel
  Let $\lst{u}1n$ be an orthonormal basis of an inner
  product space $V$ and $v,w\in V$.  Then:
  \begin{compactenum}[(1)]
  \item \textbf{Parseval's identity}:
    $\ip{v,w}=\sum_{i=1}^n\ip{v,u_i}\ip{u_i,w}$.
  \item \textbf{Bessel's equality}:
    $\norm{v}^2=\sum_{i=1}^n\abs{\ip{v,u_i}}^2$. 
  \end{compactenum}
\end{prop}
\begin{proof}\item[]
  \begin{compactenum}[(1)]
  \item This comes straight from \cref{th:22},
    using conjugate symmetry of the inner product to get
    $\bar{x}_i=\overline{\ip{u_i,v}}=\ip{v,u_i}$.
  \item Put $v=w$ in (1).
  \end{compactenum}
\end{proof}

All of this should make us eager to get our hands on
orthonormal bases and so we would like to know if they
always exist.  To see that they do, we need the following
construction:
\begin{thm}[Gram--Schmidt orthogonalisation]
  \label{th:24}
  % Gram-Schmidt
  Let $\lst{v}1m$ be linearly independent vectors in an
  inner product space $V$.

  Then there is an orthonormal list $\lst{u}1m$ such that
  \begin{equation*}
    \Span{\lst{u}1k}=\Span{\lst{v}1k},
  \end{equation*}
  for all $\bw1{k}m$, defined inductively by:
  \begin{warpprint}
    \begin{align*}
      u_k&:=w_k/\norm{w_k}\\
      \intertext{where,}
      w_1&:=v_1\\
      \intertext{and, for $k>1$,}
      w_k&:=v_k-\sum_{j=1}^{k-1}\ip{u_j,v_k}u_j
           =v_k-\sum_{j=1}^{k-1}\frac{\ip{w_j,v_k}}{\norm{w_j}^2}w_j.
    \end{align*}
\end{warpprint}
  \begin{warpHTML}
    \begin{equation*}
      u_k:=w_k/\norm{w_k}
    \end{equation*}
    where
    \begin{equation*}
      w_1:=v_1
    \end{equation*}
    and, for $k>1$,
    \begin{equation*}
      w_k:=v_k-\sum_{j=1}^{k-1}\ip{u_j,v_k}u_j
      =v_k-\sum_{j=1}^{k-1}\frac{\ip{w_j,v_k}}{\norm{w_j}^2}w_j.
    \end{equation*}
\end{warpHTML}
\end{thm}
\begin{proof}
  We induct with inductive hypothesis at $k$ that
  $\lst{u}1k$ is orthonormal and that, for
  $\bw1\ell{k}$,
  $\Span{\lst{u}1\ell}=\Span{\lst{v}1\ell}$.

  At $k=1$, this reads $\norm{u_1}=1$ and
  $\Span{u_1}=\Span{v_1}$ which is certainly true.

  Now assume the hypothesis is true at $k-1$ so that
  $\lst{u}1{k-1}$ is orthonormal and
  $\Span{\lst{u}1{k-1}}=\Span{\lst{v}1{k-1}}$. Then
  \begin{equation*}
    \Span{\lst{u}1k}=\Span{\lst{v}1{k-1},u_k}=
    \Span{\lst{v}1{k-1},w_k}=\Span{\lst{v}1k},
  \end{equation*}
  where the first equality comes from the induction
  hypothesis and the last from the definition of $w_k$.
  Moreover, for any $i<k$,
  \begin{equation*}
    \ip{u_i,w_k}=\ip{u_i,v_k}-\sum_{j<k}\ip{u_j,v_k}\ip{u_i,u_j}=
    \ip{u_i,v_k}-\sum_{j<k}\ip{u_j,v_k}\delta_{ij}=\ip{u_i,v_k}-\ip{u_i,v_k}=0
  \end{equation*}
  Thus $w_k\perp\lst{u}1{k-1}$ so that $u_k$ is also whence
  $\lst{u}1k$ is orthonormal.  Thus the inductive hypothesis
  is true at $k$ and so at $m$ by induction.
\end{proof}

\begin{cor}
  \label{th:25}
  Any finite-dimensional inner product space $V$ has an
  orthonormal basis.
\end{cor}
\begin{proof}
  Let $\lst{v}1n$ be any basis of $V$ and apply
  \cref{th:24} to get an orthonormal (and so
  linearly independent by \cref{th:21}) list
  $\lst{u}1n$ with
  \begin{equation*}
    \Span{\lst{u}1n}=\Span{\lst{v}1n}=V.
  \end{equation*}
  Thus the $\lst{u}1n$ span also and so are an orthonormal
  basis.
\end{proof}

\begin{rem}
  For practical purposes such as computations, it is easiest
  to phrase the Gram--Schmidt algorithm in terms of the
  $w_k$: we set
  \begin{align*}
    w_1&:=v_1\\
    w_k&:=v_k-\sum_{j=1}^{k-1}\frac{\ip{w_j,v_k}}{\norm{w_j}^{2}} w_j
  \end{align*}
  (which can be computed without introducing square roots)
  and then finally set $u_k=w_k/\norm{w_k}$.
\end{rem}

\begin{xmpl}
  Let $U\leq\R^3$ be given by $\set{x\in\R^3\st
    x_1+x_2+x_3=0}$.
  Let us find an orthonormal basis for $U$.

  First we need a basis of $U$ to start with: $\dim U=2$
  (why?) with basis $v_1=(1,0,-1)$, $v_2=(0,1,-1)$ (of
  course, there are many other bases).

  First, $\norm{w_1}^2=\norm{v_1}^2=2$ while
  $\ip{w_1,v_2}=\ip{v_1,v_2}=1$ so that
  \begin{align*}
    w_2&=v_2-\frac{\ip{w_1,v_2}}{\ip{w_1,w_1}}w_1 \\
     &=(0,1,-1)-\half(1,0,-1)=(-\half,1,-\half).
  \end{align*}
  This means that $\norm{w_2}^2={1/4+1+1/4}=3/2$
  so that
  \begin{align*}
    u_1&=w_1/\sqrt{2}=(\tfrac1{\sqrt{2}},0,-\tfrac1{\sqrt{2}})\\
    u_2&=\sqrt{\tfrac23}w_2=\sqrt{\tfrac23}(-\half,1,-\half)=
    (-\tfrac1{\sqrt{6}},\sqrt{\tfrac23},\tfrac{-1}{\sqrt{6}}).
  \end{align*}
\end{xmpl}

Let us conclude our discussion of orthonormal bases with an
application of Gram--Schmidt which has uses in Statistics
(see MA20227) and elsewhere.  First, a definition:
\begin{defn}
  A matrix $Q\in M_{n\times n}(\R)$ is \emph{orthogonal} if
  \begin{equation*}
    Q^TQ=\I_n,
  \end{equation*}
  or, equivalently, $Q$ has orthonormal columns with respect
  to the dot product.  Here $\I_n$ is the $n\times n$
  identity matrix.
\end{defn}

\begin{rem}
  The two conditions in this definition are indeed
  equivalent: if $\bq_i$ is the $i$-th column of $Q$ then
  \begin{equation*}
    (Q^TQ)_{ij}=\bq^T_i\bq_j.
  \end{equation*}
\end{rem}

\begin{thm}[QR decomposition]
  \label{th:26}
  % QR
  Let $A\in M_{n\times n}(\R)$ be an invertible matrix.
  Then we can write
  \begin{equation*}
    A=QR,
  \end{equation*}
  where $Q$ is orthogonal and $R$ is upper triangular
  ($R_{ij}=0$ if $i>j$) with positive entries on the
  diagonal.
\end{thm}

We apply \cref{th:24} to the columns of $A$ to get the
columns of $Q$.

So let $\lst{\bv}1n$ be the columns of $A$.  Since $A$ is
invertible, these are a basis so we can apply \cref{th:24}
to get an orthonormal basis $\lst{\bu}1n$.  Let $Q$ be the
orthogonal matrix whose columns are the $\bu_i$.
Unravelling the formulae of the Gram--Schmidt procedure, we
have
\begin{warpprint}
  \begin{align*}
    \bv_1&=\norm{\bv_1}\bu_1 \\
    \bv_2&=\norm{\mathbf{w}_2}\bu_2+\ip{\bu_1,\bv_2}\bu_1\\
    \intertext{and, more generally,}
    \bv_k&=\norm{\mathbf{w}_k}\bu_k+\sum_{j<k}\ip{\bu_j,\bv_k}\bu_j.
  \end{align*}
\end{warpprint}
\begin{warpHTML}
    \begin{align*}
    \bv_1&=\norm{\bv_1}\bu_1 \\
      \bv_2&=\norm{\mathbf{w}_2}\bu_2+\ip{\bu_1,\bv_2}\bu_1
    \end{align*}
    and, more generally,
    \begin{equation*}
    \bv_k=\norm{\mathbf{w}_k}\bu_k+\sum_{j<k}\ip{\bu_j,\bv_k}\bu_j.
  \end{equation*}
\end{warpHTML}
Otherwise said, $A=QR$ where $R_{kk}=\norm{\mathbf{w}_k}$,
$R_{jk}=\ip{\bu_j,\bv_k}$, for $j<k$, and $R_{ij}=0$ if
$i>j$.


To compute $Q$ and $R$ in practice, first do Gram--Schmidt
orthogonalisation on the columns of $A$ to get $Q$ and then
note that $Q^TA=Q^TQR=\I_nR=R$ so that
\begin{equation*}
  R=Q^TA
\end{equation*}
which is probably easier to compute than keeping track of intermediate
coefficients in the orthogonalisation!

\begin{rems}
\item[]
  \begin{compactenum}
  \item In pure mathematics, the QR decomposition is a
    special case of the \emph{Iwasawa decomposition}.
  \item We shall have more to say about orthogonal matrices
    in the next chapter, see
    \S\ref{sec:linear-isometries}.
  \end{compactenum}
\end{rems}

\subsection{Orthogonal complements and orthogonal
  projection}
\label{sec:orth-compl-orth}

\begin{defn}
  Let $V$ be an inner product space and $U\leq V$.  The
  \emph{orthogonal complement $U^{\perp}$ of $U$ (in $V$)}
  is given by
  \begin{equation*}
    U^{\perp}:=\set{v\in V\st\text{$\ip{u,v}=0$, for all
        $u\in U$}}.
  \end{equation*}
\end{defn}
\begin{figure}[ht]
  \centering
  \ThisAltText{Orthogonal complements in the plane.}
  \begin{tikzpicture}
    \draw[blue] (-2,-1)--(2,1) node[right,black]{$U$};
    \draw[blue] (-1,2)--(1,-2)
    node[right,black]{$U^{\perp}$};
    \draw[fill,red] circle[radius=1pt] (0,0);
    \draw (.25,.125)--(.125,.375)--(-.125,.25);
  \end{tikzpicture}
  \caption{Orthogonal complements in $\R^2$}
  \label{fig:ortho-comp}
\end{figure}

\begin{prop}
  \label{th:27}
  % orthocomplement
  Let $V$ be an inner product space and $U\leq V$.  Then
  \begin{compactenum}[(1)]
  \item $U^{\perp}\leq V$;
  \item $U\cap U^{\perp}=\set0$;
  \item $U\leq(U^{\perp})^{\perp}$.
  \end{compactenum}
\end{prop}
\begin{proof}
  \begin{compactenum}[(1)]
  \item This is a straightforward exercise using the
    second slot linearity of the inner product.
  \item If $u\in U\cap U^{\perp}$, $\ip{u,u}=0$ so that
    $u=0$ by positive-definiteness of the inner product.
  \item If $u\in U$ and $w\in U^{\perp}$ then
    \begin{equation*}
      \ip{w,u}=\overline{\ip{u,w}}=0
    \end{equation*}
    so that $u\in(U^{\perp})^{\perp}$.
  \end{compactenum}
\end{proof}

If $U$ is finite-dimensional then $U^{\perp}$ is a
complement to $U$ in the sense of
\S\ref{sec:internal-direct-sum} (even if $V$ is
infinite-dimensional!):
\begin{thm}
  \label{th:28}
  % Ortho comp is comp for finite-dimensional U
  Let $U$ be a finite-dimensional subspace of an inner
  product space $V$.  Then $V$ is an internal direct sum:
  \begin{equation*}
    V=U\oplus U^{\perp}.
  \end{equation*}
\end{thm}
\begin{proof}\item[]
  By \cref{th:5} and \cref{th:27}(2), we just need to prove
  that $V=U+U^{\perp}$.  For this, let $\lst{u}1k$ be an
  orthonormal basis of $U$ and let $v\in V$.  We write
  \begin{equation*}
    v=\bigl(\sum_{i=1}^k\ip{u_i,v}u_i\bigr)+\bigl(v-\sum_{i=1}^k\ip{u_i,v}u_i\bigr)
    =:v_1+v_2.
  \end{equation*}
  Now $v_1\in U$ being in the span of the $u_i$ while, for $\bw1jk$,
  \begin{align*}
    \ip{u_j,v_2} & =\ip{u_j,v}-\sum_{i=1}^k\ip{u_i,v}\ip{u_j,u_i} \\
                 & =\ip{u_j,v}-\ip{u_j,v}=0.
  \end{align*}
  Thus, for $u=\lc{\lambda}u1k\in U$,
  \begin{equation*}
    \ip{u,v_2}=\sum_{j=1}^k\bar{\lambda}_j\ip{u_j,v_2}=0
  \end{equation*}
  so that $v_2\in U^{\perp}$.
\end{proof}
\begin{cor}
  \label{th:29}
  % dim of U-perp etc
  Let $V$ be a finite-dimensional inner product space and
  $U\leq V$.  Then
  \begin{compactenum}[(1)]
  \item $\dim U^{\perp}=\dim V-\dim U$.
  \item $U=(U^{\perp})^{\perp}$.
  \end{compactenum}
\end{cor}
\begin{proof}
\item[]
  \begin{compactenum}[(1)]
  \item This is immediate from \cref{th:7}.
  \item We give two proofs of this.
    \begin{compactitem}
    \item Two applications of (1) give
      \begin{equation*}
        \dim(U^{\perp})^{\perp}=\dim V-\dim U^{\perp}=\dim U
      \end{equation*}
      while \cref{th:27}(3) gives
      $U\leq(U^{\perp})^{\perp}$.  We conclude that we have
      equality by \cref{th:32}.
    \item Alternatively, let $v\in(U^{\perp})^{\perp}$ and
      write $v=v_1+v_2$ with $v_1\in U$ and $v_2\in
      U^{\perp}$.  Then
      \begin{equation*}
        0=\ip{v_2,v}=\ip{v_2,v_1}+\ip{v_2,v_2}=\norm{v_2}^2
      \end{equation*}
      so that $v_2=0$ giving $v=v_1\in U$.  Thus
      $(U^{\perp})^{\perp}\leq U$ which, with
      \cref{th:27}(3) yields $U=(U^{\perp})^{\perp}$.  This
      argument works when $V$, and even $U$, are
      infinite-dimensional so long as $V=U\oplus U^{\perp}$.
    \end{compactitem}
  \end{compactenum}
\end{proof}
\begin{rem}
  Both \cref{th:28} and \cref{th:29}(2) can fail when $U$ is
  infinite-dimensional.
\end{rem}

When $V=U\oplus U^{\perp}$, we can apply the results of
\S\ref{sec:direct-sums-proj} to get projections onto $U$
and $U^{\perp}$.
\begin{defn}
  Let $V$ be an inner product space and $U\leq V$ such that
  $V=U\oplus U^{\perp}$.  The projection $\pi_U:V\to V$ with
  image $U$ and kernel $U^{\perp}$ is called the
  \emph{orthogonal projection onto $U$}.
\end{defn}
\begin{rem}
  $\pi_{U^{\perp}}=\id_V-\pi_U$.  The situation is
  illustrated in Figure~\ref{fig:orthoproj}.
\end{rem}
\begin{figure}[ht]
  \centering
  \ThisAltText{Two orthogonal projections.}
  \begin{tikzpicture}
    \draw[blue] (-1,-.5)--(3,1.5) node[right,black]{$U$};
    \draw[blue] (-1.5,3)--(.5,-1)
    node[right,black]{$U^{\perp}$};
    \draw[fill,red] circle[radius=1pt] (0,0);
    \draw (.25,.125)--(.125,.375)--(-.125,.25);
    \draw[dashed] (1,.5)--(0,2.5)--(-1,2);
    \draw[fill,red] (1,.5) circle(1pt)  node[below,black]{$\pi_U(v)$};
    \draw[fill,red] (0,2.5) circle(1pt)  node[right,black]{$v$};
    \draw[fill,red] (-1,2) circle(1pt) (-1,2) node[left,black]{$\pi_{U^{\perp}}(v)$};
  \end{tikzpicture}
  \caption{Orthogonal projections}
  \label{fig:orthoproj}
\end{figure}

\begin{lem}
  \label{th:30}
  % Properties of orthoproj
  Let $V$ be an inner product space and $U\leq V$ a
  finite-dimensional subspace with orthonormal basis
  $\lst{u}1k$ then, for all $v\in V$,
  \begin{equation*}
    \pi_U(v)=\sum_{i=1}^k\ip{u_i,v}u_i.
  \end{equation*}
\end{lem}
\begin{proof}
  This is the proof of \cref{th:28}.
\end{proof}

Let us conclude this chapter with an application to a
minimisation problem that, among other things, underlies
much of Fourier analysis (see MA20223).
\begin{thm}
  \label{th:31}
  % Minimisation
  Let $V$ be an inner product space and $U\leq V$ such that
  $V=U\oplus U^{\perp}$.

  For $v\in V$, $\pi_U(v)$ is the nearest point of $U$ to
  $v$: for all $u\in U$,
  \begin{equation*}
    \norm{v-\pi_U(v)}\leq\norm{v-u}.
  \end{equation*}
\end{thm}
\begin{figure}[ht]
  \centering
  \ThisAltText{Orthogonal projection minimises distance.}
  \begin{tikzpicture}
    \draw[blue] (-1,-.5)--(3,1.5) node[right,black]{$U$};
    \draw (-1,2) node[left]{$v$}--(0,0);
    \draw[fill,red] (-1,2) circle(1pt); 
    \draw[fill,red] circle[radius=1pt] (0,0) node[below,black]{$\pi_U(v)$};
    \draw (.25,.125)--(.125,.375)--(-.125,.25);
    \draw[dashed](-1,2)--(2.5,1.25);
    \draw[fill,red] (2.5,1.25) circle(1pt) node[black,below right]{$u$};
  \end{tikzpicture}
  \caption{The orthogonal projection minimises distance to
    $U$}
  \label{fig:minimise}
\end{figure}
\begin{proof}
  As we see in Figure~\ref{fig:minimise}, this is just the Pythagoras
  theorem (\cref{th:20}).  Indeed, for $u\in U$, note that $\pi_U(v)-u\in
  U$ while $v-\pi_U(v)=\pi_{U^{\perp}}(v)\in U^{\perp}$.
  Thus,
  \begin{align*}
    \norm{v-u}^2&=\norm{v-\pi_U(v)+\pi_U(v)-u}^2=
                  \norm{v-\pi_U(v)}^2+\norm{\pi_U(v)-u}^2\\
    &\geq\norm{v-\pi_U(v)}^2.
  \end{align*}
  Now take square roots!
\end{proof}

\begin{ex}
  Read Example 6.58 on pages 199--200 of Axler's
  \href{http://bath-ac-primo.hosted.exlibrisgroup.com/44BAT_VU1:CSCOP_44BAT_DEEP:44BAT_ALMA_DS5140605390002761}%
  {\emph{Linear Algebra Done Right}} to see a beautiful
  application of this result.  He takes $V=C^0[-\pi,\pi]$
  and $U$ to be the space of polynomials of degree at most
  $5$ to get an astonishingly accurate polynomial
  approximation to $\sin$.
\end{ex}


\chapter{Linear operators on inner product spaces}
\label{cha:line-oper-inner}

\begin{convention}
  In this chapter, we once again take the field $\F$ of scalars to be
  either $\R$ or $\C$.
\end{convention}

\section{Linear operators and their adjoints}
\label{sec:line-oper-their}

\subsection{Linear operators and matrices}
\label{sec:line-oper-matr}

\begin{defn}
  Let $V$ be a vector space over $\F$.  A \emph{linear
    operator on $V$} is a linear map $\phi:V\to V$.

  The vector space of linear operators on $V$ is denoted
  $L(V)$ (instead of $L(V,V)$).
\end{defn}

A special case of the analysis of
\S\ref{sec:linear-maps-matrices} tell us that linear
operators in the presence of a basis are closely related to
square matrices: if $V$ is a finite-dimensional vector space
over $\F$ with basis $\cB=\lst{v}1n$ and $\phi\in L(V)$ then
the matrix of $\phi$ with respect to $\cB$ is the square
matrix $A=(A_{ij})\in M_{n\times n}(\F)$ with
\begin{equation}
  \label{eq:12}
  \phi(v_j)=\sum_{i=1}^nA_{ij}v_i,
\end{equation}
for $\bw{1}jn$.

Equivalently, $\phi(\lc{x}v1n)=\lc{y}v1n$ where
\begin{equation*}
  \by=A\bx.
\end{equation*}
  



\subsection{Adjoints}
\label{sec:adjoints}

First a preliminary lemma:
\begin{lem}[Nondegeneracy Lemma]
  \label{th:33}
  % non-deg lemma
  Let $V$ be an inner product space and $v\in V$.  Then
  $\ip{v,w}=0$, for all $w\in V$, if and only if $v=0$.
\end{lem}
\begin{proof}
  For the forward implication, take $v=w$ to get
  $\ip{v,v}=0$ and so $v=0$ by positive-definiteness of
  inner product.

  Conversely, if $v=0$, $\ip{v,w}=0$, for any $w\in V$,
  since the inner product is anti-linear in the first
  slot\footnote{To spell it out:
    $\ip{0,w}=\ip{0+0,w}=\ip{0,w}+\ip{0,w}$}.
\end{proof}

\begin{rem}
  To put this another way: $V^{\perp}=\set{0}$.
\end{rem}

\begin{defn}
      Let $V$ be an inner product space and $\phi\in L(V)$.
    An \emph{adjoint to $\phi$} is a linear operator
    $\phi^{*}\in L(V)$ such that, for all $v,w \in V$, we
    have
\begin{warpprint}
      \begin{align*}
      \ip{\phi^{*}(v),w}&=\ip{v,\phi(w)}\\
      \intertext{or, equivalently, by conjugate symmetry,}
      \ip{w,\phi^{*}(v)}&=\ip{\phi(w),v}.
    \end{align*}
\end{warpprint}
\begin{warpHTML}
        \begin{equation*}
      \ip{\phi^{*}(v),w}=\ip{v,\phi(w)}
    \end{equation*}
    or, equivalently, by conjugate symmetry,
    \begin{equation*}
      \ip{w,\phi^{*}(v)}=\ip{\phi(w),v}.
    \end{equation*}
\end{warpHTML}
\end{defn}

Adjoints are well-behaved under most linear map
constructions:
\begin{prop}
  \label{th:36}
  % properties of adjoints
  Let $V$ be an inner product space and suppose
  $\phi,\psi\in L(V)$ have adjoints.  Then $\phi\circ\psi$;
  $\phi+\lambda\psi$, $\lambda\in\F$; $\phi^{*}$ and $\id_V$
  all have adjoints given by:
  \begin{compactenum}[(1)]
  \item $(\phi\circ\psi)^{*}=\psi^{*}\circ\phi^{*}$ (note the
    change of order here!).
  \item
    $(\phi+\lambda\psi)^{*}=\phi^{*}+\bar{\lambda}\psi^{*}$.
  \item $(\phi^{*})^{*}=\phi$.
  \item $\id_V^{*}=\id_V$.
  \end{compactenum}
\end{prop}
\begin{proof}
  These are all easy exercises\footnote{Question 1 on sheet 6.}.
\end{proof}

When $V$ is finite-dimensional, any $\phi\in L(V)$ has a
unique adjoint:
\begin{prop}
  \label{th:34}
  % adjoints exist
  Let $V$ be a \emph{finite-dimensional} inner product space
  and $\phi\in L(V)$ a linear operator.  Then
  \begin{compactenum}[(1)]
  \item $\phi$ has a unique adjoint $\phi^{*}$.
  \item Let $\lst{u}1n$ be an orthonormal basis of $V$ with
    respect to which $\phi$ has matrix $A$.  Then $\phi^{*}$
    has matrix $A^{\dagger}:=\overline{A}^T$ (which is $A^T$
    when $\F=\R$).
  \end{compactenum}
\end{prop}
\begin{proof}
For (1), let $\lst{u}1n$ be an orthonormal basis of $V$.
\Cref{th:35} tells us that any $u\in V$ can be
written
\begin{equation*}
  u=\sum_{i=1}^n\ip{u_i,u}u_i.
\end{equation*}
In particular, if $\phi^{*}$ existed, we would have
\begin{equation*}
  \phi^{*}(v)=\sum_{i=1}^n\ip{u_i,\phi^{*}(v)}u_i
  =\sum_{i=1}^n\ip{\phi(u_i),v}u_i.
\end{equation*}
Inspired by this, we \emph{define} $\phi^{*}:V\to V$ by
\begin{equation}
  \label{eq:13}
  \phi^{*}(v)=\sum_{i=1}^n\ip{\phi(u_i),v}u_i.
\end{equation}
We note that $\phi^{*}$ so defined is linear since the inner
product is linear in the second slot.  Moreover, for $w\in
V$, we have
\begin{equation*}
  w=\sum_{i=1}^n\ip{u_i,w}u_i
\end{equation*}
whence
\begin{equation*}
  \phi(w)=\sum_{i=1}^n\ip{u_i,w}\phi(u_i).
\end{equation*}
Thus,
\begin{align*}
  \ip{\phi^{*}(v),w}&=\sum_{i=1}^n\overline{\ip{\phi(u_i),v}}\ip{u_i,w}=
                     \sum_{i=1}^n
                      \ip{v,\phi(u_i)}\ip{u_i,w}\\
  &=\ip{v,\sum_{i=1}^n\ip{u_i,w}\phi(u_i)}=\ip{v,\phi(w)}.
\end{align*}
This establishes the existence of $\phi^{*}$.

For uniqueness, either observe that \eqref{eq:13} uniquely
determines $\phi^{*}$, or better (because the argument
works for infinite-dimensional $V$), suppose that $\phi$ has
adjoints $\phi_1^{*}$ and $\phi_2^{*}$.  Then we have
\begin{equation*}
  \ip{\phi^{*}_1(v),w}=\ip{v,\phi(w)}=\ip{\phi_2^{*}(v),w}
\end{equation*}
so that $\ip{\phi_1^{*}(v)-\phi_2^{*}(v),w}=0$ and
$\phi_1^{*}(v)=\phi_2^{*}(v)$ by the Nondegeneracy
\cref{th:33}.

For (2), note that if $\psi\in L(V)$ has matrix $B$ with
respect to $\lst{u}1n$ so that
\begin{equation*}
  \psi(u_j)=\sum_{i=1}^nB_{ij}u_i,
\end{equation*}
then
\begin{equation*}
  \ip{u_k,\psi(u_j)}=\sum_{i=1}^nB_{ij}\ip{u_k,u_i}=B_{kj}.
\end{equation*}
Taking $\psi$ to be $\phi^{*}$ and then $\phi$ in this, we see
that if $C$ is the matrix of $\phi^{*}$ then
\begin{equation*}
  C_{kj}=\ip{u_k,\phi^{*}(u_j)}=\ip{\phi(u_k),u_j}
  =\overline{\ip{u_j,\phi(u_k)}}=\overline{A_{jk}}. 
\end{equation*}
Thus $C=A^{\dagger}$.
\end{proof}
\begin{rems}\item[]
  \begin{compactenum}
  \item \cref{th:34} along with
    \cref{th:36}(2) tells us that when $V$ is
    finite-dimensional, $\phi\mapsto\phi^{*}:L(V)\to L(V)$
    is an anti-linear map (and so a linear map when
    $\F=\R$).
  \item The uniqueness part of \cref{th:34} holds
    even for infinite-dimensional $V$: if $\phi\in L(V)$ has
    an adjoint at all, it has only one.
  \end{compactenum}
\end{rems}

\begin{xmpl}
  Let $A\in M_{n\times n}(\R)$.  Let us show that
  $(\phi_{A})^{*}=\phi_{A^T}$.  Indeed:
  \begin{equation*}
    \phi_{A^T}(y)\cdot x=(A^T\by)^T\bx=\by^TA\bx=y\cdot \phi_A(x)
  \end{equation*}
  where we have used the familiar identities
  $(AB)^T=B^TA^T$, for $B\in M_{n\times m}$, and
  $(A^T)^T=A$.

  Similarly, when $\F=\C$, $(\phi_A)^{*}=\phi_{A^{\dagger}}$.
\end{xmpl}

\begin{defns}
\item[]
  \begin{compactenum}
  \item  Let $V$ be an inner product space and $\phi\in L(V)$.

  Say that $\phi$ is \emph{self-adjoint} if $\phi^{*}=\phi$,
  or, equivalently, for all $v,w\in V$,
  \begin{equation*}
    \ip{\phi(v),w}=\ip{v,\phi(w)}.
  \end{equation*}
  Say $\phi$ is \emph{skew-adjoint} if $\phi^{*}=-\phi$ or,
  equivalently, for all $v,w\in V$,
  \begin{equation*}
    \ip{\phi(v),w}=-\ip{v,\phi(w)}.
  \end{equation*}
\item Let $A\in M_{n\times n}(\F)$.
  \begin{compactenum}[(a)]
  \item If $\F=\C$, say that $A$ is \emph{Hermitian} if
    $A^{\dagger}=A$ and \emph{skew-Hermitian} if $A^{\dagger}=-A$.
  \item If $\F=\R$, say that $A$ is \emph{symmetric} if
    $A^T=A$ and \emph{skew-symmetric} if $A^T=-A$.
  \end{compactenum}
  \end{compactenum}
\end{defns}

\begin{rem}
  If $\phi$ has matrix $A$ with respect to an orthonormal
  basis of $V$ then \cref{th:34}(2) tells us that
  $\phi$ is self-adjoint if and only if $A$ is Hermitian or
  symmetric (according to whether $\F$ is $\C$ or $\R$).
  Similarly, $\phi$ is skew-adjoint if and only if $A$ is
  skew-Hermitian or skew-symmetric.
\end{rem}

\begin{xmpls}
Using \cref{th:36}, we get
  \begin{compactenum}[(i)]
  \item $\id_V^{*}=\id_V$ so $\id_V$ is self-adjoint.
  \item $\phi^{*}\circ\phi$ is self-adjoint:
    $(\phi^{*}\circ\phi)^{*}=\phi^{*}\circ(\phi^{*})^{*}=\phi^{*}\circ\phi$.
    Replacing $\phi$ by $\phi^{*}$ shows that
    $\phi\circ\phi^{*}$ is self-adjoint also.
  \item Exercise\footnote{Question 3 on sheet 6.}: when
    $\F=\C$, $\phi$ is self-adjoint if and only if $i\phi$
    is skew-adjoint (here $i=\sqrt{-1}$!).
  \end{compactenum}
\end{xmpls}

\subsection{Linear isometries}
\label{sec:linear-isometries}

\begin{defn}
  Let $V,W$ be inner product spaces with inner products
  $\ip{\, ,\,}_V$ and $\ip{\, ,\,}_W$ respectively.  A linear
  map $\phi:V\to W$ is a \emph{linear isometry} if, for all
  $v_1,v_2\in V$,
  \begin{equation*}
    \ip{\phi(v_1),\phi(v_2)}_W=\ip{v_1,v_2}_V.
  \end{equation*}
\end{defn}

In this case we have that:
\begin{compactitem}
\item $\phi$ is \emph{norm-preserving}:
  $\norm{\phi(v)}_W=\norm{v}_V$, for all $v\in V$.
\item $\phi$ is \emph{distance-preserving}:
  $\norm{\phi(v_1)-\phi(v_2)}_W=\norm{v_1-v_2}_V$, for all
  $v_1,v_2\in V$, (since both sides equal
  $\norm{\phi(v_1-v_2)}_W$).
\end{compactitem}

\begin{xmpl}
  Let $\cB=\lst{u}1n$ be an orthonormal basis of an inner
  product space $V$.  Then $\phi_{\cB}:\F^n\to V$ is a linear
  isometry when $\ip{\, ,\,}_{\F^n}$ is dot product.  This is
  the content of \cref{th:22}.
\end{xmpl}

Let us now focus on the case where $V=W$ and is
finite-dimensional.
\begin{prop}
  \label{th:37}
  % isom if and only if unitary
  Let $V$ be a finite-dimensional inner product space and
  $\phi\in L(V)$.  Then $\phi$ is a linear isometry if and
  only if $\phi$ is an isomorphism with $\phi^{-1}=\phi^{*}$
  (equivalently, $\phi^{*}\circ\phi=\id_V=\phi\circ\phi^{*}$).
\end{prop}
\begin{proof}
  We prove the reverse implication first: if
  $\phi^{-1}=\phi^{*}$, then $\phi^{*}\circ\phi=\id_V$ so
  that, for all $v,w\in V$,
  \begin{equation*}
    \ip{v,w}=\ip{v,\phi^{*}(\phi(w))}=\ip{\phi(v),\phi(w)}.
  \end{equation*}
  Thus $\phi$ is a linear isometry.

  Conversely, if $\phi$ is a linear isometry then, for all
  $v,w\in V$,
  \begin{equation*}
    \ip{v,w}=\ip{\phi(v),\phi(w)}=\ip{\phi^{*}\circ\phi(v),w}
  \end{equation*}
  so that $\ip{v-\phi^{*}\circ\phi(v),w}=0$, for all $w\in
  V$.  Thus by the nondegeneracy \cref{th:33}, we get
  $v=\phi^{*}\circ\phi=\id_V$, that is:
  \begin{equation}
    \label{eq:14}
    \phi^{*}\circ\phi=\id_V.
  \end{equation}
  Since $\id_V$ injects, $\phi$ injects also and so, by
  \cref{th:4}, is an isomorphism\footnote{This is
    the part where we use that $V$ is
    finite-dimensional.}. Now apply $\phi^{-1}$ on the right
  of both sides of \eqref{eq:14} to yield $\phi^{*}=\phi^{-1}$.
\end{proof}

\begin{rem}
  If $V$ is infinite-dimensional, linear isometries $V\to V$
  need not surject.  For example: $Z:\ell_2\to\ell_{2}$
  given by $(a_0,a_1,\dots)\mapsto (0,a_0,a_1,\dots)$ is a
  non-surjective isometry (exercise\footnote{Question 7 on
    sheet 6.}!).
\end{rem}

\Cref{th:37} prompts some terminology:
\begin{defns}
  Let $V$ be an inner product space over $\F$ and $\phi\in
  L(V)$.  If $\phi$ is an isomorphism with
  $\phi^{-1}=\phi^{*}$, then say $\phi$ is:
  \begin{compactitem}
  \item an \emph{orthogonal transformation} if $\F=\R$;
  \item a \emph{unitary transformation} if $\F=\C$.
  \end{compactitem}
  The set of all orthogonal, resp.\ unitary transformations
  is denoted $\rO(V)$, resp.\ $\rU(V)$.

  Let $A\in M_{n\times n}(\F)$.
  \begin{compactitem}
  \item $A$ is \emph{orthogonal} if $\F=\R$ and $A^TA=\I$;
  \item $A$ is \emph{unitary} if $\F=\C$ and $A^{\dagger}A=\I$.
  \end{compactitem}
  The set of all $n\times n$ orthogonal, resp.\ unitary
  matrices is denoted $\rO(n)$, resp.\ $\rU(n)$.
\end{defns}

\begin{rems}
\item[]
  \begin{compactenum}
  \item The argument of \cref{th:37} shows that
    $A$ is orthogonal if and only if $A$ is invertible with
    $A^{-1}=A^T$.  Similarly $A$ is unitary if and only if
    $A$ is invertible with $A^{-1}=A^{\dagger}$.
  \item If $\phi$ has matrix $A$ with respect to an
    \emph{orthonormal} basis of $V$ then $\phi$ is an
    orthogonal or unitary transformation if and only if $A$
    is an orthogonal or unitary matrix.
  \end{compactenum}
\end{rems}

What sort of an object is $\rO(n)$ or $\rU(n)$?  They are
\emph{groups}!  Recall from Algebra 1A:

A \emph{group} is a set $G$ with a binary operation $G\times
G\to G$, written $(g,h)\mapsto gh$, such that:
\begin{compactitem}
\item $(gh)k=g(hk)$, for all $g,h,k\in G$;
\item there is an element $1\in G$ such that $g1=1g=g$, for
  all $g\in G$.  $1$ is the \emph{neutral} or \emph{identity
  element} of $G$.
\item Each $g\in G$ has an \emph{inverse} $g^{-1}$ such that
  $g^{-1}g=1=gg^{-1}$.
\end{compactitem}

A \emph{subgroup} $H$ of a group $G$ is a non-empty subset
$H\subset G$ which is closed under multiplication and
inverses: whenever $h,k\in H$ then $hk\in H$ and $h^{-1}\in
H$.  We know that a subgroup is a group in its own right
using the multiplication of $G$.

With our minds refreshed on these matters, we turn to some
groups of matrices.
\begin{defns}
  Let $V$ be a vector space.  The \emph{general linear group
    of $V$}, denoted $\GL(V)$, is:
  \begin{equation*}
    \GL(V):=\set{\phi\in L(V)\st\text{$\phi$ is an isomorphism}}.
  \end{equation*}

  Similarly, the \emph{general linear group of $n\times n$
    matrices over $\F$}, denoted $\GL(n,\F)$, is:
  \begin{equation*}
    \GL(n,\F):=\set{A\in M_{n\times n}(\F)\st\text{$A$ is invertible}}.
  \end{equation*}
\end{defns}

\begin{prop}\item[]
  \label{th:38}
  % matrix groups
  \begin{compactenum}[(1)]
  \item Let $V$ be a vector space.  Then $\GL(V)$ is a group
    under composition: $\psi\phi:=\psi\circ\phi$.
  \item If $V$ is an inner product space, then $\rO(V)$,
    resp.\ $\rU(V)$, is a subgroup of $\GL(V)$, when
    $\F=\R$, resp.\ $\C$.
  \end{compactenum}
\end{prop}
\begin{proof}
  \begin{compactenum}[(1)]
  \item We check the axioms for a group, recalling that
    $\phi\in L(V)$ is an isomorphism if and only if it has
    an inverse.
    \begin{compactitem}
    \item The multiplication is well-defined: that is, if
      $\psi,\phi\in\GL(V)$ then so is $\psi\circ\phi$ which
      has inverse $\phi^{-1}\circ\psi^{-1}$.
    \item Composition of maps is always associative.
    \item $\id_V\in\GL(V)$ since $\id_V^{-1}=\id_V$ and is
      the identity element for composition.
    \item If $\phi\in\GL(V)$, then its inverse
      $\phi^{-1}\in\GL(V)$ also since
      $(\phi^{-1})^{-1}=\phi$. 
    \end{compactitem}
  \item Denote $\rO(V)$ or $\rU(V)$, depending on $\F$, by
    $K$.  Thus
    \begin{equation*}
      K=\set{\phi\in L(V)\st \phi^{-1}=\phi^{*}}.
    \end{equation*}
    Then
    \begin{compactitem}
    \item $K$ is closed under composition: if
      $\psi^{-1}=\psi^{*}$ and $\phi^{-1}=\phi^{*}$ then, by
      \cref{th:36}(1),
      \begin{equation*}
        (\psi\circ\phi)^{-1}=\phi^{-1}\circ\psi^{-1}=\phi^{*}\circ\psi^{*}=(\psi\circ\phi)^{*}
      \end{equation*}
      so that $\psi\circ\phi\in K$.
    \item $K$ is non-empty: \cref{th:36}(4) tells
      us that $\id_V^{*}=\id_V=\id_V^{-1}$ so $\id_V\in K$.
    \item $K$ is closed under inversion: using
      \cref{th:36}(3), we have $(\phi^{-1})^{*}=(\phi^{*})^{*}=\phi=(\phi^{-1})^{-1}$.
    \end{compactitem}
  \end{compactenum}
\end{proof}
\begin{rem}
  The same argument shows that $\GL(n,\F)$ is a group under
  matrix multiplication with subgroup $\rO(n)$ or $\rU(n)$,
  depending on $\F$.
\end{rem}

As an application of these ideas, let us characterise the
distance-preserving transformations of a real inner product
space.
\begin{thm}[Classification of rigid motions]
  \label{th:39}
  Let $V$ be a \emph{real} inner product space.  Recall that
  the \emph{distance} between $v,w\in V$ is
  $d(v,w):=\norm{v-w}$.

  A map $f:V\to V$ (not necessarily linear) is
  \emph{distance-preserving} or a \emph{rigid motion} if
  $d(f(v),f(w))=d(v,w)$, for all $v,w\in V$.

  $f$ is distance-preserving if and only if there is a
  $v_0\in V$ and $\phi\in L(V)$ a linear isometry such that
  \begin{equation}
    \label{eq:15}
    f(v)=\phi(v)+v_0,
  \end{equation}
  for all $v\in V$.
\end{thm}
\begin{proof}
  Suppose that $f$ is distance-preserving and that
  \eqref{eq:15} held.  Then we would have
  $f(0)=\phi(0)+v_0=0+v_0$.  So, inspired by this, we define
  \begin{align*}
    v_0&:=f(0)\\\phi(v)&:=f(v)-v_0,
  \end{align*}
  for all $v\in V$, and observe:
  \begin{subequations}\label{eq:17}
    \begin{align}
      \label{eq:16}
      \phi(0)&=v_0-v_0=0\\
      \label{eq:18}
      \norm{\phi(v)-\phi(w)}&=\norm{v-w}.
    \end{align}
  \end{subequations}
  We show that $\phi$ is a linear isometry in four steps:
  \begin{compactenum}[1.]
  \item $\phi$ is norm-preserving: using \eqref{eq:17}, we
    have
    \begin{equation*}
      \norm{\phi(v)}=\norm{\phi(v)-\phi(0)}=\norm{v-0}=\norm{v},
    \end{equation*}
    for all $v\in V$.
  \item $\ip{\phi(v),\phi(w)}=\ip{v,w}$: we know from
    \eqref{eq:18} that
    $\norm{\phi(v)-\phi(w)}^2=\norm{v-w}^2$.  Now expand
    this out, using the fact that the (real) inner product is
    symmetric, to get
    \begin{equation*}
      \norm{\phi(v)}^2-2\ip{\phi(v),\phi(w)}+\norm{\phi(w)}^2=
      \norm{v}^2-2\ip{v,w}+\norm{w}^2.
    \end{equation*}
    But, from step 1, we know that
    $\norm{\phi(v)}^2=\norm{v}^2$ and
    $\norm{\phi(w)}^2=\norm{w}^2$ and the result follows.
  \item $\phi$ preserves addition: we compute:
    \begin{align*}
      \norm{\phi(v+w)-(\phi(v)+\phi(w))}^2&=
        \norm{\phi(v+w)}^2-2\ip{\phi(v+w),\phi(v)+\phi(w)}+\norm{\phi(v)+\phi(w)}^2 \\
           \begin{split}
            &=\norm{\phi(v+w)}^2-2\ip{\phi(v+w),\phi(v)}-2\ip{\phi(v+w),\phi(w)}\\&\qquad+
            \norm{\phi(v)}^2+2\ip{\phi(v),\phi(w)}+\norm{\phi(w)}^2
          \end{split}
\\
        &=\norm{v+w}^{2}-2\ip{v+w,v}-2\ip{v+w,w}+\norm{v}^{2}+2\ip{v,w}+\norm{w}^2\\
        &=\norm{v+w}^2-2\norm{v+w}^2+\norm{v+w}^2=0.
    \end{align*}
    Here we use steps 1 and 2 to reach the third line from
    the second.  We now conclude from the definiteness of
    the inner product that $\phi(v+w)=\phi(v)+\phi(w)$, for
    all $v,w\in V$.
  \item $\phi$ preserves scalar multiplication: let
    $\lambda\in\R$ and compute:
    \begin{align*}
      \norm{\phi(\lambda v)-\lambda\phi(v)}^2
      &=\norm{\phi(\lambda v)}^2-2\ip{\phi(\lambda
        v),\lambda\phi(v)}+\norm{\lambda\phi(v)}^{2}\\
      &=\norm{\phi(\lambda v)}^2-2\lambda\ip{\phi(\lambda
        v),\phi(v)}+\lambda^2\norm{\phi(v)}^2\\
      &=\norm{\lambda v}^2-2\lambda\ip{\lambda
        v,v}+\lambda^2\norm{v}^{2}\\
      &=\lambda^2\norm{v}^2-2\lambda^2\norm{v}^2+\lambda^2\norm{v}^2=0,
    \end{align*}
    where, again, we use steps 1 and 2 for the third
    equality.  Definiteness now yields $\phi(\lambda
    v)=\lambda\phi(v)$, for all $v\in V$, $\lambda\in\R$, so
    that $\phi$ is a linear isometry.

    Conversely, any $f$ of the form \eqref{eq:15} is clearly
    distance-preserving.
  \end{compactenum}
\end{proof}

\begin{rem}
  Unitary groups play a fundamental role in theoretical
  physics.  At the heart of the Standard Model that unifies
  electromagnetism with the sub-atomic strong and weak forces is the
  group $\rU(1)\times\rSU(2)\times\rSU(3)$ where
  $\rSU(n)=\set{A\in\rU(n)\st \det A=1}$ and I leave it to
  you to work out how one might make a Cartesian product of
  groups into a group.
\end{rem}

\section{The spectral theorem}
\label{sec:spectral-theorem}

\subsection{Eigenvalues and eigenvectors}
\label{sec:eigenv-eigenv}

Recall from Chapter 5 of Algebra 1B:
\begin{defns}
  Let $V$ be a vector space over $\F$ and $\phi\in L(V)$.

  An \emph{eigenvalue} of $\phi$ is a scalar $\lambda\in\F$
  such that there is a \emph{non-zero} $v\in V$ with
  \begin{equation*}
    \phi(v)=\lambda v.
  \end{equation*}
  Such a vector $v$ is called an \emph{eigenvector of $\phi$
    with eigenvalue $\lambda$}.

  The \emph{$\lambda$-eigenspace $E_{\phi}(\lambda)$ of
    $\phi$} is given by
  \begin{equation*}
    E_{\phi}(\lambda):=\ker(\phi-\lambda\id_V)\leq V.
  \end{equation*}
\end{defns}
\begin{rem}
  Thus $E_{\phi}(\lambda)$ consists of all eigenvectors of
  $\phi$ with eigenvalue $\lambda$ along with $0$.
\end{rem}

\begin{defn}
  Let $V$ be a finite-dimensional vector space over $\F$
  and $\phi\in L(V)$.

  The \emph{characteristic polynomial $\Delta_{\phi}$ of
    $\phi$} is given by
  \begin{equation*}
    \Delta_{\phi}(\lambda):=\det(\phi-\lambda\id_V)=\det(A-\lambda
    \I),
  \end{equation*}
  where $A$ is the matrix of $\phi$ with respect to some
  (any!) basis of $V$.
\end{defn}

We know that $\Delta_{\phi}(\lambda)$ is a polynomial in
$\lambda$ with coefficients in $\F$ and
$\deg\Delta_{\phi}=\dim V$.  It is important to us because:
\begin{lem}
  \label{th:40}
  % eigenvals are roots of char poly
  A scalar $\lambda\in\F$ is an eigenvalue of $\phi$ if and
  only if $\Delta_{\phi}(\lambda)=0$, that is, $\lambda$ is
  a root of $\Delta_{\phi}$.
\end{lem}

When $\F=\C$, the Fundamental Theorem of Algebra ensures
that the characteristic polynomial has at least one root so
so we conclude:
\begin{cor}
  \label{th:41}
  % eigenvals exist over C
  Let $\phi$ be a linear operator on a finite-dimensional
  \emph{complex} vector space $V$.  Then $\phi$ has an
  eigenvalue. 
\end{cor}

\begin{rem}
  When $\F=\R$ things are more problematic: consider
  $\phi:\R^2\to\R^2$ given by $\phi(x_1,x_2)=(-x_2,x_1)$.
  Thus $\phi=\phi_A$ for
  \begin{equation*}
    A=
    \begin{pmatrix}
      0&-1\\1&0
    \end{pmatrix}.
  \end{equation*}
  Then $\Delta_{\phi}(\lambda)=\lambda^2+1$ which has no
  real roots at all!
\end{rem}

\subsection{Invariant subspaces and adjoints}
\label{sec:invar-subsp-adjo}

\begin{defn}
  Let $V$ be a vector space and $\phi\in L(V)$.
  
  A subspace $U\leq V$ is \emph{$\phi$-invariant} if
  $\phi(U)\leq U$, that is, $\phi(u)\in U$, for all $u\in U$.
\end{defn}

Note that, in this case, $\phi$ restricts to give a linear
operator on $U$: $\phi_{|U}\in L(U)$.

\begin{xmpl}
  Any eigenspace of $\phi$ is $\phi$-invariant: if $v\in
  E_{\phi}(\lambda)$, then $\phi(v)=\lambda v\in
  E_{\phi}(\lambda)$, since $E_{\phi}(\lambda)$ is a
  subspace and so closed under scalar multiplication.
\end{xmpl}

Here are two ways to find invariant subspaces.
\begin{lem}
  \label{th:42}
  % commutants preserve eigenspaces
  Let $\phi,\psi\in L(V)$ and suppose that
  \begin{compactitem}
  \item $\psi\circ\phi=\phi\circ\psi$ (say that $\phi$ and
    $\psi$ \emph{commute}).
  \item $U=E_{\phi}(\lambda)$ is an eigenspace of $\phi$.
  \end{compactitem}
  Then $U$ is $\psi$-invariant.
\end{lem}
\begin{proof}
  Let $u\in U$ so that $\phi(u)=\lambda u$.  Take $\psi$ of
  both sides to get $\psi(\phi(u))=\lambda\psi(u)$.  But
  $\psi(\phi(u))=\phi(\psi(u))$ so this reads:
  \begin{equation*}
    \phi(\psi(u))=\lambda\psi(u).
  \end{equation*}
  Thus $\psi(u)\in E_{\phi}(\lambda)$ as required.
\end{proof}

\begin{lem}
  \label{th:43}
  % adjoint preserves perp
  Let $V$ be a finite-dimensional\footnote{We only need this
    hypothesis to ensure that $\phi^{*}$ exists.} inner
  product space and $\phi\in L(V)$.

  Let $U\leq V$ be a $\phi$-invariant subspace.  Then
  $U^{\perp}$ is $\phi^{*}$-invariant.
\end{lem}
\begin{proof}
  Let $v\in U^{\perp}$ so that $\ip{u,v}=0$, for all $u\in
  U$.  Then
  \begin{equation*}
    \ip{u,\phi^{*}(v)}=\ip{\phi(u),v}=0,
  \end{equation*}
  for all $u\in U$, since $\phi(u)\in U$ also.  Thus
  $\phi^{*}(v)\in U^{\perp}$ as required.
\end{proof}

These two constructions come together for an interesting
class of operators:
\begin{defn}
  Let $V$ be a finite-dimensional inner product space.  A
  linear operator $\phi\in L(V)$ is \emph{normal} if it
  commutes with its adjoint:
  $\phi^{*}\circ\phi=\phi\circ\phi^{*}$.
\end{defn}

\begin{xmpls}
\item[]
  \begin{compactitem}
  \item Self/skew-adjoint operators are normal: here
    $\phi^{*}=\pm\phi$ so
    \begin{equation*}
      \phi^{*}\circ\phi=\pm \phi^2=\phi\circ\phi^{*}.
    \end{equation*}
  \item Unitary/orthogonal transformations are normal: here
    $\phi^{*}=\phi^{-1}$ so
    \begin{equation*}
      \phi^{*}\circ\phi=\id_V=\phi\circ\phi^{*}.
    \end{equation*}
  \end{compactitem}
\end{xmpls}

We now have:
\begin{prop}
  \label{th:44}
  % normal ops reducible
  Let $V$ be a finite-dimensional inner product space and
  $\phi\in L(V)$.

  Suppose that:
  \begin{compactitem}
  \item $\phi$ is normal;
  \item $U\leq V$ is an eigenspace of $\phi$.
  \end{compactitem}
  Then $U^{\perp}$ is $\phi$-invariant.
\end{prop}
\begin{proof}
  Since $\phi$ is normal, $\phi$ and $\phi^{*}$ commute
  whence $U$ is $\phi^{*}$-invariant by \cref{th:42}.
  But now \cref{th:43} tells us that $U^{\perp}$ is
  $(\phi^{*})^{*}=\phi$-invariant.
\end{proof}

\subsection{The spectral theorem for normal operators}
\label{sec:spectr-theor-norm}

Recall from Algebra 1B (Definition 1 of \S5.2):
\begin{defn}
  Let $V$ be a finite-dimensional vector space.  A linear
  operator $\phi\in L(V)$ is \emph{diagonalisable} if $V$
  has a basis of eigenvectors of $\phi$.
\end{defn}

This means that we have a basis $\lst{v}1n$ of $V$ and
scalars $\lst\lambda1n\in\F$ with
\begin{equation*}
  \phi(v_i)=\lambda_iv_i,
\end{equation*}
for $\bw1in$.  Equivalently, the matrix $A$ of $\phi$ with
respect to $\lst{v}1n$ is \emph{diagonal}
\begin{equation}
  \label{eq:19}
  % diagonal A
  A=
  \begin{pmatrix}
    \lambda_1&&\\&\ddots&\\&&\lambda_n
  \end{pmatrix},
\end{equation}
with the eigenvalues as diagonal entries.

\begin{ex}[Question 2 on sheet 7.]
  Let $\phi\in L(V)$ be diagonalisable and $\lst{v}1n$ be a
  basis of eigenvectors with eigenvalues $\lst\lambda1n$.
  If $\lambda$ is an eigenvalue of $\phi$ then
  \begin{equation*}
    E_{\phi}(\lambda)=\Span{v_i\st \lambda_i=\lambda}.
  \end{equation*}
  Thus $\lambda$ appears $\dim E_{\phi}(\lambda)$ times
  in the list $\lst{\lambda}1n$.
\end{ex}

\begin{defn}
  Let $V$ be a finite-dimensional inner product space.  A
  linear operator $\phi\in L(V)$ is \emph{orthogonally
    diagonalisable} if $V$ has an \emph{orthonormal} basis
  of eigenvectors.
\end{defn}

The Big Question we are going to answer is:
\begin{quotation}
  \itshape When is a linear operator orthogonally diagonalisable?
\end{quotation}

We begin by observing that there is a necessary condition:
\begin{prop}
  \label{th:45}
  % nec condition for orthog diag
  Let $V$ be a finite-dimensional inner product space over
  $\F$ and $\phi\in L(V)$ an orthogonally diagonalisable
  linear operator.  Then:
  \begin{compactenum}[(1)]
  \item If $\F=\C$, $\phi$ is normal.
  \item If $\F=\R$, $\phi$ is self-adjoint.
  \end{compactenum}
\end{prop}
\begin{proof}
  Let $\lst{u}1n$ is an orthonormal basis of eigenvectors of
  $\phi$.  The matrix $A$ of $\phi$ with respect to
  $\lst{u}1n$ has the form \eqref{eq:19} so that, by
  \cref{th:34}(2), $\phi^{*}$ has matrix
  \begin{equation*}
    A^{\dagger}=
    \begin{pmatrix}
      \overline{\lambda_1}&&\\&\ddots&\\&&\overline{\lambda_n}
    \end{pmatrix}
  \end{equation*}
  which is also diagonal.  In particular, if $F=\R$ so that each
  $\lambda_i=\overline{\lambda_i}$, $A=A^T$ whence
  $\phi=\phi^{*}$.  Otherwise said, $\phi$ is self-adjoint.

  On the other hand, when $\F=\C$, we have
  $A^{\dagger}A=AA^{\dagger}$ (diagonal matrices commute) so that
  $\phi^{*}\circ\phi=\phi\circ\phi^{*}$, that is, $\phi$ is
  normal.
\end{proof}

In both cases, the converse is also true.  We do the complex
case first.
\begin{thm}[Spectral theorem for normal operators]
  \label{th:46}
  % spec thm (normal)
  Let $V$ be a finite-dimensional \emph{complex} inner
  product space and $\phi\in L(V)$ a linear
  operator.  Then $\phi$ is orthogonally diagonalisable if
  and only if $\phi$ is normal.
\end{thm}
\begin{proof}
  The forward implication is \cref{th:45}.
    
  We prove the reverse implication by induction on $\dim V$.
  Thus our inductive hypothesis at $n$ is that the theorem
  holds when $\dim V\leq n$.

  First suppose that $\dim V=1$ and let $u\in V$ have unit
  length so that $u$ is an orthonormal basis all on its
  own.  Then any $\phi\in L(V)$ has $\phi(u)\in V$ so that
  $\phi(u)=\lambda u$, for some $\lambda\in\F$.  Thus $u$ is
  an eigenvector of $\phi$ and the inductive hypothesis
  holds at $n=1$.

  Now assume that the hypothesis holds at $n-1$ and suppose
  that $\dim V=n$ and $\phi$ is normal.  We make three
  observations:
  \begin{compactenum}[(1)]
  \item Since $\F=\C$, $\phi$ has an eigenvalue $\lambda$ by
    \cref{th:41}.  We let $U\leq V$ be the
    $\lambda$-eigenspace.
  \item Let $\lst{u}1k$ be an orthonormal basis of $U$,
    which exists by \cref{th:25}.  Of course, each
    $u_i$ is an eigenvector of $\phi$ with eigenvalue
    $\lambda$. 
  \item Since $\phi$ is normal, \cref{th:44} tells us that
    $U^{\perp}$ is $\phi$-invariant.  Moreover,
    $\dim U^{\perp}=\dim V-\dim U<n$ so we can try to apply
    the inductive hypothesis to
    $\phi_{|U^{\perp}}\in L(U^{\perp})$.  For this, we need
    $\phi_{|U^{\perp}}$ to be normal.  However, $U^{\perp}$
    is $\phi^{*}$-invariant by \cref{th:43} so that
    $\phi^{*}_{|U^{\perp}}\in L(U^{\perp})$.  Moreover, for
    $w_1,w_2\in U^{\perp}$,
    \begin{equation*}
      \ip{\phi^{*}_{|U^{\perp}}(w_2),w_1}=\ip{\phi^{*}(w_2),w_1}
      =\ip{w_2,\phi(w_1)}=\ip{w_2,\phi_{|U^{\perp}}(w_{1})}
    \end{equation*}
    so that $(\phi_{|U^{\perp}})^{*}=\phi^{*}_{|U^{\perp}}$.
    Since $\phi$ and $\phi^{*}$ commute, so do their
    restrictions to $U^{\perp}$ and we conclude that
    $\phi_{|U^{\perp}}$ is indeed normal.  We can therefore
    apply the inductive hypothesis to get an orthonormal
    basis $\lst{u}{k+1}n$ of $U^{\perp}$ consisting of
    eigenvectors of $\phi_{|U^{\perp}}$:
    \begin{equation*}
      \phi_{|U^{\perp}}(u_j)=\lambda_ju_j,
    \end{equation*}
    or, equivalently,
    \begin{equation*}
      \phi(u_j)=\lambda_ju_j,
    \end{equation*}
    for $\bw{k+1}jn$.
  \end{compactenum}
  We conclude that $\lst{u}1n$ is an orthonormal basis of
  $V$ with each $u_i$ an eigenvector of $\phi$.  Thus the
  inductive hypothesis is true at $n$ and so always. 
\end{proof}
\begin{rem}
  The only place in the argument where we used $\F=\C$ was
  at step (1) to see that $\phi$ has an eigenvalue at all.
  In the next section, we will show that real self-adjoint
  operators also have eigenvalues and so prove the spectral
  theorem in that case also.
\end{rem}

\subsection{The spectral theorem for real self-adjoint
  operators}
\label{sec:spectr-theor-real}

To prove the spectral theorem in the real case, we need the
following lemma which is interesting in its own right.
\begin{lem}
  \label{th:47}
  % real eigenvals, orthog eigenspaces.
  Let $V$ be an inner product space\footnote{We do
    \emph{not} demand that $V$ be finite-dimensional.} and
  $\phi\in L(V)$ be self-adjoint.
  \begin{compactenum}[(1)]
  \item Any eigenvalue of $\phi$ is \emph{real}.
  \item If $v,w\in V$ are eigenvectors of $\phi$ with
    eigenvalues $\lambda\neq\mu$ then $v\perp w$.
  \end{compactenum}
\end{lem}
\begin{proof}
  Let $v,w\in V$ be eigenvectors of $\phi$ with eigenvalues
  $\lambda,\mu$.  Since $\phi$ is self-adjoint, we have
  \begin{equation}\label{eq:20}
    \ip{\phi(v),w}=\ip{v,\phi(w)}.
  \end{equation}
  However,
  \begin{align*}
    \ip{\phi(v),w}&=\ip{\lambda v,w}=\bar{\lambda}\ip{v,w}\\
    \ip{v,\phi(w)}&=\ip{v,\mu w}=\mu\ip{v,w}
  \end{align*}
  so that \eqref{eq:20} reads
  \begin{equation*}
    (\bar{\lambda}-\mu)\ip{v,w}=0.
  \end{equation*}

  Now, for (1), take $v=w$ so that $\lambda=\mu$ to get
  $(\bar{\lambda}-\lambda)\norm{v}^2=0$ so that
  $\lambda=\bar{\lambda}$: thus $\lambda\in\R$.

  Now, if $\lambda\neq \mu$, we get
  $(\lambda-\mu)\ip{v,w}=0$ giving $\ip{v,w}=0$, settling (2).
\end{proof}

We apply this to find the missing ingredient for the real
spectral theorem.
\begin{prop}
  \label{th:48}
  % real self-adjoint has an eigenvalue
  A self-adjoint operator $\phi$ on a real,
  finite-dimensional inner product space $V$ has an
  eigenvalue.
\end{prop}
\begin{proof}
  Choose an orthonormal basis $\lst{u}1n$ of $V$ and let $A$
  be the matrix of $\phi$ with respect to $\lst{u}1n$.
  Then, by \cref{th:34}(2), $A=A^T$

  Now view $A$ as a \emph{complex} matrix (with real
  entries) and let $\phi_A^{\C}:\C^n\to\C^n$ be the complex
  linear map given by matrix multiplication with $A$.
  Observe:
  \begin{compactenum}
  \item $A=A^T=A^{\dagger}$ so that $\phi^{\C}_A$ is
    self-adjoint for the dot inner product on $\C^n$.
  \item Thus $\phi^{\C}_A$ has an eigenvalue by Proposition
    \ref{th:41} and, further, that eigenvalue $\lambda$ is
    real by \cref{th:47}.
  \item Otherwise said, $\lambda$ is a root of the
    characteristic polynomial $\Delta_{\phi_A^{\C}}$ of
    $\phi_A^{\C}$. But
    \begin{equation*}
      \Delta_{\phi_A^{\C}}(\lambda)=\det(A-\lambda
      \I)=\Delta_{\phi}(\lambda) 
    \end{equation*}
    so that $\lambda$ is an eigenvalue of $\phi$.
  \end{compactenum}
\end{proof}

We now have:
\begin{thm}[Spectral theorem for real self-adjoint
  operators]
  \label{th:49}
  % spectral thm: real
  Let $V$ be a real, finite-dimensional inner product space
  and $\phi\in L(V)$ a linear operator.  Then $\phi$ is
  orthogonally diagonalisable if and only if $\phi$ is
  self-adjoint.
\end{thm}
\begin{proof}
  The proof is exactly the same as that of the complex
  spectral \cref{th:46} except that we use
  \cref{th:48} as a replacement for
  \cref{th:41} in step 1.
\end{proof}

\begin{rem}
  A serious application of these ideas is to Quantum
  Mechanics.  Here a physical system is modelled by an inner
  product space $V$ (usually infinite-dimensional) and the
  \emph{observables} (things we can measure like position,
  momentum or spin) by self-adjoint operators.  This is a
  probabilistic theory where all we can hope to find out is
  the \emph{expected value} of an observable when the system
  is in a state $v\in V$.  However, there are \emph{pure
    states} where we can measure $\phi$ with certainty:
  these are the eigenvectors of $\phi$ and the corresponding
  eigenvalue is what we measure in that state.

  Let $\lst{u}1n$ be an orthonormal basis of eigenvectors of
  $\phi$ with eigenvalues $\lst\lambda1n$.  Then the
  probability that we will get a measurement of $\lambda_i$
  when in state $v$ is
  \begin{equation*}
    \frac{\abs{\ip{u_i,v}}^{2}}{\norm{v}^{2}}.
  \end{equation*}
  Note that this lies between $0$ and $1$ by Cauchy--Schwarz \eqref{eq:21} 
  and the different probabilities sum to $1$ by the Bessel
  equality (\cref{th:23}(2)).  

  It follows (exercise!) that the expected value of a
  measurement of $\phi$ when in state $v$
  \begin{equation*}
    \frac{\ip{\phi(v),v}}{\norm{v}^2}.
  \end{equation*}

  We need the theory of \emph{Hilbert spaces} (see MA40256)
  to make sense of all this in the infinite-dimensional
  case.
\end{rem}

\subsection{The spectral theorem for symmetric and Hermitian
  matrices}
\label{sec:spectr-theor-symm}

The spectral theorem can be reformulated as a result about
symmetric and Hermitian matrices:
\begin{thm}[Spectral theorem for symmetric/hermitian
  matrices]
  \label{th:50}
  % matrix spectral thm
\item{}
  \begin{compactenum}[(1)]
  \item Let $A\in M_{n\times n}(\R)$ be symmetric.  Then
    there is an orthogonal matrix $P\in\rO(n)$ such that
    $P^{-1}AP$ is diagonal.
  \item Let $A\in M_{n\times n}(\C)$ be Hermitian.  Then
    there is an unitary matrix $P\in\rU(n)$ such that
    $P^{-1}AP$ is diagonal.
  \end{compactenum}
\end{thm}
\begin{proof}
  In either case, $\phi_A:\F^n\to\F^n$ is self-adjoint with
  respect to the dot inner product and so, by the relevant
  spectral theorem, orthogonally diagonalisable.  So let
  $\cB=\lst{u}1n$ be an orthonormal basis of eigenvectors of
  $\phi_A$ with eigenvalues $\lst\lambda1n$.

  Contemplate $\phi_{\cB}:\F^n\to\F^n$ for which
  $\phi_{\cB}(e_i)=u_i$.  Then $\phi_{\cB}=\phi_P$ where
  $P\in M_{n\times n}(\F)$ is the matrix whose columns are
  $\lst\bu1n$.

  Observe:
  \begin{compactitem}
  \item The columns of $P$ are orthonormal so that $P$ is
    orthogonal/unitary.
  \item $\phi_{P^{-1}AP}=\phi_P^{-1}\circ\phi_A\circ\phi_P$
    has eigenvectors $\lst{e}1n$ with eigenvalues
    $\lst\lambda1n$:
    \begin{equation*}
      \phi_P^{-1}\circ\phi_A\circ\phi_P(e_i)=\phi_P^{-1}(\phi_A(u_i))=\lambda_i\phi_P^{-1}(u_i)
      =\lambda_ie_i.
    \end{equation*}
  \end{compactitem}
  Otherwise said, $P^{-1}AP$ is the diagonal matrix
  \begin{equation*}
    \begin{pmatrix}
      \lambda_1&&\\&\ddots&\\&&\lambda_n
    \end{pmatrix}.
  \end{equation*}
\end{proof}

\begin{xmpl}
  Let $A$ be the Hermitian matrix
  \begin{equation*}
    A=
    \begin{pmatrix}
      1&i\\-i&1
    \end{pmatrix}.
  \end{equation*}
  \textbf{Problem}: Find a unitary matrix $P$ such that
  $P^{-1}AP$ is diagonal.

  \textbf{Solution}: $P$ will have for columns an
  orthonormal basis of eigenvectors of $A$.  Then $P^{-1}AP$
  will be diagonal with the corresponding eigenvalues as
  entries.

  First we find the eigenvalues:
  \begin{equation*}
    \det(A-\lambda \I)=
    \begin{vmatrix}
      1-\lambda&i\\-i&1-\lambda
    \end{vmatrix}
    =\lambda^2-2\lambda=\lambda(\lambda-2)
  \end{equation*}
  so that the eigenvalues are $0$ and $2$.

  Corresponding eigenvectors are guaranteed to be orthogonal
  by \cref{th:47} so all we have to do is find unit
  length eigenvectors to get an orthonormal basis.

  For eigenvalue $0$, we must solve $A\bx=0$ which we
  readily do to get
  \begin{equation*}
    \bx=\mu
    \begin{pmatrix}
      1\\i
    \end{pmatrix}
  \end{equation*}
  and taking $\mu=1/\sqrt{2}$ we get a unit eigenvector
  \begin{equation*}
    \bu_1=\frac1{\sqrt{2}}
    \begin{pmatrix}
      1\\i
    \end{pmatrix}
  \end{equation*}
  For the eigenvalue $2$, we can proceed in two ways: either
  solve $A\by=2\by$ or simply seek $\by$ such that
  $\by\perp\bx$.  Either way, we get
  \begin{equation*}
    \bu_{2}=\frac1{\sqrt{2}}
    \begin{pmatrix}
      i\\1
    \end{pmatrix}
  \end{equation*}
  so that
  \begin{equation*}
    P=\frac1{\sqrt{2}}
    \begin{pmatrix}
      1&i\\i&1
    \end{pmatrix}
  \end{equation*}
  and
  \begin{equation*}
    P^{-1}AP=
    \begin{pmatrix}
      0&0\\0&2
    \end{pmatrix}.
  \end{equation*}
  We got all this by following the proof of
  \cref{th:50} but we can check our answer directly.
  First we check that $P$ really is unitary:
  \begin{equation*}
    P^{\dagger}P=\frac12
    \begin{pmatrix}
      1&-i\\-i&1
    \end{pmatrix}
    \begin{pmatrix}
      1&i\\i&1
    \end{pmatrix}=\frac12
    \begin{pmatrix}
      2&0\\0&2
    \end{pmatrix}=\I.
  \end{equation*}
  Second we check that $P^{-1}AP$ really is the diagonal
  matrix we say it is:
  \begin{align*}
    P^{-1}AP=P^{\dagger}AP
    &=\half
      \begin{pmatrix}
        1&-i\\-i&1
      \end{pmatrix}
                  \begin{pmatrix}
                    1&i\\-i&1
                  \end{pmatrix}
                             \begin{pmatrix}
                               1&i\\i&1
                             \end{pmatrix}\\
    &=\half\begin{pmatrix} 0&0\\-2i&2
    \end{pmatrix}
                                     \begin{pmatrix}
                                       1&i\\i&1
                                     \end{pmatrix}=
                                               \begin{pmatrix}
                                                 0&0\\0&2
                                               \end{pmatrix}.
  \end{align*}
\end{xmpl}

\subsection{Singular value decomposition}
\label{sec:sing-value-decomp}

Here is an application of the spectral theorem to general
linear operators.

Let $V$ be a finite-dimensional inner product space and
$\phi\in L(V)$ a linear operator.

Let us first consider the situation where $\phi$ is
self-adjoint.  By the spectral theorem, $V$ has an
orthonormal basis $\lst{u}1n$ of eigenvectors with
\emph{real} eigenvalues $\lst{\lambda}1n$ where each
distinct eigenvalue $\lambda$ appears $\dim
E_{\phi}(\lambda)$ times.  For $v\in V$, Lemma~\ref{th:35}
says
\begin{equation*}
  v=\sum_{i=1}^n\ip{u_i,v}u_i
\end{equation*}
and taking $\phi$ of this and using $\phi(u_i)=\lambda_iu_i$
yields:
\begin{equation}
  \label{eq:23}
  % spectral decomp of phi
  \phi(v)=\sum_{i=1}^n\lambda_i\ip{u_i,v}u_i.
\end{equation}

But what can be said if $\phi$ is not self-adjoint or even
diagonalisable? One answer is to consider
$\phi^{*}\circ\phi$ instead!  Recall from
\S\ref{sec:adjoints} that $\phi^{*}\circ\phi$ is
always self-adjoint.  Moreover

\begin{lem}
  \label{th:51}
  % Properties of f^{*}f
  Let $V$ be a finite-dimensional inner product space and
  $\phi\in L(V)$.  Then:
  \begin{compactenum}[(1)]
  \item All eigenvalues of $\phi^{*}\circ\phi$ are
    non-negative.
  \item $\ker(\phi^{*}\circ\phi)=\ker\phi$.
  \end{compactenum}
\end{lem}
\begin{proof}
  If $\phi^{*}(\phi(u))=\lambda u$ with $u\neq 0$ (thus $u$
  is an eigenvector of $\phi^{*}\circ\phi$ with eigenvalue
  $\lambda$), then
  \begin{equation*}
    \lambda\ip{u,u}=\ip{u,\lambda
      u}=\ip{u,\phi^{*}(\phi(u))}
    =\ip{\phi(u),\phi(u)}
  \end{equation*}
  so that
  \begin{equation*}
    \lambda=\frac{\norm{\phi(u)}^2}{\norm{u}^2}\geq 0.
  \end{equation*}
  This settles (1).  For (2), this formula says that
  $\lambda=0$ if and only if $\phi(u)=0$ so that the
  $0$-eigenspace of $\phi^{*}\circ\phi$ (that is,
  $\ker\phi^{*}\circ\phi$) coincides with $\ker\phi$.
\end{proof}

\begin{defn}
  Let $V$ be a finite-dimensional inner product space and
  $\phi\in L(V)$.  The \emph{singular values of $\phi$} are
  $\lst\sigma1n$ where $\sigma_i=\sqrt{\mu_i}\geq 0$ and
  $\lst\mu1n$ are the eigenvalues of $\phi^{*}\circ\phi$
  listed with multiplicity (thus each distinct $\mu$ appears
  $\dim E_{\phi^{*}\circ\phi}(\mu)$ times).
\end{defn}

\begin{ex}[Question 2 on sheet 8.]
  If $\phi$ is self-adjoint with eigenvalues $\lambda_i$
  then the singular values of $\phi$ are the $\abs{\lambda_i}$.
\end{ex}

We use these singular values to get a nice analogue of
\eqref{eq:23} for general $\phi$ at the cost of employing
\emph{two} orthonormal bases of $V$.
\begin{thm}[Singular value decomposition]
  \label{th:52}
  % SVD
  Let $V$ be a finite-dimensional inner product space and
  $\phi\in L(V)$ a linear operator with singular values
  $\lst\sigma1n$.

  Then there are orthonormal bases $\lst{u}1n$ and
  $\lst{w}1n$ of $V$ such that
  \begin{equation}
    \label{eq:24}
    % SVD
    \phi(v)=\sum_{i=1}^n\sigma_i\ip{u_i,v}w_i,
  \end{equation}
  for all $v\in V$.
\end{thm}
\begin{proof}
  Let $\lst{u}1n$ be an orthonormal basis of eigenvectors of
  $\phi^{*}\circ\phi$ ordered so that
  $\sigma_1\geq\sigma_2\geq\cdots\geq\sigma_n$ and let
  $k$ be the largest index for which $\sigma_k\neq 0$.
  Thus, $\sigma_j=0$ for $k<j\leq n$ so that, by
  Lemma~\ref{th:51}(2), $\phi(u_j)=0$.

  For $\bw1ik$, set $w_i:=\phi(u_i)/\sigma_i$.  We show that
  $\lst{w}1k$ is orthonormal:
  \begin{equation*}
    \ip{w_i,w_j}=\frac1{\sigma_i\sigma_j}\ip{\phi(u_i),\phi(u_j)}=
    \frac1{\sigma_i\sigma_j}\ip{u_i,\phi^{*}\circ\phi(u_j)}=
    \frac{\sigma_j^2}{\sigma_i\sigma_j}\delta_{ij}=\delta_{ij},
  \end{equation*}
  for $\bw1{i,j}k$.  Now extend $\lst{w}1k$ to an
  orthonormal basis of $V$ by choosing an orthonormal basis
  $\lst{w}{k+1}n$ of $\Span{\lst{w}1k}^{\perp}$.  Remark
  that for $\bw1in$ we have
  \begin{equation*}
    \phi(u_i)=\sigma_iw_i.
  \end{equation*}
  Indeed, for $i\leq k$, this is how we defined $w_i$ while,
  for $i>k$, both $\sigma_i=0$ and $\phi(u_i)=0$.

  Thus, for $v\in V$,
  \begin{equation*}
    \phi(v)=\phi(\sum_{i=1}^{n}\ip{u_i,v}u_i)
    =\sum_{i=1}^{n}\ip{u_i,v}\phi(u_i)=\sum_{i=1}^n\sigma_i\ip{u_i,v}w_i
  \end{equation*}
  as required.
\end{proof}

\begin{rem}
  This result has real life applications to, among other
  things, image compression.  The idea is that you can
  approximate a complicated matrix by the terms in the
  singular value decomposition with the largest singular
  values.
\end{rem}


\chapter{Duality}
\label{cha:duality}

\section{Dual spaces}
\label{sec:dual-spaces}

Recall from \cref{th:3}: if $V$ and $W$ are vector spaces
over $\F$ then the set $L(V,W)$ of linear maps from $V$ to
$W$ is also a vector space under pointwise addition and
scalar multiplication.  In this chapter we will study the
special case where $W=\F$ the field of scalars.

\begin{defn}
  Let $V$ be a vector space over $\F$.  The \emph{dual space
    $V^{*}$ of $V$} is
  \begin{equation*}
    V^{*}:=L(V,\F)=\set{\alpha:V\to\F\st\text{$\alpha$ is linear}}.
  \end{equation*}
  Elements of $V^{*}$ are called \emph{linear functionals}
  or (less often) \emph{linear forms}.
\end{defn}

Let us spell this out.  An element $\alpha\in V^{*}$ is a
function $\alpha:V\to\F$ which is linear:
\begin{equation*}
  \alpha(v_1+\lambda v_2)=\alpha(v_1)+\lambda\alpha(v_2),
\end{equation*}
for all $v_1,v_2\in V$ and $\lambda\in\F$.  The addition and
scalar multiplication on the right are the field addition
and multiplication in $\F$.

The dual space $V^{*}$ is a vector space (indeed a subspace
of $\F^V$) under pointwise addition and scalar
multiplication.  Thus:
\begin{align*}
  (\alpha_1+\alpha_2)(v)&:=\alpha_1(v)+\alpha_2(v)\\
  (\lambda\alpha)(v)&:=\lambda(\alpha(v)),
\end{align*}
for all $\alpha,\alpha_1,\alpha_2\in V^{*}$, $v\in V$ and
$\lambda\in F$.  Again, the algebraic operations on the
right hand side of these formulae are those of the field
$\F$.

\begin{xmpls}
\item[]
  \begin{compactenum}
  \item Fix $\lst\alpha1n\in\F$ and define
    $\alpha:\F^n\to\F$ by
    \begin{equation*}
      \alpha(\lst{x}1n)=\lc\alpha{x}1n.
    \end{equation*}
  \item Let $P:=\R[t]$ be the vector space of polynomials on
    $\R$.  Here are some linear functionals on $P$:
    \begin{compactenum}[(a)]
    \item integration over an interval $[a,b]$:
      $p\mapsto\int_a^bp$.
    \item Evaluation at a point: for example,
      $p\mapsto p(\sqrt{2})$.
    \item Evaluation of a derivative at a point: for example
      $p\mapsto p'''(\pi)$.
    \end{compactenum}
  \item Let $V$ be an inner product space and $w\in V$.
    Define $\alpha_w\in V^{*}$ by $\alpha_w(v)=\ip{w,v}$.

    Note that $\alpha_w$ is indeed linear since the inner
    product is linear in the second slot.

    \Cref{th:55} will show that when $V$ is
    finite-dimensional, any element of $V^{*}$ is of this
    form.
  \end{compactenum}
\end{xmpls}

When $V$ is finite-dimensional, so is $V^{*}$.  Indeed:
\begin{prop}
  \label{th:53}
  % Dual basis of V$^{*}$
  Let $V$ be a finite-dimensional vector space with basis
  $\lst{v}1n$.

  Define $\dlst{v}1n\in V^{*}$ by setting
  \begin{equation*}
    v_i^{*}(v_j)=\delta_{ij}\in\F
  \end{equation*}
  and extending by linearity (thus applying \cref{th:6}).

  Then $\dlst{v}1n$ is a basis of $V^{*}$ called the
  \emph{dual basis to $\lst{v}1n$}.
\end{prop}
\begin{proof}
  Here is the key computation: if
  $\sum_{i=1}^n\lambda_iv^{*}_i\in V^{*}$ is a linear
  combination of the $v^{*}_i$ then evaluating on $v_j$
  gives
  \begin{equation*}
    \sum_{i=1}^n\lambda_iv^{*}_i(v_j)=\sum_{i=1}^n\lambda_i\delta_{ij}=\lambda_j.
  \end{equation*}
  In particular, if $\sum_{i=1}^n\lambda_iv^{*}_i=0$ then
  each $\lambda_j=0(v_j)=0$ and $\dlst{v}1n$ are linearly
  independent.

  Now let $\alpha\in V^{*}$ and set $\lambda_i=\alpha(v_i)$,
  for $\bw1in$.  Then $\alpha$ and
  $\sum_{i=1}^n\lambda_iv_i^{*}$ agree on each $v_j$ and so
  everywhere:
  \begin{equation*}
    \alpha=\sum_{i=1}^n\alpha(v_i)v_i^{*}.
  \end{equation*}
  Thus $\dlst{v}1n$ span.
\end{proof}

\begin{rem}
  We have met these $v^{*}_i$ before, perhaps without
  realising it.  Write $v\in V$ in terms of the $\lst{v}1n$:
  $v=\sum_{j=1}^n\lambda_jv_j$.  Then
  \begin{equation*}
    v_i^{*}(v)=\sum_{j=1}^n\lambda_jv_i^{*}(v_j)=\lambda_i.
  \end{equation*}
  Thus $v^{*}_i$ is the \emph{$i$-th coordinate function on
    $V$ with respect to $\lst{v}1n$}.
\end{rem}

\begin{cor}
  \label{th:54}
  % dim V=dim V$^{*}$
  If $V$ is finite-dimensional then $\dim V=\dim V^{*}$.
\end{cor}

When $V$ is an inner product space also, we get a complete
understanding of $V^{*}$:
\begin{thm}[Riesz Representation Theorem]
  \label{th:55}
  % Riesz
  Let $V$ be a finite-dimensional inner product space and
  $\alpha\in V^{*}$.  Then there is a unique $w\in V$ such
  that
  \begin{equation*}
    \alpha(v)=\ip{w,v},
  \end{equation*}
  for all $v\in V$.  Thus $\alpha=\alpha_w$.

  Indeed, if $\lst{u}1n$ is an orthonormal basis of $V$ then
  \begin{equation}\label{eq:6}
    w=\sum_{i=1}^n\overline{\alpha(u_i)}u_i.
  \end{equation}
\end{thm}
\begin{proof}
  With $w$ defined by \eqref{eq:6} and $v\in V$, we have
  \begin{align*}
    \ip{w,v}&=\sum_{i=1}^n\alpha(u_i)\ip{u_i,v}\\
    &=\alpha(\sum_{i=1}^n\ip{u_i,v}u_i)=\alpha(v)
  \end{align*}
  where we have used the sesquilinearity of the inner
  product and \cref{th:35}.

  For uniqueness, if $w'$ had the same property, we would
  have $\ip{w-w',v}=\alpha(v)-\alpha(v)=0$, for all $v\in
  V$, so that $w=w'$ by the Nondegeneracy \cref{th:33}.
\end{proof}
\begin{rem}
  How did we magic up formula \eqref{eq:6} for $w$?  We had
  to have $\ip{w,u_i}=\alpha(u_i)$ but
  $w=\sum_{i=1}^n\ip{u_i,w}u_i$ by \cref{th:35}.
\end{rem}

\begin{xmpl}
  Fix $d\in\N$ and let $V\leq C^0[-1,1]$ be given by
  \begin{equation*}
    V=\set{p\in C^0[-1,1]\st\text{$p$ is a polynomial of
      degree no more than $d$}}.
  \end{equation*}

  Then $V$ is a finite-dimensional inner product space with
  inner product
  \begin{equation*}
    \ip{p,q}=\int_{-1}^1pq.
  \end{equation*}

  Define $\alpha:V\to\R$ by $\alpha(p)=p(0)+p'(1/\sqrt{2})$.
  We have already noted that $\alpha\in V^{*}$.

  So \cref{th:55} tells us that there is a $q\in V$ such
  that $\alpha(p)=\ip{q,p}$, for all $p\in V$.  Otherwise
  said, there is a clever polynomial $q$ of degree $d$ such
  that
  \begin{equation*}
    \int_{-1}^1qp=p(0)+p'(1/\sqrt{2}),
  \end{equation*}
  for all polynomials of degree no more than $d$!
\end{xmpl}

A basic question is how big is $V^{*}$: are there enough
linear functionals to detect all elements of $V$?  The
answer is yes and the key is the following theorem:
\begin{thm}[Sufficiency principle]
  \label{th:56}
  % sufficiency
  Let $V$ be a vector space and $v\in V$.  Then
  $\alpha(v)=0$, for all $\alpha\in V^{*}$, if and only if $v=0$.
\end{thm}
\begin{proof}
  A complete proof requires a tool from set theory called
  Zorn's Lemma, equivalent to the Axiom of Choice, which has
  the faintly controversial property that it is logically
  independent from the usual axioms of set theory (so you
  can choose to believe it or not without running into a
  contradiction).  Rather than get involved in all that we
  simply prove the result in two cases of interest.
  \begin{compactenum}[(1)]
  \item If $V$ is an inner product space and $v\in V$ is
    non-zero then $\alpha_v(v)=\ip{v,v}\neq 0$, where
    $\alpha_v\in V^{*}$ is given by $\alpha_v(w)=\ip{v,w}$.
  \item If $V$ is finite-dimensional, choose a basis
    $\lst{v}1n$.  For $v\in V$, write
    $v=\lc\lambda{v}1n$. If $\alpha(v)=0$ for all
    $\alpha\in V^{*}$ then, in particular, for each $i$,
    $0=v_i^{*}(v)=\lambda_i$ so that $v=0$.
  \end{compactenum}
\end{proof}

\begin{ex}[Question 5 on sheet 8.]
  Let $v\in V$ and $U\leq V$ with $v\notin U$.  Show that
  there is $\alpha\in V^{*}$ such that $\alpha(v)\neq 0$
  while $\alpha_{|U}=0$.

  \textbf{Hint}: apply \cref{th:56} to $V/U$.
\end{ex}

We apply \cref{th:56} to get a converse to \cref{th:53}:
\begin{prop}
  \label{th:57}
  % dual basis of V
  Let $V$ be a finite-dimensional vector space and
  $\lst{\alpha}1n$ a basis of $V^{*}$.  Then there is a
  basis $\lst{v}1n$ of $V$ such that
  \begin{equation*}
    \alpha_i(v_j)=\delta_{ij}.
  \end{equation*}
  Thus $\alpha_i=v^{*}_i$, for $\bw1{i}n$.
\end{prop}
\begin{proof}
  Define a linear map $\phi:V\to\F^n$ by
  \begin{equation*}
    \phi(v)=(\alpha_1(v),\dots,\alpha_n(v))
  \end{equation*}
  and observe that $v\in\ker\phi$ if and only if
  $\alpha_i(v)=0$, for $\bw1in$, whence, since any
  $\alpha\in V^{*}$ is a linear combination of the
  $\alpha_i$, $\alpha(v)=0$, for all $\alpha\in V^{*}$.  We
  deduce from \cref{th:56} that $v=0$ so that
  $\ker\phi=\set0$ and $\phi$ is injective.  On the other
  hand, $\dim V=\dim V^{*}=n=\dim\F^n$ so that $\phi$ is an
  isomorphism.

  Now set $v_i=\phi^{-1}(e_i)$, $\bw1in$, to get a basis of
  $V$ since $\lst{e}1n$ is a basis of $\F^n$.  Then
  \begin{equation*}
    \phi(v_j)=(\alpha_1(v_j),\dots,\alpha_n(v_j))=e_j=(0,\dots,1,\dots,0),
  \end{equation*}
  where the $1$ is in the $j$-th slot.  Otherwise said,
  $\alpha_i(v_j)=\delta_{ij}$ as required.
\end{proof}

Since the dual space $V^{*}$ is a vector space, we can
contemplate its dual space $V^{**}:=(V^{*})^{*}$, the
\emph{double dual of $V$}.  This is closely related to $V$
itself.  Indeed, each $v\in V$ defines a linear map
$\ev(v):V^{*}\to\F$ by evaluation at $v$:
\begin{equation*}
  \ev(v)(\alpha):=\alpha(v)\in\F.
\end{equation*}
\begin{exs}[Question 7 on sheet 8.]
\item[]
  \begin{compactenum}
  \item $\ev(v)$ is indeed linear: for $\alpha,\beta\in
    V^{*}$ and $\lambda\in\F$,
    \begin{equation*}
      \ev(v)(\alpha+\lambda\beta)=\ev(v)(\alpha)+\lambda\ev(v)(\beta).
    \end{equation*}
    Thus $\ev(v)\in V^{**}$.
  \item We therefore have a map $\ev:V\to V^{**}$.  Show
    that $\ev$ is linear: that is,
    \begin{equation*}
      \ev(v+\lambda w)=\ev(v)+\lambda\ev(w),
    \end{equation*}
    for all $v,w\in V$, $\lambda\in\F$.  To spell it out
    even more, this means
    \begin{equation*}
      \ev(v+\lambda w)(\alpha)=\ev(v)(\alpha)+\lambda\ev(w)(\alpha),
    \end{equation*}
    for all $\alpha\in V^{*}$.
  \item $\ev$ is injective (use \cref{th:56}) and so, when
    $V$ is finite-dimensional, an isomorphism since
    $\dim V=\dim V^{*}=\dim V^{**}$.
  \end{compactenum}
\end{exs}
Thus:
\begin{thm}
  \label{th:58}
  % V^**
  If $V$ is a finite-dimensional vector space then $\ev:V\to
  V^{**}$ is an isomorphism.
\end{thm}

\begin{rem}
  In general, a vector space for which $\ev:V\to V^{**}$ is
  an isomorphism is said to be \emph{reflexive}. 
\end{rem}

\section{Solution sets and annihilators}
\label{sec:solut-sets-annih}

Here is one way to think about $V^{*}$: consider the
equation
\begin{equation}
  \label{eq:25}
  \alpha(v)=0,
\end{equation}
for some $\alpha\in V^{*}$ and $v\in V$.  If we choose dual
bases $\lst{v}1n$ and $\dlst{v}1n$ of $V$ and $V^{*}$,
\eqref{eq:25} reads
\begin{equation*}
  \lc\alpha{x}1n=0
\end{equation*}
where we have written $\alpha=\lc\alpha{v^{*}}1n$ and
$v=\lc{x}v1n$.  This is a single homogeneous linear
equation.

This gives us the idea of viewing $V^{*}$ as the set of
linear equations on $V$.  From this point of view, a
subspace $E\leq V^{*}$ should be viewed as a system of
linear equations and so we should be interested in the
solutions of that system:
\begin{defn}
  Let $E\leq V^{*}$.  The \emph{solution set of $E$} is
  \begin{equation*}
    \sol E:=\set{v\in V\st\text{$\alpha(v)=0$, for all
        $\alpha\in E$}}=\bigcap_{\alpha\in E}\ker\alpha\leq V.
  \end{equation*}
\end{defn}

\begin{ex}[Question 1 on sheet 9.]
  If $\lst\alpha1k$ span $E$ then
  \begin{equation*}
    \sol E=\bigcap_{i=1}^k\ker\alpha_i.
  \end{equation*}
\end{ex}

For finite-dimensional $V$, one might expect each equation
in a linear system to reduce the dimension of the solution
set by one and this is exactly what happens:
\begin{prop}
  \label{th:59}
  % dim sol
  If $V$ is finite-dimensional and $E\leq V^{*}$ then
  \begin{equation*}
    \dim\sol E=\dim V-\dim E.
  \end{equation*}
  We say that $E$ and $\sol E$ have \emph{complementary
    dimension}. 
\end{prop}
\begin{proof}
  Let $\dlst{v}1k$ be a basis of $E$ and extend to a basis
  $\dlst{v}1n$ of $V^{*}$.  Let $\lst{v}1n$ be the dual
  basis of $V$ provided by \cref{th:57}.

  Now $E=\Span{\dlst{v}1k}$ so that $\sol
  E=\bigcap_{i=1}^k\ker v^{*}_i$.  Thus
  $v=\sum_{j=1}^n\lambda_jv_j$ lies in $\sol E$ if and only
  if $\lambda_i=v^{*}_i(v)=0$, for $\bw1ik$.  Otherwise
  said,
  \begin{equation*}
    \sol E=\Span{\lst{v}{k+1}n}
  \end{equation*}
  so that
  \begin{equation*}
    \dim\sol E=n-k=\dim V-\dim E.
  \end{equation*}
\end{proof}
\begin{rem}
  Here is a slicker argument.  Let $\ev^E:V\to E^{*}$ be the
  linear map given by
  \begin{equation*}
    \ev^E(v)(\alpha)=\alpha(v).
  \end{equation*}
  \begin{compactenum}%TODO: improve this argument
  \item $\im\ev^E=E^{*}$: for this, you use \cref{th:58} along
    with the fact that restriction to $E$ is a surjection
    from $V^{**}$ to $E^{*}$ thanks to \cref{th:82}.
  \item $\ker\ev^E=\set{v\in V\st\text{$\alpha(v)=0$, for all
        $\alpha\in E $}}=\sol E$.
  \end{compactenum}
  So rank-nullity tells us that
  \begin{equation*}
    \dim\sol E+\dim E^{*}=\dim V
  \end{equation*}
  and, since $\dim E=\dim E^{*}$, we are done.
\end{rem}
\begin{cor}
  \label{th:60}
  % span V^{*}
  Let $V$ have dimension $n$ and suppose that
  $\lst{\alpha}1n\in V^{*}$ are such that
  \begin{equation*}
    \bigcap_{i=1}^n\ker\alpha_i=\set0.
  \end{equation*}
  Then $\lst\alpha1n$ is a basis of $V^{*}$.
\end{cor}
\begin{proof}
  Let $E:=\Span{\lst\alpha1n}$.  The hypothesis says
  that $\sol E=\set 0$ so, by \cref{th:59}, $\dim E=n$
  whence $E=V^{*}$.  Thus $\lst\alpha1n$ span $V^{*}$ and so
  are a basis.
\end{proof}
Here is an application:
\begin{xmpl}
  Let $P_2$ be the vector space of polynomials of degree at
  most $2$.  Thus $\dim P_2=3$.

  Define $\alpha_i:P_2\to\R$, $i=1,2,3$, by
  \begin{align*}
    \alpha_1(p)&=p(1)\\
    \alpha_2(p)&=p(\sqrt{2})\\
    \alpha_3(p)&=p(\pi),
  \end{align*}
  for all $p\in P_2$.  These are all linear maps so that
  $\alpha_1,\alpha_2,\alpha_3\in P_2^{*}$.  We apply
  \cref{th:60} so see that $\alpha_1,\alpha_2,\alpha_3$ are
  a basis of $P_2^{*}$. Indeed, if $p\in
  \bigcap_{i=1}^3\ker\alpha_i$ then $p(1)=p(\sqrt{2})=p(\pi)=0$
  so that $p$ has three distinct roots and so must vanish
  since it has degree no more than $2$.

  Thus any $\alpha\in P_2^{*}$ is a linear combination of
  the $\alpha_i$.  For example, define $\alpha$ by
  \begin{equation*}
    \alpha(p)=\int_0^1p.
  \end{equation*}
  Then there are $\lambda_1,\lambda_2,\lambda_3\in\R$ such
  that
  $\alpha=\lambda_1\alpha_1+\lambda_2\alpha_2+\lambda_3\alpha_3$.
  Otherwise said, we have found clever $\lambda_i$ such
  that, for all $p\in P_2$,
  \begin{equation*}
    \int_0^1p=\lambda_1p(1)+\lambda_2p(\sqrt{2})+\lambda_3p(\pi).
  \end{equation*}
\end{xmpl}

Solution sets behave somewhat like orthogonal complements
(except that $E$ and $\sol E$ live in entirely different
vector spaces):
\begin{prop}
  \label{th:61}
  % Props of sol
  Let $E,F\leq V^{*}$.  Then
  \begin{compactenum}[(1)]
  \item If $E\leq F$ then $\sol F\leq\sol E$.
  \item $\sol$ swaps sums and intersections:
    \begin{align*}
      \sol(E+F)&=(\sol E)\cap(\sol F)\\
      (\sol E)+(\sol F)&\leq \sol(E\cap F)
    \end{align*}
    with equality if $V$ is finite-dimensional.
  \end{compactenum}
\end{prop}
\begin{proof}
\item[]
  \begin{compactenum}[(1)]
  \item Let $E\leq F$ and $v\in\sol F$.  Then $\alpha(v)=0$,
    for all $\alpha\in F$ and so, in particular, for all
    $\alpha\in E$. Thus $v\in\sol E$.
  \item This is an exercise\footnote{Question 4(a) on sheet
      9.} similar to one you have already done about
    orthogonal complements\footnote{Question 4 on sheet 6.}.
  \end{compactenum}
\end{proof}

Still thinking of $V^{*}$ as the linear equations on $V$,
we can turn things around and ask which equations the
elements of a subspace $U\leq V$ satisfy:
\begin{defn}
  Let $U\leq V$.  The \emph{annihilator of $U$, denoted
    $\ann U$ or $U^{\circ}$}, is given by:
  \begin{equation*}
    \ann U:=\set{\alpha\in
      V^{*}\st\alpha_{|U}=0}=\set{\alpha\in
      V^{*}\st\text{$\alpha(u)=0$, for all $u\in U$ }}.
  \end{equation*}
\end{defn}
\begin{ex}[Question 2 on sheet 9.]
  Show that $\ann U\leq V^{*}$.
\end{ex}

Annihilators have very similar properties to solution sets.
They also have complementary dimension:
\begin{prop}
  \label{th:62}
  % dim ann
  Let $V$ be finite-dimensional and $U\leq V$.  Then
  \begin{equation*}
    \dim \ann U=\dim V-\dim U.
  \end{equation*}
\end{prop}
\begin{proof}
  This is an exercise\footnote{Question 3 on sheet 9.} in
  imitating the proof of \cref{th:59}: start with a basis
  $\lst{v}1k$ of $U$, extend to a basis $\lst{v}1n$ of $V$
  and see that $\ann U=\Span{\dlst{v}{k+1}n}$.  Can you
  find a slick argument?
\end{proof}

Again annihilators swap the order of inclusions and sums
with intersections:
\begin{prop}
  \label{th:63}
  % properties of ann
  Let $U,W\leq V$.  Then
  \begin{compactenum}[(1)]
  \item If $U\leq W$ then $\ann W\leq\ann U$.
  \Item 
    \begin{align*}
      \ann(U+W)&=(\ann U)\cap(\ann W)\\
      (\ann U)+(\ann W)&\leq\ann(U\cap W)
    \end{align*}
    with equality if $V$ is finite-dimensional.
  \end{compactenum}
\end{prop}
\begin{proof}
  This is an exercise\footnote{Question 4(b) on sheet 9.} in
  imitating the proof of \cref{th:61}.
\end{proof}

What is the relation between annihilators and solution sets?
\begin{lem}
  \label{th:64}
  % adjunction
  Let $U\leq V$ and $E\leq V^{*}$ then $U\leq\sol E$ if and
  only if $E\leq\ann U$.
\end{lem}
\begin{proof}
  Both inclusions amount to saying $\alpha(u)=0$, for all
  $u\in U$ and $\alpha\in E$.
\end{proof}

With this in hand, we have:
\begin{thm}
  \label{th:65}
  % ann vs sol
  Let $U\leq V$ and $E\leq V^{*}$.  Then
  \begin{align*}
    U&\leq \sol(\ann U)\\
    E&\leq \ann(\sol E),
  \end{align*}
  with equality if $V$ is finite-dimensional.
\end{thm}
\begin{proof}
  Clearly $\ann U\leq \ann U$ so putting $E=\ann U$ in
  \cref{th:64} gives
  \begin{equation*}
    U\leq\sol(\ann U).
  \end{equation*}
  Similarly, $\sol E\leq \sol E$ so \cref{th:64} gives
  \begin{equation*}
    E\leq\ann(\sol E).
  \end{equation*}
  If $V$ is finite-dimensional,
  \begin{equation*}
    \dim\sol(\ann U)=\dim V-\dim\ann U=\dim U
  \end{equation*}
  so that $U=\sol(\ann U)$.  Similarly, $E=\ann(\sol E)$.
\end{proof}

\begin{rem}
  We can view $\ann$ and $\sol$ as maps:
  \begin{align*}
    \ann:\set{\text{subspaces of $V$}}&\to\set{\text{subspaces
                                        of $V^{*}$}}\\
    \sol:\set{\text{subspaces of $V^{*}$}}&\to\set{\text{subspaces
                                        of $V$}}.
  \end{align*}
  When $V$ is finite-dimensional, \cref{th:65} is telling us
  that these maps are mutually inverse bijections.  This has
  a beautiful application to geometry that you can see in
  MA30231.
\end{rem}

\section{Transposes}
\label{sec:transposes}

There is a duality construction for linear maps also: let
$V,W$ be vector spaces, $\phi\in L(V,W)$ and $\alpha\in
W^{*}$.  Then $\alpha\circ\phi:V\to\F$ is also linear, so
that $\alpha\circ\phi\in V^{*}$.  This prompts:
\begin{defn}
  Let $\phi\in L(V,W)$ be a linear map of vector spaces.  The
  \emph{transpose $\phi^T$ of $\phi$} is the map
  $\phi^T:W^{*}\to V^{*}$ given by
  \begin{equation*}
    \phi^T(\alpha):=\alpha\circ\phi,
  \end{equation*}
  for all $\alpha\in W^{*}$.
\end{defn}

\begin{lem}
  \label{th:66}
  % linearity  of transpose
  $\phi^T:W^{*}\to V^{*}$ is also a linear map.
\end{lem}
\begin{proof}
  Let $\alpha,\beta\in W^{*}$ and $\lambda\in\F$.  We must
  show that
  \begin{equation*}
    \phi^T(\alpha+\lambda\beta)=\phi^T(\alpha)+\lambda\phi^T(\beta).
  \end{equation*}
  Unravelling the definition, this means
  \begin{equation*}
    (\alpha+\lambda\beta)\circ\phi=\alpha\circ\phi+\lambda\beta\circ\phi.
  \end{equation*}
  This is an equality of functions and so holds exactly when
  \begin{equation*}
    (\alpha+\lambda\beta)(\phi(v))=\alpha(\phi(v))+\lambda(\beta(\phi(v))),
  \end{equation*}
  for all $v\in V$.  However, this last is true by the
  very definition of addition and scalar multiplication in
  $W^{*}$.
\end{proof}

\begin{xmpls}
\item[]
  \begin{compactenum}
  \item $\id_V^T=\id_{V^{*}}$.  Indeed,
    $\id_V^T(\alpha)=\alpha\circ\id_V=\alpha$, for all
    $\alpha\in V^{*}$.
  \item $(\psi\circ\phi)^T=\phi^T\circ\psi^T$.  Indeed,
    $(\psi\circ\phi)^T(\alpha)=\alpha\circ\psi\circ\phi=
    \phi^T(\alpha\circ\psi)=\phi^T(\psi^T(\alpha))$.
  \end{compactenum}
\end{xmpls}

Here is why $\phi^T$ is called the transpose of $\phi$:
\begin{prop}
  \label{th:67}
  % transpose in bases
  Let $V,W$ be finite-dimensional vector spaces and $\phi\in
  L(V,W)$ with matrix $A\in M_{m\times n}(\F)$ with respect
  to bases $\lst{v}1n$ and $\lst{w}1m$ of $V$ and $W$.

  Then $\phi^T$ has matrix $A^T$ with respect to the dual
  bases $\dlst{w}1m$ and $\dlst{v}1n$ of $W^{*}$ and $V^{*}$.
\end{prop}
\begin{proof}
  Let $\phi^T$ have matrix $B$ so that
  \begin{equation*}
    \phi^T(w^{*}_j)=\sum_{i=1}^nB_{ij}v^{*}_i.
  \end{equation*}
  Evaluate both sides of this at $v_k$ to get
  \begin{warpprint}
    \begin{align*}
      \phi^T(w^{*}_j)(v_k)&=B_{kj}\\
      \intertext{or, unravelling the definition of $\phi^T$,}
      w^{*}_j(\phi(v_k))&=B_{kj}.
    \end{align*}
\end{warpprint}
\begin{warpHTML}
  \begin{align*}
    \phi^T(w^{*}_j)(v_k)&=B_{kj}\\
  \end{align*}
  or, unravelling the definition of $\phi^T$,
  \begin{align*}
    w^{*}_j(\phi(v_k))&=B_{kj}.
  \end{align*}
\end{warpHTML}
  Now
  \begin{equation*}
    \phi(v_k)=\sum_{i=1}^mA_{ik}w_i
  \end{equation*}
  so that we also get
  \begin{equation*}
    w_j^{*}(\phi(v_k))=A_{jk}.
  \end{equation*}
  Comparing these we get $B_{kj}=A_{jk}$ whence $B=A^T$.
\end{proof}

The kernels and images of $\phi$ and $\phi^T$ are intimately
related via the annihilators and solution sets of
\S\ref{sec:solut-sets-annih}:

\begin{thm}
  \label{th:68}
  % ker and im
  Let $\phi\in L(V,W)$ be a linear map of vector spaces.
  Then
  \begin{compactenum}[(1)]
  \Item
    \begin{align*}
      \ker\phi&=\sol(\im\phi^T)\\
      \im\phi&\leq\sol(\ker\phi^T)
    \end{align*}
    with equality if $V,W$ are finite-dimensional.
  \Item
  \begin{align*}
    \ker\phi^T&=\ann(\im\phi)\\
    \im\phi^T&\leq\ann(\ker\phi)
  \end{align*}
  with equality if $V,W$ are finite-dimensional.    
  \end{compactenum}
\end{thm}
\begin{proof}
  We will prove (1) and leave (2) as an
  exercise\footnote{Question 5 on sheet 9.}.

  For the first equality, observe that $v\in\ker\phi$ if and
  only if $\phi(v)=0$ or, equivalently, by \cref{th:56},
  $\alpha(\phi(v))=0$, for all $\alpha\in W^{*}$, which is
  the same as $\phi^T(\alpha)(v)=0$, for all $\alpha\in
  W^{*}$, that is, $v\in\sol(\im\phi^T)$.

  If $V,W$ are finite-dimensional we now use this, along
  with rank-nullity and \cref{th:59}, to get
  \begin{equation*}
    \dim V-\dim\im\phi=
    \dim\ker\phi=\dim\sol(\im\phi^T)=\dim V-\dim\im\phi^T
  \end{equation*}
  so that
  \begin{equation}
    \label{eq:26}
    \rank\phi=\dim\im\phi=\dim\im\phi^T=\rank\phi^T.
  \end{equation}

  For $\im\phi\leq\sol(\ker\phi^T)$, let $w\in\im\phi$ and
  $\alpha\in\ker\phi^T$ so that $\alpha\circ\phi=0$ and
  $w=\phi(v)$, for some $v\in V$.  Then
  $\alpha(w)=\alpha(\phi(v))=(\alpha\circ\phi)(v)=0$ so that
  $w\in\sol(\ker\phi^T)$.  Thus
  $\im\phi\leq\sol(\ker\phi^T)$.

  Moreover, if $V,W$ are finite-dimensional, use
  \eqref{eq:26}, rank-nullity and \cref{th:59} to get
  \begin{equation*}
    \dim\im\phi=\dim\im\phi^T
    =\dim W-\dim\ker\phi^T=\dim\sol(\ker\phi^T).
  \end{equation*}
  We conclude that $\im\phi$ and $\dim\sol(\ker\phi^{T})$
  have the same dimension and so coincide.
\end{proof}

Along the way, we got \eqref{eq:26}:
\begin{cor}
  \label{th:69}
  Let $\phi\in L(V,W)$ be a linear map of finite-dimensional
  vector spaces.  Then
  \begin{equation*}
    \rank\phi=\rank\phi^T.
  \end{equation*}
\end{cor}
\begin{rem}
  This gives us a new take on an old result from Algebra
  1B (Chapter 3, Proposition~6).  Let $A\in M_{m\times n}(\F)$ be the matrix of $\phi$
  with respect to bases of $V$ and $W$ so that, by
  \cref{th:67}, $A^T$ is the matrix of $\phi^T$ with respect
  to the dual bases.  Then the rank of $\phi$ is the column
  rank of $A$ while the rank of $\phi^T$ is the column rank
  of $A^T$ which is the row rank of $A$.  Thus row rank and
  column rank coincide.
\end{rem}

The punchline of \cref{th:68} is that $\phi$ and $\phi^T$ have
``opposite'' properties.  For example:
\begin{prop}
  \label{th:70}
  % surj vs inj
  Let $\phi\in L(V,W)$ be a linear map of finite-dimensional
  vector spaces.  Then
  \begin{compactenum}[(1)]
  \item $\phi$ injects if and only if $\phi^T$ surjects.
  \item $\phi^T$ injects if and only if $\phi$ surjects.
  \end{compactenum}
\end{prop}
\begin{proof}
  For (1), $\phi$ injects if and only if $\ker\phi=\set0$
  while $\phi^T$ surjects if and only if
  $\dim\im\phi^T=\dim V$. By \cref{th:68}, the first happens
  if and only if $\sol(\im\phi^T)=\set0$ but, by
  \cref{th:59}, this is equivalent to the
  $\dim\im\phi^T=\dim V$.

  Item (2) is similar.
\end{proof}
\begin{rems}\item[]
  \begin{compactenum}
  \item This result is useful as it is sometimes easier to
    prove injectivity than surjectivity.
  \item With a bit more effort, we can do better than
    \cref{th:70}: for example, using \cref{th:56}, we can
    prove that \cref{th:70}(2) holds even in infinite
    dimensions.
  \end{compactenum}
\end{rems}

\chapter{Bilinearity}
\label{cha:bilinearity}

We give an introduction to a general theory of
``multiplication'' of vectors.

\section{Bilinear maps}
\label{sec:bilinear-maps}

\subsection{Definitions and examples}
\label{sec:definitions-examples}


\begin{defn}
  Let $U,V,W$ be vector spaces over a field $\F$.  A map
  $B:U\times V\to W$ is \emph{bilinear} if it is linear in
  each slot separately:
  \begin{align*}
    B(\lambda u_1+u_2,v)&=\lambda B(u_1,v)+B(u_2,v)\\
    B(u,\lambda v_1+v_2)&=\lambda B(u,v_1)+B(u,v_2),
  \end{align*}
  for all $u,u_1,u_2\in U$, $v,v_1,v_2\in V$ and
  $\lambda\in\F$.

  A bilinear map $U\times V\to\F$ is called a \emph{bilinear
    pairing}.

  A bilinear map $V\times V\to\F$ is called a \emph{bilinear
  form on $V$}.
\end{defn}

\begin{rem}
  A bilinear map $B:U\times V\to W$ has $B(u,0)=B(0,v)=0$,
  for all $u\in U$ and $v\in V$.  Indeed,
  \begin{equation*}
    B(u,0)=B(u,0+0)=B(u,0)+B(u,0)
  \end{equation*}
  and similarly for $B(0,v)$.
\end{rem}

\begin{xmpls}
\item[]
  \begin{compactenum}
  \item Matrix multiplication is bilinear:
    \begin{equation*}
      (A,B)\mapsto AB:M_{m\times n}(\F)\times M_{n\times
        k}(\F)\to M_{m\times k}(\F).
    \end{equation*}
  \item
    Composition of maps is bilinear:
    \begin{equation*}
      (\psi,\phi)\mapsto \psi\circ\phi: L(U,W)\times
      L(V,U)\to L(V,W).
    \end{equation*}
  \item Evaluation $(\alpha,v)\mapsto \alpha(v):V^{*}\times
    V\to\F$ is a bilinear pairing.
  \item Any \emph{real} inner product is a bilinear form (what goes
    wrong for complex inner products?).
  \item Let $A\in M_{m\times n}(\F)$ and define a bilinear
    pairing $B_A:\F^m\times\F^n\to\F$ by
    \begin{equation*}
      B_A(x,y)=\bx^TA\by.
    \end{equation*}
    This gives us a new use for matrices.
  \end{compactenum}
\end{xmpls}

\begin{notation}
  We let $\bil(U,V;W)$ denote the set of bilinear maps
  $U\times V\to W$.
\end{notation}

\begin{ex}
  Show that $\bil(U,V;W)\leq W^{U\times V}$.  Otherwise
  said, $\bil(U,V;W)$ is a vector space under pointwise
  addition and scalar multiplication.
\end{ex}

For the rest of the chapter we focus on the simplest case:
bilinear forms $B:V\times V\to\F$.

\subsection{Bilinear forms and matrices}
\label{sec:bilin-forms-matr}

\begin{defn}
  Let $V$ be a vector space over $\F$ with basis
  $\cB=\lst{v}1n$ and let $B:V\times V\to\F$ be a bilinear
  form.  The \emph{matrix of $B$ with respect to $\cB$} is
  $A\in M_{n\times n}(\F)$ given by
  \begin{equation*}
    A_{ij}=B(v_i,v_j),
  \end{equation*}
  for $\bw1{i,j}n$.
\end{defn}

The matrix $A$ along with $\cB$ tells the whole story:
\begin{prop}
  \label{th:71}
  % B and A
  Let $B:V\times V\to\F$ be a bilinear form with matrix $A$
  with respect to $\cB=\lst{v}1n$.  Then $B$ is completely
  determined by $A$: if $v=\sum_{i=1}^nx_iv_i$ and
  $w=\sum_{j=1}^ny_jv_j$ then
  \begin{equation*}
    B(v,w)=\sum_{i,j=1}^nx_iy_jA_{ij},
  \end{equation*}
  or, equivalently, for all $x,y\in\F^n$,
  \begin{equation*}
    B(\phi_{\cB}(x),\phi_{\cB}(y))=B_A(x,y)=\bx^TA\by.
  \end{equation*}
\end{prop}
\begin{proof}
  We simply expand out using the bilinearity of $B$:
  \begin{equation*}
    B(v,w)=\sum_{i,j=1}^nx_iy_jB(v_i,v_j)=\sum_{i,j=1}^nx_iy_jA_{ij}.
  \end{equation*}
\end{proof}

\begin{rems}
\item[]
  \begin{compactenum}
  \item When $V=\F^n$ and $\cB$ is the standard basis (so
    that $\phi_{\cB}=\id_{\F^n}$), this tells us that any
    bilinear form on $V$ is $B_{A}$ for some matrix $A\in
    M_{n\times n}(\F)$.
  \item There is a similar analysis for any bilinear map
    $B:U\times V\to W$.  In this case, $B$ is determined by
    $B(u_i,v_j)\in W$ for $\lst{u}1m$ a basis of $U$ and
    $\lst{v}1n$ a basis of $V$.
  \end{compactenum}
\end{rems}

How does $A$ change when we change basis of $V$?

\begin{prop}
  \label{th:72}
  Let $B:V\times V\to\F$ be a bilinear form with matrices
  $A$ and $A'$ with respect to bases $\cB$ and $\cB'$ of
  $V$.  Then
  \begin{equation*}
    A'=P^TAP
  \end{equation*}
  where $P$ is the change of basis matrix\footnote{See
    Definition 1 in Section 2.6 of Algebra 1B.} from $\cB$ to
  $\cB'$: thus $\phi_P=\phi_{\cB}^{-1}\circ\phi_{\cB'}$.
\end{prop}
\begin{proof}
  Since $\phi_{\cB'}=\phi_{\cB}\circ\phi_{P}$, we have
  \begin{multline*}
    \bx^TA'\by=B(\phi_{\cB'}(x),\phi_{\cB'}(y))=B(\phi_{\cB}(\phi_P(x)),\phi_{\cB}(\phi_P(y)))\\
    =B_A(\phi_P(x),\phi_P(y))=(P\bx)^TA(P\by)=\bx^T(P^TAP)\by,
  \end{multline*}
  for all $x,y\in\F^n$.  Taking $x=e_i$ and $y=e_j$, this
  gives $A'_{ij}=(P^TAP)_{ij}$ so that $A'=P^TAP$.
\end{proof}

This prompts:
\begin{defn}
  We say that matrices $A,B\in M_{n\times n}(\F)$ are
  \emph{congruent} if there is $P\in\GL(n,\F)$ such that
  \begin{equation*}
    B=P^TAP.
  \end{equation*}
\end{defn}

\begin{rem}
  The congruence relation should remind us of orthogonal
  diagonalisation but here there is no demand that
  $P^{-1}=P^T$.
\end{rem}

\section{Symmetric bilinear forms}
\label{sec:symm-bilin-forms}

\begin{defn}
  A bilinear form $B:V\times V\to\F$ is \emph{symmetric} if,
  for all $v,w\in V$,
  \begin{equation*}
    B(v,w)=B(w,v)
  \end{equation*}
\end{defn}

\begin{ex}
  If $V$ is finite-dimensional, $B$ is symmetric if and only
  if $B(v_i,v_j)=B(v_j,v_i)$, $\bw1{i,j}n$, for some basis
  $\lst{v}1n$ of $V$.

  Thus $B$ is symmetric if and only if its
  matrix with respect to some (and then any) basis is
  symmetric.
\end{ex}

\begin{xmpl}
  A real inner product is a symmetric bilinear form.
\end{xmpl}

\subsection{Rank and radical}
\label{sec:rank-radical}

\begin{defns}
  Let $B:V\times V\to\F$ be a symmetric bilinear form.

  The \emph{radical $\rad B$ of $B$} is given by
  \begin{equation*}
    \rad B:=\set{v\in V\st\text{$B(v,w)=0$, for all $w\in V$}}.
  \end{equation*}
  We shall shortly see that $\rad B\leq V$.

  We say that $B$ is \emph{non-degenerate} if $\rad B=\set0$.

  If $V$ is finite-dimensional, the \emph{rank} of $B$ is
  $\dim V-\dim \rad B$ (so that $B$ is non-degenerate if and only
  if $\rank B=\dim V$).
\end{defns}
\begin{rem}
  A real inner product is non-degenerate thanks to \cref{th:33}.
\end{rem}

Here is how to understand both the rank and the radical of
$B$.  We use $B$ to define a map $\beta:V\to V^{*}$ by
\begin{equation*}
  \beta(v)(w)=B(v,w),
\end{equation*}
for $v,w\in V$.  Then:
\begin{compactitem}
\item $\beta(v)\in V^{*}$ since $B$ is linear in the second
  slot.
\item $\beta:V\to V^{*}$ is linear since $B$ is linear in
  the first slot.
\item $\ker\beta=\set{v\in V\st\beta(v)=0}=\set{v\in V\st
    \text{$B(v,w)=0$ for all $w\in V$}}=\rad B$.  Thus $\rad B\leq V$
  and $\rank B=\rank\beta$ when $V$ is finite-dimensional.

  Moreover $B$ is non-degenerate if and only if $\beta$
  injects or, when $V$ is finite-dimensional, is an isomorphism.
\item Let $B$ have matrix $A$ with respect to a basis
  $\lst{v}1n$ of $V$.  Then
  \begin{equation*}
    \beta(v_j)(v_i)=B(v_j,v_i)=A_{ji}=A_{ij},
  \end{equation*}
  where we used the symmetry of $A$ in the last equality.
  It follows that
  \begin{equation*}
    \beta(v_j)=\sum_{i=1}^nA_{ij}v_i^{*}
  \end{equation*}
  so that $A$ is the matrix of $\beta$ with respect to the
  dual bases $\lst{v}1n$ and $\dlst{v}1n$ of $V$ and $V^{*}$.
\end{compactitem}



We learn from this how to compute the rank of $B$:
\begin{lem}
  \label{th:73}
  % rank B=rank A
  Let $B:V\times V\to\F$ be a symmetric bilinear form on a
  finite-dimensional vector space $V$ with matrix $A$ with
  respect to some basis of $V$.  Then
  \begin{equation*}
    \rank B=\rank A.
  \end{equation*}
  In particular, $B$ is non-degenerate if and only if $\det
  A\neq 0$.
\end{lem}

\begin{xmpls}
  We contemplate some symmetric bilinear forms on $\F^3$:
  \begin{compactenum}
  \item $B(x,y)=x_1y_1+x_2y_2-x_3y_3$.  With respect to the
    standard basis, we have
    \begin{equation*}
      A=
      \begin{pmatrix}
        1&0&0\\0&1&0\\0&0&-1
      \end{pmatrix}
    \end{equation*}
    so that $\rank B=3$.
  \item $B(x,y)=x_1y_2+x_2y_1$.  Here the matrix with
    respect to the standard basis is
    \begin{equation*}
      A=
      \begin{pmatrix}
        0&1&0\\1&0&0\\0&0&0
      \end{pmatrix}
    \end{equation*}
    so that $B$ has rank $2$ and radical $\Span{e_3}$.
  \item In general, $B(x,y)=\sum_{i,j=1}^3A_{ij}x_iy_j$ so
    we can read off $A$ from the coefficients of the $x_iy_j$.
  \end{compactenum}
\end{xmpls}


\subsection{Classification of symmetric bilinear forms}
\label{sec:class-symm-bilin}

\begin{convention}
  In this section, we work with a field $\F$ where $1+1\neq
  0$ so that $\half=(1+1)^{-1}$ makes sense.  This excludes,
  for example, the $2$-element field $\Z_2$.
\end{convention}

We can always find a basis with respect to which $B$ has a
diagonal matrix.  First a lemma:
\begin{lem}
  \label{th:9}
  Let $B:V\times V\to\F$ be a symmetric bilinear form such
  that $B(v,v)=0$, for all $v\in V$.  Then $B\equiv 0$.
\end{lem}
\begin{proof}
  Let $v,w\in V$.  We show that $B(v,w)=0$.  We know that
  $B(v+w,v+w)=0$ and expanding out gives us
  \begin{equation*}
    0=B(v,v)+2B(v,w)+B(w,w)=2B(v,w).
  \end{equation*}
  Since $2\neq 0$ in $\F$, $B(v,w)=0$.
\end{proof}

We can now prove:
\begin{thm}[Diagonalisation Theorem]
  \label{th:75}
  % diag thm
  Let $B$ be a symmetric bilinear form on a
  finite-dimensional vector space over $\F$.  Then there is
  a basis $\lst{v}1n$ of $V$ with respect to which the
  matrix of $B$ is diagonal:
  \begin{equation*}
    B(v_i,v_j)=0,
  \end{equation*}
  for all $\bw1{i\neq j}n$. We call $\lst{v}1n$ a
  \emph{diagonalising basis} for $B$.
\end{thm}
\begin{proof}
  This is reminiscent of the spectral theorem and we prove
  it in a similar way by inducting on $\dim V$.

  So our inductive hypothesis is that such a diagonalising
  basis exists for symmetric bilinear forms on a vector space of
  dimension $n$.

  Certainly the hypothesis holds vacuously if $\dim V=1$.
  Now suppose it holds for all vector spaces of dimension at
  most $n-1$ and that $B$ is a symmetric bilinear form on a
  vector space $V$ with $\dim V=n$.

  There are two possibilities: if $B(v,v)=0$, for all $v\in
  V$, then, by \cref{th:9}, $B(v,w)=0$, for all $v,w\in V$,
  and any basis is trivially diagonalising.

  Otherwise, there is $v_1\in V$ with $B(v_1,v_1)\neq 0$ and
  we set
  \begin{equation*}
    U:=\Span{v_1}, \qquad W:=\set{v\st B(v_1,v)=0}\leq V.
  \end{equation*}
  We have:
  \begin{compactenum}
  \item $U\cap W=\set0$: if $\lambda v_1\in W$ then
    $0=B(v_1,\lambda v_1)=\lambda B(v_1,v_1)$ forcing
    $\lambda=0$.
  \item $V=U+W$: for $v\in V$, write
    \begin{equation*}
      v=\tfrac{B(v_1,v)}{B(v_1,v_1)}v_1+(v-\tfrac{B(v_1,v)}{B(v_1,v_1)}v_1).
    \end{equation*}
    The first summand is in $U$ while
    \begin{equation*}
      B\bigl(v_1,v-\tfrac{B(v_1,v)}{B(v_1,v_1)}v_1\bigr)=B(v_1,v)-B(v_1,v)=0
    \end{equation*}
    so the second summand is in $W$.
  \end{compactenum}
  We conclude that $V=U\oplus W$.  We therefore apply the
  inductive hypothesis to $B_{|W\times W}$ to get a basis
  $\lst{v}2n$ of $W$ with $B(v_i,v_j)=0$, for $\bw2{i\neq
    j}n$.

  Now $\lst{v}1n$ is a basis of $V$ and, further, since
  $v_j\in W$, for $j>1$, $B(v_1,v_j)=0$ so that
  \begin{equation*}
    B(v_i,v_j)=0,
  \end{equation*}
  for all $\bw1{i\neq j}n$.

  Thus the inductive hypothesis holds at $\dim V=n$ and so
  the theorem is proved.
\end{proof}

\begin{rem}
  We can do a little better if $\F$ is $\C$ or $\R$: when
  $B(v_i,v_i)\neq 0$, either
  \begin{compactenum}
  \item If $\F=\C$, replace $v_i$ with
    $v_i/\sqrt{B(v_i,v_i)}$ to get a diagonalising basis
    with each $B(v_i,v_i)$ either $0$ or $1$.
  \item If $\F=\R$, replace $v_i$ with
    $v_i/\sqrt{\abs{B(v_i,v_i)}}$ to get a diagonalising
    basis with each $B(v_i,v_i)$ either $0$, $1$ or $-1$.
  \end{compactenum}
\end{rem}

\begin{cor}
  \label{th:10}
  Let $A\in M_{n\times n}(\F)$ be symmetric.  
  Then there is an invertible matrix $P\in\GL(n,\F)$ such
  that $P^TAP$ is diagonal.
\end{cor}
\begin{proof}
  We apply \cref{th:75} to $B_A$ to get a diagonalising
  basis $\mathcal{B}$ and then let $P$ be the change of
  basis matrix from the standard basis to $\mathcal{B}$.
  Now apply \cref{th:72}.
\end{proof}

\begin{rem}
  When $\F=\R$, \cref{th:10} also follows from \cref{th:50},
  the spectral theorem for symmetric matrices, which assures
  the existence of $P\in\rO(n)$ with $P^{-1}AP=P^TAP$ diagonal.
\end{rem}

\cref{th:75} also gives us a recipe for computing a
diagonalising basis: find $v_1$ with $B(v_1,v_1)\neq 0$,
compute $W=\set{v\st B(v_1,v)=0}$ and iterate.  Here are
some examples:

\begin{xmpls}\item[]
  \begin{compactenum}
  \item Problem: find a diagonalising basis for
    $B=B_A:\R^3\times\R^3\to\R$ where
    \begin{equation*}
      A=
      \begin{pmatrix}
        1&2&1\\2&0&1\\1&1&0
      \end{pmatrix}.
    \end{equation*}
    Solution: First notes that $A_{11}\neq 0$ so take
    $v_1=e_1$.  We seek $v_2$ among $y$ such that
    \begin{equation*}
      0=B(v_1,y)=
      \begin{pmatrix}
        1&0&0
      \end{pmatrix}A\by=
      \begin{pmatrix}
        1&2&1
      \end{pmatrix}\by=y_1+2y_2+y_3.
    \end{equation*}
    We try $v_2=(1,-1,1)$ for which
    \begin{equation*}
      B(v_2,y)=
      \begin{pmatrix}
        1&-1&1
      \end{pmatrix}A\by=
      \begin{pmatrix}
        0&3&0
      \end{pmatrix}\by=3y_{2}
    \end{equation*}
    In particular, $B(v_2v_2)=-3\neq 0$ so we can carry on.

    Now seek $v_3$ among $y$ such that
    $B(v_1,y)=B(v_2,y)=0$, that is:
    \begin{align*}
      y_1+2y_2+y_3&=0\\
      3y_2&=0.
    \end{align*}
    A solution is given by $v_3=(1,0,-1)$ and
    $B(v_3,v_3)=-1$.

    We have therefore arrived at the diagonalising basis
    $(1,0,0),(1,-1,1),(1,0,-1)$.

    Note that such bases are
    far from unique: starting from a different $v_1$ would
    give a different, equally correct answer.
  \item The same calculation solves another problem: find
    $P\in\GL(3,\R)$ such that $P^{T}AP$ is diagonal.

    Solution: we take our diagonalising basis as the columns
    of $P$ so that
    \begin{equation*}
      P=
      \begin{pmatrix}
        1&1&1\\0&-1&0\\0&1&-1
      \end{pmatrix}.
    \end{equation*}
    \begin{ex}
      Check that $P^TAP$ really is diagonal!
    \end{ex}
    \begin{rem}
      We could also solve this by finding an orthonormal
      basis of eigenvectors of $A$ but this is way more
      difficult because we would have to find the
      eigenvalues by solving a cubic equation.
    \end{rem}
  \item Now let us take
    \begin{equation*}
      A=
      \begin{pmatrix}
        1&2&3\\2&4&6\\3&6&9
      \end{pmatrix}
    \end{equation*}
    and find a diagonalising basis for $B=B_A$.

    Solution: As before, we can take $v_1=e_1$ and seek
    $v_2$ among $y$ with
    \begin{equation*}
      0=B(v_1,y)=y_1+2y_2+3y_3.
    \end{equation*}
    Let us try $v_2=(3,0,-1)$.  Then
    \begin{equation*}
      B(v_2,y)=
      \begin{pmatrix}
        3&0&-1
      \end{pmatrix}A\by=0,
    \end{equation*}
    for \emph{all} $y$.  Otherwise said, $v_2\in\rad B$.  We
    keep $v_2$ and try again with $v_3=(0,-3,2)$.  Again we
    find that $v_3\in\rad B$ and conclude that $v_1,v_2,v_3$
    are a diagonalising basis with $B(v_1,v_1)=1$ and
    $B(v_2,v_2)=B(v_3,v_3)=0$. 
  \item Here is a trick that can short-circuit these
    computations if there is a zero in an off-diagonal
    slot.  Take
    \begin{equation*}
      A=
      \begin{pmatrix}
        1&1&0\\1&0&1\\0&1&-1
      \end{pmatrix}
    \end{equation*}
    and seek a diagonalising basis for $B=B_A$.

    We can exploit the zero in the $(1,3)$-slot of $A$:
    observe that
    \begin{align*}
      B(e_1,e_1)&=1\\B(e_3,e_3)&=-1\\B(e_1,e_3)&=0
    \end{align*}
    so we are well on the way to getting a diagonalising
    basis starting with $e_1,e_3$.  To get the last basis
    vector, we seek $y\in\R^3$ with
    \begin{align*}
      0=B(e_1,y)&=y_1+y_2\\
      0=B(e_3,y)&=y_2-y_3.
    \end{align*}
    We solve these to get $y=(-1,1,1)$, for example, and so
    that $(1,0,0), (0,0,1), (-1,1,1)$ are a diagonalising
    basis and
    \begin{equation*}
      B(y,y)=1-2+2-1=0.
    \end{equation*}
  \end{compactenum}
\end{xmpls}

\subsection{Sylvester's Theorem}
\label{sec:sylvesters-theorem}

Let $B$ be a symmetric bilinear form on a real
finite-dimensional vector space.  We know that there is a
diagonalising basis $\lst{v}1n$ with each
$B(v_i,v_i)\in\set{\pm1,0}$ and would like to know how many
of each there are.  We give a complete answer.

\begin{defns}
  Let $B$ be a symmetric bilinear form on a \emph{real}
  vector space $V$.

  Say that $B$ is \emph{positive definite} if $B(v,v)>0$,
  for all $v\in V\setminus\set0$.

  Say that $B$ is \emph{negative definite} if $-B$ is
  positive definite.

  If $V$ is finite-dimensional, the \emph{signature} of $B$
  is the pair $(p,q)$ where
  \begin{align*}
    p&=\max\set{\dim U\st\text{$U\leq V$ with $B_{|U\times U}$
       positive definite}}\\
    q&=\max\set{\dim W\st\text{$W\leq V$ with $B_{|W\times W}$
       negative definite}}.
  \end{align*}
\end{defns}

\begin{rem}
  A symmetric bilinear form $B$ on $V$ is positive definite if
  and only if it is an inner product on $V$.
\end{rem}

The signature is easy to compute:
\begin{thm}[Sylvester's Law of Inertia]
  \label{th:76}
  % Sylvester
  Let $B$ be a symmetric bilinear form of signature $(p,q)$ on a
  finite-dimensional real vector space
  Then:
  \begin{compactitem}
  \item $p+q=\rank B$;
  \item any \emph{diagonal} matrix representing $B$ has $p$
    positive entries and $q$ negative
    entries (necessarily on the diagonal!).
  \end{compactitem}
\end{thm}
\begin{proof}
  Set $K=\rad B$, $r=\rank B$ and $n=\dim V$ so that $\dim
  K=n-r$.

  Let $U\leq V$ be a $p$-dimensional subspace on which $B$
  is positive definite and $W$ a $q$-dimensional subspace on
  which $B$ is negative definite.

  First note that $U\cap K=\set0$ since $B(k,k)=0$, for all
  $k\in K$.  Thus,
  by the dimension formula,
  \begin{equation*}
    \dim(U+K)=\dim U+\dim K=p+n-r.
  \end{equation*}
  Moreover, if $v=u+k\in U+K$, with $u\in U$ and $k\in K$,
  then $B(v,v)=B(u+k,u+k)=B(u,u)\geq 0$.

  From this we see that $W\cap (U+K)=\set0$: if $w\in W\cap(U+K)$
  then $B(w,w)\geq 0$ by what we just proved but also
  $B(w,w)\leq 0$ since $w\in W$.  Thus $B(w,w)=0$ and so, by
  definiteness on $W$, $w=0$.  Thus
  \begin{equation*}
    \dim W+(U+K)=\dim W+\dim(U+K)=q+n+p-r\leq\dim V=n
  \end{equation*}
  so that $p+q\leq r$.

  Now let $\lst{v}1n$ be a diagonalising basis of $B$ with
  $\hat{p}$ positive entries on the diagonal of the
  corresponding matrix representative $A$ of $B$ and
  $\hat{q}$ negative entries.  Then $B$ is positive definite
  on the $\hat{p}$-dimensional space
  $\Span{v_i\st B(v_i,v_{i})>0}$ (exercise!).  Thus
  $\hat{p}\leq p$.  Similarly, $\hat{q}\leq q$.

  However $r=\rank A$ is the number of non-zero entries on the
  diagonal, that is $r=\hat{p}+\hat{q}$.  We therefore have
  \begin{equation*}
    r=\hat{p}+\hat{q}\leq p+q=r
  \end{equation*}
  so that $p=\hat{p}$, $q=\hat{q}$ and $p+q=r$.
\end{proof}

\begin{xmpl}
  Find the rank and signature of $B=B_A$ where
  \begin{equation*}
    A=
    \begin{pmatrix}
      1&2&1\\2&0&1\\1&1&0
    \end{pmatrix}.
  \end{equation*}
  Solution: we have already found a diagonalising basis
  $v_1=(1,0,0), v_2=(1,-1,1), v_3=(1,0,-1)$ so we need only
  count how many $B(v_i,v_i)$ are positive and how many
  negative.  In this case, $B(v_1,v_1)=1>0$ while
  $B(v_2,v_2)=-3<0$ and $B(v_3,v_3)=-1<0$.  Thus the
  signature is $(1,2)$ while $\rank B=1+2=3$.
\end{xmpl}

\begin{rems}
\item[]
  \begin{compactenum}
  \item Here is a useful sanity check: symmetric bilinear
    $B$ of signature $(p,q)$ on an $n$-dimensional $V$ has
    $p,q,p+q\leq n$ (since $p,q,p+q$ are all dimensions of
    subspaces of $n$-dimensional $V$ or $V^{*}$).
  \item A symmetric bilinear form of signature $(n,0)$ on a
    real $n$-dimensional vector space is simply an inner
    product.
  \item In physics, the setting for Einstein's theory of
    special relativity is a $4$-dimensional real vector
    space (\emph{space-time}) equipped with a symmetric
    bilinear form of signature $(3,1)$.
  \end{compactenum}
\end{rems}


\section{Application: Quadratic forms}
\label{sec:quadratic-forms}

\begin{convention}
  We continue working with a field $\F$ where $1+1\neq
  0$.
\end{convention}

We can construct a function on $V$ from a bilinear form $B$
(which is a function on $V\times V$).
\begin{defn}
  A \emph{quadratic form} on a vector space $V$ over
  $\F$ is a function $Q:V\to\F$ of the form
  \begin{equation*}
    Q(v)=B(v,v),
  \end{equation*}
  for all $v\in V$, where $B:V\times V\to\F$ is a symmetric
  bilinear form.
\end{defn}

\begin{rem}
  For $v\in V$ and $\lambda\in\F$, $Q(\lambda v)=B(\lambda
  v,\lambda, v)=\lambda^2Q(v)$ so $Q$ is emphatically not a
  linear function!
\end{rem}

\begin{xmpls}
  Here are two quadratic forms on $\F^3$:
  \begin{compactenum}
  \item $Q(x)=x_1^2+x_2^2-x_3^2=B_A(x,x)$ where
    \begin{equation*}
      A=
      \begin{pmatrix}
        1&0&0\\0&1&0\\0&0&-1
      \end{pmatrix}.
    \end{equation*}
  \item $Q(x)=x_1x_2=B_A(x,x)$ where
    \begin{equation*}
      A=
      \begin{pmatrix}
        0&\half&0\\\half&0&0\\0&0&0
      \end{pmatrix}.
    \end{equation*}
  \end{compactenum}
\end{xmpls}

We can recover the symmetric bilinear form $B$ from its
quadratic form $Q$:
\begin{lem}
  \label{th:74}
  % Polarisation
  Let $Q:V\to\F$ be a quadratic form with $Q(v)=B(v,v)$ for
  a symmetric bilinear form $B$.  Then
  \begin{equation*}
    B(v,w)=\half\bigl(Q(v+w)-Q(v)-Q(w)\bigr),
  \end{equation*}
  for all $v,w\in V$.
  
  $B$ is called the \emph{polarisation of $Q$}.
\end{lem}
\begin{proof}
  Expand out to get
  \begin{equation*}
    Q(v+w)-Q(v)-Q(w)=B(v,w)+B(w,v)=2B(v,w).
  \end{equation*}
\end{proof}

Here is how to do polarisation in practice: any quadratic
form $Q:\F^n\to\F$ is of the form
\begin{equation*}
  Q(x)=\sum_{1\leq i\leq j\leq n}q_{ij}x_ix_j=\bx^{T}
  \begin{pmatrix}
    q_{11}&&\half q_{ji}\\&\ddots&\\\half q_{ij}&&q_{nn}
  \end{pmatrix}\bx
\end{equation*}
so that the polarisation is $B_A$ where
\begin{equation*}
  A_{ij}=A_{ji}=
  \begin{cases}
    q_{ii}&\text{if $i=j$;}\\
    \half q_{ij}&\text{if $i<j$}.
  \end{cases}
\end{equation*}

\begin{xmpl}
  Let $Q:\R^3\to\R$ be given by
  \begin{equation*}
    Q(x)=x_1^2+2x_2^2+2x_1x_2+x_1x_3.
  \end{equation*}
  Let us find the polarisation $B$ of $Q$, that is, we find
  $A$ so that $B=B_A$: we have $q_{11}=1$. $q_{22}=2$,
  $q_{12}=2$ and $q_{13}=1$ with all other $q_{ij}$
  vanishing so
  \begin{equation*}
    A=
    \begin{pmatrix}
      1&1&\half\\1&2&0\\\half&0&0
    \end{pmatrix}.
  \end{equation*}
\end{xmpl}
  
\begin{defns}
  Let $Q$ be a quadratic form on a finite-dimensional vector
  space $V$ over $\F$.

  The \emph{rank} of $Q$ is the rank of its polarisation.

  If $\F=\R$, the \emph{signature} of $Q$ is the signature
  of its polarisation.
\end{defns}

What does the diagonalisation theorem mean for a quadratic
form $Q$?  Observe:
\begin{compactitem}
\item Any $\alpha\in V^{*}$ can be squared to give a
  quadratic form: $\alpha^2:V\to\F$ given by
  $\alpha^2(v)=\alpha(v)^2$.  Note that this is indeed a quadratic
  form with polarisation $B(v,w)=\alpha(v)\alpha(w)$.
\item If $\lst{v}1n$ diagonalises the polarisation $B$ of
  $Q$ then
  $Q(\sum_i\lambda_iv_i)=\sum_iB(v_i,v_i)\lambda_i^2$ so
  that
  \begin{equation*}
    Q=\sum_{i=1}^nQ(v_i)(v_i^{*})^2.
  \end{equation*}
  That is, we have written $Q$ as a linear combination of
  $n$ \emph{linearly independent} squares.
\end{compactitem}

Let us now apply the classification results of
\S\ref{sec:symm-bilin-forms} and summarise the situation for
quadratic forms on vector spaces over our favourite fields:
\begin{thm}
  \label{th:77}
  % normal form
  Let $Q$ be a quadratic form with rank $r$ polarisation on
  a finite-dimensional vector space over $\F$.
  \begin{compactenum}[(1)]
  \item When $\F=\C$, there is a basis $\lst{v}1n$ of $V$
    such that
    \begin{equation*}
      Q(\sum_{i=1}^nx_iv_i)=\plst{x^2}1r.
    \end{equation*}
  \item When $\F=\R$ and $Q$ has signature $(p,q)$, there is
    a basis $\lst{v}1n$ of $V$ such that
    \begin{equation*}
       Q(\sum_{i=1}^nx_iv_i)=\plst{x^2}1p-x_{p+1}^2-\dots-x_r^2.
    \end{equation*}
  \end{compactenum}
\end{thm}

\begin{xmpl}
  Find the signature of $Q:\R^3\to\R$ given by
  \begin{equation*}
    Q(x)=x_1^2+x_2^2+x_3^2+2x_1x_3+4x_2x_3.
  \end{equation*}
  $Q$ has polarisation $B=B_A$ with
  \begin{equation*}
    A=
    \begin{pmatrix}
      1&0&1\\0&1&2\\1&2&1
    \end{pmatrix}.
  \end{equation*}
  Solution: exploit the zero in the $(1,2)$-slot of $A$ to
  see that $e_1,e_2,y=(-1,-2,1)$ is a diagonalising basis
  and so gives us a diagonal matrix representing $B$ with
  $Q(e_1)=Q(e_2)=1>0$ and $Q(y)=-4<0$ along the diagonal.
  So the signature is $(2,1)$.

  Here are two alternative techniques:
  \begin{compactenum}
  \item Orthogonal diagonalisation yields a diagonal matrix
    representing $B$ with the eigenvalues of $A$ down the
    diagonal so we just count how many positive and negative
    eigenvalues there are.

    In fact, $A$ has eigenvalues $1$ and $1\pm\sqrt{5}$.
    Since $\sqrt{5}>2$, $1-\sqrt{5}<0$ and we again conclude
    that the signature is $(2,1)$.

    \textbf{Danger}: this method needed us to solve a cubic
    equation which is already difficult.  For an $n\times n$
    $A$ with $n\geq 5$, this could be impossible!
  \item Finally, we could try and write $Q$ as a linear
    combination of linearly independent squares and then
    count the number of positive and negative coefficients.
    In fact,
    \begin{align*}
      Q(x)&=x_1^2+x_2^2+x_3^2+2x_1x_3+4x_2x_3\\
          &=(x_1+x_3)^2+x_2^2+4x_2x_3=(x_1+x_3)^2+(x_2+2x_3)^2-4x_3^2.
    \end{align*}
    But now we need to check that $x_1+x_3, x_2+2x_3,x_3$
    are linearly independent linear functionals on $\R^3$.
    Here \cref{th:60} comes to the rescue and says we only
    need show that
    $(\ker x_1+x_2)\cap(\ker x_2+2x_3)\cap(\ker
    x_3)=\set{0}$.  But $x_3=0=x_1+x_3=x_2+2x_3$ rapidly
    implies that each $x_i=0$ and we are done.  The
    coefficients of these squares are $1,1,-4$ and so, once
    more, we get that the signature is $(2,1)$.
  \end{compactenum}
\end{xmpl}

\end{document}




\appendix


\chapter{Further results}
\label{cha:appendicies}

We collect some further topics for which there was no time
in lectures.  All of the following material is
\emph{non-examinable}.

\section{More on sums and products}
\label{sec:more-sums-products}

\subsection{Sums, products and linear maps}
\label{sec:sums-products-linear}

The key point of the direct sum construction is that the
large vector space $\oplst{V}1k$ can be studied via their
simpler (lower dimensional) summands $V_i$.  We discuss two
incarnations of this principle.

\begin{prop}[Maps from a direct sum]\label{th:14}%maps from sum
  Let $\lst{V}1k,U$ be vector spaces and $\phi_i:V_i\to U$
  be linear maps, $\bw1ik$.

  Then there is a linear map $\phi:\oplst{V}1k\to U$ defined
  by
  \begin{equation}\label{eq:4}
    \phi(\lst{v}1k)=\plus{\phi_1(v_1)}{\phi_k(v_k)}
  \end{equation}
  and any $\phi\in L(\oplst{V}1k,U)$ arises this way for
  unique linear maps $\phi_i:V_i\to U$.
\end{prop}
\begin{proof}
  The map $\phi$ defined by \eqref{eq:4} is certainly linear
  and we can recover the $\phi_i$ from $\phi$ by noting that
  \begin{equation}\label{eq:5}
    \phi_i(v_i)=\phi(0,\dots,v_i,\dots,0).
  \end{equation}
  On the other hand, given $\phi\in L(\oplst{V}1k,U)$, we
  use \eqref{eq:5} to \emph{define} linear maps
  $\phi_i:V_i\to U$.  Then
  \begin{equation*}
    \vec{v}1k=(v_1,0,\dots,0)+\dots+(0,\dots,0,v_k)
  \end{equation*}
  and the linearity of $\phi$ establishes \eqref{eq:4}.
\end{proof}
\begin{rem}
  When the direct sum is internal, the $\phi_i$ are simply
  the restrictions $\phi_{|V_i}$ of $\phi$ to $V_i$.
\end{rem}

\begin{prop}[Maps to a direct sum]\label{th:13}%maps to prod
  Let $\lst{V}1k,W$ be vector spaces and $\phi_i:W\to V_i$
  be linear maps, $\bw1ik$.

  Then there is a linear map $\phi:W\to\oplst{V}1k$ given by
  \begin{equation*}
    \phi(w)=(\phi_1(w),\dots,\phi_k(w))
  \end{equation*}
  and all $\phi\in L(W,\oplst{V}1k)$ arise this way for
  unique linear maps $\phi_i:W\to V_i$.
\end{prop}
\begin{proof}
  This is almost obvious: the only issue is to see that
  $\phi$ is linear if and only if each component $\phi_i$ is
  linear.  But this comes straight from the definition of
  the vector space structure of $\oplst{V}1k$. 
\end{proof}

\begin{rem}
  With a little bit more work, these results can be made
  into linear isomorphisms of vector spaces of linear maps:
  \begin{align*}
    L(\oplst{V}1k,U)&\cong \bigoplus_{i=1}^kL(V_i,U)\\
    L(W,\oplst{V}1k)&\cong\bigoplus_{i=1}^kL(W,V_i).
  \end{align*}
\end{rem}

\subsection{Infinite sums and products}
\label{sec:infin-sums-prod}

Suppose now we have an arbitrary, possibly infinite,
collection $\col{V}{i}\cI$ of vector spaces.  How can we
make the direct sum or product of all the $V_i$?  It turns
out that we can make sense of the constructions but with the
twist that, when $\cI$ is infinite, we get two different
answers!

For this, let us start with a critical look at the Cartesian
product construction that lies at the heart of the direct
product. One fruitful way to think about this is to view
$\vec{x}1k\in\pplst{V}1k$ as a map
$v:\set{\rng1k}\to\bigcup_{i=1}^kV_i$, defined by
$v(i)=v_i$, with the property that $v(i)\in V_i$.
Equivalently, view $v\in\pplst{V}1k$ as a collection
$\col{v}i{\set{\rng1k}}$ with each $v_i\in V_i$.  Said like
this, we see how to generalise to arbitrary $\cI$ instead of
just $\set{\rng1k}$:
\begin{defn}
  Let $\col{V}i\cI$ be a collection of vector spaces indexed
  by a set $\cI$.  The \emph{direct product} of
  $\col{V}i\cI$ is the set of maps
  \begin{equation*}
    \prod_{i\in\cI}V_i:=\set{v:\cI\to\bigcup_{i\in\cI}V_i\st
      \text{$v(i)\in V_i$, for all $i\in\cI$}}.
  \end{equation*}
  It is a vector space under pointwise addition and scalar
  multiplication:
  \begin{align*}
    (v+w)(i)&:=v(i)+w(i)\\
    (\lambda v)(i)&:= \lambda v(i),
  \end{align*}
  where the operations on the right are those of $V_i$.
  Equivalently, in collection notation:
  \begin{align*}
    \col{v}i\cI+\col{w}i\cI&:=(v_i+w_i)_{i\in\cI}\\
    \lambda\col{v}i\cI&:=\col{\lambda v}i\cI.
  \end{align*}
\end{defn}

\begin{xmpl}
  If each $V_i=\F$, $\prod_{i\in\cI}V_i=\F^{\cI}$.
\end{xmpl}

In this context, \cref{th:13} remains true: any
linear map $\phi:W\to\prod_{i\in\cI}V_i$ is of the form
\begin{equation*}
  \phi(w)=(\phi_i(w))_{i\in\cI},
\end{equation*}
for unique linear maps $\phi_i:W\to V_i$.  However, a
moment's thought reveals that \cref{th:14} or
\cref{th:10} do not even make sense for infinite
products.  For example, in the context of
\cref{th:14}, $\sum_{i\in\cI}\phi_i(v_i)$ is not defined for
infinite $\cI$.

On the other hand, if all but finitely many $v_i$ vanish,
such a sum is defined.  This prompts:
\begin{defns}
  Let $\col{V}i\cI$ be a collection of vector spaces.
  \begin{compactenum}
  \item The \emph{support} of
    $v=\col{v}i\cI\in\prod_{i\in\cI}V_i$ is the subset
    $\supp(v)\sub\cI$ given by
    \begin{equation*}
      \supp(v):=\set{i\in\cI\st v_i\neq 0}.
    \end{equation*}
  \item The \emph{external direct sum} of $\col{V}i\cI$ is
    given by
    \begin{equation*}
      \bigoplus_{i\in\cI}V_i:=\set{v\in\prod_{i\in\cI}V_i\st\text{$\supp(v)$
        is finite}}
    \end{equation*}
  \end{compactenum}
\end{defns}

\begin{prop}
  \label{th:15}% inf dir sum
  $\bigoplus_{i\in\cI}V_i\leq\prod_{i\in\cI}V_i$.
\end{prop}
\begin{proof}
  The zero element of $\prod_{i\in\cI}V_i$ is
  $0=(0_i)_{i\in\cI}$ has empty (and so finite!) support
  whence $\bigoplus_{i\in\cI}V_i\neq\emptyset$.

  If $v,w\in\bigoplus_{i\in\cI}V_i$ then, if $v_i+w_i\neq0$,
  we must have at least one of $v_i,w_i$ non-zero so that
  \begin{equation*}
    \supp(v+w)\sub\supp(v)\cup\supp(w)
  \end{equation*}
  whence $\supp(v+w)$ is finite and
  $v+w\in\bigoplus_{i\in\cI}V_i$.

  Similarly, $\supp(\lambda v)=\supp(v)$, unless $\lambda=0$
  and then $\supp(\lambda v)$ is empty.  Thus
  $\bigoplus_{i\in\cI}V_i$ is also closed under scalar multiplication.
\end{proof}

Now \cref{th:14} holds for
$\bigoplus_{i\in\cI}V_i$: any linear map
$\phi:\bigoplus_{i\in\cI}V_i\to U$ is of the form
\begin{equation*}
  \phi(\col{v}i\cI)=\sum_{i\in\cI}\phi_i(v_i)
\end{equation*}
for unique linear maps $\phi_i:V_i\to U$.  Note that the sum
really is finite:
\begin{equation*}
  \sum_{i\in\cI}\phi_i(v_i)=\sum_{i\in\supp(v)}\phi_i(v_i).
\end{equation*}

Similarly, we can use the idea of \cref{th:10} to
define internal direct sums:
\begin{defn}
  Let $\col{V}i\cI$ be a collection of subspaces of a
  vector space $V$.  Then $V$ is the \emph{internal direct
    sum} of $\col{V}i\cI$ if the linear map
  $\Gamma:\bigoplus_{i\in\cI}V_i\to V$ given by
  \begin{equation*}
    \Gamma\bigl(\col{v}i\cI\bigr)=\sum_{i\in\cI}v_i
  \end{equation*}
  is an isomorphism.

  In this case, write $V=\bigoplus_{i\in\cI}V_i$.
\end{defn}

\begin{xmpl}
  Let $\R[t]$ be the vector space of real polynomials in $t$
  and set $M_n=\Span{t^n}$, for $n\in\N$.  Then
  \begin{equation*}
    \R[t]=\bigoplus_{n\in\N}M_n.
  \end{equation*}
\end{xmpl}

The case where each $V_i=\F$ will be of use later:
\begin{defn}
  Let $\cI$ be a set.  The \emph{free vector space over $\F$ on
    the set $\cI$} is
  \begin{equation*}
    \F_{\cI}:=\set{v\in\F^{\cI}\st\text{$\supp(v)$ is finite}}.
  \end{equation*}
\end{defn}


%% leftovers
If $V$ is a real inner product space and our original basis
was orthonormal, then the diagonalising basis we find this
way is also orthonormal so we have found a basis that
simultaneously diagonalises both $B$ and the inner product.
In general, the question of whether two symmetric bilinear
forms can be simultaneously diagonalised is a subtle one.






%%% Local Variables:
%%% TeX-command-extra-options: " -shell-escape"
%%% compile-command: "make install"
%%% End:
