linear_algebra.tex

\documentclass[a4paper]{article}

\def\npart{IB}

\def\ntitle{Linear Algebra}
\def\nlecturer{A.\ M.\ Keating}

\def\nterm{Michaelmas}
\def\nyear{2017}

\input{header}

\newcommand*{\M}{\matrixring}
\newcommand*{\spans}{\generation}

\newcommand*{\ann}{\circ}

\newcommand*{\basis}{\mathcal}

\newcommand*{\ip}{\innerproduct}

\theoremstyle{definition}
\newtheorem*{caution}{Caution}

\begin{document}

\input{titlepage}

\tableofcontents

\section{Vector Space}

\begin{convention}
  Throughout this course, $\mathbb{F}$ denotes a general field. If you wish, think of it as $\mathbb{R}$ or $\mathbb{C}$.
\end{convention}

\subsection{Definitions}

\begin{definition}[Vector space]\index{vector space}
  An $\mathbb{F}$-\emph{vector space} (or a vector space over $\mathbb{F}$) is an abelian group $(V, +)$ equipped with a function, called \emph{scalar multiplication}:
  \begin{align*}
    \mathbb{F}\times V &\to V \\
    (\lambda, v) &\mapsto \lambda\cdot v
  \end{align*}
  satisfying the axioms
  \begin{itemize}
  \item distributive over vectors: $\lambda(v_1+v_2) = \lambda(v_1+v_2)$,
  \item distributive over scalars: $(\lambda_1+\lambda_2)v= \lambda_1 v+\lambda_2 v$,
  \item $\lambda(\mu v) = \lambda \mu v$,
  \item $1\cdot v = v$.
  \end{itemize}
\end{definition}

The additive unit of $V$ is denoted by $\V 0$.

\begin{eg}\leavevmode
  \label{eg:matrix as V}
  \begin{enumerate}
  \item For all $n \in \mathbb{N}, \mathbb{F}^n$ is the space of column vectors of length $n$ with entries in $\mathbb{F}$. It is an vector space by entry-wise addition and entry-wise scalar multiplication.
  \item $\M_{m,n}(\mathbb{F})$, the set of $m\times n$ matrices with entries in $\mathbb{F}$, with the operation defined as entry-wise addition.
  \item For any set $X$, $\mathbb{R}^X = \{f: X \to \mathbb{R}\}$, the set of $\mathbb{R}$-valued functions on $X$, with addition and scalar multiplication defined pointwise. For instance, $(f_1+f_2)(x) = f_1(x)+f_2(x)$.
  \end{enumerate}
\end{eg}

\begin{ex}\leavevmode
  \begin{enumerate}
  \item Check the above examples satisfy the axioms.
    \item $0\cdot v = \V 0$ and $(-1)\cdot v = -v$ for all $v \in V$.
  \end{enumerate}
\end{ex}

\subsection{Vector Subspace}

\begin{definition}[Vector subspace]\index{vector space!subspace}
  Let $V$ be an $\mathbb{F}$-vector space. A subset $U \subseteq V$ is a \emph{subspace}, denoted $U \leq V$, if
  \begin{itemize}
  \item $\V 0 \in U$,
  \item $U$ is closed under addition: $\forall u_1, u_2 \in U, u_1+u_2 \in U$,
    \item $U$ is closed under scalar multiplication: $\forall u \in U, \forall \lambda \in \mathbb{F}, \lambda u \in U$.
  \end{itemize}
\end{definition}

\begin{ex}
  If $U$ is a subspace of $V$, then $U$ is also an $\mathbb{F}$-vector space.
\end{ex}

\begin{eg}\leavevmode
  \begin{enumerate}
  \item $V = \mathbb{R}^{\mathbb{R}}$, the set all functions from $\mathbb{R}$ to itself, has a (proper) subspace $C(\mathbb{R})$, the space of continuous functions on $\mathbb{R}$ as continuous functions are closed under addition and scalar multiplication. $C(\mathbb{R})$ in turn has a proper subspace $P(\mathbb{R})$, the set of all polynomials in $\mathbb{R}$.
    \item $\{(x_1,x_2,x_3) \in \mathbb{R}^3: x_1+x_2+x_3 = t\}$ where $t$ is some fixed constant is a subspace of $\mathbb{R}^3$ if and only if $t = 0$.
  \end{enumerate}
\end{eg}

\begin{proposition}
  Let $V$ be an $\mathbb{F}$-vector space, $U, W \leq V$. Then $U \cap W \leq V$.
\end{proposition}

\begin{proof}\leavevmode
  \begin{itemize}
  \item $\V 0 \in U, \V 0 \in V$ so $\V 0 \in U \cap W$.
    \item Suppose $u, w \in U \cap W$. Fix $\lambda, \mu \in \mathbb{F}$. As $U \leq V$, $\lambda u + \mu w \in U$. As $W \leq V$, $\lambda u +\mu w \in W$ so $\lambda u + \mu w \in U \cap W$. Take $\lambda = \mu = 1$ for vector addition and $\mu = 0$ for scalar multiplication.
  \end{itemize}
\end{proof}

\begin{eg}
  $V = \mathbb{R}^3, U = \{(x,y,z): x=0\}, W=\{(x,y,z):y=0\}$, then $U\cap W=\{(x,y,z):x=y=0\}$.
\end{eg}

\begin{note}
The union of a family of subspaces is \emph{almost never} a subspace. For example, $V = \mathbb{R}^2$, $U, V$ be $x$- and $y$-axis.
\end{note}

\begin{definition}[Sum of vector spaces]\index{vector space!sum}
  Let $V$ be an $\mathbb{F}$-vector space, $U, W \leq V$, the \emph{sum} of $U$ and $W$ is the set
  \[
    U + W = \{u+w: u\in U, w\in W\}
  \]
\end{definition}

\begin{eg}
  Use the definition from the previous example, $U+W=V$.
\end{eg}

\begin{proposition}
  $U+W \leq V$.
\end{proposition}

\begin{proof}\leavevmode
  \begin{itemize}
  \item $\V 0 = \V 0 + \V 0 \in U+W$,
  \item $u_1,u_1\in U, w_1,w_2\in W$, $(u_1+w_2) + (u_2+w_2) = (u_1+u_2)+(w_1+w_2) \in U+W$,
    \item similar for scalar multiplication. Left as an exercise.
  \end{itemize}
\end{proof}

\begin{note}
  $U+W$ is the smallest subspace containing both $U$ and $W$. This is because all elements of the form $u+w$ are in such a space by closure under addition.
\end{note}

\begin{definition}[Quotient vector space]\index{vector space!quotient}
  Let $V$ be an $\mathbb{F}$-vector space, $U \leq V$. The \emph{quotient space} $V/U$ is the abelian gropup $V/U$ equipped with scalar multiplication
  \begin{align*}
    \mathbb{F} \times V/U &\to V/U \\
    (\lambda, v+U) &\mapsto \lambda v+U
  \end{align*}
\end{definition}

\begin{proposition}
  This is well-defined and $V/U$ is an $\mathbb{F}$-vector space.
\end{proposition}

\begin{proof}
  First check it is well-defined. Suppose $v_1+U= v_2+U \in V/U$. Then $v_1-v_2\in U$. Now use closure under scalar multiplication and distributivity, $\lambda v_1 - \lambda v_2 = \lambda(v_1-v_2)\in U$ so $\lambda v_1 + U = \lambda v_2 +U\in V/U$.
  Now check vector space axioms of $V/U$, which will follow from the axioms for $V$:
  \begin{itemize}
  \item $\lambda(\mu(v+U)) = \lambda(\mu v+U) = \lambda(\mu v)+U = (\lambda\mu) v+U = \lambda\mu(v+U)$,
  \item other axioms are left as an exercise.
  \end{itemize}
\end{proof}

\subsection{Span, Linear Independence \& Basis}

\begin{definition}[Span]\index{span}
  Let $V$ be a $\F$-vector space, $S \subseteq V$ be a subset. The \emph{span} of $S$
  \[
    \spans S = \Big\{\sum_{s\in S} \lambda_s s : \lambda_s \in \F \Big\}
  \]
  is the set of all the finite linear combinations of elements (i.e.\ all but finitely many of the $\lambda$ are zero) of $S$.
\end{definition}

\begin{remark}
  $\spans S$ is the smallest subspace of $V$ containing all elements of $S$.
\end{remark}

\begin{convention}
  $\spans \emptyset = \{\V 0\}$
\end{convention}

\begin{eg}\leavevmode
  \begin{enumerate}
 \item $V=\R^3$, $S = \{(1,0,0),(0,1,2),(3,-2,-4)\}$, $\spans S = \{(a,b,2b): a,b\in \R \}$
 \item For any set $X$, $\R^X$ is a vector space. For $x \in X$, define $\delta_x: X \to \R, \delta_x(x) = 1, \delta_x(y) = 0 \: \forall y \neq x$, then
   \[
     \spans{\delta_x: x\in X} = \{f\in \R^X: f \text{ has finite support} \}
   \]
  \end{enumerate} 
\end{eg}

\begin{definition}[Span]
  $S$ spans $V$ if $\spans S = V$.
\end{definition}

\begin{definition}[Finite-dimensional]\index{finite-dimensional}
  $V$ is \emph{finite-dimensional} over $\F$ if it is spanned by a finite set.
\end{definition}

\begin{definition}[Linear independence]\index{linear independence}
  The vectors $v_1,\ldots, v_n$ are \emph{linearly independent} over $\F$ if
  \[
    \sum_{i=1}^n \lambda_i = 0 \Rightarrow \lambda_i = 0 \: \forall i
  \]

  A subset $S \subseteq V$ is \emph{linearly independent} if every finite subset of $S$ is linearly independent.

  A subset is \emph{linearly dependent} if it is not linearly independent.
\end{definition}

\begin{eg}
  In the first example above, the three vectors are not linearly independent.
\end{eg}

\begin{ex}
  The set $\{\delta_x: x \in X\}$ is linearly independent.
\end{ex}

\begin{definition}[Basis]\index{basis}
  $S$ is a \emph{basis} of $V$ if it is linearly independent and spans $V$.
\end{definition}

\begin{eg}\leavevmode
  \begin{enumerate}
  \item $\F^n$ has standard basis $\{e_1,e_2,\ldots,e_n\}$ where $e_i$ is the column vector with $1$ in the $i$th entry and $0$ elsewhere.
  \item $V=\C$ over $\C$ has natural basis $\{1\}$, but over $\R$ it has natural basis $\{1, i\}$.
  \item $V=P(\R)$, the space of real polynomials, has natural basis
    \[
      \{1, x, x^2, \dots \}.
    \]
    It is an exercise to check this carefully.
    \end{enumerate}
\end{eg}

\begin{lemma}
  Let $V$ be a $\F$-vector space. The vectors $v_1,\ldots,v_n$ form a basis of $V$ if and only if each vector $v\in V$ has a unique expression
  \[
    v = \sum_{i=1}^n \lambda_i v_i, \lambda_i \in \F.
  \]
  
\end{lemma}

\begin{proof}\leavevmode
  \begin{itemize}
  \item $\Rightarrow:$ Fix $v\in V$. The $v_i$ span $V$, so exists $\lambda_i \in \F$ such that $v = \sum \lambda_i v_i$. Suppose also $v = \sum \mu_i v_i$ for some $\mu_i \in \F$. Then the difference
  \[
    \sum (\mu_i - \lambda_i) v_i = \V 0.
  \]
  Since the $v_i$ are linearly independent, $\mu_i-\lambda_i = 0$ for all $i$.
\item $\Leftarrow:$ The $v_i$ span $V$ by assumption. Suppose $\sum_{i=1}^n \lambda_i v_i = \V 0$. Note that $\V 0 = \sum_{i=0}^n 0 \cdot v_i$. By appying uniqueness to $\V 0$, $\lambda_i = 0$ for all $i$.
  \end{itemize}
\end{proof}

\begin{lemma}
  If $v_1,\ldots, v_n$ spans $V$ over $\F$, then some subset of $v_1,\ldots,v_n$ is a basis of $V$ over $\F$.
\end{lemma}

\begin{proof}
  If $v_1,\ldots, v_n$ is linearly independent then done. Otherwise for some $\ell$, there exist $\alpha_1, \ldots, \alpha_{\ell-1} \in \F$ such that
  \[
    v_\ell = \sum_{i=1}^{\ell-1} \alpha_i v_i.
  \]
  (If $\sum \lambda_i v_i = 0$, not all $\lambda_i$ is zero. Take $\ell$ maximal with $\lambda_\ell \neq 0$, then $\alpha_i = -\frac{\lambda_i}{\lambda_\ell}$.)

  Now $v_1,\ldots,v_{\ell-1},v_{\ell+1},\ldots,v_n$ still span $V$. Continue iteratively until we have linear independence.
\end{proof}

\begin{theorem}[Steinitz Exchange Lemma]
  Let $V$ be a finite-dimensional vector space over $\F$. Take $v_1,\ldots,v_m$ to be linearly independent, $w_1,\ldots,w_n$ to span $V$. Then
  \begin{itemize}
  \item $m \leq n$, and
    \item reordering the $w_i$ if needed, $v_1,\ldots, v_m, w_{m+1},\ldots,w_n$ spans $V$.
  \end{itemize}
\end{theorem}

\begin{proof}
  Proceed by induction. Suppose that we have replaced $\ell \geq 0$ of the $w_i$. Reordering $w_i$ if needed, $v_1,\ldots,v_\ell,w_{\ell+1},\ldots,w_n$ spans $V$.
  \begin{itemize}
  \item If $\ell = m$, done.
  \item If $\ell < m$, then $v_{\ell+1} = \sum_{i=1}^\ell \alpha_i v_i + \sum_{i> \ell} \beta_i w_i$. As the $v_i$ are linearly independent, $\beta_i \neq 0$ for some $i$. After reordering, $\beta_{\ell+1} \neq 0$,
    \[
      w_{\ell+1} = \frac{1}{\beta_{\ell+1}} (v_{\ell+1}-\sum_{i\leq \ell} \alpha_i v_i - \sum_{i>\ell+1} \beta_i w_i).
    \]
    Thus $v_1,\ldots, v_\ell, v_{\ell+1},w_{\ell+2},\ldots, w_n$ also spans $V$. After $m$ steps, we will replace $m$ of the $w_i$ by $v_i$. Thus $m \leq n$.
  \end{itemize}
\end{proof}

\subsection{Dimension}

\begin{theorem}
  If $V$ is a finite-dimensional vector space over $\F$, then any two bases for $V$ have the same cardinality, which is called the \emph{dimension} of $V$, donoted $\dim_\F V$.
\end{theorem}

\begin{proof}
  If $v_1,\ldots, v_n$ and $w_1,\ldots,w_m$ are both bases, then $\{v_i\}$ is linearly independent and $\{w_i\}$ spans $V$ so $n \leq m$. Similarly $m \leq n$.
\end{proof}

\begin{eg}
  $\dim_\C \C = 1$, but $\dim_\R \C = 2$.
\end{eg}

\begin{lemma}
  Let \(V\) be a finite-dimensional \(\F\)-vector space. If \(w_1,\ldots,w_\ell\) is a linearly independent set of vectors, we can extend it to a basis \(w_1,\ldots,w_\ell,w_{\ell+1},\ldots,w_n\).
\end{lemma}

\begin{proof}
  Apply Steinitz exchange lemma to \(w_1,\ldots, w_\ell\) and any basis \(v_1,\ldots, v_n\).

  Or more direcly, if \(V=\langle w_1,\ldots, w_\ell \rangle\), done. Otherwise take \(v_{\ell+1} \in V\setminus\langle w_1,\ldots, w_\ell\rangle\). Now \(w_1,\ldots, w_\ell,w_{\ell+1}\) is linearly independent. Iterate.
\end{proof}

\begin{corollary}
  Let \(V\) be a finite-dimensional vector space of dimension \(n\). Then
  \begin{enumerate}
  \item Any linearly independent set of vectors has at most \(n\) elements, with equality if and only if the set is a basis.
  \item Any spanning set of vectors has at least \(n\) elements, with equaility if and only if the set is a basis.
  \end{enumerate}
\end{corollary}

\begin{slogan}
  Choose the best basis for the job.
\end{slogan}

\begin{theorem}
  Let \(U, W\) be subspaces of \(V\). If \(V\) and \(W\) are finite-dimensional, so is \(U+W\) and
  \[
\dim(U+W) = \dim U + \dim W - \dim(U\cap W).
  \]
\end{theorem}

\begin{proof}
  Pick basis \(v_1,\ldots, v_\ell\) of \(U\cap W\). Extend it to basis \(v_1,\ldots,v_\ell,u_1,\ldots,u_m\) of \(U\) and \(v_1,\ldots,v_\ell,w_1,\ldots,w_n\) of \(W\). Claim \(v_1,\ldots, v_\ell,u_1,\ldots,u_m,w_1,\ldots,w_n\) is a basis for \(U+W\):
  \begin{itemize}
  \item spanning: if \(u\in U\), then \(u= \sum \alpha_iv_i + \sum \beta_iu_i\) and if \(w\in W\), \(w = \sum_{}^{}\gamma_iv_i + \sum_{}^{}\delta_iw_i\), so \(u+w = \sum_{}^{}(\alpha_i + \gamma_i)v_i + \sum_{}^{}\beta_iu_i + \sum_{}^{}\delta_iu_i\).
  \item linear independence: assume \(\sum \alpha_iv_i + \sum \beta_iu_i+ \sum \gamma_iw_i=0\). Rearrange, \(\sum\alpha_iv_i + \sum\beta_iu_i = -\sum\gamma_iw_i \in U\cap W\) so it equals to \(\sum\delta_iv_i\) for some \(\delta_i\in \F\) because \(v_i\) is a basis for \(U\cap W\). As \(v_i\) and \(w_i\) are linearly independent, \(\gamma_i=\delta_i=0\) for all \(i\). Thus \(\sum\alpha_iv_i + \sum\beta_iv_i=0\), so \(\alpha_i=\beta_i=0\) since \(v_i\) and \(u_i\) form a basis for \(U\).
  \end{itemize}
\end{proof}

\begin{theorem}
  Let \(V\) be a finite-dimensional vector space over \(\F\) and \(U \leq V\), then \(U\) and \(V/U\) are also finite-dimensional and
  \[
\dim V = \dim U + \dim V/U.
  \]
\end{theorem}

\begin{proof}
  Left as an exercise. Outline: first show \(U\) is finite-dimensional, then let \(u_1,\ldots,u_\ell\) be a basis for \(U\). Extend it to a basis for \(V\), say \(u_1,\ldots,u_\ell,w_{\ell+1},\ldots,w_n\) of \(V\). Check \(w_{\ell+1}+U,\ldots,w_n+U\) form a basis for \(V/U\).
\end{proof}

\begin{corollary}
  If \(U\) is a proper subspace of \(V\), which is finite-dimensional, then \(\dim U < \dim V\).
\end{corollary}

\begin{proof}
  \(V/U \neq 0\) so \(\dim V/U > 0\).
\end{proof}

\subsection{Direct Sum}

\begin{definition}[Direct sum]\index{vector space!sum!direct}
  Let \(V\) be a vector space over \(\F\), \(U, W\leq V\). Then
  \[
    V = U \oplus W
  \]
  if every element of \(V\) can be written as \(v=u+w\) for some unique \(u\in U, w\in W\). This is called the \emph{internal direct sum}. \(W\) is a \emph{direct complement} of \(U\) in \(V\).
\end{definition}

\begin{lemma}
  Suppose \(U,W\leq V\), TFAE:
  \begin{enumerate}
  \item \(V = U \oplus W\),
  \item \(V=U+W\) and \(U\cap W = 0\),
  \item Given \(\basis B_1\) any basis of \(U\), \(\basis B_2\) any basis of \(V\), \(\basis B_1 \cap \basis B_2 = \emptyset\) and \(\basis B = \basis B_1\cup \basis B_2\) is a basis of \(V\).
  \end{enumerate}
\end{lemma}

\begin{proof}\leavevmode
  \begin{itemize}
  \item \(2 \Rightarrow 1\): any \(v\in V\) is \(u+w\) for some \(u\in U, w\in W\). Suppose \(u_1+w_1=u_2+w_2\), then \(u_1-u_2 = w_2-w_1 \in U\cap W = 0\). Thus \(u_1=u_2,w_1=w_2\).
  \item \(1 \Rightarrow 3\): \(\basis B\) spans as any \(v\in V\) is \(u+w\). Write \(u\) in terms of \(\basis B_1\) and \(w\) in terms of \(\basis B_2\). Then \(u+w\) is a linear combination of elements of \(\basis B\). To show \(\basis B\) is linearly independent, suppose \(\sum_{v\in \basis B} \lambda_v v = \V 0 = \V 0_V + \V 0_W\). Write LHS as \(\sum_{v\in \basis B_1} \lambda_vv + \sum_{v\in \basis B_2}\lambda_vv\). By uniqueness of expression, \(\sum_{v\in \basis B_1}\lambda_vv=\V 0_V\) and \(\sum_{w\in \basis B_2}\lambda_ww=\V 0_w\). As \(\basis B_1, \basis B_2\) are bases, all of the \(\lambda_v, \lambda_w\) are zero.
  \item \(3 \Rightarrow 2\): if \(v\in V, v=\sum_{x\in V}\lambda_xx = \sum_{u\in \basis B_1}\lambda_uu + \sum_{w\in \basis B_1}\lambda_ww\) so \(v\in U+W\). Conversely, if \(v\in U\cap W, v = \sum_{u\in \basis B_1}\lambda_uu=\sum_{w\in \basis B_2}\lambda_ww\) so all \(\lambda_u, \lambda_v\) are zero since \(\basis B_1\cup \basis B_2\) is linearly independent.
  \end{itemize}
\end{proof}

\begin{lemma}
  Let \(V\) be a finite-dimensional vector space over \(\F\) and \(U\leq V\). Then there exists a direct complement to \(U\) in \(V\).
\end{lemma}

\begin{proof}
  Let \(u_1,\ldots, u_\ell\) be a basis for \(U\). Extend this to a basis \(u_1,\ldots, u_\ell,w_{\ell+1},\ldots,w_n\) for \(V\). Then \(\spans{w_{\ell+1},\ldots,w_n}\) is a direct complement of \(U\).
\end{proof}

\begin{caution}
  Direct complements are \emph{not} unique.
\end{caution}

\begin{definition}[Direct sum]\index{vector space!direct sum}
  Suppose \(V_1,\ldots, V_\ell \leq V\), then the sum
  \[
    \sum_i V_i = V_1+\cdots+V_\ell = \{v_1+\cdots+v_\ell: v_i\in V_i\}.
  \]
  is \emph{direct} if
  \[
    v_1+\cdots+v_\ell = v_1'+\cdots+ v_\ell' \Rightarrow v_i = v_i' \text{ for all } i.
  \]
  In which case it is denoted
  \[
    V = \bigoplus_{i=1}^\ell V_i.
  \]
\end{definition}

\begin{ex}
  \(V_1,\ldots, V_\ell \leq V\), TFAE:
  \begin{enumerate}
  \item The sum \(\sum_i V_i\) is direct,
  \item \(V_i \cap \sum_{j\neq i}V_j = 0\) for all \(i\),
  \item For any basis \(B_i\) of \(V_i\), the union \(B=\bigcup_{i=1}^\ell B_i\) is a basis for \(\sum_i V_i\).
  \end{enumerate}
\end{ex}

\begin{definition}[Direct sum]\index{vector space!direct sum}
  Let \(U, W\) be vector spaces over \(\F\). The \emph{external direct sum} is
  \[
    U\oplus W = \{(u,w): u\in U, w\in W\}
  \]
  with pointwise addition and scalar multiplication.
\end{definition}

\section{Linear Map}

\subsection{Definitions}

\begin{definition}[Linear map]\index{linear map}
  \(V, W\) two \(\F\)-vector space, a map \(\alpha: V\to W\) is \emph{linear} if
  \begin{itemize}
  \item \(\alpha(v_1 + v_2) = \alpha(v_1) + \alpha(v_2)\),
  \item \(\alpha(\lambda v) = \lambda \alpha(v)\).
  \end{itemize}
  This is equivalent to
  \[
\alpha(\lambda_1v_1+ \lambda_2v_2) = \lambda_1\alpha(v_1) + \lambda_2\alpha(v_2).
  \]
\end{definition}

\begin{eg}\leavevmode
  \begin{enumerate}
  \item Given an \(n\times m\) matrix \(A\) with coefficients in \(\F\), the map \(\alpha: \F^m\to \F^n, v\to Av\).
  \item Differentiation \(D: P(\R) \to P(\R), f\mapsto \frac{df}{dx}\).
  \item Integration \(I: C[0,1] \to C[0,1], f \mapsto I(f)\) where \(I(f)(x) = \int_0^x f(t)dt\).
  \item Fix \(x\in [0,1]\), the map \(C[0,1]\to \R, f\mapsto f(x)\).
  \end{enumerate}
\end{eg}

\begin{note}[Categoricity of \(\mathbf{Vect}_\F\)]
  Suppose \(U, V, W\) are \(\F\)-vector spaces, then
  \begin{enumerate}
  \item \(\id: V\to V\) is linear.
  \item Given \(U \stackrel{\alpha}{\to} V \stackrel{\beta}{\to} W\), if \(\alpha, \beta\) are linear then so is \(\beta \compose \alpha\).
  \end{enumerate}
\end{note}

\begin{lemma}[Free functor \(\mathbf{Set} \to \mathbf{Vect}_\F\)]
  Suppose \(V, W\) are \(\F\)-vector spaces and \(\basis B\) is a basis for \(V\). If \(\alpha_0: \basis B\to W\) is \emph{any} map, then there is a \emph{unique} linear map \(\alpha: V\to W\) extending \(\alpha_o\).
\end{lemma}

\begin{proof}
  Let \(v\in V\). Write \(v = \sum \lambda_iv_i\) in a unique way. By linearity \(\alpha(v) = \alpha(\sum \lambda_iv_i) = \sum \lambda_i \alpha(v_i) = \sum \lambda_i \alpha_0(v_i)\). Uniqueness follows.
\end{proof}

\begin{note}\leavevmode
  \begin{itemize}
  \item This is true for infinite-dimensional vector spaces as well.
  \item Very often, to define a linear map, define it on a basis and extend it linearly to the vector space.
  \item Two linear maps \(\alpha_1,\alpha_2: V\to W\) are equal if and only if they agree on a basis.
  \end{itemize}
\end{note}

\subsection{Isomorphism of Vector Spaces}

\begin{definition}[Isomorphism]\index{isomorphism}
  Given \(V, W\) two \(\F\)-vector spaces, the map \(\alpha:V\to W\) is an \emph{isomorphism} if it is linear and bijective, denoted \(V \cong W\).
\end{definition}

\begin{lemma}
  \(\cong\) is an equivalence relation on the class of all \(\F\)-vector spaces.
\end{lemma}

\begin{proof}\leavevmode
  \begin{itemize}
  \item symmetric: obvious.
  \item reflexive: blah blah in lecture. Left as an exercise to reader.
  \item transitive: obvious.
  \end{itemize}
\end{proof}

\begin{theorem}
  If \(V\) is an \(\F\)-vector space, then \(V \cong \F^n\) for some \(n\).
\end{theorem}

\begin{proof}
  Choose a basis for \(V\), say \(v_1,\ldots, v_n\). Define a map
  \begin{align*}
    V &\to \F^n \\
    \sum_{i}^{ }\lambda_iv_i &\mapsto (\lambda_1,\ldots,\lambda_n)
  \end{align*}
which is an isomorphism.
\end{proof}

\begin{remark}
  Choosing an isomorphism \(V \cong \F^n\) is equivalent to choosing a basis for \(V\), i.e.\ there is a bijection
  \[
    \{\alpha\in\Hom(V,\F^n), \alpha\text{ bijective}\} \leftrightarrow \{\text{bases of } V\}.
  \]
\end{remark}

\begin{theorem}
  Given two finite-dimensional \(\F\)-vector spaces \(V, W\), they are isomorphic if and only if they have the same dimension.
\end{theorem}

\begin{proof}\leavevmode
  \begin{itemize}
  \item \(\Leftarrow\): \(V \cong \F^{\dim V} = \F^{\dim W} \cong W\).
  \item \(\Rightarrow\): let \(a:V\to W\) be an isomorphism and \(\basis B\) be a basis for \(V\). Claim \(\alpha(\basis B)\) is a basis for \(W\): \(\alpha(\basis B)\) spans \(W\) due to surjectivity and \(\alpha(\basis B)\) is linearly independent due to injectivity.
  \end{itemize}
\end{proof}

\begin{definition}[Kernel \& Image]\index{linear map!kernel}\index{linear map!image}
  Given \(\alpha: V\to W\),
  \begin{itemize}
  \item \(N(\alpha) = \ker \alpha = \{v\in V: \alpha(v) = 0\} \leq V\),
  \item \(\im \alpha = \{w\in W: \exists v\in V, \alpha(v) = w \} \leq W\).
  \end{itemize}
\end{definition}

\begin{proposition}\leavevmode
  \begin{itemize}
  \item \(\alpha\) is injective if and only if \(N(\alpha) = 0\),
  \item \(\alpha\) is surjective if and only if \(\im \alpha = W\).
  \end{itemize}
\end{proposition}

\begin{proof}
  Easy.
\end{proof}

\begin{eg}
  Let \(\alpha: C^\infty(\R) \to C^\infty(\R), \alpha(f)(t) = f''(t)+2f'(t)+5f(t)\). \(\ker \alpha = \{f:f''+2f'+5f=0\}\) and \(g\in \im \alpha\) if and only if there exists an \(f\) such that \(f''+2f'+5f=g\).
\end{eg}

\begin{theorem}[First Isomorphism Theorem]\index{isomorphism}
  Let \(\alpha: V\to W\) be a linear map. It induces an isomprhism
  \begin{align*}
    \bar \alpha: V/\ker \alpha &\to \im \alpha \\
    v + \ker \alpha &\mapsto \alpha(v)
  \end{align*}
\end{theorem}

\begin{proof}
  Check the following:
  \begin{itemize}
  \item \(\bar \alpha\) is well-defined,
  \item \(\bar \alpha\) is linear: immediate from linearity of \(\alpha\),
  \item \(\bar \alpha\) is surjective.
  \end{itemize}
\end{proof}

\begin{definition}[Rank \& Nullity]\index{linear map!rank}\index{linear map!nullity}\leavevmode
  \begin{itemize}
  \item \(r(\alpha) = rk(\alpha) = \dim( \im \alpha)\) is the \emph{rank} of \(\alpha\),
  \item \(n(\alpha) = \dim N(\alpha)\) is the \emph{nullity} of \(\alpha\).
  \end{itemize}
\end{definition}

\begin{theorem}[Rank-nullity]
  Let \(U, V\) be \(\F\)-vector spaces, \(\dim U < \infty\). Let \(\alpha:U\to V\) be a linear map. Then
  \[
\dim U = r(\alpha) + n(\alpha).
  \]
\end{theorem}

\begin{proof}
  \(U/\ker \alpha \cong \im \alpha\) so \(\dim U - \dim (\ker \alpha) = \dim (\im \alpha)\). Rearrange.
\end{proof}

\begin{lemma}
  Let \(V, W\) be \(\F\)-vector spaces with equal, finite dimension. Let \(\alpha:V\to W\) be linear, then TFAE:
  \begin{enumerate}
  \item \(\alpha\) is injective,
  \item \(\alpha\) is surjective,
  \item \(\alpha\) is an isomorphism.
  \end{enumerate}
\end{lemma}

\begin{proof}
  Rank-nullity theorem.
\end{proof}

\subsection{Linear Maps as Vector Space}

Suppose \(V\) and \(W\) are \(\F\)-vector spaces. Let \(L(V,W) = \{\alpha:V\to W, \alpha \text{ linear}\}\).

\begin{proposition}
  \(L(V,W)\) is an \(\F\)-vector space, under operations
  \begin{align*}
    (\alpha_1+\alpha_2)(v) &= \alpha_1(v) + \alpha_2(v) \\
    (\lambda\alpha)(v) &= \lambda(\alpha(v))
  \end{align*}
\end{proposition}

\begin{proof}
  \(\alpha_1+\alpha_2, \lambda\alpha\) as above are well-defined linear maps. The vector space axioms can be easily checked.
\end{proof}

\begin{proposition}
  \label{prop:dimension of linear map space}
  If both \(V\) and \(W\) are finite-dimensional over \(\F\) then so is \(L(V,W)\) and \(L(V,W) = \dim V \cdot \dim W\).
\end{proposition}

\begin{proof}
  See Lemma~\ref{cor:dim of hom}.
\end{proof}

\subsubsection{Matrices, an Interlude}

\begin{definition}[Matrix]\index{matrix}
  An \emph{\(m\times n\) matrix} over \(\F\) is an array with \(m\) rows and \(n\) columns with entries in \(\F\). We write
  \[
A = (a_{ij}), a_{ij}\in\F, 1\leq i \leq m, 1\leq j \leq n.
  \]
\end{definition}

\begin{definition}
  \(\M_{m,n}(\F)\) is the set of all such \(m\times n\) matrices.
\end{definition}

\begin{proposition}
  \(\M_{m,n}(\F)\) is an \(\F\)-vector space and \(\dim \M_{m,n}(\F) = m\cdot n\).
\end{proposition}

\begin{proof}
  See the \hyperref[eg:matrix as V]{example} on page~\pageref{eg:matrix as V} for the proof of vector space axioms. For the dimensional claim, a standard basis for \(\M_{m,n}(F)\) is
  \[
    E_{ij}=
    \begin{pmatrix}
      0 & \dots & 0 \\
      \vdots & \ddots & \vdots \\
      0 & 1 & 0 \\
      \vdots & \ddots & \vdots \\
      0 & \dots & 0 
    \end{pmatrix}
  \]
  with \(1\) in the \((i,j)\)th entry so \(a_{ij} = \sum_{i,j}^{} a_{ij}E_{ij}\), from which span and linear independence follow. The basis has cardinality \(m\cdot n\).
\end{proof}

\subsubsection{Representation of Linear Maps by Matrices}

Let \(V\) and \(W\) be finite-dimensional \(\F\)-vector space, \(\alpha: V\to W\) linear. Let \(\basis B = \{v_1,\ldots,v_n\}\) be a basis for \(V\), \(\basis C = \{w_1,\ldots,w_m\}\) be a basis for \(W\). If \(v=\sum_{i}\lambda_iv_i \in V\), write
\[
[v]_{\basis B} =
\begin{pmatrix}
  \lambda_1 \\
  \vdots \\
  \lambda_n
\end{pmatrix}
\in \F^n
\]
which is called the \emph{coordinate vector of \(v\) with respect to \(\basis B\)}. Similarly \([w]_{\basis C}\in \F^m\).

\begin{definition}[Matrix representation]\index{linear map!matrix representation}
  \([\alpha]_{\basis B, \basis C}\) is the matrix representation of \(\alpha\) with respect to \(\basis B\) and \(\basis C\) with
  \begin{align*}
    [\alpha]_{\basis B, \basis C} &= \Big( [\alpha(v_1)]_{\basis C} \: \Big| \: [\alpha(v_2)]_{\basis C} \: \Big | \: \cdots \: \Big| \: [\alpha(v_n)]_{\basis C} \Big) \\
                                  &= (a_{ij})
  \end{align*}
\end{definition}

The matrix says
\[
  \alpha(v_j) = \sum_{i}^{ }a_{ij}w_i.
\]

\begin{lemma}
  For any \(v\in V\),
  \[
[\alpha(v)]_{\basis C} = [\alpha]_{\basis B, \basis C}\cdot [v]_{\basis B}
  \]
  where \(\cdot\) is matrix multiplication.
\end{lemma}

\begin{proof}
  Fix \(v =\sum_{j=1}^{n}\lambda_jv_j \in V\), so
  \[
[v]_{\basis B} =
\begin{pmatrix}
  \lambda_1 \\
  \vdots \\
  \lambda_n
\end{pmatrix}
\]
\begin{align*}
  \alpha(v) &= \alpha\left( \sum_{j}^{ }\lambda_jv_j \right) \\
            &= \sum_{j}^{ }\lambda_j\alpha(v_j) \\
            &= \sum_{j}^{ }\lambda_j\left( \sum_{i}^{ }\alpha_{ij}w_i \right) \\
            &= \sum_{i}^{ }\left( \sum_{j}^{} a_{ij}\lambda_j \right) w_i
\end{align*}
so the \(i\)th entry of \(\alpha(v)\) is the \(i\)th entry of \([\alpha]_{\basis B, \basis C} \cdot [v]_{\basis B}\).
\end{proof}

\begin{lemma}
  Suppose \(U \stackrel{\beta}{\to} V \stackrel{\alpha}{\to} W\) with \(\alpha, \beta\) linear, with \(\alpha \compose \beta: U\to W\). Let \(\basis A, \basis B, \basis C\) be bases for \(U,V,W\) respectively. Then
  \[
    [\alpha\compose\beta]_{\basis A, \basis C} = [\alpha]_{\basis B,\basis C}\cdot[\beta]_{\basis A, \basis B}.
  \]
\end{lemma}

\begin{proof}
  \begin{align*}
    (\alpha\compose\beta)(u_\ell) &= \alpha(\beta(u_\ell)), \: u_\ell\in A\\
                                  &= \alpha\Big( \sum_{j}^{ }b_{jl}v_j \Big), \: v_j\in B \\
                                  &= \sum_{j}^{ }b_{jl}\alpha(v_j) \\
                                  &= \sum_{j}^{ }b_{jl}\sum_{i}^{ }a_{ij}w_i, \: w_i\in W \\
                                  &= \sum_{i}^{ }\left( \sum_{j}^{ }a_{ij}b_{jl} \right)w_i
  \end{align*}
\end{proof}

\begin{proposition}
  Let \(V\) and \(W\) be \(\F\)-vector spaces with \(\dim V = n, \dim W = m\), then
  \[
L(V,W) \cong \M_{m,n}(\F).
  \]
\end{proposition}

\begin{proof}
  Fix bases \(B=\{v_1\ldots,v_n\}, C=\{w_1,\ldots,w_m\}\) for \(V\) and \(W\) respectively. Claim
  \begin{align*}
    \theta: L(V,W) &\to \M_{m,n}(\F) \\
    \alpha &\mapsto [\alpha]_{\basis B, \basis C}
  \end{align*}
  is an isomorphism:
  \begin{itemize}
  \item linearity: \([\lambda_1\alpha_1 + \lambda_2\alpha_2]_{\basis B, \basis C} = \lambda_1[\alpha_1]_{\basis B, \basis C} + \lambda_2[\alpha_2]_{\basis B, \basis C}\).
  \item surjectivity: given \(A = (a_{ij})\), let \(\alpha:v_j\mapsto \sum_{i=1}^{m}a_{ij}w_i \) and extend linearly. It follows that \(\alpha\in L(V,W)\) and \(\theta(\alpha) = A\).
  \item injectivity: \([\alpha]_{\basis B, \basis C} = \V 0\) implies that \(\alpha\) is the zero map.
  \end{itemize}
\end{proof}

\begin{corollary}
  \label{cor:dim of hom}
  \[
\dim L(V,W) = \dim V \cdot \dim W.
  \]
\end{corollary}

\begin{eg}
  Suppose \(\alpha:V\to W\), \(Y\leq V, Z\leq W\) with \(\alpha(Y)\leq Z\). Let \(\basis B'=\{v_1,\ldots,v_k\}\) be a basis of \(Y\) and extend to \(\basis B=\{v_1,\dots,v_k,v_{k+1}, \dots, v_n\}\) a basis for \(V\). Similarly \(\basis C' = \{w_1,\dots,w_l\}\) and \(\basis C\) for \(Z\) and \(W\).
  \begin{itemize}
  \item \([\alpha]_{\basis B, \basis C} =
\begin{pmatrix}
  A & B \\
  0 & C
\end{pmatrix}
\) for some \(A, B, C\) because for \(1\leq j \leq k\), \(\alpha(v_j)\) is a linear combination of \(w_i\) where \(1\leq i \leq l\).
  \item \([\alpha|_Y]_{B',C'} = A. \)
  \item \(\alpha\) induces a map
    \begin{align*}
      \bar\alpha: V/Y &\to W/Z \\
      v+ Y &\mapsto \alpha(v) + Z
    \end{align*}
    This is well-defined. Linearity follows from that of \(\alpha\). A basis for \(V/Y\) is \(\basis B''=\{v_{k+1}+Y,\ldots,v_n+Y\}\) and similarly for \(W/Z\). It is an exercise to show \([\bar\alpha]_{\basis B'', \basis C''} = C \).
  \end{itemize}
\end{eg}

\subsubsection{Change of Bases}

Throughout this section, let \(V\) and \(W\) be \(\F\)-vector spaces and suppose they have the following bases:
\begin{table}[htbp]
  \centering
  \begin{tabular}{|c||c|c|}
    \hline
    Vector space & \(V\) & \(W\) \\ \hline
    Basis 1 & \(\basis B = \{v_1,\dots,v_n\}\) & \(\basis C = \{w_1,\dots,w_m\}\) \\ \hline
    Basis 2 & \(\basis B' = \{v_1',\dots,v_n'\}\) & \(\basis C' = \{w_1',\dots,w_m'\}\) \\ \hline
  \end{tabular}
\end{table}

\begin{definition}[Change-of-basis matrix]\index{matrix!change-of-basis}
  The \emph{change-of-basis matrix} from \(\basis B'\) to \(\basis B\) is \(P = (p_{ij})\) given by
  \begin{align*}
    v_j' &= \sum_{i}^{ }p_{ij}v_i \\
    P &= \Big( [v_1']_{\basis B} \: \Big| \: [v_2']_{\basis B} \: \Big| \: \dots \Big| \: [v_n']_{\basis B} \Big) = [\id]_{\basis B', \basis B}
  \end{align*}
\end{definition}

\begin{lemma}
  \[
    [v]_{\basis B} = P[v]_{\basis B'}.
  \]
\end{lemma}

\begin{proof}
  \[
    P[v]_{\basis B'} = [\id]_{\basis B', \basis B}[v]_{\basis B'} = [v]_{\basis B}.
  \]
\end{proof}

\begin{lemma}
  \(P\) is an invertible \(n\times n\) matrix and \(P^{-1}\) is the change-of-basis matrix from \(\basis B\) to \(\basis B'\).
\end{lemma}

\begin{proof}
  \begin{align*}
    [\id]_{\basis B, \basis B'}[\id]_{\basis B', \basis B} &= [\id]_{\basis B', \basis B'} = I_n \\
    [\id]_{\basis B', \basis B}[\id]_{\basis B, \basis B'} &= [\id]_{\basis B, \basis B} = I_n
  \end{align*}
\end{proof}

Let \(Q\) be the change-of-basis matrix from \(\basis C'\) to \(\basis C\). Then \(Q\) is an invertible \(m\times m\) matrix.

\begin{proposition}
  Let \(\alpha: V\to W\) be a linear map, \(A = [\alpha]_{\basis B,\basis C}\), \(A' = [\alpha]_{\basis B',\basis C'}\), then
  \[
    A' = Q^{-1}AP.
  \]
\end{proposition}

\begin{proof}
  \[
    \underbrace{[\id]_{\basis C,\basis C'}}_{Q^{-1}} [\alpha]_{\basis B,\basis C} \underbrace{[\id]_{\basis B',\basis B}}_P = \underbrace{[\id\compose\alpha\compose\id]_{\basis B',\basis C'}}_{A'}
  \]
\end{proof}

\begin{definition}[Equivalence of matrices]\index{matrix!equivalence}
  \(A, A' \in \M_{m,n}(\F)\) are \emph{equivalent} if
  \[
    A' = Q^{-1}AP
  \]
  for some invertible \(P\in \M_{n,n}(\F)\) and \(Q\in \M_{m,m}(\F)\).
\end{definition}

\begin{note}
  This defines an equivalence relation on \(\M_{m,n}(\F)\).
\end{note}

\begin{proposition}
  Let \(V, W\) be \(\F\)-vector spaces of dimension \(n\) and \(m\) respectively. Let \(\alpha:V\to W\) be a linear map. Then there exist bases \(\basis B\) of \(V\), \(\basis C\) of \(W\), and some \(r\leq m,n\) such that
  \[
    [\alpha]_{\basis B,\basis C} =
    \begin{pmatrix}
      I_r & 0 \\
      0 & 0 
    \end{pmatrix}
  \]
  where \(I_r\) the is \(r\times r\) the identity matrix.
\end{proposition}

\begin{note}
  \(r = rk(\alpha) = r(\alpha)\).
\end{note}

\begin{proof}
  Fix \(r\) such that \(\dim N(\alpha) = n-r\). Fix a basis for \(N(\alpha)\), say \(v_{r+1},\dots,v_n\). Extend this to a basis \(\basis B\) for \(V\), say \(v_1,\dots,v_r,v_{r+1},\dots,v_n\). Now \(\alpha(v_1),\dots,\alpha(v_r)\) is a basis for \(\im(\alpha)\):
  \begin{itemize}
  \item span: \(\alpha(v_1),\dots, \alpha(v_n)\) certainly span \(\im(\alpha)\). Since \(v_{r+1}, \dots ,v_n \in \ker \alpha\), \(\alpha(v_{r+1}),\dots,\alpha(v_n) = 0\) so we can remove them from the spanning set.
  \item linear independence: assume \(\sum_{i=1}^{n}\lambda_i \alpha(v_i) =\V 0 \). Then \(\alpha \big(\sum_{i=1}^n\lambda_iv_i\big) =\V0\). This implies that
    \[
      \sum_{i=1}^{n}\lambda_iv_i = \sum_{j=r+1}^{n}\mu_jv_j.
    \]
    As \(v_1,\dots v_n\) are linearly independent, \(\lambda_i=\mu_j=0\) for all \(i,j\).
  \end{itemize}
  Extend \(\alpha(v_1),\dots,\alpha(v_r)\) to a basis for \(W\), say \(\basis C\). By construction,
  \[
    [\alpha]_{\basis B,\basis C} =
    \begin{pmatrix}
      I_r & 0 \\
      0 & 0
    \end{pmatrix}
  \]
\end{proof}

\begin{remark}
  In the proof above we didn't need to assume that \(r = r(\alpha)\). This gives us another way prove Rank-nullity Theorem.
\end{remark}

\begin{corollary}
  Any \(m\times n\) matrix is equivalent to
  \[
  \begin{pmatrix}
      I_r & 0 \\
      0 & 0
    \end{pmatrix}
  \]
  for some \(r\).
\end{corollary}

\begin{definition}[Row and column rank]\index{matrix!rank}
  Let \(A\in \M_{m,n}(\F)\).
  \begin{itemize}
  \item The \emph{column rank} of \(A\), \(r(A)\) is the dimension of the subspace of \(\F^m\) spanned by the columns of \(A\).
  \item The \emph{row rank} of \(A\) is the column rank of \(A^T\).
  \end{itemize}
\end{definition}

\begin{note}
  If \(\alpha\) is a linear map represented by \(A\) with respect to any choice of bases, then \(r(\alpha) = r(A)\).
\end{note}

\begin{proposition}
  Two \(m\times n\) matrices \(A, A'\) are equivalent if and only if
  \[
    r(A) = r(A').
  \]
\end{proposition}

\begin{proof}\leavevmode
  \begin{itemize}
  \item \(\Leftarrow\): Both \(A\) and \(A'\) are equivalent to \(
    \begin{pmatrix}
      I_r & 0 \\
      0 & 0
    \end{pmatrix}
    \) and matrix equivalence is transitive.
  \item \(\Rightarrow\): Let \(\alpha:\F^n\to \F^m\) be the linear map represented by \(A\) with respect to, say, the standard basis. Since \(A'=Q^{-1}AP\) for some invertible \(P\) and \(Q\), \(A'\) represents the same \(\alpha\) with respect to another bases. \(r(\alpha)\) is defined in a basis-invariant way so \(r(A) = r(\alpha) = r(A')\).
  \end{itemize}
\end{proof}

\begin{theorem}
  \label{thm:upper corner matrix}
  \[
    r(A) = r(A^T).
  \]
\end{theorem}

\begin{proof} \(
    Q^{-1}AP =
    \begin{pmatrix}
      I_r & 0 \\
      0 & 0
    \end{pmatrix}_{m, n}
  \) where \(P\) and \(Q\) are invertible. Take transpose of the whole equation:
  \[
    \begin{pmatrix}
      I_r & 0 \\
      0 & 0
    \end{pmatrix}_{n,m}
    =(Q^{-1}AP)^T = P^TA^T(Q^T)^{-1}
  \]
  so \(A^T\) is equivalent to
  \[
      \begin{pmatrix}
      I_r & 0 \\
      0 & 0
    \end{pmatrix}
  \]
\end{proof}

Note a special case for change of basis: \(V = W\), \(\basis C = \basis B\) and \(\basis C' = \basis B'\). \(P\), the change-of-basis matrix from \(\basis B'\) to \(\basis B\), is given the map \(\alpha \in L(V,V)\)
\[
  [\alpha]_{\basis B',\basis B'} = P^{-1}[\alpha]_{\basis B,\basis B}P.
\]

\begin{definition}[Similar matrices]\index{matrix!similar}\index{matrix!conjugacy}
  Given \(A, A' \in \M_{n,n}(\F)\), \(A\) and \(A'\) are \emph{similar}, or \emph{conjugate} if
  \[
    A' = P^{-1}AP
  \]
  for some invertible \(P\).
\end{definition}

\subsubsection{Elementary Matrices and Operations}

\begin{definition}[Elementary column operation]\index{elementary operation}
  \emph{Elementary column operation} on a \(m\times n\) matrix \(A\) is one of the following operations:
  \begin{enumerate}
  \item swap column \(i\) and \(j\) (wlog \(i\neq j\)),
  \item scale column \(i\) by \(\lambda\)  (\(\lambda\neq0\)),
  \item add \(\lambda\) times column \(i\) to column \(j\) (\(i\neq j,\lambda\neq 0\)).
  \end{enumerate}
\end{definition}

\begin{definition}[Elementary row operation]
  Defined analoguously, replacing ``column'' by ``row''.
\end{definition}

\begin{note}
  All of these operations are invertible.
\end{note}

\begin{definition}[Elementary matrix]\index{matrix!elementary}
The elementary column (row, respectively) operations have corresponding elementary matrices, which are the results of performing these column (row, respectively) operations on \(I_n\) (\(I_m\), respectively):
\begin{enumerate}
\item
  \[
    \begin{pmatrix}
      1 & 0 & \cdots & & & 0 \\
      \vdots & \ddots & & & & \vdots \\
      & & 0 & & 1 & 0 \\
      0 & \cdots & 0 & \ddots & 0 & 0 \\
      & & 1 & 0 & 0 & & \\
      \vdots & & &  \ddots & \\
      0 & & \cdots & & \cdots & 0
    \end{pmatrix}
  \]
\item
  \[
    \begin{pmatrix}
      1 & 0 & \cdots & & 0 \\
       & \ddots & & & \\
      \vdots & & \lambda & & \vdots \\
       & & & \ddots & \\
      0 & \cdots & & 0 & 1
    \end{pmatrix}
  \]
\item \(I_n+\lambda E_{ij}\) where \(E_{ij}\) is the matrix with \(1\) on \(ij\)th entry and \(0\) elsewhere.
\end{enumerate}
\end{definition}

An elementary column (row, respectively) operation on \(A\in \M_{m,n}(\F)\) can be performed by multiplying \(A\) by these corresponding elementary matrices on the right (left respectively).

\begin{eg}
  \[
    \begin{pmatrix}
      1 & 2 \\ 3 & 4
    \end{pmatrix}
    \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 2 & 1 \\ 4 & 3 \end{pmatrix}
  \]
\end{eg}

Given the elementary matrices, we can give a constructive proof that any \(m\times n\) matrix is equivalent to \(\begin{pmatrix} I_r & 0 \\ 0 & 0 \end{pmatrix}\) for some \(r\):

\begin{proof}[Constructive proof of Theorem~\ref{thm:upper corner matrix}]
  Start with \(A\). If all entries of \(A\) are zero then done. If not then some \(a_{ij} = \lambda \neq 0\). Perform the following:
  \begin{enumerate}
  \item swap row \(1\) and \(i\), swap column \(1\) and \(j\) so \(\lambda\) is in position \((1,1)\),
  \item multiply column \(1\) by \(1/\lambda\) to get \(1\) in position \((1,1)\),
  \item add \((-a_{12})\) times column \(1\) to column \(2\). Do so for the other entries in row \(1\). Also use row operations to clear out all other entries in column \(1\). Now the matrix is in the form
    \[
      \begin{pmatrix}
        1 & 0 \\
        0 & A'
      \end{pmatrix}
    \]
  \item iterate for \(A'\). Stop when the new \(A' = 0\).
  \end{enumerate}
  The result of these operations is
  \[
    \begin{pmatrix}
      I_r & 0 \\
      0 & 0
    \end{pmatrix}
    =\underbrace{E'_{\ell}E'_{\ell-1}\dots E'_1}_{Q^{-1}} A \underbrace{E_1E_2\dots E_{\ell-1}E_\ell}_{P}.
  \]
  As elementary operations are invertible, the elementary matrices are invertible so
  \[
    Q^{-1}AP = 
     \begin{pmatrix}
      I_r & 0 \\
      0 & 0
    \end{pmatrix}
  \]
\end{proof}

If you only use elementary row operations, we can get the \emph{row echelon form} of a matrix:
\[
  \begin{pmatrix}
    a & b & \dots & c \\
    0 & d & \dots & e \\
    \vdots & & \ddots & \vdots \\
    0 & 0 & \dots & f
  \end{pmatrix}
\]

\begin{lemma}
  If \(A\) is an \(n\times n\) invertible matrix then we can obtain \(I_n\) by using only elementary row/column operations.
\end{lemma}

\begin{proof}
  We prove the column operation case. Use induction on \(n\), the number of rows. Suppose we have got \(\begin{pmatrix} I_k & 0 \\ \star & \ast \end{pmatrix}\) for some \(k\geq 0\). There exists \(j>k\) such that \(a_{k+1,j}\neq 0\), (i.e.\ in the \(\ast\) block) as otherwise \((0,\dots,1,\dots, 0)\) with \(1\) in \((k+1)\)th position would not be in the span of the column vectors, contradicting the invertiblity. Next we carry out the following operations:
  \begin{enumerate}
  \item swap column \(k+1\) and \(j\),
  \item divide column \(k+1\) by \(a_{k + 1, k + 1}\) so have \(1\) in \((k+1,k+1)\) position,
  \item use column operation to clear other entries of \((k+1)\)th row.
  \end{enumerate}
  Proceed inductively.
\end{proof}

Note that the equality
\[
  AE_1E_2\dots E_c = I_n
\]
gives
\[
  A^{-1} = E_1E_2\dots E_c,
\]
which is one way to compute inverses.

\begin{proposition}
  Any invertible matrix can be written as a product of elementary ones.
\end{proposition}

\section{Dual Space \& Dual Map}

\subsection{Definitions}

\begin{definition}[Dual space]\index{vector space!dual}
  Let \(V\) be an \(\F\)-vector space. The \emph{dual space} of \(V\) is defined to be
  \[
    V^* = L(V,\F) = \{\alpha:V\to \F, \alpha \text{ linear}\}.
  \]
\end{definition}

\(V^*\) is itself an \(\F\)-vector space. Its elements are sometimes called \emph{linear functionals}.

\begin{eg}\leavevmode
  \begin{enumerate}
  \item \(\R^3 \to \R, (a,b,c)\mapsto a-c\) is an element of \(V^*\).
  \item \(\tr: \M_{n,n}(\F)\to \F, A\mapsto \sum_i A_{ii}\) is an element of \(\M_{n,n}(\F)^*\).
  \end{enumerate}
\end{eg}

\begin{lemma}[Dual basis]
  Let \(V\) be a finite-dimensional \(\F\)-vector space with basis \(\basis B = \{e_1,\dots,e_n\}\). Then there is a basis for \(V^*\), given by
  \[
    \basis B^* = \{\varepsilon_1,\dots, \varepsilon_n\}
  \]
  where
  \[
    \varepsilon_j \Big( \sum_{i=1}^{n} a_i e_i \Big) = a_j
  \]
  for \(1\leq j\leq m\).

  \(\basis B^*\) is called the \emph{dual basis} to \(\basis B\).
\end{lemma}

\begin{proof}\leavevmode
  \begin{itemize}
  \item linear independence: suppose
    \[
      \sum_{j=1}^{n}\lambda_j\varepsilon_j = 0.
    \]
    Apply the relation to basis vectors,
    \[
      0 = \Big( \sum_{j=1}^n \lambda_j\varepsilon_j \Big) e_i = \sum_{j=1}^n \lambda_j\varepsilon_j(e_i)
      \]
      The last expression is 
      \[
        \varepsilon_j(e_i) = 
      \begin{cases}
        0 & \text{ if } i \neq j \\
        1 & \text{ if } i = j
      \end{cases}
    \]
    so \(\lambda_i=0\) for all \(1 \leq i \leq n\).
  \item span: if \(\alpha \in V^*\), then
    \[
      \alpha = \sum_{i=1}^{n}\alpha(e_i)\varepsilon_i
    \]
    since linear maps are uniquely determined by the action on basis.
  \end{itemize}
\end{proof}

\begin{corollary}
  If \(V\) is a finite-dimensional \(\F\)-vector space then
  \[
    \dim V = \dim V^*.
  \]
\end{corollary}

\begin{remark}
  Sometimes it is useful to think about \((\F^n)^*\) as the space of row vectors of length \(n\) over \(\F\).
\end{remark}

\subsection{Dual Map}

It turns out dual spaces have maps between them. Before studying them in detail, we introduce this concept to add richness to the theory of dual map:

\begin{definition}[Annihilator]\index{annihilator}
  If \(U \subseteq V\), the \emph{annihilator} of \(U\) is
  \[
    U^\ann = \{\alpha\in V^*: \forall u \in U,\,\alpha(u) = 0 \}.
  \]
\end{definition}

\begin{lemma}\leavevmode
  \begin{enumerate}
  \item \(U^\ann \leq V^*\),
  \item If \(U \leq V\) and \(\dim V = n < \infty\) then
    \[
      \dim V = \dim U + \dim U^\ann.
    \]
  \end{enumerate}
\end{lemma}

\begin{proof}\leavevmode
  \begin{enumerate}
  \item \(0 \in U^\ann\). If \(\alpha\) and \(\alpha'\) are in \(U^\ann\) then
    \[
      (\alpha+ \alpha')(u) = \alpha(u) + \alpha'(u) = 0+0 = 0
    \]
    for all \(u\in U\). Similarly \(\lambda\alpha\in U^\ann\) for any \(\lambda \in \F\).
  \item Let \(\basis B = \{e_1,\dots, e_k\}\) be a basis for \(U\) and extend it to a basis for \(V\), say \(e_1,\dots,e_k,e_{k+1},\dots,e_n\). Let \(\basis B^*=\{\varepsilon_1,\dots,\varepsilon_n\}\) be its dual basis. Claim \(\varepsilon_{k+1},\dots,\varepsilon_n \) is a basis for \(U^\ann\):
    \begin{itemize}
    \item If \(i>k,j\leq k\) then \(\varepsilon_i(e_j) = 0 \) so \(\varepsilon_i\in U^\ann\).
    \item Linear independence comes from the fact that \(B^*\) is a basis.
    \item If \(\alpha\in U^\ann\), \(\alpha = \sum_{i=1}^na_i\varepsilon_i\) for some \(\alpha_i\in \F\). Then for any \(j\leq k\),
      \[
        \Big( \sum_{i=1}^{n}a_i\varepsilon_i \Big) (e_j) = 0
      \]
      so \(a_j=0\). It follows that \(\alpha \in \langle \varepsilon_{k+1},\dots,\varepsilon_n \rangle\).
    \end{itemize}
  \end{enumerate}
\end{proof}

\begin{lemma}[Dual space as a contravariant functor]
  Let \(V\) and \(W\) be \(\F\)-vector spaces. Let \(\alpha \in L(V,W)\). Then the map
  \begin{align*}
    \alpha^*: W^* &\to V^* \\
    \varepsilon &\mapsto \varepsilon \compose \alpha
  \end{align*}
  is linear. \(\alpha^*\) is called the \emph{dual} of \(\alpha\).
\end{lemma}

\begin{proof}\leavevmode
  \begin{itemize}
  \item \(\varepsilon \compose \alpha \in V^*\) since composition preserves linearity.
  \item Fix \(\theta_1,\theta_2\in W^*\),
    \begin{align*}
      \alpha^*(\theta_1+\theta_2) &= (\theta_1+\theta_2)\compose \alpha \\
                                  &= \theta_1\compose \alpha + \theta_2 \compose \alpha \\
      &= \alpha^*\theta_1 + \alpha^*\theta_2
    \end{align*}
  \item Similarly \(\alpha^*(\lambda\theta) = \lambda\alpha^*(\theta)\).
  \end{itemize}
\end{proof}

\begin{proposition}
  Let \(V\) and \(W\) be \(\F\)-vector spaces with bases \(\basis B\) and \(\basis C\) respectively. Let \(\basis B^*\) and \(\basis C^*\) be the dual bases. Consider \(\alpha\in L(V,W)\) with dual \(\alpha^*\), then
  \[
    [\alpha^*]_{\basis C^*,\basis B^*} = [\alpha]^T_{\basis B,\basis C}.
  \]
\end{proposition}

\begin{proof}
  Say \(\basis B = \{b_1,\dots,b_n\}\), \(\basis B^* = \{\beta_1,\dots,\beta_n\}\), \(\basis C = \{c_1,\dots,c_m\}\) and \(\basis C^* = \{\gamma_1,\dots,\gamma_n\}\). Further let \([\alpha]_{\basis B,\basis C} = (a_{ij})\), an \(m\times n\) matrix.
  \begin{align*}
    \alpha^*(\gamma_r)(b_s) &= \gamma_r \compose \alpha(b_s) \\
                            &= \gamma_r(\alpha(b_s)) \\
                            &= \gamma_r \Big( \sum_{t}^{ }a_{ts}c_t \Big) \\
                            &= \sum_{t}^{ } a_{ts} \gamma_r(c_t) \\
                            &= a_{rs} \\
                            &= \Big( \sum_{i}^{ } a_{ri}\beta_i \Big) (b_s)
  \end{align*}
  Thus
  \[
    \alpha^*(\gamma_r) = \sum_{i}^{ } a_{ri}\beta_i
  \]
  so
  \[
    [\alpha^*]_{\basis C^*,\basis B^*} = [\alpha]^T_{\basis B,\basis C}.
  \]
\end{proof}

It follows that
\begin{lemma}
  Let \(V\) be a finite-dimensional \(\F\)-vector space with bases \(\basis E\) and \(\basis F\). They have correponding dual bases \(\basis E^*\) and \(\basis F^*\). If the change-of-basis matrix from \(\basis F\) to \(\basis E\) is \(P\) then the change-of-basis matrix from \(\basis F^*\) to \(\basis E^*\) is
  \[
    (P^{-1})^T.
  \]
\end{lemma}

\begin{proof}
  \[
    [\id]_{\basis F^*,\basis E^*} = [\id]_{\basis E, \basis F}^T = ([\id]_{\basis F, \basis E}^{-1})^T.
  \]
\end{proof}

\begin{caution}
  \(V \cong V^*\) only if \(V\) is finite-dimensional. Let \(V = P\), the space of all real polynomials. It has basis \(\{p_j\}_{j\in \N}\) where \(p(j) = t^j\). In example sheet 2 we will see
\begin{align*}
  P^* &\cong \R^\N \\
  \varepsilon &\mapsto (\varepsilon(p_0), \varepsilon(p_1), \dots)
\end{align*}
and on example sheet 1 we prove
\[
  P \ncong \R^\N
\]
as the latter does not have a countable basis.
\end{caution}

Now we move on to more discussion about annhilator.

\begin{lemma}
  Let \(V\) and \(W\) be \(\F\)-vector spaces. Fix \(\alpha \in L(V,W)\) and let \(\alpha^* \in L(W^*, V^*)\) be its dual. Then
  \begin{itemize}
  \item \(N(\alpha^*) = (\im \alpha)^\ann\), so \(\alpha^*\) is injectve if and only if \(\alpha\) is surjective.
  \item \(\im \alpha^* \leq N(\alpha)^\ann\), with equality if \(V\) and \(W\) are both finite-dimensional, in which case \(\alpha^*\) is surjective if and only if \(\alpha\) is injective.
  \end{itemize}
\end{lemma}

\begin{proof}\leavevmode
  \begin{itemize}
  \item Let \(\varepsilon \in W^*\), then
  \begin{align*}
    & \varepsilon \in N(\alpha^*) \\
    \Leftrightarrow & \alpha^* (\varepsilon) = 0 \\
    \Leftrightarrow & \varepsilon \compose \alpha = 0 \\
    \Leftrightarrow & \varepsilon(u) = 0 \, \forall u \in \im \alpha \\
    \Leftrightarrow & \varepsilon \in (\im \alpha)^\ann
  \end{align*}

\item Let \(\varepsilon \in \im \alpha^*\), Then \(\varepsilon = \alpha^* (\phi)\) for some \(\phi \in W^*\). For any \(u \in N(a)\),
  \[
    \varepsilon(u) = (\alpha^*(\phi))(u) = (\phi\compose \alpha)(u) = \phi(\alpha(u)) = \phi(0) = 0
  \]
  so \(\varepsilon \in N(\alpha)^\ann\).

  Now use the fact that \(V\) and \(W\) are finite-dimensional:
  \[
    \dim \im(\alpha^*) = r(\alpha^*) = r(\alpha)
  \]
  as \(r(A) = r(A^T)\). On the other hand,
  \[
    r(\alpha) = \dim V - \dim N(\alpha) = \dim (N(\alpha))^\ann
  \]
  Thus they are equal.
\end{itemize}
\end{proof}

\subsection{Double Dual}

Let \(V\) be an \(\F\)-vector space. Then \(V^* = L(V,\F)\) is its dual space. The natural (oops) next step is

\begin{definition}[Double dual]\index{vector space!double dual}
  The \emph{double dual} of \(V\) is
  \[
    V^{**} = V^* = L(V^*, \F).
  \]
\end{definition}

\begin{theorem}[Naturallity of double dual]
  If \(V\) is an \(\F\)-vector space, then the map
  \begin{align*}
    \hat \cdot: V &\to V^{**} \\
    v &\mapsto \hat v
  \end{align*}
  where \(\hat v(\varepsilon) = \varepsilon(v)\), is a natural homomorphism. In particular when \(V\) is finite-dimensional this is a natural isomorphism.
\end{theorem}

\begin{proof}\leavevmode
  \begin{itemize}
  \item For \(v\in V\), the map \(\hat v: V^* \to \F\) is linear so \(\hat \cdot\) does give a map from \(V\) to \(V^{**}\).
  \item Linearity: for \(v_1, v_2 \in V\), \(\lambda_1, \lambda_2 \in \F\), \(\varepsilon \in V^*\), then
    \[
      \reallywidehat{\lambda_1v_1 + \lambda_2v_2}(\varepsilon) = \varepsilon(\lambda_1v_1 + \lambda_2v_2) = \lambda_1 \varepsilon(v_1) + \lambda_2 \varepsilon(v_2) = \lambda_1 \hat v_1(\varepsilon) + \lambda_2 \hat v_2(\varepsilon)
    \]
  \item Injectivity: let \(e \in V\setminus\{0\}\). Extend it to a basis of \(V\), say \(e, e_2,\dots, e_n\). Let \(\varepsilon, \varepsilon_2,\dots, \varepsilon_n\) be its corresponding dual basis. Now
    \[
      \hat e(\varepsilon) = \varepsilon(e) = 1 
    \]
    so \(\hat e\) is non-zero. \(\hat \cdot\) is injective.
  \item Finally, if \(V\) is finite-dimensional, \(\dim V = \dim V^* = \dim V^{**}\) so \(\hat \cdot\) is an isomorphism.
  \end{itemize}
\end{proof}

\begin{lemma}
  Let \(V\) be an \(\F\)-vector space and \(U \leq V\). Then
  \[
    \hat U \leq U^{\ann \ann}.
  \]
  If \(V\) is finite-dimensional then \(\hat U = U^{\ann \ann}\) so \(U \cong U^{\ann \ann}\).
\end{lemma}

\begin{proof}\leavevmode
  \begin{itemize}
  \item First show \(\hat U \leq U^{\ann \ann}\): given \(u \in U\), for all \(\varepsilon \in U^\ann\), \(\varepsilon(u) = 0\) so \(\hat u(\varepsilon) = 0\). Thus \(\hat u \in (U^\ann)^\ann = U^{\ann \ann}\).
  \item If \(V\) is finite-dimensional then
    \[
      \dim U^{\ann \ann} = \dim V^* - \dim U^\ann = \dim V - \dim U^\ann = \dim U
    \] so \(\hat U = U^{\ann \ann}\).
  \end{itemize}
\end{proof}

\begin{lemma}
  Let \(V\) be a finite-dimensional \(\F\)-vector space and \(U_1, U_2 \leq V\). Then
  \begin{itemize}
  \item \((U_1 + U_2)^\ann = U_1^\ann \cap U_2^\ann\),
  \item \((U_1 \cap U_2)^\ann = U_1^\ann + U_2^\ann\).
  \end{itemize}
\end{lemma}

\begin{proof}\leavevmode
  \begin{itemize}
  \item Let \(\theta \in V^*\), \(\theta \in (U_1+U_2)^\ann\) if and only if \(\theta(u_1+u_2) = 0\) for all \(u_1\in U_1, u_2 \in U_2\), if and only if \(\theta(u) = 0\) for all \(u \in U_1 \cup U_2\), so \(\theta\in U_1^\ann \cap U_2^\ann\).
  \item Apply \(^\ann\) to the first result and use the previous lemma.
  \end{itemize}
\end{proof}

\section{Bilinear Form I}

\begin{definition}[Bilinear form]\index{bilinear form}
  Let \(U\) and \(V\) be \(\F\)-vector spaces. A map \(\varphi: U \times V \to \F\) is \emph{bilinear} if it is linear in both arguments, i.e.
  \begin{align*}
    \forall u \in U, \, \varphi(u, -) &\in V^*, \\
    \forall v \in V, \, \varphi(-, v) &\in U^*.
  \end{align*}
\end{definition}

\begin{eg}\leavevmode
  \begin{enumerate}
  \item \(V \times V^* \to \F, (v, \theta) \mapsto \theta(v)\).
  \item \(U = V = \R^n, \varphi(x, y) = \sum_{i=1}^{n}x_iy_i\).
  \item \(A \in \M_{m,n}(\F), \varphi: \F^m \times \F^n \to \F, (u, v) \mapsto u^TAv\).
  \item \(U = V = C([0, 1], \R), (f, g) \mapsto \int_{0}^{1} f(t)g(t) dt \)
  \end{enumerate}
\end{eg}

\begin{definition}[Matrix of bilinear form]\index{matrix!bilinear form, of}
  Let \(\basis B = \{e_1,\dots,e_m\}\) be a basis for \(U\) and \(\basis C = \{f_1,\dots,f_n\}\) be a basis for \(V\). Given a bilinear map \(\varphi: U \times V \to \F\), the \emph{matrix of \(\varphi\)} with respect to \(\basis B\) and \(\basis C\) is
  \[
    [\varphi]_{\basis B, \basis C} = \left( \varphi(e_i, f_j) \right)_{m \times n}.
  \]
\end{definition}

\begin{lemma}
  \[
    \varphi(u, v) = [u]_{\basis B}^T [\varphi]_{\basis B, \basis C} [v]_{\basis C}.
  \]
\end{lemma}

\begin{proof}
  Let \(u = \sum_{i}^{ }\lambda_ie_i, v = \sum_{j}^{} \mu_jf_j\), then
  \begin{align*}
    \varphi(u, v) &= \varphi\left( \sum_{i}^{ }\lambda_ie_i, \sum_{j}^{} \mu_jf_j \right) \\
                  &= \sum_{i}^{ }\lambda_i \varphi\left(e_i, \sum_{j}^{} \mu_jf_j \right)\\
                  &= \sum_{i, j}^{ }\lambda_i \varphi(e_i, f_j) \mu_j
  \end{align*}
\end{proof}

\begin{note}\leavevmode
  \begin{enumerate}
  \item \([\varphi]_{\basis B, \basis C}\) is the unique matrix with this property.
  \item A bilinear form \(\varphi: U \times V \to \F\) induces linear maps
    \begin{align*}
      \varphi_L: U &\to V^* \\
      u &\mapsto \varphi(u, -) \\
      \varphi_R: V &\to U^* \\
      v &\mapsto \varphi(-, v)
    \end{align*}
  \end{enumerate}
\end{note}

\begin{lemma}
  Let \(\basis B = \{e_1,\dots, e_m\}\) be a basis for \(U\), \(\basis B^* = \{\varepsilon_1,\dots, \varepsilon_m\}\) a basis for \(U^*\), \(\basis C = \{f_1,\dots, f_n\}, \basis C^* = \{\eta_1,\dots, \eta_n\}\) for \(V\) and \(V^*\). If \([\varphi]_{\basis B, \basis C} = A\) then
  \begin{align*}
    [\varphi_L]_{\basis B, \basis C^*} &= A^T, \\
    [\varphi_R]_{\basis C, \basis B^*} &= A. \\
  \end{align*}
\end{lemma}

\begin{proof}
  \begin{align*}
    \varphi_L(e_i)(f_j) = A_{ij} &\Longrightarrow \varphi_L(e_i) = \sum_{j}^{ }A_{ij}\eta_j \\
    \varphi_R(f_j)(e_i) = A_{ij} &\Longrightarrow \varphi_R(f_j) = \sum_{i}^{ }A_{ij}\varepsilon_i
  \end{align*}
\end{proof}

\begin{definition}[Left and right kernel]\index{bilinear!kernel}
  The \emph{left (right, respectively) kernel} of \(\varphi\) is \(\ker \varphi_L\) (\(\ker \varphi_R\), respectively).
\end{definition}

\begin{definition}[Degeneracy]\index{bilinear!dengeneracy}
  \(\varphi\) is \emph{non-degenerate} if \(\ker \varphi_L = 0\) and \(\ker \varphi_R = 0\). Otherwise, \(\varphi\) is \emph{degenerate}.
\end{definition}

\begin{lemma}
  Let \(U, V\) have bases as before, and \(\varphi, A\) as before. Then \(\varphi\) is non-degenerate if and only if \(A\) is invertible.
\end{lemma}

\begin{proof}
  \begin{align*}
    & \varphi \text{ is non-degenerate} \\
    \Leftrightarrow & \ker \varphi_L = 0 \text{ and } \ker \varphi_R = 0 \\
    \Leftrightarrow & n(A^T) = n(A) = 0 \\
    \Leftrightarrow & r(A^T) = \dim V, r(A) = \dim U \\
    \Leftrightarrow & A \text{ is invertible}
  \end{align*}
\end{proof}

\begin{corollary}
  If \(\varphi\) is non-degenerate and \(U\) and \(V\) are finite-dimensional then \(\dim U = \dim V\).
\end{corollary}

\begin{corollary}
  When \(U\) and \(V\) are finite-dimensional, choosing a non-degenerate bilinear form \(\varphi: U \times V \to \F\) is equivalent to picking an homomorphism \(\varphi_L: U \to V^*\).
\end{corollary}

\begin{definition}
  For \(T \subseteq U, S \subseteq V\),
  \begin{align*}
    T^\perp &= \{ v\in V: \varphi(t, v) = 0 \, \forall t\in T \} \leq V \\
    \prescript{\perp}{}{S} &= \{ u\in U: \varphi(u, s) = 0 \, \forall s\in S \} \leq U
  \end{align*}
\end{definition}
They are generalisation of annihilators.

\begin{proposition}
  \label{prop:change of basis of bilinear form}
  Suppose \(U\) have bases \(\basis B, \basis B'\) and \(V \) have bases \(\basis C, \basis C'\), \(P = [\id]_{\basis B', \basis B}, Q = [\id]_{\basis C',\basis C}\). Let \(\varphi: U \times V \to \F\) be a bilinear form. Then
  \[
    [\varphi]_{\basis B',\basis C'} = P^T[\varphi]_{\basis B,\basis C}Q.
  \]
\end{proposition}

\begin{proof}
  \begin{align*}
    \varphi(u, v) &= [u]_{\basis B}^T [\varphi]_{\basis B, \basis C} [v]_{\basis C} \\
                  &= (P[u]_{\basis B'})^T [\varphi]_{\basis B, \basis C} (Q[v]_{\basis C'}) \\
                  &= [u]_{\basis B'}^T P^T[\varphi]_{\basis B, \basis C}Q[v]_{\basis C'} 
  \end{align*}
\end{proof}

\begin{definition}[Rank of bilinear form]\index{rank}
  The \emph{rank} of \(\varphi\), \(r(\varphi)\), is the rank of its matrix representation (which is well-defined by the previous proposition).
\end{definition}

\begin{note}
  \[
    r(\varphi) = r(\varphi_L) = r(\varphi_R).
  \]
\end{note}

\section{Determinant \& Trace}

% TODO: add exposition about eigenvalues and basis-independent values.

\subsection{Trace}

\begin{definition}[Trace]\index{trace}
  For \(A \in \M_n(\F) = \M_{n,n}(\F)\), the \emph{trace} of \(A\) is
  \[
    \tr(A) = \sum_{i=1}^{n}A_{ii}.
  \]
\end{definition}

\begin{lemma}
  For \(A, B\in \M_n(\F)\),
  \[
    \tr(AB) = \tr(BA).
  \]
\end{lemma}

\begin{proof}
  \[
    \tr(AB) = \sum_{i}^{ }\sum_{j}^{ }a_{ij}b_{ji} = \sum_{j}^{ }\sum_{i}^{ }b_{ji}a_{ij} = \tr(BA).
  \]
\end{proof}

\begin{lemma}
  Similar (or conjugate) matrices have the same trace.
\end{lemma}

\begin{proof}
  Suppose \(A\) and \(B\) are conjugates, then there exists \(P\) such that \(B = P^{-1}AP\) so
  \[
    \tr(B) = \tr(P^{-1}AP) = \tr(APP^{-1}) = \tr(A).
  \]
\end{proof}

\begin{definition}[Trace]\index{trace}
  Let \(\alpha: V \to V\) be a linear map. The \emph{trace} of \(\alpha\) is
  \[
    \tr \alpha = \tr[\alpha]_{\basis B} = \tr [\alpha]_{\basis B, \basis B}
  \]
  with repsect to a basis \(\basis B\). This is well-defined by the previous lemma.
\end{definition}

\begin{lemma}
  Let \(\alpha: V \to V\) be linear and \(\alpha^*: V^* \to V^*\) be its dual. Then
  \[
    \tr \alpha = \tr \alpha^*.
  \]
\end{lemma}

\begin{proof}
  \[
    \tr \alpha = \tr [\alpha]_{\basis B} = \tr [\alpha]_{\basis B}^T = \tr[\alpha^*]_{\basis B^*} = \tr \alpha^*.
  \]
\end{proof}

\subsection{Determinant}

Recall some results from IA Groups: let \(S_n\) be the permutation group of the set \(\{1, 2, \dots, n\}\) and \(\varepsilon: S_n \to \{1, -1\}\) be the signature of a permutation, i.e.
\[
  \varepsilon(\sigma) =
  \begin{cases}
    1 &\text{if \(\sigma\) is a product of even number of transpotitions}\\
    0 &\text{otherwise}
  \end{cases}
\]

\begin{definition}[Determinant]\index{determinant}
  Suppose \(A \in \M_n(\F)\), \(A = (a_{ij})\), the \emph{determinant} of \(A\) is
  \[
    \det A = \sum_{\sigma \in S_n}^{ } \varepsilon(\sigma) a_{\sigma(1), 1} a_{\sigma(2), 2} \cdots a_{\sigma(n), n}.
  \]
\end{definition}

There are \(n!\) terms in this summation and each is the signed product of \(n\) elements (one from each row and each column).

\begin{eg}
  For \(n = 2\),
  \[
    \det
    \begin{pmatrix}
      a_{11} & a_{12} \\
      a_{21} & a_{22}
    \end{pmatrix}
    =a_{11}a_{22} - a_{21}a_{12}
  \]
\end{eg}

\begin{lemma}
  If \(A = (a_{ij})\) is an upper-triangular matrix (i.e.\ \(a_{ij} = 0\) for all \(i > j\)) then
  \[
    \det A = a_{11}a_{22}\dots a_{nn}.
  \]
  Similar for lower-trianglular matrices.
\end{lemma}

\begin{proof}
  In the summation
  \[
    \det A = \sum_{\sigma \in S_n}^{ }\varepsilon(\sigma) a_{\sigma(1), 1}\dots a_{\sigma(n),n},
  \]
  for a summand to be non-zero, we need \(\sigma(j) \leq j\) for all \(j\). Thus \(\sigma = \id\).
\end{proof}

\begin{lemma}
  \[
    \det A = \det A^T
  \]
\end{lemma}

\begin{proof}
  \begin{align*}
    \det A &= \sum_{\sigma \in S_n}^{ } \varepsilon(\sigma) \prod_{i = 1}^n a_{\sigma(i), i} \\
           &= \sum_{\sigma \in S_n}^{ } \varepsilon(\sigma) \prod_{i = 1}^n a_{i, \sigma^{-1}(i)} \\
           &= \sum_{\sigma \in S_n}^{ } \varepsilon(\sigma^{-1}) \prod_{i = 1}^n a_{i, \sigma^{-1}(i)} \\
           &= \sum_{\tau \in S_n}^{ } \varepsilon(\tau) \prod_{i = 1}^n a_{i, \tau(i)} \text{ where \(\tau = \sigma^{-1}\)} \\
           &= \det A^T
  \end{align*}
\end{proof}

\begin{definition}[Volume form]\index{volume form}
  A \emph{volume form} on \(\F^n\) is a function
  \[
    d: \underbrace{\F^n \times \F^n \times \dots \times \F^n}_{\text{\(n\) copies}} \to \F
  \]
  which is:
  \begin{itemize}
  \item multilinear: for any \(i\) and \(v_1, \dots, v_{i-1}, v_i, v_{i + 1}, \dots, v_n \in \F^n\),
    \[
      d(v_1, \dots, v_{i-1}, -, v_{i+1}, \dots, v_n) \in (\F^n)^*.
    \]
  \item alternating: if \(v_i = v_j\) for \(i \neq j\), \(d(v_1, \dots, v_n) = 0\).
  \end{itemize}
\end{definition}

\begin{notation}
  Given \(A = (a_{ij})\), write \(A\) in column form
  \[
    \left( A^{(1)} | \cdots | A^{(n)} \right).
  \]
\end{notation}
For example, if \(\{e_i\}\) is a standard basis for \(\F^n\) then
\[
  I = \left(e_1 | \cdots | e_n \right).
\]

\begin{lemma}
  \begin{align*}
    \det: \F^n \times \dots \times \F^n &\to \F \\
    (A^{(1)}, \dots, A^{(n)}) &\mapsto \det A
  \end{align*}
  is a volume form.
\end{lemma}

\begin{proof}\leavevmode
  \begin{itemize}
  \item Multilinear: for any fixed \(\sigma \in S_n\), \(\prod_{i = 1}^n a_{\sigma(i), i}\) contains exactly one term from each column so it is multilinear. Multilinearity is preserved under addition.
  \item Alternating: suppose \(A^{(k)} = A^{(l)}\) for some \(l \neq k\). Let \(\tau = (kl)\). Then \(a_{ij} = a_{i \tau(j)}\) for all \(i, j\). Also \(S_n\) can be expressed as a union of two disjoint cosets \(A_n\) and \(\tau A_n\) so
    \begin{align*}
      \det A &= \sum_{\sigma \in A_n}^{ } \varepsilon(\sigma) \prod_{i = 1}^n a_{i, \sigma(i)} - \sum_{\sigma \in A_n}^{ } \varepsilon(\sigma) \prod_{i = 1}^n a_{i, \tau\sigma(i)} \\
      \intertext{since \(\varepsilon\) is a homomorphism}
             &= \sum_{\sigma \in A_n}^{ } \varepsilon(\sigma) \prod_{i = 1}^n a_{i, \sigma(i)} - \sum_{\sigma \in A_n}^{ } \varepsilon(\sigma) \prod_{i = 1}^n a_{i, \sigma(i)} \\
             &= 0
    \end{align*}
  \end{itemize}
\end{proof}

In the rest of the section we are going to prove that the converse is also true, i.e.\ all volume forms are determinant up to a scaling constant.

\begin{lemma}
  Let \(d\) be a volume form. Then swapping two entries changes the sign:
  \[
    d(v_1, \dots, v_i, \dots, v_j, \dots, v_n) = - d(v_1, \dots, v_j, \dots, v_i, \dots, v_n).
  \]
\end{lemma}

\begin{proof}
  \begin{align*}
    0 &= d(v_1, \dots, v_{i-1}, v_i + v_j, v_{i+1}, \dots, v_{j-1}, v_i + v_j, v_{j + 1}, \dots, v_n) \\
      &= \underbrace{d(v_1, \dots, v_i, \dots, v_i, \dots, v_n)}_{ = 0} + d(v_1, \dots, v_j, \dots, v_i, \dots, v_n) \\
      &+ d(v_1, \dots, v_i, \dots, v_j, \dots, v_n) + \underbrace{d(v_1, \dots, v_j, \dots, v_j, \dots, v_n)}_{ = 0} \\
  \end{align*}
  Rearrange.
\end{proof}

\begin{corollary}
  If \(\sigma \in S_n\),
  \[
    d(v_{\sigma(1)}, \dots, v_{\sigma(n)}) = \varepsilon(\sigma) d(v_1, \dots, v_n).
  \]
\end{corollary}

\begin{theorem}
  Let \(d\) be a volume form on \(\F^n\), \(A = (A^{(1)}|\dots | A^{(n)})\), then
  \[
    d(A^{(1)}, \dots, A^{(n)}) = \det A \cdot d(e_1, \dots, e_n).
  \]
\end{theorem}

\begin{proof}
  \begin{align*}
    d(A^{(1)}, \dots, A^{(n)}) &= d \left( \sum_{i=1}^{n} a_{i1}e_i, A^{(2)}, \dots, A^{(n)} \right) \\
                               &= \sum_{i = 1}^{n}a_{i_1} d(e_i, A^{(2)}, \dots, A^{(n)}) \\
                               &= \sum_{i}^{} \sum_{j}^{ } a_{i1} a_{j2} d(e_i, e_j, \dots, A^{(n)}) \\
                               &= \sum_{i_1, i_2, \dots, i_n}^{ } \prod_{k = 1}^{n} a_{{i_k},k} d(e_{i_1}, \dots e_{i_n})
\end{align*}
The last term is \(0\) unless all of \(i_k\) are distinct, i.e.\ exists \(\sigma \in S_n\) such that \(i_k = \sigma(k)\). Thus
\begin{align*}
  d(A^{(1)}, \dots, A^{(n)}) = \sum_{\sigma \in S_n}^{ } \prod_{k = 1}^{n} a_{\sigma(k), k} \underbrace{d(e_{\sigma(1)}, \dots, e_{\sigma(n)})}_{= \varepsilon(\sigma) d(e_1, \dots, e_n)}
\end{align*}
\end{proof}

\begin{corollary}
  \(\det\) is the unique volume form \(d\) such that \(d(e_1, \dots, e_n) = 1\).
\end{corollary}

\begin{proposition}
  Suppose \(A, B \in \M_n(\F)\), then
  \[
    \det AB =\det A \det B.
  \]
\end{proposition}

\begin{proof}
  Define
  \begin{align*}
    d_A: \F^n \times \dots \times \F^n &\to \F \\
    (v_1, \dots, v_n) &\mapsto \det(Av_1|\cdots|Av_n)
  \end{align*}
  which is a volume form:
  \begin{itemize}
  \item multilinear: \(v_i \mapsto Av_i\) is linear and \(\det\) is multilinear.
  \item alternating: \(v_i = v_j\) implies \(Av_i = Av_j\) and \(\det\) is alternating.
  \end{itemize}
  It follows that
  \begin{align*}
    d_A(Be_1, \dots, Be_n) &= \det B \cdot d_A(e_1, \dots, e_n) = \det B \det A \\
                           &= \det (ABe_1| \cdots | ABe_n) = \det AB
  \end{align*}
\end{proof}

\begin{definition}[Singular]\index{matrix!singular}
  \(A \in \M_n(\F)\) is \emph{singular} if \(\det A = 0\). Otherwise it is \emph{non-singular}.
\end{definition}

\begin{lemma}
  If \(A\) is invertible then it is non-singular and
  \[
    \det A^{-1} = \frac{1}{\det A}.
  \]
\end{lemma}

\begin{proof}
  \[
    1 = \det I_n = \det(AA^{-1}) = \det A \det A^{-1}
  \]
\end{proof}

\begin{theorem}
  Suppose \(A \in \M_n(\F)\) then TFAE:
  \begin{enumerate}
  \item \(A\) is invertible,
  \item \(A\) is non-singular,
  \item \(r(A) = n\).
  \end{enumerate}
\end{theorem}

\begin{proof}\leavevmode
  \begin{itemize}
  \item \(1 \Rightarrow 2\): done.
  \item \(2 \Rightarrow 3\): suppose that \(r(A) < n\). By rank-nullity \(n(A) > 0\) so \(\exists \lambda \in \F^n \setminus \{0\}\) such that \(A \lambda = 0\). Say \(\lambda = (\lambda_i)\) and \(\lambda_k \neq 0\). Have \(\sum_{i = 1}^{n}A^{(i)}\lambda_i = 0 \). Let
    \[
      B= (e_1|e_2|\cdots|e_{k-1}|\lambda|e_{k+1}|\cdots|e_n)
    \]
    It follows that \(AB\) has \(k\)th column zero so
    \[
      0 = \det AB = \det A \det B = \lambda_k \det A.
    \]
    So \(\det A = 0\).
  \item \(3 \Rightarrow 1\): by rank-nullity.
  \end{itemize}
\end{proof}

\subsection{Determinant of Linear Maps}

\begin{lemma}
  Conjugate matrices have the same determinant.
\end{lemma}

\begin{proof}
  Let \(B = P^{-1}AP\). Then
  \[
    \det B = \det (P^{-1}AP) = \det P^{-1} \det A \det P = \det (P^{-1}P) \det A = \det A.
  \]
\end{proof}

\begin{definition}[Determinant]\index{determinant}
  Let \(\alpha: V \to V\) where \(V\) is a finite-dimensional vector space. The \emph{determinant} of \(\alpha\) is
  \[
    \det \alpha = \det [\alpha]_{\basis B, \basis B}
  \]
  where \(\basis B\) is any basis for \(V\). 
\end{definition}
This is well-defined by the previous lemma.

\begin{theorem}
  \(\det: L(V, V) \to \F\) satisfies
  \begin{enumerate}
  \item \(\det \id = 1\),
  \item \(\det \alpha \compose \beta = \det \alpha \det \beta\),
  \item \(\det \alpha \neq 0\) if and only if \(\alpha\) is invertible, in which case \(\det (\alpha^{-1}) = \frac{1}{\det \alpha}\).
  \end{enumerate}
\end{theorem}

\begin{proof}
  Restatement of previous results.
\end{proof}

\subsection{Determinant of Block-triangular Matrices}

\begin{lemma}
  Suppose \(A \in \M_k(\F), B \in \M_\ell(\F)\) and \(C \in \M_{k, \ell}(\F)\), then
  \[
    \det
    \begin{pmatrix}
      A & C \\
      0 & B
    \end{pmatrix}
    = \det A \det B.
  \]
\end{lemma}

\begin{proof}
  Let \(n = k + \ell\) and call the block matrix \(X = (x_{ij})\), which is an element of \(\M_n(\F)\). Then
  \begin{align*}
    \det X &= \sum_{\sigma \in S_n}^{ }\varepsilon(\sigma) \prod_{i = 1}^{n} x_{\sigma(i), i} \\
    \intertext{Note that \(x_{\sigma(i), i} = 0\) if \(i \leq k\) and \(\sigma(i) > k\). Thus we are only concerned about \(\sigma\) under which these are in different orbits, i.e.\ \(\sigma = \sigma_1\sigma_2\) where \(\sigma_1 \in \sym_{\{1,\dots, k\}}\) and \(\sigma_2 \in \sym_{\{k+1, \dots, n\}}\).}
           &= \sum_{\sigma_1 \in \sym_{\{1, \dots, k\}}}^{ } \varepsilon(\sigma_1) \prod_{j = 1}^{k} a_{\sigma_1(j),j} \\
           &\times \sum_{\sigma_2 \in \sym_{\{k+1, \dots, n\}}}^{ } \varepsilon(\sigma_2) \prod_{j = k + 1}^{n} a_{\sigma_2(j),j} \\
           &= \det A \det B
  \end{align*}
\end{proof}

\begin{corollary}
  For a sequence of matrices \(A_1, \dots, A_k\),
  \[
    \det
    \begin{pmatrix}
      A_1 & & & & \\
      & A_2 & & * & \\
      & & A_3 & & \\
      & 0 & & \ddots & \\
      & & & & A_k
    \end{pmatrix}
    = \prod_{i = 1}^{k} \det A_i
  \]
\end{corollary}

\begin{proof}
  Apply the previous lemma inductively.
\end{proof}

\begin{caution}
  In general,
  \[
    \det
    \begin{pmatrix}
      A & B \\
      C & D
    \end{pmatrix}
    \neq \det A \det D - \det B \det C.
  \]
\end{caution}

\subsection{Volume Interpretation of Determinant}

In \(\R^2\), the determinant of a matrix
\[
  \det
  \begin{pmatrix}
    a_{11} & a_{12} \\
    a_{21} & a_{22} 
  \end{pmatrix}
\]
can be intepreted as the signed area of the parallelogram spanned by the column vectors \(\binom{a_{11}}{a_{21}}\) and \(\binom{a_{12}}{a_{22}}\) of the matrix.
    
Similarly in \(\R^3\) the determinant of a matrix is the signed volume of the parallelepiped spanned by the column vectors of the matrix.

For higher dimensions, although difficult to visualise, the same interpretation still works: consier a hypercube \(H = [0, 1]^n \subseteq \R^n\). Then a map \(A \in \M_n(\F)\) sends
\begin{align*}
  H &\to A(H) \\
  \sum_{i = 1}^{n} t_ie_i &\mapsto \sum_{i = 1}^{n}t_i A^{(i)}
\end{align*}
and the generalised signed volume of RHS is \(\det A\).

\subsection{Determinant of Elementary Operation}

Consider the determinants of elementary column operation matrices:
\begin{itemize}
\item \(E_1\) swaps two columns so \(\det E_1 = -1\),
\item \(E_2\) multiplies a column by \(\lambda \neq 0\) so \(\det E_2 = \lambda\),
\item \(E_3\) adds \(\lambda\) times of a column to another column so \(\det E_3 = 1\).
\end{itemize}

One could prove properties of \(\det\) by decomposing any matrix into elementary matrices.

\subsection{Column Expansion \& Adjugate Matrices}

\begin{lemma}
  Suppose \(A \in \M_n(\F)\), \(A = (a_{ij})\). Define \(A_{\widehat{ij}} \in \M_{n - 1}(\F)\) by deleting row \(i\) and column \(j\) from \(A\). Then \(\det A\) can be calculated by
  \begin{enumerate}
  \item expansion in column \(j\): for a fixed \(j\),
    \[
      \det A = \sum_{i = 1}^{n} (-1)^{i + j} a_{ij} \det A_{\widehat{ij}}.
    \]
  \item expansion in row \(i\): for a fixed \(i\),
    \[
      \det A = \sum_{j = 1}^{n} (-1)^{i + j} a_{ij} \det A_{\widehat{ij}}.
    \]
  \end{enumerate}
\end{lemma}

\begin{remark}
  It is possible to use one of the expressions above to define determinant inductively, with base case \(\det a = a\) for \(n = 1\).
\end{remark}

\begin{eg}
  \[
    \begin{vmatrix}
      a & b & c \\
      d & e & f \\
      g & h & i
    \end{vmatrix}
    =
    a
    \begin{vmatrix}
      e & f \\
      h & i
    \end{vmatrix}
    -b
    \begin{vmatrix}
      d & f \\
      g & i
    \end{vmatrix}
    +c
    \begin{vmatrix}
      d & e \\
      g & h
    \end{vmatrix}
  \]
\end{eg}

\begin{proof}
  We prove \(1\):
  
  \begin{align*}
    \det A &= \det \left( A^{(1)} | \cdots | \sum_{i = 1}^{n} a_{ij}e_i | \cdots | A^{(n)} \right) \\
           &= \sum_{i = 1}^{n} a_{ij} \det( A^{(1)} | \cdots | e_i | \cdots | A^{(n)} ) \\
    \intertext{use row and column operations to move the entry to top left corner,}
           &= \sum_{i = 1}^{n} a_{ij} (-1)^{(i - 1) + (j - 1)} \det
             \begin{pmatrix}
               1 & 0 \\
               0 & A_{\widehat{ij}}
             \end{pmatrix} \\
           &= \sum_{i = 1}^{n} a_{ij} (-1)^{i + j} \det A_{\widehat{ij}}
  \end{align*}
\end{proof}

\begin{definition}[Adjugate]\index{matrix!adjugate}
  Let \(A \in \M_n(\F)\). The \emph{adjugate matrix} of \(A\), \(\adj A\), is the \(n \times n\) matrix
  \[
    (\adj A)_{ij} = (-1)^{i + j} \det A_{\widehat{ji}}.
  \]
\end{definition}

Notice the transposition of indices.

\begin{theorem}\leavevmode
  \begin{enumerate}
  \item \((\adj A ) A = \det A \cdot I\),
  \item If \(A\) is invertible then
    \[
      A^{-1} = \frac{\adj A}{\det A}.
    \]
  \end{enumerate}
\end{theorem}

\begin{proof}\leavevmode
  \begin{enumerate}
  \item For a fixed \(j\), \(\det A = \sum_i (\adj A)_{ji} a_{ij} = (\adj A \cdot A)_{jj}\). For \(j \neq k\), replace the \(j\)th column with the \(k\)th:
    \begin{align*}
      0 &= \det(A^{(1)} | \cdots | A^{(k)} | \cdots | A^{(k)} | \cdots | A^{(n)}) \\
        &= \sum_{i}^{ } (\adj A)_{ji} a_{ik} \\
        &= (\adj A \cdot A)_{jk}
    \end{align*}
  \item If \(A\) is invertible then \(\det A \neq 0\) so
    \[
      I = \frac{\adj A}{\det A} A.
    \]
  \end{enumerate}
\end{proof}

\subsection{Application: System of Linear Equations}

A system of linear equations can be written as
\[
  A \V x = \V b
\]
where \(A \in \M_{m, n}(\F)\) and \(\V b \in \M_{m, 1}(\F)\) are known and \(\V x \in \M_{n, 1}(\F)\) is unknown.

The system has a solution if and only if \(r(A) = r(A|\V b)\) where the matrix on RHS is the \emph{augmented matrix} by adding \(\V b\) as a column to \(A\) since this happens if and only if \(\V b\) is a linear combination of columns of \(A\).

The solution is unique if and only if \(r(A) = n\).

In particular, if \(m = n\), if \(A\) is non-singular then there is a unique solution
\[
  \V x = A^{-1} \V b.
\]

Although in theory we could invert the matrix to solve the system of equations, it is terribly inefficient. Instead, we use

\begin{proposition}[Cramer's rule]
  If \(A \in \M_n(\F)\) is invertible then the system
  \[
    A \V x = \V b
  \]
  has unique solution \(\V x = (x_i)\) where
  \[
    x_i = \frac{\det (A_{\hat{i} \V b})}{\det A}
  \]
  where \(A_{\hat{i} \V b}\) is obtained from \(A\) by deleting \(i\)th column and replacing it with \(\V b\).
\end{proposition}

\begin{proof}
  Assume \(\V x\) is a solution of the system.
  \begin{align*}
    \det (A_{\hat i \V b}) &= \det(A^{(1)} | \cdots | \V b | \cdots | A^{(n)}) \\
                           &= \det(A^{(1)} | \cdots | A \V x | \cdots | A^{(n)}) \\
                           &= \sum_{j = 1}^{n} x_j \det(A^{(1)} | \cdots | A^{(j)} | \cdots | A^{(n)}) \\
    \intertext{\(A^{(j)}\) is one of the other columns unless \(j = i\) so}
                           &= x_i \det A
  \end{align*}
\end{proof}

\begin{corollary}
  If \(A \in \M_n(\Z)\) with \(\det A = \pm 1\), then
  \begin{enumerate}
  \item \(A^{-1} \in \M_n(\Z)\).
  \item Given \(\V b \in \Z^n\), \(A \V x = \V b\) has an integer solution.
  \end{enumerate}
\end{corollary}

\section{Endomorphism}

\subsection{Definitions}

Let \(V\) be an \(\F\)-vector space with \(\dim V = n < \infty\). Let \(\basis B =\{v_1, \dots, v_n\}\) be a basis and \(\alpha \in L(V) = L(V, V)\). The general problem studied in this chapter is to choose a basis \(\basis B\) such that \([\alpha]_{\basis B}\) has ``nice forms'', for example, to be amenable to \(\det\) and \(\tr\).

Suppose there is another basis \(\basis B'\) with change-of-basis matrix \(P\). Recall that
\[
  [\alpha]_{\basis B} = P^{-1}[\alpha]_{\basis B'}P.
\]
The above problem is thus euqivalent to the following: given \(A \in \M_n(\F)\), find \(A'\) conjugate to \(A\) and in a ``nice form''.

What are the nice forms that we desire? The best we can have is

\begin{definition}[Diagonalisable]\index{diagonalisable}
  \(\alpha \in L(V)\) is \emph{diagonalisable} if there exists \(\basis B\) such that \([\alpha]_{\basis B}\) is diagonal.
\end{definition}

A slightly weaker, albeit still ``nice'' enough form is

\begin{definition}[Triangulable]\index{triangulable}
  \(\alpha \in L(V)\) is \emph{triangulable} if there exists \(\basis B\) such that \([\alpha]_{\basis B}\) is upper triangular.
\end{definition}

Equivalent, rephrasing using languages of matrices, \(A \in \M_n(\F)\) is diagonalisable (triangulable, respectively) if it is conjugate to a diagonal (upper triangle, respectively) matrix.

\begin{definition}[Eigenvalue, eigenvector, eigenspace]\index{eigenvalue}\leavevmode
  \begin{enumerate}
  \item \(\lambda \in \F\) is an \emph{eigenvalue} of \(\alpha\) if there exists some \(v \in V\setminus\{0\}\) such that \(\alpha(v) = \lambda v\).
  \item \(v \in V\) is an \emph{eigenvector} of \(\alpha\) if \(\alpha(v) = \lambda v\) for some eigenvalue \(\lambda\).
  \item \(V_\lambda = \{v \in V: \alpha(v) = \lambda v\}\) is the \emph{\(\lambda\)-eigenspace} of \(\alpha\).
  \end{enumerate}
\end{definition}

\begin{remark}
  It is easy to check that \(V_\lambda \leq V\).
\end{remark}

\begin{remark}\leavevmode
  \begin{enumerate}
  \item \(V_\lambda = \ker(\alpha - \lambda \iota)\) and
    \begin{align*}
      & \lambda \text{ is an eigenvalue} \\
      \Leftrightarrow & \alpha - \lambda \iota \text{ is singular} \\
      \Leftrightarrow & \det (\alpha - \lambda \iota) = 0
    \end{align*}
  \item If \(\alpha(v_j) = \lambda v_j\) then the \(j\)th column of \([\alpha]_{\basis B}\) is \((0, \dots, \lambda, \dots, 0)^T\).
  \item \([\alpha]_{\basis B}\) is diagonal if and only if \(\basis B\) consists of eigenvectors. \([\alpha]_{\basis B}\) is upper triangular if and only if \(\alpha(v_j) \in \spans{v_1, \dots, v_j}\) for all \(j\). In particular, \(v_1\) is an eigenvector.
  \end{enumerate}
\end{remark}

\subsection{Polynomial Ring, an Aside}

Before discussing polynomials associated with a linear map, we need some background knowledge about the ambient polynomial space that we will be working with. The following results should be self-evident and proofs are omitted. Most of them will be studied in detail in IB Groups, Rings and Modules and a proof the Fundamental Theorem of Algebra can be found in IB Complex Analysis.

Let
\[
  \F[t] = \{\text{polynomials with coefficients in } \F\}
\]
and \(\deg f\) be the degree of \(f\) in \(\F[t]\). In addition for the convenience of stating the following properties we let \(\deg 0 = -\infty\). We have the following properties:
\begin{enumerate}
\item \(\deg (f + g) \leq \max(\deg f, \deg g), \deg(f g) = \deg f + \deg g\).
\item If \(\lambda \in \F\) is a root of some \(f \in \F[t]\), i.e.\ \(f(\lambda) = 0\) then \((t - \lambda) \divides f\). In other words, \(f(t) = (t - \lambda) g(t)\) for some \(g(t) \in \F[t]\) and \(\deg g = \deg f - 1\).
\item We say \(\lambda\) is a root of \(f \in \F[t]\) with \emph{multiplicity} \(e \in \N\) if \((t - \lambda)^e \divides f\) but \((t - \lambda)^{e + 1} \ndivides f\).
\item A polynomial of degree \(n\) has at most \(n\) roots, counted with multiplicity.
\item Fundamental Theorem of Algebra: any \(f \in \C[t]\) of positive degree has a root (hence \(\deg f\) roots).
\end{enumerate}

\subsection{Characteristic Polynomial of Endormorphism}

\begin{definition}[Characteristic polynomial]\index{polynomial!characteristic}
   The \emph{characteristic polynomial} of \(\alpha \in L(V)\) is
  \[
    \chi_\alpha(t) = \det (\alpha - t \iota).
  \]
  The \emph{characteristic polynomial} of \(A \in \M_n(\F)\) is
  \[
    \chi_A(t) = \det (A - t I).
  \]
\end{definition}

Conjugate matrices have the same characteristic polynomial.

\begin{theorem}
  A linear map \(\alpha\) is triangulable if and only if \(\chi_\alpha(t)\) can be written as a product of linear factors over \(\F\).
\end{theorem}

\begin{proof}\leavevmode
  \begin{itemize}
  \item \(\Rightarrow\): suppose \(\alpha\) is triangulable and is represented by
    \[
      \begin{pmatrix}
        a_1 & \cdots & * \\
        & \ddots & \vdots \\
        0 & & a_n
      \end{pmatrix}
    \]
    with respect to some basis. Then
    \[
      \chi_\alpha(t) = \det
      \begin{pmatrix}
        a_1 - t & \cdots & * \\
        & \ddots & \vdots \\
        0 & & a_n -t
      \end{pmatrix}
      = \prod_{i = 1}^{n} (a_i - t)
    \]
  \item \(\Leftarrow\): induction of \(n = \dim V\): if \(n = 1\) then done. Suppose \(n > 1\) and the theorem holds for all endomorphisms of spaces of smaller dimensions. By hypothesis \(\chi_\alpha(t)\) has a root in \(\F\), say \(\lambda\). Let \(U = V_\lambda \neq 0\), then \(\alpha(U) \leq U\) so \(\alpha\) induces \(\overline \alpha: V/U \to V/U\). Pick basis \(v_1, \dots, v_k\) for \(U\) and extend it to a basis \(\basis B = \{v_1, \dots, v_n\}\) for \(V\). With respect to \(\basis B\), \(\alpha\) has representation
    \[
      \begin{pmatrix}
        \lambda I_k & * \\
        0 & C
      \end{pmatrix}
    \]
    so
    \[
      \chi_\alpha(t) = \det(\alpha - t \iota) = (\lambda - t)^k \chi_{\overline \alpha}(t).
    \]
    Thus \(\chi_{\overline \alpha}(t)\) is also a product of linear factors. Since \(\chi_{\overline \alpha}(t)\) acts on a linear space of strictly smaller dimension, by induction hypothesis there is a basis \(w_{k + 1} + U, \dots, w_n + U\) for \(V/U\) with respect to which \(\overline \alpha\) has an upper-triangular matrix representation, say T. Then with respect to basis \(v_1, \dots, v_k, w_{k + 1}, \dots, w_n\), \(\alpha\) has matrix representation
    \[
      \begin{pmatrix}
        \lambda I_k & * \\
        0 & T
      \end{pmatrix}
    \]
  \end{itemize}
\end{proof}

\begin{eg}
  \label{eg:rotation}
  Let \(\F = \R\), \(V = \R^2\) and \(\alpha\) be a rotation. Then with respect to the standard basis \(\alpha\) has representation
  \[
    \begin{pmatrix}
      \cos \theta & \sin \theta \\
      -\sin \theta & \cos \theta
    \end{pmatrix}
  \]
  and thus \(\chi_\alpha(t) = t^2 - 2 \cos \theta t + 1\), which is irreducible in general. Thus \(\alpha\) is not triangulable over \(\R\).
\end{eg}

\begin{lemma}
  \label{lem:determinant from characteristic}
  Let \(V\) be an \(n\)-dimensional \(\F\)-vector space and \(\alpha \in L(V)\) with \(\chi_\alpha(t) = (-1)^n t^n + c_{n - 1} t^{n - 1} + \dots c_0\). Then
  \begin{itemize}
  \item \(c_0 = \det \alpha\),
  \item \(c_{n - 1} = (-1)^{n - 1} \tr \alpha\) for \(\F = \R\) or \(\C\).
  \end{itemize}
\end{lemma}

\begin{proof}\leavevmode
  \label{proof:determinant from characteristic}
  \begin{itemize}
  \item \(c_0 = \chi_\alpha(0) = \det (\alpha - 0) = \det \alpha\).
  \item If \(\F = \R\) then there is an extension of scalars \(\M_n(\R) \otimes \C \embed \M_n(\C)\) induced by \(\R \embed \C\) (i.e.\ complexification). For \(\F = \C\), use Fundamental Theorem of Algebra to write
    \[
      \chi_\alpha(t) = \det
      \begin{pmatrix}
        a_0 - t & \cdots & * \\
        & \ddots & \vdots \\
        0 & & a_n - t
      \end{pmatrix}
      = \prod_{i = 1}^{n} (a_i - t)
    \]
    where \(\sum_{i = 1}^n a_i = \tr \alpha\).
  \end{itemize}
\end{proof}

\begin{notation}
  Let \(p(t)\) be a polynomial over \(\F\),
  \[
    p(t) = a_nt^n + \dots + a_0 \in \F[t].
  \]
  For \(A \in \M_n(\F)\), define
  \[
    p(A) = a_nA^n + \dots + a_0I \in \M_n(\F).
  \]
  For \(\alpha \in L(V)\), define
  \[
    p(\alpha) = a_n\alpha^n + \dots + a_0\iota \in L(V).
  \]
\end{notation}

\begin{theorem}
  Let \(V\) be a finite-dimensional \(\F\)-vector space. Let \(\alpha \in L(V)\). Then \(\alpha\) is diagonalisable if and only if \(p(\alpha) = 0\) for some \(p \in \F[t]\) which is the product of distinct linear factors.
\end{theorem}

\begin{proof}\leavevmode
  \begin{enumerate}
  \item \(\Rightarrow\): Suppose \(\alpha\) is diagonalisable with distinct eigenvalues \(\lambda_1, \dots, \lambda_k\). Let
    \[
      p(t) = (t - \lambda_1) \cdots (t - \lambda_k).
    \]
    Let \(\basis B\) be a basis of eigenvectors. For \(v \in \basis B\), \(\alpha(v) = \lambda_i v\) for some \(i\). Thus
    \[
      0 = (\alpha - \lambda_i \iota) v \Rightarrow p(\alpha)(v) = 0.
    \]
    As this holds for all \(v \in \basis B\), \(p(\alpha) = 0\).
  \item \(\Leftarrow\): Suppose \(p(\alpha) = 0\) for this \(p\), which is monic wlog. Claim that
    \[
      V = \bigoplus_{i = 1}^k V_{\lambda_i}
    \]
    \begin{proof}
      For \(j = 1, \dots, k\), let
      \[
        q_j(t) = \prod_{i = 1, i \neq j}^k \frac{t - \lambda_i}{\lambda_j - \lambda_i}
      \]
      and \(q(t) = \sum_{j = 1}^k q_j(t)\). \(q(t)\) has degree at most \(k - 1\) and \(q(\lambda_i) = 1\) for all \(i = 1, \dots, k\) so \(q(t) = 1\).

      Let \(\pi_j = q_j(\alpha): V \to V\). By construction
      \[
        \sum_{j = 1}^{k} \pi_j = q(\alpha) = \iota \in L(V)
      \]
      so given \(v \in V\),
      \[
        v = q(\alpha) (v) = \sum_{j = 1}^{k} \pi_j(v).
      \]
      Also
      \[
        (\alpha - \lambda_j \iota)(\pi_j(v)) = (\alpha - \lambda_j\iota)(q_j(\alpha)(v)) = \frac{1}{\prod_{i \neq j}^{ } (\lambda_j - \lambda_i)} \underbrace{p(\alpha)}_{= 0}(v) = 0.
      \]
      We have thus shown that
      \[
        \im \pi_j \leq \ker(\alpha - \lambda_j \iota) = V_{\lambda_j}.
      \]
      Thus \(V = \sum_{j = 1}^{k} V_{\lambda_j}\).

      To prove the sum is direct, suppose \(v \in V_{\lambda_j} \cap (\sum_{i \neq j}^k V_{\lambda_i})\) and apply \(\pi_j\) to \(v\):
      \begin{align*}
        v \in V_{\lambda_j} &\Rightarrow \pi_j(v) = \prod_{i = 1, i \neq j}^{k} \frac{\lambda_j - \lambda_i}{\lambda_j - \lambda_i} v = v \\
        v \in \sum_{i \neq j}^{k}V_{\lambda_i} &\Rightarrow \pi_j(v) = 0
      \end{align*}
        so \(v = 0\) and the sum is direct.

        Now take the union of bases for \(V_{\lambda_i}\) as a basis for \(V\).
    \end{proof}
  \end{enumerate}
\end{proof}

\begin{remark}\leavevmode
  \begin{enumerate}
  \item \(\pi_j\) is the projection from \(V\) to \(V_{\lambda_j}\).
  \item The proof shows that for \(k\) distinct eigenvalues \(\lambda_1, \dots \lambda_k\) of \(\alpha\), the sum \(\sum_j V_{\lambda_j}\) is direct. The only way for diagonalisation to fail is if \(\sum_j V_{\lambda_j} \lneq V\).
  \end{enumerate}
\end{remark}

\begin{corollary}
  Suppose \(A \in \M_n(\C)\) has finite order then \(A\) is diagonalisable. 
\end{corollary}

\begin{proof}
  \(p(A) = 0\) for \(p(t) = t^m - 1\) where \(m\) is the order of \(A\). This factorises as \(\prod_{i = 0}^{m - 1} (t - \xi^i)\) where \(\xi\) is a primitive \(m\)th root of unity.
\end{proof}

\begin{theorem}[Simultaneous diagonalisation]
  Let \(\alpha, \beta \in L(V)\) be diagonalisable. Then \(\alpha\) and \(\beta\) are \emph{simultaneous diagonalisable} (there exists a basis with respect to which they are both diagonal) if and only if \(\alpha\) and \(\beta\) commute.
\end{theorem}

\begin{proof}\leavevmode
  \begin{itemize}
  \item \(\Rightarrow\): Suppose there is a basis \(\basis B\) such that \(A = [\alpha]_{\basis B}\) and \(B = [\beta]_{\basis B}\) are diagonal. Any two diagonal matrices commute so \(AB = BA\), \(\alpha\beta = \beta\alpha\).
  \item \(\Leftarrow\): Suppose \(\alpha\) and \(\beta\) commute and both are diagonalisable. We have
    \[
      V = V_1 \oplus \cdots \oplus V_k
    \]
    where \(V_i = \ker(\alpha - \lambda_i\iota)\). Claim that \(\beta(V_j) \leq V_j\): suppose \(v \in V_j\),
    \[
      \alpha\beta (v) = \beta\alpha (v) = \beta(\lambda_j v) = \lambda_j \beta(v).
    \]

    As \(\beta\) is diagonalisable, there is a polynomial \(p\) with distinct linear factors such that \(p(\beta) = 0\). Now
    \[
      p(\beta|_{V_i}) = p(\beta)|_{V_i} = 0
    \]
    so \(\beta|_{V_i} \in L(V_i)\) is diagonal. Pick a basis \(\basis B_i\) of \(V_i\) combining its eigenvectors for \(\beta\). By construction these are also eigenvectors for \(\alpha\). With respect to \(\basis B = \bigcup_i \basis B_i\) both \(\alpha\) and \(\beta\) are diagonal.
  \end{itemize}
\end{proof}

\begin{lemma}[{\(\F[t]\)} as a Euclidean domain]
  Given \(a, b \in \F[t]\) with \(b \neq 0\), there eixst \(q, r \in \F[t]\) with \(\deg r < \deg b\) and \(a = qb + r\).
\end{lemma}

\begin{proof}
  IB Groups, Rings and Modules.
\end{proof}

\begin{definition}[Minimal polynomial]\index{polynomial!minimal}
  Suppose \(\alpha \in L(V)\) and \(V\) is finite-dimensional. The \emph{minimal polynomial} of \(\alpha\), \(m_\alpha\), is the monic non-zero polynomial of smallest degree such that
  \[
    m_\alpha(\alpha) = 0.
  \]
\end{definition}

\begin{remark}
  Let \(\dim V = n < \infty\), \(\dim L(V) = n^2\) so
  \[
    \iota, \alpha, \alpha^2, \dots, \alpha^{n^2} \in L(V)
  \]
  must be linearly dependent so there is a non-trivial relation. Thus minimal polynomial exists.
\end{remark}

\begin{lemma}
  Let \(\alpha \in L(V)\), \(p \in \F[t]\). Then \(p(\alpha) = 0\) if and only if \(m_\alpha(t) \divides p(t)\).
\end{lemma}

\begin{proof}
  By Euclidean algorithm there exist \(q, r \in \F[t]\) such that
  \[
    p(t) = m_\alpha(t) q(t) + r(t)
  \]
  where \(\deg r < \deg m_\alpha\). Then
  \[
    0 = p(\alpha) = m_\alpha(\alpha) q(\alpha) + r(\alpha)
  \]
  so \(r(\alpha) = 0\). By the minimality of the degree of \(m_\alpha\), \(r = 0\).
\end{proof}

\begin{corollary}
  \(m_\alpha\) is uniquely defined.
\end{corollary}

\begin{proof}
  Suppose \(m_1\) and \(m_2\) are both minimal polynomials of \(\alpha\). Then by the previous lemma \(m_1 \divides m_2\) and vice versa. By assumption both of them are monic so \(m_1 = m_2\).
\end{proof}

\begin{theorem}[Cayley-Hamilton Theorem]
  Let \(V\) be a finite-dimensional \(\F\)-vector space. Let \(\alpha \in L(V)\). Then
  \[
    \chi_\alpha(\alpha) = 0.
  \]
\end{theorem}

First we give a proof for \(\F = \C\):

\begin{proof}
  For some basis \(\basis B = \{v_1, \dots, v_n\}\), \(\alpha\) has matrix representation
  \[
    [\alpha]_{\basis B} =
    \begin{pmatrix}
      a_1 & \cdots & * \\
      & \ddots & \vdots \\
      0 & & a_n
    \end{pmatrix}
  \]
  Let \(U_j = \spans{v_1, \dots, v_j}\). Then \((\alpha - a_j \iota) U_j \leq U_{j - 1}\) so
  \[
    \underbrace{(\alpha - a_1 \iota) (\alpha - a_2 \iota) \cdots \underbrace{(\alpha - a_{n - 1} \iota) \underbrace{(\alpha - a_n \iota) V}_{\leq U_{n - 1}}}_{\leq U_{n - 2}}}_{\leq (\alpha - a_1\iota) U_1 = 0} = 0
  \]
  so
  \[
    \chi_\alpha(\alpha) = 0.
  \]
\end{proof}

However, this proof is unsatisfactory in that it relies on the fact of \(\C\) being algebraically closed, which is partially, to say the least, an analytical and not an algebraic property\footnote{While being closed is an algebraic property, the construction of \(\C\) via \(\R\) from \(\Q\) is not. The point here is that Caylay-Hamilton holds for all fields, not just closed ones.}. In actuality, Cayley-Hamilton is a general result that applies to all fields. Thus we give an alternative algebraic proof:

\begin{proof}(Non-examinable)
  Let \(A \in \M_n(\F)\), then
  \[
    \chi_A(t) \cdot (-1)^n = t^n + a_{n - 1}t^{n - 1} + \dots + a_0 = \det(tI - A).
  \]
  For any matrix \(B\), we have
  \[
    B \adj B = \det B \cdot I.
  \]
  Let \(B = tI - A\). Then \(\adj B\) is a matrix whose entries are polynomials in \(t\) of degree smaller than \(n\), i.e.\ polynomials in \(t\) with coefficients in \(\M_n(\F)\).

  Thus
  \[
    (tI - A) \underbrace{(B_{n - 1}t^{n - 1} + \cdots + B_1 t + B_0)}_{\adj B} = \underbrace{(t^n + a_{n - 1}t^{n - 1} + \cdots + a_0)}_{\det B} I
  \]
  Equating the coefficients of each power of \(t\),
  \begin{align*}
    I &= B_{n - 1} \\
    a_{n - 1} I &= B_{n - 2} - AB_{n - 1} \\
    & \vdots \\
    a_0 I &= -AB_0
  \end{align*}
  multiply by \(A^{n - i + 1}\) for the \(i\)th row
  \begin{align*}
    A^n &= A^n B_{n - 1} \\
    a_{n - 1} A^{n - 1} &= A^{n - 1} B_{n - 2} - A^n B_{n - 1} \\
    & \vdots \\
    a_0 I &= -AB_0
  \end{align*}
  and add them up,
  \[
    A^n + a_{n - 1}A^{n - 1} + \dots a_1 A + A_0 I = 0.
  \]
\end{proof}

\begin{definition}[Algebraic multiplicity]\index{multiplicity!algebraic}
  Let \(\lambda\) be an eigenvalue of \(\alpha \in L(V)\) where \(V\) is a finite-dimensional \(\F\)-vector space. Write
  \[
    \chi_\alpha(t) = (t - \lambda)^{a_\lambda} q(t)
  \]
  for some \(q(t) \in \F[t]\) and \((t - \lambda) \ndivides q(t)\). \(a_\lambda\) is the \emph{algebraic multiplicity} of \(\lambda\) as an eigenvalue of \(\alpha\).
\end{definition}

\begin{definition}[Geometric multiplicity]\index{multiplicity!geometric}
  \(g_\lambda = n(\alpha - \lambda \iota)\) is the \emph{geometric multiplicity} of \(\alpha\).
\end{definition}

\begin{lemma}
  If \(\lambda\) is an eigenvalue then
  \[
    1 \leq g_\lambda \leq a_\lambda.
  \]
\end{lemma}

\begin{proof}
  \(1 \leq g_\lambda\) since \(\alpha - \lambda \iota\) is singular.

  Let \(\basis B = \{v_1, \dots v_n\}\) be a basis of \(V\) with \(\{v_1, \dots, v_g\}\) a basis of \(\ker(\alpha - \lambda \iota)\). Let \(g = g_\lambda\). Then
  \[
    [\alpha]_{\basis B} =
    \begin{pmatrix}
      \lambda I_g & * \\
      0 & A_1
    \end{pmatrix}
  \]
  where \(A_1 \in \M_{n - g}(\F)\). Thus
  \[
    \chi_\alpha(t) = (t - \lambda)^g \alpha_{A_1}(t)
  \]
  and \(g_\lambda \leq a_\lambda\).
\end{proof}

\begin{lemma}
  Let \(\lambda\) be an eigenvalue. Let \(c_\lambda\) be the multiplicity of \(\lambda\) as a root of \(m_\alpha\). Then
  \[
    1 \leq c_\lambda \leq a_\lambda.
  \]
\end{lemma}

\begin{proof}
  As \(m_\alpha \divides \chi_\alpha\), \(c_\lambda \leq a_\lambda\).

  As \(\lambda\) is an eigenvalue, \(\alpha(v) = \lambda v\) for some \(v \neq 0\). Now given \(p \in \F[t]\), \(p(\alpha)(v) = p(\lambda)(v)\). Apply this to \(m_\alpha\),
  \[
    0 = m_\alpha(\alpha)(v) = m_\alpha(\lambda)(v)
  \]
  so \(m_\alpha(\lambda) = 0\).
\end{proof}

\begin{eg}\leavevmode
  \begin{enumerate}
  \item Let
  \[
    A =
    \begin{pmatrix}
      1 & 0 & -2 \\
      0 & 1 & 1 \\
      0 & 0 & 2
    \end{pmatrix}
  \]
  then
  \[
    \chi_A(t) = \det(A - tI) = (2 - t)(1 - t)^2.
  \]
  There are two candidates for the minimal polynomial:
  \begin{itemize}
  \item \((t - 2)(t - 1)^2\),
  \item \((t - 2)(t - 1)\).
  \end{itemize}
  We can check that \((A - I)(A - 2I) = 0\) so the second one is the minimal polynomial. It follows that \(A\) is diagonalisable.
\item Let
  \[
    A =
    \begin{pmatrix}
      \lambda & 1 & & \\
      & \lambda & 1 &  \\
      & & \ddots & 1 \\
      & & & \lambda
    \end{pmatrix}
  \]
  which has \(g_\lambda = 1, a_\lambda = n, c_\lambda = n\).
  \end{enumerate}
\end{eg}

\begin{lemma}
  Let \(\alpha \in L(V)\), then TFAE:
  \begin{enumerate}
  \item \(\alpha\) is diagonalisable,
  \item \(a_\lambda = g_\lambda\) for all eigenvalues \(\lambda\),
  \item if \(\F = \C\), \(c_\lambda = 1\) for all eigenvalues \(\lambda\).
  \end{enumerate}
\end{lemma}

\begin{proof}\leavevmode
  \begin{itemize}
  \item \(1 \Leftrightarrow 2\): Let \(\lambda_1, \dots, \lambda_k\) be eigenvalues of \(\alpha\). Then \(\alpha\) is diagonalisable if and only if \(V = \bigoplus_i V_{\lambda_i}\). Take dimension of both sides,
    \begin{align*}
      \dim V &= n = \deg \chi_\alpha = a_1 + \dots + a_k \\
      \dim \bigoplus_i V_{\lambda_i} &= g_1 + \dots + g_k
    \end{align*}
    But \(g_i \leq a_i\) for all \(i\) so \(\alpha\) is diagonalisable if and only if \(g_i = \alpha_i\) for all \(i\).
  \item \(2 \Leftrightarrow 3\): By the Fundamental Theorem of Algebra, \(m_\alpha\) is a product of linear factors. \(\alpha\) is diagonalisable if and only if these are all distinct, i.e. \(c_\lambda = 1\) for all eigenvalues \(\lambda\).
  \end{itemize}
\end{proof}

\begin{remark}
  Over \(\C\),
  \begin{align*}
    \chi_\alpha(t) &= (\lambda_1 - t)^{a_1} \cdots (\lambda_k - t)^{a_k} \\
    m_\alpha(t) &= (t - \lambda_1)^{c_1} \cdots (t - \lambda_k)^{c_k}
  \end{align*}
  with \(1 \leq c_i \leq a_i\).
\end{remark}

\begin{definition}[Jordan normal form]\index{Jordan normal form}
  \(A \in \M_n(\F)\) is in \emph{Jordan normal form} if it is a block diagonal matrix
  \[
    A =
    \begin{pmatrix}
      J_{n_1}(\lambda_1) & & & \\
      & J_{n_2}(\lambda_2) & & \\
      & & \ddots & \\
      & & & J_{n_k}(\lambda_k)
    \end{pmatrix}
  \]
  where \(k \geq 1\), \(n_1, \dots, n_k \in \N\) with \(\sum_i n_i = n\), \(\lambda_i \in \F\) not necessarily distinct and
  \[
    J_m(\lambda) =
    \begin{pmatrix}
      \lambda & 1 & & \\
      & \lambda & 1 & \\
      & & \ddots & 1 \\
      & & & \lambda
    \end{pmatrix}
    \in M_m(\F)
  \]
  is a \emph{Jordan block}.
\end{definition}

\begin{theorem}
  \label{thm:jordan normal form}
  Every \(A \in \M_n(\C)\) is similar to a matrix in Jordan normal form, unique up to reordering the Jordan blocks.
\end{theorem}

\begin{proof}(Non-examinable)
  It is a consequence of a main theorem on modules in IB Groups, Rings and Modules.
\end{proof}

In the rest of this section assume \(\F = \C\) unless stated otherwise.

\begin{eg}\leavevmode
  \begin{enumerate}
  \item Classification of Jordan normal forms for \(\M_2(\C)\):
  \[
    \begin{array}[h]{c|c|c}
      \begin{psmallmatrix}
        \lambda_1 & \\
        & \lambda_2
      \end{psmallmatrix}
        &
          \begin{psmallmatrix}
            \lambda & \\
            & \lambda
          \end{psmallmatrix}
        &
          \begin{psmallmatrix}
            \lambda & 1 \\
            & \lambda
          \end{psmallmatrix}
      \\ \hline
      (t - \lambda_1)(t - \lambda_2) & t - \lambda & (t - \lambda)^2
    \end{array}
  \]
\item Classification of Jordan normal forms for \(\M_3(\C)\):
  \[
    \begin{array}[h]{c|c|c}
      \begin{psmallmatrix}
        \lambda_1 & & \\
        & \lambda_2 & \\
        & & \lambda_3
      \end{psmallmatrix}
        &
          \begin{psmallmatrix}
            \lambda_1 & & \\
            & \lambda_2 & \\
            & & \lambda_2
          \end{psmallmatrix}
        &
          \begin{psmallmatrix}
            \lambda & & \\
            & \lambda & \\
            & & \lambda
          \end{psmallmatrix}
      \\ \hline
      (t - \lambda_1)(t - \lambda_2)(t - \lambda_3) & (t - \lambda_1)(t - \lambda_2) & t - \lambda \\ \hline \hline
      & & \\
      \begin{psmallmatrix}
        \lambda_1 & & \\
        & \lambda_2 & 1 \\
        & & \lambda_2
      \end{psmallmatrix}
        &
          \begin{psmallmatrix}
            \lambda & & \\
            & \lambda & 1 \\
            & & \lambda
          \end{psmallmatrix}
        &
          \begin{psmallmatrix}
            \lambda & 1 & \\
            & \lambda & 1 \\
            & & \lambda
          \end{psmallmatrix}
      \\ \hline
      (t - \lambda_1)(t - \lambda_2)^2 & (t - \lambda)^2 & (t - \lambda)^3
    \end{array}
  \]
  \end{enumerate}
\end{eg}

\begin{theorem}[Generalised Eigenspace Decomposition]
  \label{thm:generalised eigenspace decomposition}
  Let \(V\) be a finite-dimensional \(\C\)-vector space and \(\alpha \in L(V)\). Suppose that
  \[
    m_\alpha(t) = (t - \lambda_1)^{c_1} \cdots (t - \lambda_k)^{c_k}
  \]
  where \(\lambda_i\)'s are distinct. Then
  \[
    V = \bigoplus_j V_j
  \]
  where
  \[
    V_j = N(\alpha - \lambda_j \iota)^{c_j}
  \]
  is the \emph{generalised eigenspace}.
\end{theorem}

\begin{proof}[Sketch of proof]
  Let
  \[
    p_j(t) = \prod_{i \neq j}^{ } (t - \lambda_i)^{c_i}.
  \]
  The \(p_j\) have no common factor so by Euclidean algorithm we can find \(q_1, \dots, q_k \in \C[t]\) such that
  \[
    \sum_{j}^{ } p_j(t)q_j(t) = 1.
  \]
  Let \(\pi_j = q_j(\alpha)p_j(\alpha) \in L(V)\). Note \(\sum_{j = 1}^{k} \pi_j = \iota\).
  \begin{enumerate}
  \item As \(m_\alpha(\alpha) = 0\), \((\alpha - \lambda_j \iota)^{c_j} \pi_j = 0\) so \(\im \pi_j \leq V_j\).
  \item Suppose \(v \in V\), \(v = \iota(v) = \sum \pi_j(v)\) so \(V = \sum_j V_j\).
  \item To show the sum is direct, \(\pi_i \pi_j = 0\) for \(i \neq j\) so
    \[
      \pi_i = \pi_i \left( \sum_{j = 1}^{k} \pi_j \right) = \pi_i^2
    \]
    i.e.\ \(\pi_i\) is a projection. Then
    \[
      \pi_i |_{V_j} =
      \begin{cases}
        \id & i = j \\
        0 & i \neq j
      \end{cases}
    \]
    Directness follows.
  \end{enumerate}
\end{proof}

\begin{remark}\leavevmode
  \begin{enumerate}
  \item We can use \nameref{thm:generalised eigenspace decomposition} to reduce the proof of \Cref{thm:jordan normal form} to a single eigenvalue.
  \item Considering \(\alpha - \lambda \iota\) can reduce to the case of eigenvalue \(0\).
  \end{enumerate}
\end{remark}

\begin{lemma}
  Let \(\alpha \in L(V)\) with Jordan normal form \(A \in \M_n(\C)\). Then the number of Jordan blocks \(J_\ell(\lambda)\) of \(A\) with \(\ell \geq 1\) is
  \[
    n((\alpha - \lambda \iota)^\ell) - n((\alpha - \lambda \iota)^{\ell - 1}).
  \]
\end{lemma}

\begin{proof}
  Work blockwise, for each \(s \times s\) block, 
  \[
    \begin{array}[h]{c|c|c}
      \begin{psmallmatrix}
        \lambda & 1 & & \\
        & \ddots & \ddots & \\
        & & \ddots & 1 \\
        & & & \lambda
      \end{psmallmatrix}
        &
          \begin{psmallmatrix}
            0 & 1 & & \\
            & & \ddots & \\
            & & & 1 \\
            & & & 0
          \end{psmallmatrix}
                 &
                   \begin{psmallmatrix}
                     0 & 0 & 1 & \\
                     & & \ddots & 1 \\
                     & & & 0 \\
                     & & & 0
                   \end{psmallmatrix}
      \\ \hline
      J_s(\lambda) & J_s(\lambda) - \lambda I & (J_s(\lambda) - \lambda I)^2
    \end{array}
  \]
  so
  \[
    n((J_s(\lambda) - \lambda I)^k) =
    \begin{cases}
      k & k \leq s \\
      s & k \geq s
    \end{cases}
  \]
\end{proof}

\begin{eg}
  Let
  \[
    A =
    \begin{pmatrix}
      0 & -1 \\
      1 & 2
    \end{pmatrix}
  \]
  we want to find a basis \(\basis B = \{v_1, v_2\}\) with respect to which \(A\) is in Jordan normal form.
  \begin{enumerate}
  \item
    \[
      \chi_A(t) =
      \begin{vmatrix}
        -t & -1 \\
        1 & 2 - t
      \end{vmatrix}
      = t^2 - 2t + 1 = (t - 1)^2
    \]
    There are two possibilities:
    \begin{enumerate}
    \item \(m_A(t) = t - 1\). Then the Jordan normal form is
      \[
        \begin{pmatrix}
          1 & 0 \\
          0 & 1
        \end{pmatrix}
      \]
    \item \(m_A = (t - 1)^2\). Then the Jordan normal form is
      \[
        \begin{pmatrix}
          1 & 1 \\
          0 & 1
        \end{pmatrix}
      \]
    \end{enumerate}
    A trick here is to note that if \(A\) is conjugate to \(I\) then \(A = I\). Thus (b) holds.
  \item The eigenspace is spanned by \(v_1 = \binom{1}{-1}\).
  \item \(v_2\) satisfies \((A - I)v_2 = v_1\) so
    \[
      \begin{pmatrix}
        -1 & -1 \\
        1 & 1
      \end{pmatrix}
      v_2 =
      \begin{pmatrix}
        1 \\
        -1
      \end{pmatrix}
    \]
    so \(v_2 = \binom{-1}{0}\). Note that \(v_2\) is not unique.
  \item Finally,
    \[
      A =
      \begin{pmatrix}
        1 & -1 \\
        -1 & 0
      \end{pmatrix}
      \begin{pmatrix}
        1 & 1 \\
        0 & 1
      \end{pmatrix}
      \begin{pmatrix}
        1 & -1 \\
        -1 & 0
      \end{pmatrix}
      ^{-1}
    \]
  \end{enumerate}
\end{eg}

We can use the diagonalisation to calculate powers of matrices:
\[
  A^n = (P^{-1}JP)^n = P^{-1}J^nP = P^{-1}
  \begin{pmatrix}
    1 & n \\
    0 & 1
  \end{pmatrix}
  P
\]

\begin{remark}
  In Jordan normal form,
  \begin{itemize}
  \item \(a_\lambda\) is the total number of times that \(\lambda\) appears in the diagonal.
  \item \(g_\lambda\) is the number of \(\lambda\)-Jordan blocks.
  \item \(c_\lambda\) is the size the largest \(\lambda\)-Jordan block.
  \end{itemize}
\end{remark}

\section{Bilinear Form II}

\subsection{Symmetric Bilinear Forms}

In this chapter we are going to studying a special bilinear form (and variants whereof) in detail. Let \(\varphi: V \times V \to \F\) be a bilinear form on \(V\) and assume we take the same basis for both factors of \(V\), say \(\basis B\). Therefore if \(\dim V < \infty\), \(\varphi\) has matrix representation
\[
  [\varphi]_{\basis B} = [\varphi]_{\basis B, \basis B}.
\]

Recall that
\begin{lemma}
  Let \(\varepsilon: V \times V \to \F, \dim V < \infty\) and \(\basis B\) and \(\basis B'\) are two bases for \(V\). Let \(P = [\id]_{\basis B', \basis B}\). Then
  \[
    [\varphi]_{\basis B'} = P^T[\varphi]_{\basis B}P.
  \]
\end{lemma}

\begin{proof}
  Special case of \Cref{prop:change of basis of bilinear form}.
\end{proof}

This motivates us to define a relation on \(\M_n(\F)\)

\begin{definition}[Congruency]\index{matrix!congruency}
  \(A, B \in \M_n(\F)\) are \emph{congruent} if
  \[
    A = P^TBP
  \]
  for some invertible \(P\).
\end{definition}

\begin{note}
  This is an equivalence relation.
\end{note}

Naturally, we want to find nice forms to which a general bilinear form is congruent. Certainly the nicest form we can have is diagonal matrix. It turns out the property we require a bilinear form to be ``diagonalisable'' is

\begin{definition}[Symmetric]\index{bilinear!symmetric}
  A bilinear form \(\varphi\) on \(V\) is \emph{symmetric} if
  \[
    \varphi(u, v) = \varphi(v, u)
  \]
  for all \(u, v \in V\).
\end{definition}

\begin{note}\leavevmode
  \begin{itemize}
  \item \(A \in \M_n(\F)\) is symmetric if \(A = A^T\). Then \(\varphi\) is symmetric if and only if \([\varphi]_{\basis B}\) is symmetric for any basis \(\basis B\), if and only if \([\varphi]_{\basis B}\) is symmetric for one \(\basis B\).
  \item To be able to be represented by a diagonal matrix, \(\varphi\) needs to be symmetric:
    \[
      [\varphi]_{\basis B} = P^TAP = D \Rightarrow D^T = D = P^TA^TP \Rightarrow A = A^T
    \]
  \end{itemize}
\end{note}

\begin{definition}[Quadratic form]\index{quadratic form}
  A map \(Q: V \to \F\) is a \emph{quadratic form} if there is a bilinear form \(\varphi\) on \(V\) such that
  \[
    Q(v) = \varphi(v, v)
  \]
  for all \(v \in V\).
\end{definition}

\begin{eg}
  Let \(V = \R^2\). A general quadratic form is
  \[
    \begin{pmatrix}
      x \\
      y
    \end{pmatrix}
    \mapsto
    \begin{pmatrix}
      x & y
    \end{pmatrix}
    %
    \begin{pmatrix}
      a & b \\
      c & d
    \end{pmatrix}
    %
    \begin{pmatrix}
      x \\
      y
    \end{pmatrix}
    = ax^2 + (b + c) xy + dy^2
  \]
\end{eg}

\begin{remark}
  A quadratic form does not change under \(A \mapsto \frac{1}{2}(A + A^T)\) where \(A\) is a representation of the inducing bilinear form.
\end{remark}

\begin{proposition}
  Assume \(\ch \F \neq 2\). If \(Q: V \to \F\) is a quadratic form then there exists a unique symmetric bilinear form \(\varphi\) on \(V\) such that
  \[
    Q(v) = \varphi(v, v)
  \]
  for all \(v \in V\).
\end{proposition}

\begin{proof}
  First we prove the existence. Let \(\psi\) be a bilinear form on \(V\) such that \(Q(v) = \psi(v, v)\) for all \(v \in V\). We construct a symmetric bilinear form by adding \(\psi\) and its transpose. Let
  \[
    \varphi(u, v) = \frac{1}{2}(\psi(u, v) + \psi(v, u))
  \]
  (this is where we require \(\ch \F \neq 2\)) then it is bilinear and symmetric and
  \[
    \varphi(v, v) = \psi(v, v) = Q(u).
  \]

  To show the uniqueness, suppose \(\varphi\) is such a symmetric bilinear form. Consider
  \begin{align*}
    Q(u + v) &= \varphi(u + v, u + v) \\
             &= \varphi(u, u) + \varphi(u, v) + \varphi(v, u) + \varphi(v, v) \\
             &= Q(u) + 2\varphi(u, v) + Q(v)
  \end{align*}
  Rearrange,
  \[
    \varphi(u, v) = \frac{1}{2}(Q(u + v) - Q(u) - Q(v))
  \]
  which is uniquely determined.
\end{proof}

\begin{remark}
  The last identity
  \[
    \varphi(u, v) = \frac{1}{2}(Q(u + v) - Q(u) - Q(v))
  \]
  is called the \emph{polarisation identity} and will appear later.
\end{remark}

The note after the definition of symmetric bilinear form shows that being symmetric is a necessary condition for a bilinear form to be ``diagonalisable''. The following theorem says that it is also sufficient:

\begin{theorem}
  Let \(\varphi\) be a symmetric bilinear form on \(V\), an \(\F\)-vector space and assume \(\ch \F \neq 2\) and \(\dim V < \infty\). Then there is a basis \(\basis B\) of \(V\) such that \([\varphi]_{\basis B}\) is diagonal.
\end{theorem}

\begin{proof}
  Induction on \(n = \dim V\). If \(n = 0\) or \(1\) then obviously true.

  Suppose the theorem holds for all spaces of dimension smaller than \(n\). There are two cases to consider:
  \begin{enumerate}
  \item if \(\varphi(u, u ) = 0\) for all \(u\) then by the polarisation identity \(\varphi = 0\) so diagonal.
  \item otherwise choose \(e_1 \in V\) such that \(\varphi(e_1, e_1) \neq 0\). Let
    \[
      U = \spans{e_1}^\perp = \{u \in V: \varphi(e_1, u) = 0\} = \ker (\varphi(e_1, -): V \to \F)
    \]
    which has dimension \(n - 1\) by rank-nullity. Moreover, \(V = \spans{e_1} \oplus U\) since \(\spans{e_1} \cap U = 0\) and \(\dim(\spans{e_1} \oplus U) = n\). Consider \(\varphi|_U: U \times U \to \F\) which is also symmetric bilinear. By induction hypothesis there is a basis \(e_2, \dots e_n\) of \(U\) with respect to which \(\varphi|_U\) is diagonal. Now \(\varphi\) is diagonal with respect to \(e_1, \dots, e_n\).
  \end{enumerate}
\end{proof}

\begin{notation}
  In \(V = \R^n\) with standard basis \(e_1, \dots, e_n\), write
  \[
    Q(x_1, x_2, \dots, x_n) = Q \left(\sum_{i = 1}^n x_i e_i \right).
  \]
\end{notation}

\begin{eg}
  Let \(V = \R^3\) with standard basis \(e_1, e_2, e_3\) and
  \[
    Q(x_1, x_2, x_3) = x_1^2 + x_2^2 + 2x_3^2 + 2x_1x_2 + 2x_1x_3 -2x_2x_3.
  \]
  We want a basis \(f_1, f_2, f_3\) of \(\R^3\) such that
  \[
    Q(af_1 + bf_2 + cf_3) = \lambda a^2 + \mu b^2 + \nu c^2
  \]
  for some \(\lambda, \mu, \nu \in \R\), which are the diagonal entries.

  The martix representation of \(Q\) with repect to \(e_1, e_2, e_3\) is
  \[
    A =
    \begin{pmatrix}
      1 & 1 & 1 \\
      1 & 1 & -1 \\
      1 & -1 & 2
    \end{pmatrix}
  \]

  We could use the algorithm as outlined in the induction proof above but choose to do it differently by completing the square:
    \begin{align*}
      Q(x_1, x_2, x_3) &= \underbrace{(x_1 + x_2 + x_3)^2}_{\text{used all terms in } x_1} + x_3^2 - 2x_2x_3 - 2 x_2x_3 \\
                       &= (x_1 + x_2 + x_3)^2 + \underbrace{(x_3 - 2x_2)^2}_{\text{used all terms in } x_3} - (2x_2)^2
    \end{align*}
    From here we can read off the diagonal matrix and the basis: for some \(P\),
    \[
      P^TAP =
      \begin{pmatrix}
        1 & 0 & 0 \\
        0 & 1 & 0 \\
        0 & 0 & -1
      \end{pmatrix}
    \]
    To find \(P\), note that
    \[
      \begin{pmatrix}
        x_1' \\
        x_2' \\
        x_3'
      \end{pmatrix}
      =
      \underbrace{
      \begin{pmatrix}
        1 & 1 & 1 \\
        0 & -2 & 1 \\
        0 & 2 & 0 
      \end{pmatrix}
    }_{P^{-1}}
    %
    \begin{pmatrix}
      x_1 \\
      x_2 \\
      x_3
    \end{pmatrix}
    \]
\end{eg}

\begin{corollary}
  Let \(\varphi\) be a symmetric bilinear form on \(V\), a finite-dimensional \(\C\)-vector space. Then there is a basis \(\basis B = \{v_1, \dots v_n\}\) of \(V\) such that
  \[
    [\varphi]_{\basis B} =
    \begin{pmatrix}
      I_r & 0 \\
      0 & 0
    \end{pmatrix}
  \]
  where \(r = r(\varphi)\).
\end{corollary}

\begin{proof}
  Pick basis \(\basis E = \{e_1, \dots e_n\}\) such that
  \[
    [\varphi]_{\basis E} =
    \begin{pmatrix}
      a_1 & & \\
      & \ddots & \\
      & & a_n
    \end{pmatrix}
  \]
  Reorder the \(e_i\)'s such that
  \[
    \begin{cases}
      a_i \neq 0 & 1 \leq i \leq r \\
      a_i = 0 & i > r
    \end{cases}
  \]
  For \(i \leq r\), pick a complex square root of \(a_i\), say \(\sqrt{a_i}\). Now let
  \[
    v_i =
    \begin{cases}
      \frac{e_i}{\sqrt{a_i}} & 1 \leq i \leq r \\
      e_i & i > r
    \end{cases}
  \]
\end{proof}

\begin{corollary}
  Every symmetric matrix \(A \in \M_n(\C)\) is congruent to a unique matrix of the form \(\begin{psmallmatrix} I_r & 0 \\ 0 & 0 \end{psmallmatrix}\).
\end{corollary}

Equivalently,
\[
  Q \left( \sum_{i = 1}^{n} \lambda_i v_i \right) = \sum_{i = 1}^{r} \lambda_i^2.
\]

We have derived a corollary for our favourite field \(\C\), and there is another one corresponding to our second favourite field, \(\R\):

\begin{corollary}
  Let \(\varphi\) be a symmetric bilinear form on \(V\), a finite-dimensional \(\R\)-vector space. There is a basis \(\basis B = \{v_1, \dots, v_n\}\) such that
  \[
    [\varphi]_{\basis B} =
    \begin{pmatrix}
      I_p & & \\
      & -I_q & \\
      & & 0
    \end{pmatrix}
  \]
  where \(p, q \geq 0\) and \(p + q = r(\varphi)\).
\end{corollary}

\begin{proof}
  The proof is the same as for \(\C\) up to the point of exhibiting a basis with respect to which \(\varphi\) is diagonal. Note that we \emph{cannot} choose a square root for all the entries. Instead, reorder the indices such that
  \[
    \begin{cases}
      a_i > 0 & 1 \leq i \leq p \\
      a_i < 0 & p + 1 \leq i \leq p + q \\
      a_i = 0 & i > p + q
    \end{cases}
  \]
  and let
  \[
    v_i =
    \begin{cases}
      \frac{e_i}{\sqrt{a_i}} & 1 \leq i \leq p \\
      \frac{e_i}{\sqrt{-a_i}} & p + 1 \leq i \leq p + q \\
      e_i & i > p + 1
    \end{cases}
  \]
\end{proof}

Equivalently,
\[
  Q \left( \sum_{i = 1}^{n} \lambda_i v_i \right) = \sum_{i = 1}^{p} \lambda_i^2 - \sum_{i = p + 1}^{q + p} \lambda_i^2.
\]

\begin{definition}[Positive/Negative (semi-)definiteness]\index{matrix!postive definite}
  A symmetric bilinear form \(\varphi\) on a real vector space \(V\) is
  \begin{itemize}
  \item \emph{positive definite} if \(\varphi(u, u) > 0\) for all \(u \in V\setminus \{0\}\).
  \item \emph{positive semi-definite} if \(\varphi(u, u) \geq 0\) for all \(u \in V\setminus \{0\}\).
  \item \emph{negative definite} if \(\varphi(u, u) < 0\) for all \(u \in V\setminus \{0\}\).
  \item \emph{negative semi-definite} if \(\varphi(u, u) \leq 0\) for all \(u \in V\setminus \{0\}\).
  \item \emph{indefinite} if none of the above.
  \end{itemize}
\end{definition}

The same terminologies apply to quadratic forms.

\begin{eg}
  A bilinear form on \(\R^n\) represented by \(\begin{psmallmatrix} I_p & 0 \\ 0 & 0 \end{psmallmatrix} \in \M_n(\R)\) is positive definite if \(p = n\) and positive semi-definite if \(p < n\).
\end{eg}

\begin{definition}[Signature]\index{bilinear!signature}
  The \emph{signature} of a real symmetric bilinear form \(\varphi\) is
  \[
    s(\varphi) = p - q.
  \]
\end{definition}

Again, this applies to quadratic forms as well.

However, we have not even checked whether this is well-defined. Thus we need

\begin{theorem}[Sylvester's Law of Inertia]
  If a real symmetric bilinear bilinear form \(\varphi\) has with respect to basis \(\basis B\) and \(\basis B'\)
  \[
    [\varphi]_{\basis B} =
    \begin{pmatrix}
      I_p & & \\
      & -I_q & \\
      & & 0
    \end{pmatrix}
    \quad
    [\varphi]_{\basis B'} =
    \begin{pmatrix}
      I_p' & & \\
      & -I_q' & \\
      & & 0
    \end{pmatrix}
  \]
  then
  \begin{align*}
    p &= p', \\
    q &= q'.
  \end{align*}
\end{theorem}

It is then immediate that

\begin{corollary}
  Signature is well-defined.
\end{corollary}

\begin{proof}
  For uniqueness of \(p\), show that \(p\) is the largest dimension of a subspace on which \(\varphi\) is positive definite. This suffices as it is a basis invariant characterisation.

  Let \(\basis B = \{v_1, \dots, v_n\}\). Let \(X = \spans{v_1, \dots, v_p}\) and \(Y = \spans{v_{p + 1}, \dots, v_n}\). \(\dim X = p\) and \(\varphi\) is positive definite on \(X\):
  \[
    Q(v) = Q \left( \sum_{i = 1}^{p} \lambda_i v_i \right) = \sum_{i = 1}^{p} \lambda_i^2 > 0
  \]
  for all \(v \neq 0\). Similarly \(\varphi\) is negative semi-definite on \(Y\).

  Suppose is \(\varphi\) is positive definite on some other subspace \(X'\). Then \(X' \cap Y = 0\) since \(Q\) is positive definite on \(X'\) and negative semi-definite on \(Y\). Therefore
  \[
    \dim (Y + X') = \dim Y \oplus X' = \dim Y + \dim X' \leq n
  \]
  but since \(\dim Y = n - p\) we have \(\dim X' \leq p\).

  For \(q\), we can either run the same argument with negative definite spaces, or use the fact that \(q = r(\varphi) - q\) is invariant.
\end{proof}

The zero diagonal block is not very interesting but it does get a speical name:

\begin{definition}[Kernel of symmetric bilinear form]\index{bilinear!kernel}
  The \emph{kernel} of a symmetric bilinear form is
  \[
    K = \{ v \in V: \varphi(u, v) = 0 \text{ for all } u \in V\}.
  \]
\end{definition}

\begin{note}
  \[
    \dim K = n - r(\varphi).
  \]
\end{note}

In our previous notation, the kernel is simply
\[
  K = \spans{v_{p + q + 1}, \dots, v_n}.
\]

\begin{caution}
  There is a subspace \(T\) of dimension \(n - (p + q) + \min(p, q)\) such that \(\varphi|_T = 0\): say \(p \geq q\),
  \[
    T = \spans{v_1 + v_{p + 1}, \dots, v_q + v_{p + q}, v_{p + q + 1}, \dots, v_n}.
  \]
\end{caution}

\begin{ex}
  Check that \(T\) above is the largest possible such space.
\end{ex}

\subsection{Sesquilinear Form}

Let \(\F = \C\) throughout this section.

The dot product on a real vector space comes naturally as a bilinear form. However, its generalisation to complex vector space, the standard inner product defined by
\[
  \ip{x, y} = \sum_{i = 1}^{n} x_i \conj y_i
\]
is not bilinear: the second coordinate transforms by ``conjugate-linearity'' instead of linearity. Among many other examples of the same spirit, this serves as a motivation to modify the definition of bilinear forms for \(\C\)-vector spaces:

\begin{definition}[Sesquilinear form]\index{sesquilinear form}
  Let \(V\) and \(W\) be \(\C\)-vector spaces. A \emph{sesquilinear form} is a function \(\varphi: V \times W \to \C\) such that
  \begin{align*}
    \varphi(\lambda_1v_1 + \lambda_2v_2, w) &= \lambda_1 \varphi(v_1, w) + \lambda_2 \varphi(v_2, w) \\
    \varphi(v, \mu_1w_1 + \mu_2w_2) &= \conj \mu_1 \varphi(v, w_1) + \conj \mu_2 \varphi(v, w_2)
  \end{align*}
  for all \(\lambda_1, \mu_1 \in \C\) and \(v, v_1, v_2 \in V\), \(w, w_1, w_2 \in W\).
\end{definition}

Naturally we would expect a sesquilinear form, just like a bilinear form, to have a matrix representation which behaves and transforms accordingly under change-of-basis:

\begin{definition}[Matrix of sesquilinear form]\index{matrix!sesquilinear form, of}
  Same notation as above. Let \(\basis B = \{v_1, \dots, v_m\}\) be a basis for \(V\) and \(\basis C = \{w_1, \dots, v_n\}\) be a basis for \(W\). Then the \emph{matrix} of \(\varphi\) with respect to \(\basis B\) and \(\basis C\) is
  \[
    [\varphi]_{\basis B, \basis C} = \left(\varphi(v_i, w_j)\right)_{i,j}
  \]
\end{definition}

\begin{lemma}
  \[
    \varphi(u, v) = [u]_{\basis B}^T [\varphi]_{\basis B, \basis C} \conj{[v]}_{\basis C}.
  \]
\end{lemma}

\begin{proof}
  Easy.
\end{proof}

\begin{lemma}
  Let \(\basis B, \basis B'\) be bases for \(V\), \(P = [\id]_{\basis B', \basis B}\) and \(\basis C, \basis C'\) be bases for \(W\), \(Q = [\id]_{\basis C', \basis C}\). Then
  \[
    [\varphi]_{\basis B', \basis C'} = P^T [\varphi]_{\basis B, \basis C} \conj Q.
  \]
\end{lemma}

\begin{proof}
  Ditto.
\end{proof}

\subsection{Hermitian Form}

We have special bilinear forms that are symmetric. The analogue for sesquilinear form is

\begin{definition}[Hermitian form]\index{Hermitian form}
  A sesquilinear form \(\varphi: V \times V \to \C\) is \emph{Hermitian} if
  \[
    \varphi(u, v) = \conj{\varphi(v,u)}.
  \]
\end{definition}

\begin{note}\leavevmode
  \begin{enumerate}
  \item For \(\varphi\) Hermitian, \(\varphi(u, u) \in \R\) and \(\varphi(\lambda u, \lambda u) = |\lambda|^2 \varphi(u,u)\) so we can still talk about positive/negative (semi-)definite Hermitian forms.
  \item For a Hermitian form \(\varphi: V \times V \to \C\), let \(\basis B\) be a basis for \(V\). Then we write
    \[
      [\varphi]_{\basis B} = [\varphi]_{\basis B, \basis B}.
    \]
  \end{enumerate}
\end{note}

\begin{lemma}
  A sesquilinear form \(\varphi: V \times V \to \C\) is Hermitian if and only if for any basis \(\basis B\),
  \[
    [\varphi]_{\basis B} = \conj{[\varphi]}^T_{\basis B}.
  \]
\end{lemma}

As before, if and only if this holds for one basis.

\begin{proof}
  Let \(\basis B = \{v_1, \dots, v_n\}\) and \(A = [\varphi]_{\basis B} = (a_{ij})\).
  \begin{itemize}
  \item \(\Rightarrow\):
    \begin{align*}
      a_{ij} &= \varphi(v_i, v_j) \\
             &= \conj{\varphi(v_j, v_i)} \\
      &= \conj{a_{ji}}
    \end{align*}
  \item \(\Leftarrow\):
    \begin{align*}
      \varphi \left( \sum \lambda_iv_i, \sum \mu_jv_j \right) &= \lambda^T A \conj \mu \\
                                                              &= \lambda^T \conj A^T \conj \mu \\
                                                              &= \conj \mu^T \conj A \lambda \text{ taking transpose of a scalar} \\
                                                              &= \conj{\mu^T A \conj \lambda} \\
                                                              &= \conj{\varphi \left( \sum \mu_jv_j, \sum \lambda_iv_i \right)}
    \end{align*}
  \end{itemize}
\end{proof}

Similarly we have polarisation identity for sesquilinear form: a Hermitian form \(\varphi\) on a \(\C\)-vector space \(V\) is determined by
\begin{align*}
  Q: V &\to \R \\
  v &\mapsto \varphi(v, v)
\end{align*}
via the formula
\[
  \varphi(u, v) = \frac{1}{4} \left( Q(u + v) - Q(u - v) + i Q(u + iv) - i Q(u - iv) \right).
\]

\begin{proof}
  Exercise.
\end{proof}

Lastly,
\begin{theorem}[Diagonalisation of Hermitian Form and Sylvester's Law]\index{Hermitian!diagonalisation}\index{Sylvester's Law}
  Let \(V\) be a finite-dimensional \(\C\)-vector space and \(\varphi: V \times V \to \C\) be a Hermitian form. There is a basis \(\basis B = \{v_1, \dots, v_n\}\) of \(V\) with respect to which
  \[
    [\varphi]_{\basis B} =
    \begin{pmatrix}
      I_p & & \\
      & -I_q & \\
      & & 0
    \end{pmatrix}
  \]
  where \(p\) and \(q\) are invariants of \(\varphi\).
\end{theorem}

\begin{proof}
  This is nearly as identical to the symmetric case so we only give a sketch here.

  For existence, if \(\varphi(u, u) = 0\) for all \(u\) then by polarisation identity \(\varphi(u, v) = 0\) so done. Assume not. There exists \(e_1\) such that \(\varphi(e_1, e_1) \neq 0\). Rescale to have
  \[
    v_1 = \frac{e_1}{\sqrt{|\varphi(e_1, e_1)|}}
  \]
  so \(\varphi(v_1, v_1) = \pm 1\). Note that we used the fact that \(\varphi(e_1, e_1) \in \R\).

  Consider the complementary space
  \[
    W = \spans{v_1}^\perp = \left\{ w \in V: \varphi(v_1, w) = 0 \right\}
  \]
  Check that \(V = \spans{v_1} \oplus W\). Now proceed by induction on \(W\).

  For uniqueness part (Sylvester's law), note \(p\) is the maximal dimension of a subspace of \(V\) on which \(\varphi\) is positive definite.
\end{proof}

\subsection{Alternating Form}

\begin{definition}[Alternating form]\index{alternating}\index{skew-symmetric}
  A bilinear form \(\varphi: V \times V \to \F\) is \emph{alternating} or \emph{skew-symmetric} if
  \[
    \varphi(u, v) = - \varphi(v, u)
  \]
  for all \(u, v \in V\).
\end{definition}

As a consequence \(\varphi(u, u) = 0\) for all \(u \in V\) and for any basis \(\basis B\), \([\varphi]_{\basis B} = - [\varphi]_{\basis B}^T\).

\begin{remark}
  Alternating form is useful since for any \(A \in \M_n(\F)\) with \(\ch \F \neq 2\),
  \[
    A = \underbrace{\frac{1}{2}(A + A^T)}_{\text{symmetric}} + \underbrace{\frac{1}{2}(A - A^T)}_{\text{skew-symmetric}}.
  \]
\end{remark}

\begin{theorem}
  If \(\varphi\) is skew-symmetric, there exists a basis
  \[
    \basis B = \{v_1, w_1, v_2, w_2, \dots, v_m, w_m, v_{2m + 1}, \dots, v_n\}
  \]
  such that
  \[
    [\varphi]_{\basis B} =
    \begin{pmatrix}
      0 & 1 & & & & & & & & \\
      -1 & 0 & & & & & & & & \\
      & & 0 & 1 & & & & & & \\
      & & -1 & 0 & & & & & & \\
      & & & & \ddots & & & & & \\
      & & & & & 0 & 1 & & & \\
      & & & & & -1 & 0 & & & \\
      & & & & & & & 0 & &\\
      & & & & & & & & \ddots & \\
      & & & & & & & & & 0 \\
    \end{pmatrix}
  \]
  where there are \(m\) blocks of \(\begin{psmallmatrix} 0 & 1 \\ -1 & 0 \end{psmallmatrix}\).
\end{theorem}

\begin{remark}
  By reordering the basis, with respect to
  \[
    \{v_1, \dots, v_m, w_1, \dots, w_m, v_{2m + 1}, \dots v_n\}
  \]
  it has matrix representation
  \[
    \begin{pmatrix}
      0 & I_m & \\
      -I_m & 0 & \\
      & & 0
    \end{pmatrix}
  \]
\end{remark}

\begin{remark}
  Skew-symmetric matrices have even rank.
\end{remark}

\begin{proof}[Sketch of proof]
  Induction on \(\dim V\): If \(\varphi = 0\) then done. Assume not. Then there exists \(v_1, w_1\) such that \(\varphi(v_1, w_1) \neq 0\). In particular \(v_1\) and \(w_1 \) are linearly independent. Scale \(v_1\) to get \(\varphi(v_1, w_1) = 1 = -\varphi(w_1, v_1)\) and let
  \begin{align*}
    U &= \spans{v_1, w_1} \\
    W &= \prescript{\perp}{}{U} = \{ v\in V: \varphi(v, v_1) = \varphi(v, w_1) = 0 \}
  \end{align*}
  Check \(V = U \oplus W\) by dimension argument. Now apply the induction hypothesis to \(\varphi|_W\).
\end{proof}

\section{Inner Product Space}

\subsection{Definitions}

Let \(\F = \R\) or \(\C\) in this chapter.

\begin{definition}[Inner product]\index{inner product}
  Let \(V\) be a vector space over \(\R\) (\(\C\), repsectively). An \emph{inner product} on \(V\) is a positive definite symmetric bilinear form (Hermitian form, respectively) \(\varphi\) on \(V\).

  \(V\) is called a real (complex, respectively) \emph{inner product space}, or a \emph{Euclidean} (\emph{unitary}, repsectively) space.
\end{definition}

\begin{notation}
  Write \(\ip{u, v}\) for \(\varphi(u, v)\). Note that it is the same as our notation for span so we will spell out span whenever we use it in this chapter.
\end{notation}

\begin{eg}\leavevmode
  \begin{itemize}
  \item Dot product on \(\R^n\) or \(\C^n\).
  \item \(V = C([0, 1], \C)\), \(\ip{f, g} = \int_0^1 f(t) \conj{g(t)} dt\).
  \item This can be generalised. Given \(w: [0, 1] \to \R_{> 0}\) continuous, think of it as a weight function, we can define an inner product
    \[
      \ip{f, g} = \int_{0}^{1} w(t)f(t)\conj{g(t)} dt.
    \]
  \end{itemize}
\end{eg}

\begin{remark}
  An inner product induces a distance function, i.e.\ a norm on \(V\) by
  \[
    \norm v = \sqrt{\ip{v, v}}
  \]
  whose axioms will be checked later.
  
  Conversely, \(\norm \cdot\) determines the inner product because of the polarisation identity.
\end{remark}

\begin{lemma}[Cauchy-Schwarz Inequality]\index{Cauchy-Schwarz}
  \[
    |\ip{u, v}| \leq \norm u \cdot \norm v
  \]
  for all \(u, v \in V\).
\end{lemma}

\begin{proof}
  Wlog \(u \neq 0\). For all \(t \in \F\),
  \begin{align*}
    0 &\leq \norm{tu - v}^2 \\
      &= \ip{tu - v, tu - v} \\
      &= \norm{tu}^2 - t \ip{u, v} - \conj t \conj{\ip{u, v}} + \norm v^2 \\
    \intertext{by setting \(t = \conj{\ip{u, v}}/\norm u^2\),}
      &\leq - \frac{|\ip{u, v}|^2}{\norm u^2} + \norm v^2
  \end{align*}
  Rearrange.
\end{proof}

\begin{note}
  We only used polarisation identity and did not assume any of the norm properties of \(\norm \cdot\), which we will prove now.
\end{note}

\begin{corollary}[Triangle Inequaility]
  \[
    \norm{u + v} \leq \norm u + \norm v
  \]
  for all \(u, v \in V\).
\end{corollary}

\begin{proof}
  \begin{align*}
    \norm{u + v}^2 &= \norm u^2 + \ip{u, v} + \conj{\ip{u, v}} + \norm v^2 \\
                   &\leq \norm u^2 + 2 \norm u \cdot \norm v + \norm v^2 \\
                   &= (\norm u + \norm v)^2
  \end{align*}
\end{proof}

\begin{corollary}
  \(\norm \cdot\) is a norm.
\end{corollary}

\begin{remark}
  For \(\F = \R\), the angle \(\theta\) between two non-zero vectors \(u\) and \(v\) satisfies (or defined by, actually)
  \[
    \cos \theta = \frac{\ip{u, v}}{\norm u \cdot \norm v}.
  \]
\end{remark}

\subsection{Orthonomal Basis}

\begin{definition}[Orthogonality]\index{orthogonal}
  A set \(\{e_1, \dots, e_k\}\) of vectors in \(V\) is \emph{orthogonal} if
  \[
    \ip{e_i, e_j} = 0
  \]
  for \(i \neq j\).
\end{definition}

\begin{definition}[Orthonormality]\index{orthonormal}
  A set \(\{e_1, \dots, e_k\}\) of vectors in \(V\) is \emph{orthonormal} if
  \[
    \ip{e_i, e_j} = \delta_{ij}
  \]
  for all \(i, j\).
\end{definition}

\begin{lemma}
  If \(\{e_1, \dots, e_k\}\) is orthogonal and non-zero then they are linearly independent.

  Moreover if \(v = \sum_{j = 1}^k \lambda_j e_j\),
  \[
    \lambda_j = \frac{\ip{v, e_j}}{\ip{e_j, e_j}}.
  \]
\end{lemma}

\begin{proof}
  \[
    \ip{v, e_j} = \ip*{\sum_{i = 1}^{k} \lambda_ie_i, e_j} = \lambda_j \ip{e_j, e_j}
  \]
  and the results follow.
\end{proof}

\begin{lemma}[Parseval's Identity]\index{Parseval}
  Let \(V\) be a finite-dimensional inner product space with an orthonormal basis \(e_1, \dots, e_n\). Then
  \[
    \ip{u, v} = \sum_{i = 1}^{n}\ip{u, e_i} \conj{\ip{v, e_i}}.
  \]
\end{lemma}

\begin{proof}
  Follows immediately from the orthonormal basis expansion formula in the previous lemma:
  \[
    \ip{u, v} = \ip*{\sum_{i = 1}^n \ip{u, e_i}e_i, \sum_{j = 1}^n \ip{v,e_j}e_j}.
  \]
\end{proof}

\begin{theorem}[Gram-Schmidt Orthonormalisation Process]\index{Gram-Schmidt}
  Let \(V\) be an inner product space and \(\{v_1, v_2, \dots \}\) be a countable set of linearly indpendent vectors in \(V\). Then there exists a sequence \(e_1, e_2, \dots\) orthonormal such that
  \[
    \text{span} \{v_1, \dots, v_k\} = \text{span} \{e_1, \dots, e_k\}
  \]
  for all \(k\).
\end{theorem}

\begin{proof}
  We see the word ``countable'' and instinctly use induction on \(k\). If \(k = 1\) then done. Suppose we have found \(e_1, \dots, e_k\). Inspired by the orthonormal basis expansion formula, let
  \[
    e'_{k + 1} = v_{k + 1} - \underbrace{\sum_{i = 1}^k \ip{v_{k + 1}, e_i} e_i}_{\text{linear combination of } v_1, \dots, v_k}
  \]
  which is non-zero by linear independence of \(\{v_1, \dots, v_{k + 1}\}\). Also \(\ip{e'_{k + 1}, e_i} = 0\) for \(1 \leq i \leq k\) by construction. Finally,
\[
  \text{span} \{v_1, \dots, v_k, v_{k + 1}\} = \text{span} \{e_1, \dots, e_k, e'_{k + 1}\}.
\]
Finally normalise it by
\[
  e_{k + 1} = \frac{e'_{k + 1}}{\norm{e'_{k + 1}}}.
\]
\end{proof}

\begin{corollary}
  Let \(V\) be a finite-dimensional inner product space. Any orthonormal set of vectors can be extended to an orthonormal basis.
\end{corollary}

\begin{proof}
  Say \(\{e_1, \dots, e_k\}\) are orthonormal. They are linearly independent so we can extend to a basis \(\{e_1, \dots, e_k, v_{k + 1}, \dots, v_n\}\) of \(V\).

  Now apply Gram-Schmidt to this set. As the first \(k\) vectors are already orthonormal it has no effect on them.
\end{proof}

\begin{note}
  \(A \in \M_{m, n}(\R)\) has orthonormal columns if \(A^TA = I\) and \(A \in \M_{m, n}(\C)\) has orthonormal columns if \(A^T \conj A = I\).
\end{note}

We give special names to them:

\begin{definition}[Orthogonal matrix]\index{matrix!orthogonal}
  \(A \in \M_n(\R)\) is \emph{orthogonal} if \(A^T A = I\).
\end{definition}

Equivalently \(A^{-1} = A^T\).

\begin{definition}[Unitary matrix]\index{matrix!unitary}
  \(A \in \M_n(\R)\) is \emph{unitary} if \(A^T \conj A = I\).
\end{definition}

Equivalently \(A^{-1} = \conj A^T\).

Given these terminologies, Gram-Schmidt may be equivalently formulated as follow:

\begin{proposition}
  \(A \in \M_n(\R)\) (\(\M_n(\C)\), respectively) non-singular can be written as \(A = RT\) where
  \begin{itemize}
  \item \(T\) is upper triangular,
  \item \(R\) is orthogonal (unitary, respectively).
  \end{itemize}
\end{proposition}

\begin{proof}
  Apply Gram-Schmidt to columns of \(A\). The details are left as an exercise.
\end{proof}

\subsection{Orthogonal Complements \& Projections}

\begin{definition}[Orthogonal direct sum]\index{orthogonal direct sum}
  Let \(V\) be an inner product space and \(V_1, V_2 \leq V\). \(V\) is the \emph{orthogonal direct sum} of \(V_1\) and \(V_2\) if
  \begin{enumerate}
  \item \(V = V_1 \oplus V_2\),
  \item \(\ip{v_1, v_2} = 0\) for all \(v_1 \in V_1, v_2 \in V_2\).
  \end{enumerate}
  Write \(V = V_1 \perp V_2\).
\end{definition}

\begin{note}
  The first condition is actually redundant: \(V_1 \cap V_2 = 0\) because of positive definiteness of inner product.
\end{note}

\begin{definition}[Orthogonal complement]\index{orthogonal complement}
  Let \(W \leq V\). The \emph{orthogonal complement} of \(W\) in \(V\) is
  \[
    W^\perp = \{v \in V: \ip{v, w} = 0 \text{ for all } v \in W \}.
  \]
\end{definition}

\begin{lemma}
  Let \(V\) be a finite-dimensional inner product space and \(W \leq V\). Then
  \[
    V =  W \perp W^\perp.
  \]
\end{lemma}

\begin{proof}
  If \(w \in W, u \in W^\perp\) then \(\ip{w, u} = 0\) so it remains to show that \(V = W + W^\perp\).

  Let \(\{e_1, \dots, e_k\}\) be an orthonormal basis for \(W\). By a previous lemma we can extend it to an orthonormal basis \(\{e_1, \dots, e_n\}\) of \(V\). Note that \(e_{k + 1}, \dots, e_n \in W^\perp\).
\end{proof}

\begin{note}
  Complementary space is, in general, not unique but orthogonal complement is.
\end{note}

A concept closely related to orthogonal complement is

\begin{definition}[Projection]\index{projection}
  Suppose \(V = U \oplus W\), a \emph{projection} from \(V\) to \(W\) is a map
  \begin{align*}
    \pi: V &\to W \\
    u + w &\mapsto w
  \end{align*}
  where \(u \in U, w \in W\). This a well-defined linear map and is idempotent, i.e.\ \(\pi^2 = \pi\).
\end{definition}

If the direct sum is orthogonal, however, there is a unique projection:

\begin{definition}[Orthogonal projection]
  If \(U = W^\perp\) above then \(\pi\) is the \emph{orthgonal projection} from \(V\) to \(W\).
\end{definition}

\begin{note}
  \(\pi' = \iota - \pi\) is the orthogonal projection from \(V\) to \(W^\perp\).
\end{note}

So far we have discussed orthogonal complement only at an abstract level and we don't know yet how to find one, although you should have a good intuition of how. The following lemma tells us how it works:

\begin{lemma}
  Let \(V\) be an inner product space, \(W \leq V\) with orthonormal basis \(e_1, \dots, e_k\) and \(\pi\) is the orthogonal projection onto \(W\). Then
  \begin{enumerate}
  \item For all \(v \in V\),
    \[
      \pi(v) = \sum_{i = 1}^k \ip{v, e_i} e_i
    \]
  \item \(\norm{v - \pi(v)} \leq \norm{v - w}\) for all \(v \in V\), \(w \in W\) with equality if and only if \(\pi(v) = w\). Equivalently, \(\pi(v)\) is the closest point in \(W\) to \(v\).
  \end{enumerate}
\end{lemma}

\begin{proof}\leavevmode
  \begin{enumerate}
  \item We need
    \[
      v - \sum_{i = 1}^k \ip{v, e_1}e_i \in W^\perp.
    \]
    But
    \[
      \ip*{v - \sum_{i = 1}^k \ip{v, e_i}e_i, e_j} = \ip{v, e_j} - \ip{v, e_j} = 0.
    \]
  \item
    \begin{align*}
      \norm{v - w}^2 &= \norm{\underbrace{v - \pi(v)}_{\in W^\perp} + \underbrace{\pi(v) - w}_{\in W}}^2 \\
                     &= \norm{v - \pi(v)}^2 + \norm{\pi(v) - w}^2 \\
                     &\leq \norm{v - \pi(v)}^2
    \end{align*}
    with equality if and only if \(\pi(v) = w\).
  \end{enumerate}
\end{proof}

\begin{remark}
  We met internal and external direct sum before. There is an analogous distinction for orthogonal direct sum.

  Given \(V_1, V_2\) two inner product spaces over \(\F\), we can define the \emph{external orthogonal} direct sum \(V_1 \perp V_2\) by equipping \(V_1 \oplus V_2\) the inner product
  \[
    \ip{(u_1, u_2), (v_1, v_2)} = \ip{u_1, v_1} + \ip{u_2, v_2}.
  \]
  In practice we often suppress the distinction between internal and external (orthogonal) direct sums.
\end{remark}

\subsection{Adjoints}

\begin{proposition}
  Let \(V\) and \(W\) be finite-dimensional inner product spaces and \(\alpha \in L(V, W)\). Then there exists a unique linear map \(\alpha^*: W \to V\) such that for all \(v \in V, w \in W\),
  \[
    \ip{\alpha v, w} = \ip{v, \alpha^*w}.
  \]

  If \(\basis B\) is an orthonormal basis for \(V\) and \(\basis C\) is an orthonormal basis for \(W\),
  \[
    [\alpha^*]_{\basis C, \basis B} = \conj{[\alpha]}^T_{\basis B, \basis C}.
  \]
\end{proposition}

\begin{definition}[Adjoint]\index{adjoint}
  \(\alpha^*\) as above is the \emph{adjoint} of \(\alpha\).
\end{definition}

\begin{proof}
  Let \(\basis B = \{v_1, \dots, v_n\}, \basis C = \{w_1, \dots, w_m\}\) and as usual, let
  \begin{align*}
    A &= [\alpha]_{\basis B, \basis C} = (a_{ij}) \\
    \conj A^T &= C = (c_{ij})
  \end{align*}
  where \(c_{ij} = \conj{a_{ij}}\).

  Since the formula for the adjoint map is given, we might as well just verify it. Consider the linear map \(\beta\) such that \([\beta]_{\basis C, \basis B} = C\). Then
  \begin{align*}
    \ip*{\alpha \left( \sum_i \lambda_iv_i \right), \sum_j \mu_jw_j} &= \ip*{\sum_{i, k}\lambda_ia_{ki}w_k, \sum_j \mu_jw_j} = \sum_{i, j} \lambda_ia_{ji}\conj{\mu_j} \\
    \intertext{while on the other hand}
    \ip*{\sum_i \lambda_iv_i, \beta \left( \sum_j \mu_jw_j \right)} &= \ip*{\sum_i\lambda_iv_i, \sum_{j, k}\mu_jc_{kj}v_k}  = \sum_{i, j}\lambda_i \conj{c_{ij}}\conj{\mu_j} \\
  \end{align*}
  and we see that they are equal since \(c_{ij} = \conj{a_{ij}}\). Thus we have proved the existence of adjoint.

  By specialising the above calculation to basis elements uniqueness follows.
\end{proof}

\begin{notation}
  Denote the Hermitian conjugate by
  \[
    A^\dag = \conj A^T.
  \]
\end{notation}

\begin{caution}
  We use the same notation \(\alpha^*\) for the adjoint and the dual of \(\alpha\). Hopefully the context should be clear which one is in use.
\end{caution}

\begin{remark}
  This usage of notation is not entirely coincidental. In fact, let \(V\) and \(W\) be finite-dimensional real inner product spaces and \(\alpha \in L(V, W)\). In finite dimension there is an isomorphism
  \begin{align*}
    \psi_{R, V}: V &\to V^* \\
    v &\mapsto \ip{-, v}
  \end{align*}
  and similarly \(\psi_{R, W}: W \to W^*\) such that the following diagram commutes:
  \[
    \begin{tikzcd}
      W \ar[r, "\text{adjoint of } \alpha"] \ar[d, "\psi_{R, W}"']  & V \ar[d, "\psi_{R, V}"] \\
      W^* \ar[r, "\text{dual of } \alpha"'] & V^*
    \end{tikzcd}
  \]
  In the fancy language of category theory, this essentially says that adjoint and dual are naturally isomorphic as contravariant functors, with components \(\psi_{R, -}\).
\end{remark}

\subsection{Self-adjoint Maps \& Isomoetries}

Let \(V = W\) throughout this section.

\begin{definition}[Self-adjoint]\index{self-adjoint}
  Let \(V\) be an inner product space and \(\alpha \in L(V)\). Let \(\alpha^*\) be the adjoint of \(\alpha\). \(\alpha\) is \emph{self-adjoint} if it satisfies one of the equivalent properties below:
  \begin{itemize}
  \item For all \(u, v \in V\), \(\ip{\alpha u, v} = \ip{u, \alpha v}\),
  \item \(\alpha = \alpha^*\).
  \end{itemize}

  \(\alpha\) is said to be symmetric (Hermitian, respectively) if the vector space is real (complex, respectively).
\end{definition}

\begin{definition}[Isometry]\index{isometry}
  Let \(V\) be an inner product space and \(\alpha \in L(V)\). Let \(\alpha^*\) be the adjoint of \(\alpha\). \(\alpha\) is an \emph{isometry} if it satisfies one of the equivalent properties below:
  \begin{itemize}
  \item For all \(u, v \in V\), \(\ip{\alpha u, \alpha v} = \ip{u, v}\),
  \item \(\alpha^{-1} = \alpha^*\).
  \end{itemize}

  \(\alpha\) is said to be orthogonal (unitary, respectively) if the vector space is real (complex, respectively).
\end{definition}

The equivalences should be quite obvious and in case you don't find it so,

\begin{proof}[Proof of 2nd equivalence]\leavevmode
  \begin{itemize}
  \item \(\Rightarrow\): \(\norm{\alpha v}^2 = \norm{v}^2\) so \(\alpha\) is injective and \(\alpha^{-1}\) exists. For all \(u, v \in V\),
    \[
      \ip{u, \alpha^*v} = \ip{\alpha u, v} = \ip{u, \alpha^{-1}v}
    \]
    so \(\alpha^{-1} = \alpha^*\).
  \item \(\Leftarrow\):
    \[
      \ip{\alpha u, \alpha v} = \ip{u, \alpha^*\alpha v} = \ip{u, v}
    \]
    for all \(u, v \in V\).
  \end{itemize}
\end{proof}

\begin{remark}
  By the polarisation identity there is yet another equivalent definition of isometry: \(\alpha\) is an isometry if
  \[
    \norm{\alpha v} = \norm{v}
  \]
  for all \(v \in V\), which might be closer to the intuition of an ``isometry''.
\end{remark}

\begin{lemma}
  Let \(V\) be a finite-dimensional real (complex, respectively) inner product space and \(\alpha \in L(V)\). Then
  \begin{itemize}
  \item \(\alpha\) is self-adjoint if and only if for all \emph{orthonormal basis} \(\basis B\), \([\alpha]_{\basis B}\) is symmetric (Hermitian, repsectively).
  \item \(\alpha\) is an isometry if and only if for all \emph{orthonormal basis} \(\basis B\), \([\alpha]_{\basis B}\) is orthogonal (unitary, respectively).
  \end{itemize}
\end{lemma}

\begin{proof}
  There is very little to do actually. For any orthonormal basis \(\basis B\),
  \[
    [\alpha^*]_{\basis B} = \conj{[\alpha]}^T_{\basis B}
  \]
  and the two cases follow.
\end{proof}

It turns out all the isometries on an inner product space form a group:

\begin{definition}[Orthogonal/Unitary group]\index{orthogonal group}\index{unitary group}\leavevmode
  \begin{itemize}
  \item If \(\F = \R\), the \emph{orthogonal group} of \(V\) is
    \[
      O(V) = \{\alpha \in L(V): \alpha \text{ isometry}\}.
    \]
  \item If \(\F = \C\), the \emph{unitary group} of \(V\) is
    \[
      U(V) = \{\alpha \in L(V): \alpha \text{ isometry}\}.
    \]
  \end{itemize}
\end{definition}

\begin{lemma}
  Let \(V\) be an inner product space with orthonormal basis \(e_1, \dots, e_n\). Then
  \begin{itemize}
  \item if \(\F = \R\), there is a correspondence
    \begin{align*}
      O(V) &\leftrightarrow \{\text{orthonormal basis of } V\} \\
      \alpha &\leftrightarrow (\alpha(e_1), \dots, \alpha(e_n))
    \end{align*}
  \item if \(\F = \C\), there is a correspondence
    \begin{align*}
      U(V) &\leftrightarrow \{\text{orthonormal basis of } V\} \\
      \alpha &\leftrightarrow (\alpha(e_1), \dots, \alpha(e_n))
    \end{align*}
  \end{itemize}
\end{lemma}

\subsubsection{Spectral Theory for Self-adjoint Maps}

Spectral theory is the study of eigenvalues and eigenvectors of linear operators, particularly those on infinite dimensional spaces. They have enormous importance in many areas of mathematics and physics, including for example functional analysis, harmonic analysis and quantum mechanics. In this course, spectral simply refers the the collection of all eigenvalues of an endomorphism on a finite-dimensional vector space.

\begin{lemma}
  Let \(V\) be an inner product space. If \(\alpha \in L(V)\) is self-adjoint then
  \begin{enumerate}
  \item \(\alpha\) has real eigenvalues.
  \item eigenvectors of \(\alpha\) for different eigenvalues are orthogonal.
  \end{enumerate}
\end{lemma}

Note that this true for any inner product space, regardless of dimension.

\begin{proof}\leavevmode
  \begin{enumerate}
  \item Suppose \(\alpha v = \lambda v\) for some non-zero \(v \in V\) and \(\lambda \in \C\). Then
    \[
      \lambda \ip{v, v} = \ip{\lambda v, v} = \ip{\alpha v, v} = \ip{v, \alpha v} = \ip{v, \lambda v} = \conj \lambda \ip{v, v}
    \]
    so \(\lambda = \conj \lambda \in \R\).
  \item Suppose \(\alpha v = \lambda v, \alpha w = \mu w\) where \(\lambda \neq \mu \in \R\). Use the similar idea,
    \[
      \lambda \ip{v, w} = \ip{\lambda v, w} = \ip{\alpha v, w} = \ip{v, \alpha w} = \mu \ip{v, w}
    \]
    so \(\ip{v, w} = 0\).
  \end{enumerate}
\end{proof}

For infinite dimensional space, we may not have any eigenvalues (although in which case the above is vacuously true). However, in finite-dimesional case we have

\begin{theorem}
  Let \(V\) be a finite-dimensional inner product space and \(\alpha \in L(V)\) is self-adjoint. Then \(V\) has an orthonormal basis of eigenvectors, whose eigenvalues are real by the previous lemma.
\end{theorem}

\begin{proof}
  Let \(\F = \R\) or \(\C\). Induction on \(n = \dim V\). If \(n = 0\) this is vacuously true. If \(n = 1\) then also true by the previous lemma. Suppose \(n > 1\). Say
  \[
    [\alpha]_{\basis B} = A
  \]
  where \(\basis B\) is the standard basis. Passing to \(\C\) in the same way we did in the \hyperref[proof:determinant from characteristic]{proof} of \Cref{lem:determinant from characteristic}. By Fundamental Theorem of Algebra, \(\chi_A(t) \in \C[t]\) has a root so \(A \in \M_n(\C)\) has an eigenvalue. Note that the argument so far applies to all maps, not just self-adjoint operators.

  Now using self-adjointness, this eigenvalue is real. So \(\chi_A(t)\) has a (real) root. Thus for both fields \(\alpha\) has a real eigenvalue, say \(\lambda\). Pick \(v_1 \in V \setminus \{0\}\) such that \(\alpha v_1 = \lambda v_1\). Now use the old trick of passing to a space of strictly smaller dimension, in this case the orthogonal complement
  \[
    U = \spans{v_1}^\perp \leq V
  \]
  where \(\spans{v_1}\) is the subspace spanned by \(v_1\). Check conditions for induction: if \(u \in V\),
  \[
    \ip{\alpha u, v_1} = \ip{u, \alpha v_1} = \ip{u, \lambda v_1} = \lambda \ip{u, v_1} = 0
  \]
  so \(\alpha\) is \(U\)-stable. \(\alpha|_U \in L(U)\) is obviously self-adjoint so by induction hypothesis there is an orthonormal basis \(v_2, \dots, v_n\) of \(U\) which are eigenvectors for \(\alpha|_U\). Adjoining \(\frac{v_1}{\norm{v_1}}\) gives an orthonormal basis of eigenvectors of \(\alpha\).
\end{proof}

\begin{corollary}
  Let \(V\) be a finite-dimensional inner product space. If \(\alpha \in L(V)\) is self-adjoint, \(V\) is the orthogonal direct sum of all the eigenspaces of \(\alpha\).
\end{corollary}

\begin{proof}
  Immediate.
\end{proof}

One reason self-adjoint operators are important is that many physical systems can be described by self-adjoint operators. By the theorem we can decompose such a space into orthogonal direct sum of eigenspaces, and when in orthonormal basis, the action of a self-adjoint operator is simply ``scaling''.

\subsubsection{Spectral Theory for Unitary Maps}

The other important map is isometry. Let \(\F = \C\) throughout this subsection.

\begin{lemma}
  Let \(V\) be a complex inner product space and \(\alpha \in L(V)\) unitary. Then
  \begin{enumerate}
  \item all eigenvalues lie on the unit circle.
  \item eigenvectors corresponding to different eigenvalues are orthogonal.
  \end{enumerate}
\end{lemma}

\begin{proof}
  This involves similar ideas as the lemma in the last subsection.
  \begin{enumerate}
  \item Suppose \(\alpha v = \lambda v\) for non-zero \(v \in V\). In addition \(\lambda \neq 0\) as \(\alpha\) is invertible. Then
    \[
      \lambda \ip{v, v} = \ip{\lambda v, v} = \ip{\alpha v, v} = \ip{v, \alpha^{-1} v} = \ip{v, \lambda^{-1} v} = \conj \lambda^{-1} \ip{v, v}
    \]
    so \(\lambda = \conj \lambda^{-1}\), \(|\lambda|^2 = 1\).
  \item Suppose \(\alpha v = \lambda v, \alpha w = \mu w\) where \(\lambda \neq \mu\). Then
    \[
      \lambda \ip{v, w} = \ip{\alpha v, w} = \ip{v, \alpha^{-1} w} = \conj \mu^{-1} \ip{v, w} = \mu \ip{v, w}
    \]
    so \(\ip{v, w} = 0\).
  \end{enumerate}
\end{proof}

\begin{theorem}
  Let \(V\) be a finite-dimensional complex inner product space and \(\alpha \in L(V)\). Then \(V\) has an orthonormal basis of eigenvectors.
\end{theorem}

\begin{proof}
  By Fundamental Theorem of Algebra, \(\alpha\) has an eigenvalue, say \(\lambda \in \C\). Fix non-zero \(v_1 \in V\) such that \(\alpha v_1 = \lambda v_1\) and further assume \(\norm{v_1} = 1\). Let
  \[
    U = \spans{v_1}^\perp \leq V.
  \]
  For all \(u \in U\),
  \[
    \ip{\alpha u, v_1} = \ip{u, \alpha^{-1} v_1} = \conj \lambda^{-1} \ip{u, v_1} = 0
  \]
  so \(\alpha\) is \(U\)-stable. By induction on dimension, \(U\) has an orthonormal basis of eigenvectors of \(\alpha|_U\), say \(v_2, \dots, v_n\). Thus \(v_1, \dots, v_n\) is an orthonormal basis of eigenvectors of \(\alpha\).
\end{proof}

\begin{remark}\leavevmode
  \begin{enumerate}
  \item Self-adjoint operators and isometries have different physical properties. However spectral theory says that they have similar properties and the proofs of which are essentially identical. This is because they are both examples of a more general type of operators called \emph{normal} maps, which are defined to be those satisfying
    \[
      \alpha \alpha^* = \alpha^* \alpha.
    \]
    Other examples of normal maps include skew-Hermitian maps. We will meet more in example sheet.
  \item Note that unlike the previous subsection, we only discuss unitary operators (i.e.\ complex isometries). An orthogonal matrix \(A \in \M_n(\R)\) cannot, in general, be diagonalised over \(\R\). For example, rotation of \(\R^2\). See example on page~\pageref{eg:rotation}.

    However, we can still get orthonormal basis with respect to which it is \emph{block-diagonal} with each blocks of size 1 or 2. See also example sheet. In a sense, this is the ``worst'' can happen to an isometry.
  \end{enumerate}
\end{remark}

\subsubsection{Application to Bilinear Forms}

Recall spectral theorem for self-adjoint maps and isometries.

\begin{corollary}
  Let \(A \in \M_n(\R)\) (\(\M_n(\C)\) respectively) be a symmetric (Hermitian respectively) matrix. Then there is an orthogonal (unitary respectively) matrix \(P\) such that \(P^\dag AP\) is diagonal with real entries.
\end{corollary}

\begin{proof}
  Let \(\F = \R\) or \(\C\) and equip \(\F^n\) with the standard inner product. Then \(A \in L(\F^n)\) is self-adjoint. Thus there is an orthonormal basis of \(\F^n\) of eigenvectors of \(A\) (with real eigenvalues), say \(v_1, \dots, v_n\). Let
  \[
    P = (v_1 \:|\: \cdots \:|\: v_n)
  \]
  then \(P^{-1}AP\) is diagonal with real entries. Now use \(P^{-1} = P^\dag\).
\end{proof}

\begin{note}
  For an orthogonal change-of-basis matrix \(P\),
  \[
    P^{-1}AP = P^\dag AP
  \]
  where LHS is change-of-basis of \(A\) as a linear map while RHS is change-of-basis of \(A\) as a bilinear (sesquilinear respectively) form. This interpretation can be exploited to tell us more about the structure of it.
\end{note}

\begin{corollary}
  Let \(V\) be a finite-dimensional real (complex respectively) inner product space and \(\varphi: V \times V \to \F\) be a symmetric bilinear (Hermitian respectively) form. Then there is an orthonormal basis of \(V\) with respect to which \(\varphi\) is represented by  a diagonal matrix with real entries.
\end{corollary}

Recall that previously we have shown that in general a symmetric bilinear (Hermitian respectively) form is diagonalisable using perpendicular space. However, if we equip the same space with an inner product, this corollary not only tells us that the bilinear form is diagonalisable, but also gives us an orthonormal basis with respect to which this holds.

\begin{proof}
  Let \(\basis B = \{v_1, \dots, v_n\}\) be any orthonormal basis and \(A = [\varphi]_{\basis B}\). \(A = A^\dag\) and there is an orthogonal (unitary respectively) matrix \(P\) such that \(D = P^\dag AP\) is diagonal. Let \(w_i\) be the \(i\)th column of \(P\), then \(\basis B' = \{w_1, \dots, w_n\}\) is an orthonormal basis of \(V\) and \([\varphi]_{\basis B'} = D\).
\end{proof}

\begin{remark}
  The diagonal entries of \(P^\dag AP\) are the eigenvalues of \(A\) and thus the signature could be equivalently defined as
  \[
    s(\varphi) = \# \text{positive eigenvalues of } A - \# \text{negative eigenvalues of } A.
  \]
\end{remark}

\begin{corollary}[Simultaneous diagonalisation of bilinear forms]
  Let \(V\) be a finite-dimensional real (complex respectively) vector space. Let \(\varphi, \psi\) be symmetric (Hermitian respectively) bilinear forms on \(V\). Assume \(\varphi\) is positive definite. There is a basis \(\basis B = \{v_1, \dots, v_n\}\) of \(V\) such that \([\varphi]_{\basis B}\) and \([\psi]_{\basis B}\) are both diagonal.
\end{corollary}

\begin{proof}
  First note that \(V\) equipped with \(\varphi\) is an inner product space. Thus there exists an orthonormal (with respect to this inner product) basis with respect to which \(\psi\) is represented by a diagonal matrix. By definition \(\varphi\) is represented by the identity matrix, which is unchanged under any change of basis. The result follows.
\end{proof}

\begin{caution}
  The positive definite assumption is necessary. See example sheet for counterexamples when this assumption is not satisfied.
\end{caution}

And we have a version correpsonding to matrices:

\begin{corollary}
  Let \(A, B \in \M_n(\R)\) (\(\M_n(\C)\) respectively) be symmetric (Hermitian respectively). Suppose \(\conj x^T Ax > 0\) for all non-zero \(x\). Then there exists \(Q \in \M_n(\R)\) (\(\M_n(\C)\) respectively) invertible such that \(Q^TAQ\) and \(Q^TBQ\) (\(Q^TA\conj Q\) and \(Q^TB\conj Q\) respectively) are both diagonal.
\end{corollary}

\begin{proof}
  Easy.
\end{proof}

\printindex
\end{document}