Title: Linear Algebra
Tags: A3.1

Q: Vector Space
A: An \emph{$\F$-vector space} is an (additive) abelian group $V$ together with a function $\F \times V \to V$, written $(\lambda, \mathbf{v}) \mapsto \lambda \mathbf{v}$, such that
  \begin{enumerate}
    \item $\lambda(\mu \mathbf{v}) = \lambda \mu \mathbf{v}$ for all $\lambda, \mu \in \F$, $\mathbf{v}\in V$ \hfill (associativity)
    \item $\lambda(\mathbf{u} + \mathbf{v}) = \lambda \mathbf{u} + \lambda \mathbf{v}$ for all $\lambda\in \F$, $\mathbf{u}, \mathbf{v}\in V$\hfill (distributivity in $V$)
    \item $(\lambda + \mu) \mathbf{v} = \lambda \mathbf{v} + \mu \mathbf{v}$ for all $\lambda, \mu \in \F$, $\mathbf{v}\in V$ \hfill (distributivity in $\F$)
    \item $1\mathbf{v} = \mathbf{v}$ for all $\mathbf{v}\in V$ \hfill (identity)
  \end{enumerate}

Q: Subspace
A: If $V$ is an $\F$-vector space, then $U\subseteq V$ is an ($\F$-linear) \emph{subspace} if
  \begin{enumerate}
    \item $\mathbf{u}, \mathbf{v}\in U\implies \mathbf{u} + \mathbf{v} \in U$.
    \item $\mathbf{u}\in U, \lambda \in \F\implies\lambda \mathbf{u}\in U$.
    \item $\mathbf{0}\in U$.
  \end{enumerate}
More concisely: ``$U$ is non-empty and if $\lambda, \mu\in \F, \mathbf{u}, \mathbf{v}\in U$, then $\lambda \mathbf{u} + \mu \mathbf{v}\in U$''.

Q: Sum of subspaces
A: Suppose $U, W$ are subspaces of an $\F$ vector space $V$. The \emph{sum} of $U$ and $V$ is
  \[
    U + W = \{\mathbf{u} + \mathbf{w}: \mathbf{u}\in U, \mathbf{w}\in W\}.
  \]
\begin{prop}
$U + W$ is a vector space.
\end{prop}
\begin{proof}
  $U + W$ contains $\mathbf{0}$ so is non-empty.
Given $\mathbf{u}_1 + \mathbf{w}_1$, $\mathbf{u}_2 + \mathbf{w}_2 \in U + W$, $\lambda, \mu\in \F$. Then
  \[
    \lambda(\mathbf{u}_1 + \mathbf{w}_1) + \mu(\mathbf{u}_2 + \mathbf{w}_2) = (\lambda\mathbf{u}_1 + \mu\mathbf{u}_2) + (\lambda\mathbf{w}_1 + \mu\mathbf{w}_2) \in U + W.
  \]
\end{proof}

Q: Intersection of vector spaces
A: \begin{prop}
  Let $U, W$ be subspaces of $V$. Then $U\cap W$ is a subspace.
\end{prop}
\begin{proof}
 $U\cap W$ contains $\mathbf{0}$ so is non-empty. Given $\mathbf{v}_1,\mathbf{v}_2 \in U\cap W$, then $\lambda \mathbf{v}_1 + \mu \mathbf{v}_2\in U$ and $\lambda \mathbf{v}_1 + \mu \mathbf{v}_2\in W$. So $\lambda \mathbf{v}_1 + \mu \mathbf{v}_2\in U\cap W$.
\end{proof}

Q: Writing vectors in terms of a basis
A: If $S$ is a subset of $V$ over $\F$, then it is a basis if and only if every $v\in V$ can be written uniquely as a finite linear combination of elements in $S$, ie. as
  \[
    v = \sum_{s \in S} \lambda_s s
  \]
with almost all $\lambda_s$ zero.
\begin{proof}
If $S$ is a basis, then existence is immediate. For uniqueness, suppose
 \[
    v = \sum_{s\in S}\lambda_s s = \sum_{s \in S}\mu_s s.
  \]
Then
  \[
    0 = v-v = \sum_{s\in S} (\lambda_s - \mu_s) s.
\]
So $\forall i: \lambda_i=\mu_i$ by linear independence.
Conversely, if $S$ is linearly dependent, then $\exists\lambda_s$ not all zero such that
  \[
    0 = \sum_{s\in S} \lambda_s s.
  \]
But clearly
  \[
    0 = \sum_{s \in S} 0 \cdot s.
  \]
  So there are two ways to write $0$.
\end{proof}

Q: Steinitz exchange lemma
A: Let $V$ be a vector space over $\F$, and $S = \{\mathbf{e}_1, \cdots, \mathbf{e}_n\}$ a finite LI subset of $V$, and $T$ a spanning subset of $V$. Then there is some $T'\subseteq T$ of order $n$ such that $(T\setminus T') \cup S$ still spans $V$.
In particular, $|T| \geq n$ and for $|T|<\infty$, let $T=\{\mathbf{f}_1, \cdots, \mathbf{f}_m\}$. Then there is a re-ordering of the $\{\mathbf{f}_i\}$ such that $\{\mathbf{e}_1,\cdots, \mathbf{e}_n, \mathbf{f}_{n + 1}, \cdots, \mathbf{f}_m\}$ spans $V$.
\begin{proof}
  Suppose inductively that $T_r'\subseteq T$ of order $0 \leq r < n$ such that
  \[
    T_r = (T\setminus T_r') \cup \{\mathbf{e}_1, \cdots, \mathbf{e}_r\}
  \]
  spans $V$. Then
  \[
    \mathbf{e}_{r + 1} = \sum_{i = 1}^k \lambda_i \mathbf{t}_i
  \]
for some $\lambda_i \in \F, \mathbf{t}_i \in T_r$ where not all $\mathbf{t}_i$'s are $\mathbf{e}_i$'s by linear independence. So there is some $j$ such that $\mathbf{t}_j \in (T\setminus T_r')$. Then
  \[
    \mathbf{t}_j = \frac{1}{\lambda_j} \mathbf{e}_{r + 1} + \sum_{i \not= j} -\frac{\lambda_i}{\lambda_j} \mathbf{t}_i.
  \]
  Now pick $T_{r + 1}' = T_r' \cup \{\mathbf{t}_j\}$ such that
  \[
    T_{r + 1} = (T\setminus T_{r + 1}') \cup \{\mathbf{e}_1, \cdots, \mathbf{e}_{r + 1}\} = (T_r \setminus \{\mathbf{t}_j\}\} \cup \{\mathbf{e}_{r + 1}\}
  \]
 has $\mathbf{t}_j \in \bra T_{r + 1}\ket$. So
  \[
   V=\bra T_r \ket \subseteq \bra T_{r + 1}\ket \subseteq  V
  \]
Hence $\bra T_{r + 1}\ket = V$.
\end{proof}

Q: Dimension of a vector space is well-defined
A: Suppose $V$ is a vector space over $\F$ with a basis $S = \{\mathbf{e}_1, \cdots, \mathbf{e}_n\}$. Then every basis of $V$ has order $n$.
\begin{proof}
 Suppose $T$ is another basis.
Since $T$ is spanning and $S$ is LI, $|T| \geq |S|$.
 Since $T$ is LI, every finite subset of $T$ is LI. Also, $S$ is spanning. So every finite subset of $T$ has order $\leq|S|$. Hence $|T| \leq |S|$.
Therefore $|T| = |S|$.
\end{proof}

Q: Linearly independent $\implies$ basis.
A: Let $V$ be a vector space with basis $S$ of order $n$. For any linearly independent subset $T$ of order $n$, we have that $T$ is a basis.
\begin{proof}
Suppose $\bra T\ket \not= V$. Then $\exists \mathbf{v} \in V\setminus \bra T\ket$. We show that $T\cup \{\mathbf{v}\}$ is an independent set of size $>n$.
Suppose
      \[
        \lambda_0 \mathbf{v} + \sum_{i = 1}^m \lambda_i \mathbf{t}_i = 0
      \]
      with $\lambda_i \in \F$, $\mathbf{t}_1, \cdots, \mathbf{t}_m\in T$ distinct. Then
      \[
        \lambda_0 \mathbf{v} = \sum_{i = 1}^m (-\lambda_i) \mathbf{t}_i.
      \]
      So $\lambda_0 \mathbf{v} \in \bra T\ket$. Hence $\lambda_0= 0$. Then $0=\lambda_0 = \cdots = \lambda_m $ by linear independence.
\end{proof}

Q: Spanning $\implies$ basis
A: Let $V$ be a vector space with basis $S$ of order n. Let $T$ be a spanning set of order $n$. Then $T$ is a basis.
\begin{proof}
Suppose $T$ is linearly dependent. Then there is some $\mathbf{t}_0, \cdots, \mathbf{t}_m \in T$ distinct and $\lambda_1, \cdots, \lambda_m \in \F$ such that
      \[
        \mathbf{t}_0 = \sum \lambda_i \mathbf{t}_i.
      \]
      So $\mathbf{t}_0 \in \bra T\setminus \{\mathbf{t}_0\}\ket$, ie. $\bra T\setminus \{\mathbf{t}_0\} \ket = V$. Then $T\setminus \{\mathbf{t}_0\}$ is a spanning set of order $n - 1$, which is a contradiction.
\end{proof}

Q: Spanning sets contain a basis
A: Let $V$ be a vector space with basis $S$ of order $n$. Let $T$ be a finite spanning set. Then $T$ contains a basis.
\begin{proof}
Let $T' \subseteq T$ be a minimal spanning subset.
If $|T'|$ has size $n$, then it is a basis.
Otherwise $|T'| > n$. So $T'$ is LD since $S$ is spanning. So there is some $\mathbf{t}_0, \cdots, \mathbf{t}_m \in T$ distinct and $\lambda_1, \cdots, \lambda_m \in \F$ such that $\mathbf{t}_0 = \sum \lambda_i \mathbf{t}_i$. Then $T'\setminus \{\mathbf{t}_0\}$ is a smaller spanning set. Contradiction.
\end{proof}

Q: Linearly independent subsets can be extended to a basis
A: Let $V$ be a vector space with basis $S$ of order $n$. Let $T$ be a linearly independent subset. Then $T'$ can be extended to a basis.
\begin{proof}
Since $S$ spans and $T$ is LI, $\exists S' \subseteq S$ of order $|T|$ such that $(S\setminus S')\cup T$ spans $V$. Then by sizes $(S\setminus S')\cup T$ is a basis of $V$.
\end{proof}

Q: Inclusion-exclusion
A: If $U, W$ are subspaces of a finite dimensional vector space $V$, then
  \[
    \dim (U + W) = \dim U + \dim W - \dim (U\cap W).
  \]
\begin{proof}
  Let $R = \{\mathbf{v}_1, \cdots, \mathbf{v}_r\}$ be a basis for $U\cap W$. Extended to a basis of $U$
  \[
    S = \{\mathbf{v}_1, \cdots, \mathbf{v}_r, \mathbf{u}_{r + 1}, \cdots, \mathbf{u}_s\}
  \]
and a basis of $W$
  \[
    T = \{\mathbf{v}_1, \cdots, \mathbf{v}_r, \mathbf{w}_{r + 1}, \cdots, \mathbf{w}_t\}
  \]
using linear independence.
We show $S\cup T$ is a basis for $U + W$.
\textbf{Span}. Given $\mathbf{u} + \mathbf{w} \in U + W$, $\mathbf{u}\in U, \mathbf{w}\in W$, we have that $\mathbf{u}\in \bra S\ket$ and $\mathbf{w}\in \bra T\ket$. So $\mathbf{u} + \mathbf{w} \in \bra S\cup T\ket$. So $U + W \subseteq \bra S \cup T\ket$. Also $S\cup T\subseteq U+W$ so $\bra S \cup T\ket \subseteq U+W$. Hence $U + W = \bra S \cup T\ket$.
\textbf{Linear independence}. Suppose
  \[
    \sum_{i = 1}^r \lambda_i \mathbf{v}_i + \sum_{j = r + 1}^s \mu_j \mathbf{u}_j + \sum_{k = r + 1}^t \nu_k \mathbf{w}_k = 0.
  \]
  So
  \[
    \sum \lambda_i \mathbf{v}_i + \sum \mu_j \mathbf{u}_j = - \sum \nu_k \mathbf{w}_k.
  \]
  Since LHS $\in U$, and RHS $\in W$, they both lie in $U\cap W$.
  Since $S$ spans $U$, the LHS can be written as a sum of $\mathbf{v}_i$'s and $\mathbf{u}_j$'s. However, since $R$ is a basis of $U\cap W$, the LHS can be written as a sum of $\mathbf{v}_i$'s. Since $S$ is LI we must have $\forall j: \mu_j = 0$. Then
  \[
    \sum \lambda_i \mathbf{v}_i + \sum \nu_k \mathbf{w}_k = \mathbf{0}.
  \]
  Finally, since $T$ is LI, $\forall i,k: \lambda_i = \nu_k = 0$.
\end{proof}

Q: Quotient space
A: Let $V$ be a vector space, and $U\subseteq V$ a subspace. Then the quotient group $V/U$ is a vector space under scalar multiplication $(\lambda, \mathbf{v} + U) = (\lambda \mathbf{v}) + U$.
 \textbf{Well-defined} If $\mathbf{v} + U = \mathbf{w} + U\in V/U$, then $\mathbf{v} - \mathbf{w} \in U$. So $\lambda \mathbf{v} - \lambda \mathbf{w} \in U$. Hence $\lambda \mathbf{v} + U = \lambda \mathbf{w} + U$.
The other properties of a vector space are inherited.

Q: Lagrange's Theorem
A: If $V$ is a finite dimensional vector space $\F$ and $U$ is a subspace, then
  \[
    \dim V = \dim U + \dim V/U.
  \]
\begin{proof}
  Let $\{\mathbf{u}_1, \cdots, \mathbf{u}_m\}$ be a basis for $U$ and extend this to a basis $\{\mathbf{u}_1, \cdots, \mathbf{u}_m,\allowbreak \mathbf{v}_{m + 1}, \cdots, \mathbf{v}_n\}$ for $V$. We show that $\{\mathbf{v}_{m + 1} + U, \cdots, \mathbf{v}_n + U\}$ is a basis for $V/U$.
 \textbf{Spans}. Given $\mathbf{v} + U \in V/U$, we can write
  \[
    \mathbf{v} = \sum \lambda_i \mathbf{u}_i + \sum \mu_i \mathbf{v}_i.
  \]
Then
  \[
    \mathbf{v} + U = \sum \mu_i (\mathbf{v}_i + U) + \sum \lambda_i (\mathbf{u}_i + U) = \sum \mu_i (\mathbf{v}_i + U).
  \]
\textbf{Linear independence}. Suppose that
  \[
    \sum \lambda_i (\mathbf{v}_i + U) = \mathbf{0} + U = U.
  \]
  Then
  \[
    \sum \lambda_i \mathbf{v}_i \in U.
  \]
  So
  \[
    \sum \lambda_i \mathbf{v}_i = \sum \mu_j \mathbf{u}_j
  \]
  for some $\mu_j$. By linear independence of the basis for $V$, we have $\forall i,j: \lambda_i = \mu_j = 0$.
\end{proof}

Q: Direct sums
A: Suppose $V$ is a vector space over $\F$ and $U, W\subseteq V$ are subspaces. The \emph{(internal) direct sum} of $U$ and $W$ if
  \begin{enumerate}
    \item $U + W = V$
    \item $U \cap W = 0$.
  \end{enumerate}
  We write $V = U\oplus W$.
 Equivalently, every $\mathbf{v}\in V$ can be written uniquely as $\mathbf{u} + \mathbf{w}$ with $\mathbf{u}\in U, \mathbf{w}\in W$ (this is the condition for multiple sums). We say that $U$ and $W$ are \emph{complementary subspaces} of $V$.
  If $U, W$ are vector spaces over $\F$, the \emph{(external) direct sum} is
  \[
    U\oplus W = \{(\mathbf{u}, \mathbf{w}): \mathbf{u}\in U, \mathbf{w}\in W\},
  \]
  with addition and scalar multiplication componentwise:
  \[
    (\mathbf{u}_1, \mathbf{w}_1) + (\mathbf{u}_2, \mathbf{w}_2) = (\mathbf{u}_1 + \mathbf{u}_2, \mathbf{w}_1 + \mathbf{w}_2),\quad \lambda (\mathbf{u}, \mathbf{w}) = (\lambda \mathbf{u}, \lambda \mathbf{w}).
  \]

Q: Isomorphisms preserve dimension
A: Let $\alpha: U\to V$ be an $\F$-linear map. Then
  \begin{enumerate}
    \item If $\alpha$ is injective and $S\subseteq U$ is linearly independent, then $\alpha (S)$ is linearly independent in $V$.
    \item If $\alpha$ is surjective and $S\subseteq U$ spans $U$, then $\alpha (S)$ spans $V$.
  \end{enumerate}
\begin{proof}\leavevmode
  \begin{enumerate}
    \item We prove the contrapositive. Let $\alpha(S)$ be linearly dependent. So there are $\mathbf{s}_0, \cdots, \mathbf{s}_n \in S$ distinct and $\lambda_1, \cdots, \lambda_n\in \F$ not all zero such that
      \begin{align*}
        \alpha(\mathbf{s}_0) &= \sum_{i = 1}^n \lambda_i \alpha(\mathbf{s}_i) = \alpha\left(\sum_{i = 1}^n \lambda_i \mathbf{s}_i\right) \\
\mathbf{s}_0 &= \sum_{i = 1}^n \lambda_i \mathbf{s}_i
      \end{align*}
by injectivity. So $S$ is linearly dependent.
    \item Let $S$ span $U$. Given $\mathbf{v} \in V$, $\exists\mathbf{u}\in U$ such that $\alpha(\mathbf{u}) = \mathbf{v}$. Since $S$ spans $U$, there is some $\mathbf{s}_1, \cdots, \mathbf{s}_n\in S$ and $\lambda_1, \cdots, \lambda_n\in \F$ such that
      \[
        \mathbf{u} = \sum_{I = 1}^n \lambda_i \mathbf{s}_i.
      \]
      Then
      \[
        \mathbf{v} = \alpha (\mathbf{u}) = \sum_{i = 1}^n \lambda_i \alpha (\mathbf{s}_i).
      \]
      So $\alpha (S)$ spans $V$.
  \end{enumerate}
\end{proof}
  If $U$ and $V$ are finite-dimensional vector spaces over $\F$ and $\alpha: U\to V$ is an isomorphism, then $\dim U = \dim V$.
\begin{proof}
  Let $S$ be a basis for $U$. Then $\alpha(S)$ is a basis for $V$ . Since $\alpha$ is bijective, $|S| = |\alpha(S)|$.
\end{proof}

Q: Bases are isomorphic to the standard basis in many ways
A: \begin{prop}
  Suppose $V$ is a $\F$-vector space of dimension $n < \infty$. Then writing $\mathbf{e}_1,\cdots, \mathbf{e}_n$ for the standard basis of $\F^n$, there is a bijection
  \begin{align*}
    \Phi: &\{\text{isomorphisms }\F^n \to V\} \\
\to &\{\text{(ordered) basis} (\mathbf{v}_1, \cdots, \mathbf{v}_n)\text{ for }V\}
  \end{align*}
  defined by
  \[
    \alpha \mapsto (\alpha (\mathbf{e}_1), \cdots, \alpha(\mathbf{e}_n)).
  \]
\end{prop}
\begin{proof}
\textbf{Image}. If $\alpha$ is an isomorphism, then it sends a basis to a basis. So $(\alpha(\mathbf{e}_1), \cdots, \alpha(\mathbf{e}_n))$ is indeed a basis for $V$.
 \textbf{Injective}. Suppose $\alpha, \beta: \F^n \to V$ are isomorphisms such that $\Phi(\alpha) = \Phi(\beta)$, i.e. $\forall i: \alpha (\mathbf{e}_i) = \beta(\mathbf{e}_i)$. Then $\forall x_i$:
  \begin{align*}
    \alpha\left(
    \begin{pmatrix}
      x_1\\\vdots\\x_n
    \end{pmatrix}
    \right) &= \alpha \left(\sum_{i = 1}^n x_i \mathbf{e}_i\right) \\
& = \sum x_i \alpha (\mathbf{e}_i)\\
& = \sum x_i \beta (\mathbf{e}_i) \\
&= \beta\left(
    \begin{pmatrix}
      x_1\\\vdots\\x_n
    \end{pmatrix}\right).
  \end{align*}
  So $\alpha = \beta$.
 \textbf{Surjective}.  Suppose that $(\mathbf{v}_1, \cdots, \mathbf{v}_n)$ is an ordered basis for $V$. Then define
  \[
    \alpha\left(
    \begin{pmatrix}
      x_1\\\vdots\\x_n
    \end{pmatrix}
    \right) = \sum x_i \mathbf{v}_i.
  \]
This is clearly well-defined and linear. Injectivity follows from linearly independence. Surjectivity follows since $(\mathbf{v}_1, \cdots, \mathbf{v}_n)$ spans $V$. So $\alpha$ is an isomorphism and by construction $\Phi(\alpha) = (\mathbf{v}_1, \cdots, \mathbf{v}_n)$.
\end{proof}

Q: Basis determination of linear maps
A: \begin{prop}
  Suppose $U, V$ are vector spaces over $\F$ and $S = \{\mathbf{e}_1, \cdots, \mathbf{e}_n\}$ is a basis for $U$. Then every function $f: S \to V$ extends uniquely to a linear map $U \to V$.
\end{prop}
\begin{proof}
\textbf{Uniqueness}. Suppose $\alpha, \beta: U \to V$ are linear and extend $f: S \to V$. Given $\mathbf{u}\in U$, we can write $\mathbf{u} = \sum_{i = 1}^n u_i \mathbf{e}_i$ with $u_i \in \F$ since $S$ spans. Then
  \[
    \alpha (\mathbf{u}) = \alpha\left(\sum u_i \mathbf{e}_i\right) = \sum u_i \alpha (\mathbf{e}_i) = \sum u_i f( \mathbf{e}_i)=\beta(\mathbf{u}).
  \]
\textbf{Existence} Given $\mathbf{u} \in U$, we can write $\mathbf{u} = \sum u_i \mathbf{e}_i$ in a unique way. So
  \[
    \alpha(\mathbf{u}) = \sum u_i f(\mathbf{e}_i)
  \]
  is well-defined and extends $f$. Linearity: $\forall \lambda, \mu\in \F$, $\mathbf{u}, \mathbf{v}\in U$
  \begin{align*}
    \alpha (\lambda \mathbf{u} + \mu \mathbf{v}) &= \alpha \left(\sum (\lambda u_i + \mu v_i) \mathbf{e}_i\right) \\
    &= \sum (\lambda u_i + \mu v_i) f(\mathbf{e}_i)\\
    &= \lambda \left(\sum u_i f(\mathbf{e}_i)\right) + \mu \left(\sum v_i f(\mathbf{e}_i)\right)\\
    &= \lambda \alpha(\mathbf{u}) + \mu \alpha(\mathbf{v}).
  \end{align*}
\end{proof}

Q: Matrices vs. linear maps
A: If $U$ and $V$ are finite-dimensional vector spaces over $\F$ with bases $(\mathbf{e}_1, \cdots, \mathbf{e}_m)$ and $(\mathbf{f}_1, \cdots, \mathbf{f}_n)$ respectively, then there is a bijection (in fact an isomorphism)
  \[
    \Mat_{n, m}(\F) \to \mathcal{L}(U, V),
  \]
  sending $A$ to the unique linear map $\alpha$ such that $\alpha(\mathbf{e}_i) = \sum A_{ji} \mathbf{f}_j$.
\begin{proof}
  If $\alpha$ is a linear map $U \to V$, then for each $1 \leq u \leq m$, we can write $\alpha(\mathbf{e}_i)$ uniquely as
  \[
    \alpha(\mathbf{e}_i) = \sum_{j = 1}^n a_{ji} \mathbf{f}_j
  \]
  for some $a_{ji} \in \F$. This gives a corresponding matrix $A = (a_{ij})$ by basis determination.
Conversely, $A$ determines $\alpha(e_i)$ and hence $\alpha$.
\end{proof}

Q: Dimension of a space of linear maps
A: $\dim \mathcal{L}(U, V) = (\dim U)(\dim V)$.
\begin{proof}
Let \[
S=\{ A\in \Mat_{m,n} (\F) \ | \ A\textrm{ has one non-zero entry which is $1$} \}. \]
Then clearly $S$ is a basis for $\Mat_{m,n} (\F)$. So $\dim \Mat_{m,n} (\F)=|S|=(\dim U)(\dim V)$. Since $\Mat_{m,n} (\F)\cong\mathcal{L}(U, V)$, we have $\dim \mathcal{L}(U, V) = (\dim U)(\dim V)$.
\end{proof}

Q: Matrix product
A: Suppose $U, V, W$ are finite-dimensional vector spaces over $\F$ with bases $R = (\mathbf{u}_1, \cdots, \mathbf{u}_r)$ , $S = (\mathbf{v}_1, .., \mathbf{v}_2)$ and $T = (\mathbf{w}_1, \cdots, \mathbf{w}_t)$ respectively.
  If $\alpha: U\to V$ and $\beta: V\to W$ are linear represented by $A$ and $B$ respectively (with respect to $R$, $S$ and $T$), then $\beta\alpha$ is linear and represented by $BA$ with respect to $R$ and $T$.
\begin{proof}
\textbf{Linear}. $\beta\alpha(\lambda \mathbf{x}+\mu\mathbf{y}=\beta(\lambda \alpha(\mathbf{x})+\mu\alpha(\mathbf{y})=\lambda \beta\alpha(\mathbf{x})+\mu\beta\alpha(\mathbf{y})$
\textbf{Matrix Representation}.
  \begin{align*}
    \beta\alpha(\mathbf{u}_i) &= \beta\left(\sum_k A_{ki}\mathbf{v}_k\right) \\
    &= \sum_k A_{ki}\beta(\mathbf{v}_k) \\
    &= \sum_k A_{ki}\sum_j B_{jk} \mathbf{w}_j \\
    &= \sum_j \left(\sum_k B_{jk}A_{ki}\right)\mathbf{w}_j\\
    &= \sum_j (BA)_{ji} \mathbf{w}_j.
  \end{align*}
\end{proof}

Q: First isomorphism theorem
A: Let $\alpha: U\to V$ be a linear map. Then $\ker \alpha$ and $\im \alpha$ are subspaces of $U$ and $V$ respectively. Moreover, $\alpha$ induces an isomorphism
  \begin{align*}
    \bar{\alpha}: U/\ker \alpha &\to \im \alpha\\
    (\mathbf{u} + \ker \alpha) &\mapsto \alpha(\mathbf{u})
  \end{align*}
\begin{proof}
  We know that $\mathbf{0} \in \ker \alpha$ and $\mathbf{0}\in \im \alpha$.
  Suppose $\mathbf{u}_1, \mathbf{u}_2 \in \ker \alpha$ and $\lambda_1, \lambda_2\in \F$. Then
  \[
    \alpha (\lambda_1 \mathbf{u}_1 + \lambda_2 \mathbf{u}_2) = \lambda_1 \alpha(\mathbf{u}_1) + \lambda_2 \alpha(\mathbf{u}_2) = \mathbf{0}.
  \]
  So $\lambda_1 \mathbf{u}_1 + \lambda_2 \mathbf{u}_2 \in \ker \alpha$. So $\ker \alpha$ is a subspace.
  Similarly, if $\alpha(\mathbf{u}_1), \alpha(\mathbf{u}_2) \in \im \alpha$, then $\lambda\alpha(\mathbf{u}_1) + \lambda_2 \alpha(\mathbf{u}_2) = \alpha(\lambda_1 \mathbf{u}_1 + \lambda_2 \mathbf{u}_2) \in \im \alpha$. So $\im \alpha$ is a subspace.
  Now by the first isomorphism theorem of groups, $\bar{\alpha}$ is a well-defined isomorphism of groups. We just check $\bar{\alpha}$ is a linear map:
  \[
    \bar{\alpha}(\lambda(\mathbf{u} + \ker \alpha)) = \alpha (\lambda \mathbf{u}) = \lambda \alpha(\mathbf{u}) = \lambda (\bar{\alpha}(\mathbf{u} + \ker \alpha)).
  \]
\end{proof}

Q: Rank-nullity theorem
A: If $\alpha: U \to V$ is a linear map and $U$ is finite-dimensional, then $r(\alpha) + n(\alpha) = \dim U$.
\begin{proof}
  By the first isomorphism theorem, we have that $U/\ker \alpha \cong \im \alpha$. By Lagrange
  \[
    \dim \im \alpha = \dim (U/\ker \alpha) = \dim U - \dim \ker \alpha.
  \]
\end{proof}
  If $\alpha: U\to V$ is a linear map between finite-dimensional vector spaces over $\F$, then there are bases $(\mathbf{e}_1, \cdots, \mathbf{e}_m)$ for $U$ and $(\mathbf{f}_1, \cdots, \mathbf{f}_n)$ for $V$ such that $\alpha$ is represented by the $m\times n$ matrix
  \[
    \begin{pmatrix}
      I_r & 0\\
      0 & 0
    \end{pmatrix},
  \]
  where $r = r(\alpha)$ and $I_r$ is the $r\times r$ identity matrix. In particular, $r(\alpha) + n(\alpha) = \dim U$.
\begin{proof}
  Let $\mathbf{e}_{k + 1}, \cdots, \mathbf{e}_m$ be a basis for $\ker\alpha$. Then we can extend this to a basis $(\mathbf{e}_1,\cdots, \mathbf{e}_m)$ of $U$.
  Let $\mathbf{f}_i = \alpha(\mathbf{e}_i)$ for $1 \leq i \leq k$. We now show that $(\mathbf{f}_1, \cdots, \mathbf{f}_k)$ is a basis for $\im \alpha$ (and thus $k = r$).
\textbf{Spans}. Given $\mathbf{v}\in \im \alpha$, $\exists\lambda_i \in \F$ such that
  \begin{align*}
    \mathbf{v} &= \alpha\left(\sum_{i = 1}^m \lambda_i \mathbf{e}_i\right) \\
&= \sum_{i = 1}^m \lambda_i \alpha(\mathbf{e}_i)\\
 &= \sum_{i = 1}^k \lambda_i \mathbf{f}_i \\
\mathbf{v}&\in \bra \mathbf{f}_1, \cdots, \mathbf{f}_k\ket.
  \end{align*}
\textbf{Linear independence} Suppose that
  \begin{align*}
\sum_{i = 1}^k \mu_i \mathbf{f}_i &= 0. \\
\intertext{Then}
    \alpha \left(\sum_{i = 1}^k \mu_i \mathbf{e}_i\right) &= \mathbf{0} \\
\sum_{i = 1}^k \mu_i \mathbf{e}_i &\in \ker \alpha.
  \end{align*}
Since $( \mathbf{e}_{k + 1}, \cdots, \mathbf{e}_m )$ is a basis for $\ker \alpha$
  \[
    \sum_{i = 1}^k \mu_i \mathbf{e}_i = \sum_{i = k + 1}^m \mu_i \mathbf{e}_i
  \]
  for some $\mu_i$ ($i = k + 1, \cdots, m$). Since $(\mathbf{e}_1, \cdots, \mathbf{e}_m)$ is a basis, we must have $\forall i: \mu_i = 0$.
\textbf{Matrix representation}.  Now extend $(\mathbf{f}_1, \cdots, \mathbf{f}_r)$ to a basis for $V$ and recall that
  \[
    \alpha(\mathbf{e}_i) =
    \begin{cases}
      \mathbf{f}_i & 1 \leq i \leq k\\
      0 & k + 1 \leq i \leq m.
    \end{cases}
  \]
\end{proof}

Q: Isomorphism vs bijective linear map
A: If $U$ and $V$ are vector spaces over $\F$ and $\alpha: U\to V$, then $\alpha$ is an isomorphism iff $\alpha$ is a bijective linear map.
\begin{proof}
  If $\alpha$ is an isomorphism, then it is clearly bijective since it has an inverse function.
  Suppose $\alpha$ is a linear bijection. Then it has an inverse $\beta: V\to U$. We show it is linear: $\forall\mathbf{v}_1, \mathbf{v}_2 \in V$, $\lambda, \mu \in \F$
  \begin{align*}
    \alpha \beta(\lambda \mathbf{v}_1 + \mu \mathbf{v}_2) &= \lambda \mathbf{v}_1 + \mu \mathbf{v}_2 \\
& = \lambda \alpha \beta (\mathbf{v}_1) + \mu \alpha \beta (\mathbf{v}_2) \\
& = \alpha (\lambda \beta(\mathbf{v}_1) + \mu \beta (\mathbf{v}_2))  \\
\beta(\lambda \mathbf{v}_1 + \mu \mathbf{v}_2)
 &= \lambda \beta (\mathbf{v}_1) + \mu \beta (\mathbf{v}_2)
  \end{align*}
by injectivity.
\end{proof}

Q: Maps between spaces of the same dimension
A: Suppose $\alpha: U\to V$ is a linear map between vector spaces over $\F$ both of dimension $n < \infty$. Then the following are equivalent
  \begin{enumerate}
    \item $\alpha$ is injective;
    \item $\alpha$ is surjective;
    \item $\alpha$ is an isomorphism.
  \end{enumerate}
\begin{proof}
  It is clear that, (iii) implies (i) and (ii), and (i) and (ii) together implies (iii). So it suffices to show that (i) and (ii) are equivalent.
  Note that $\alpha$ is injective iff $n(\alpha) = 0$ (injectivity via kernels), and $\alpha$ is surjective iff $r(\alpha) = \dim V = n$. By the rank-nullity theorem, $n(\alpha) + r(\alpha) = n$. So the result follows immediately.
\end{proof}

Q: Inverse matrix
A: Let $A \in M_{n, n}(\F) = M_n(\F)$ be a square matrix. The following are equivalent
  \begin{enumerate}
    \item There exists $B\in M_n (\F)$ such that $BA = I_n$.
    \item There exists $C\in M_n (\F)$ such that $AC = I_n$.
  \end{enumerate}
  If these hold, then $B = C$. We call $A$ \emph{invertible} or \emph{non-singular}, and write $A^{-1} = B = C$.
\begin{proof}
  Let $\alpha, \beta, \gamma, \iota: \F^n \to \F^n$ be the linear maps represented by matrices $A, B, C, I_n$ respectively with respect to the standard basis.
  We note that (i) is equivalent to saying that there exists $\beta$ such that $\beta\alpha = \iota$. This is true iff $\alpha$ is inrjective, which is true iff $\alpha$ is an isomorphism, which is true iff $\alpha$ has an inverse $\alpha^{-1}$.
  Similarly, (ii) is equivalent to saying that there exists $\gamma$ such that $\alpha\gamma = \iota$. This is true iff $\alpha$ is surjective, which is true iff $\alpha$ is isomorphism, which is true iff $\alpha$ has an inverse $\alpha^{-1}$.
  So (i)$\iff$(ii) and we have $\beta = \alpha^{-1} = \gamma$.
\end{proof}

Q: Matrix transformation law
A: \begin{thm}
  Suppose that $(\mathbf{e}_1, \cdots, \mathbf{e}_m)$ and $(\mathbf{u}_1,\cdots, \mathbf{u}_m)$ are basis for a finite-dimensional vector space $U$ over $\F$, and $(\mathbf{f}_1, \cdots, \mathbf{f}_n)$ and $(\mathbf{v}_1, \cdots, \mathbf{v}_n)$ are basis of a finite-dimensional vector space $V$ over $\F$.
  Let $\alpha: U\to V$ be a linear map represented by a matrix $A$ with respect to $(\mathbf{e}_i)$ and $(\mathbf{f}_i)$ and by $B$ with respect to $(\mathbf{u}_i)$ and $(\mathbf{v}_i)$. Then
  \[
    B = Q^{-1}AP,
  \]
  where $P$ and $Q$ are given by
  \[
    \mathbf{u}_i = \sum_{k = 1}^m P_{ki}\mathbf{e}_k,\quad \mathbf{v}_i = \sum_{k = 1}^n Q_{ki}\mathbf{f}_k.
  \]
\end{thm}
Note that one can view $P$ as the matrix representing the identity map $i_U$ from $U$ with basis $(\mathbf{u}_i$) to $U$ with basis $(\mathbf{e}_i)$, and similarly for $Q$. So both are invertible.
\begin{proof}
  On the one hand, we have
  \[
    \alpha(\mathbf{u}_i) = \sum_{j = 1}^n B_{ji}\mathbf{v}_j = \sum_j\sum_\ell B_{ji} Q_{\ell j}\mathbf{f}_\ell = \sum_\ell [QB]_{\ell i}\mathbf{f}_\ell.
  \]
  On the other hand, we can write
  \[
    \alpha (\mathbf{u}_i) = \alpha \left(\sum_{k = 1}^m P_{ki}\mathbf{e}_k\right) = \sum_{k = 1}^m P_{ki} \sum_\ell A_{\ell k}\mathbf{f}_\ell = \sum_{\ell}[AP]_{\ell i} f_\ell.
  \]
  Since the $\mathbf{f}_\ell$ are linearly independent, we conclude that
  \[
    QB = AP.
  \]
  Since $Q$ is invertible, we get $B = Q^{-1}AP$.
\end{proof}

Q: Rank is well-defined
A: If $A \in \Mat_{n, m}(\F)$, then $r(A) = r(A^T)$, ie. the row rank is equivalent to the column rank.
\begin{proof}
  We know that there are some invertible $P, Q$ such that
  \[
    Q^{-1}AP =
    \begin{pmatrix}
      I_r & 0\\
      0 & 0
    \end{pmatrix},
  \]
  where $r = r(A)$ (column rank $=$ rank of linear map). We can transpose this whole equation to obtain
  \[
    (Q^{-1}AP)^T = P^T A^T (Q^T)^{-1} =
    \begin{pmatrix}
      I_r & 0\\
      0 & 0
    \end{pmatrix}
  \]
  So $r(A^T) = r$.
\end{proof}

Q: Elementary matrices
A: We call the following matrices of $\GL_n(\F)$ \emph{elementary matrices}:
  \setcounter{MaxMatrixCols}{11}
  \[
    S_{ij}^n =
    \begin{pmatrix}
      1\\
      & \ddots\\
      & & 1\\
      & & & 0 & & & & 1\\
      & & & & 1\\
      & & & & & \ddots\\
      & & & & & & 1\\
      & & & 1 & & & & 0\\
      & & & & & & & & 1\\
      & & & & & & & & & \ddots\\
      & & & & & & & & & & 1
    \end{pmatrix}
  \]
This is called a reflection, where the rows we changed are the $i$th and $j$th row.
  \[
    E_{ij}^n (\lambda) =
    \begin{pmatrix}
      1 \\
      & \ddots \\
      & & 1 & & \lambda\\
      & & & \ddots\\
      & & & & 1\\
      & & & & & \ddots\\
      & & & & & & 1
    \end{pmatrix}
  \]
  This is called a shear, where $\lambda$ appears at the $i,j$th entry.
  \[
    T_{i}^n (\lambda) =
    \begin{pmatrix}
      1 \\
      & \ddots\\
      & & 1 \\
      & & & \lambda\\
      & & & & 1\\
      & & & & & \ddots\\
      & & & & & & 1
    \end{pmatrix}
  \]
  This is called a stretch, where $\lambda\not= 0$ appears at the $i$th column. % not a shear
Observe that if $A$ is a $m\times n$ matrix, then
\begin{enumerate}
  \item $AS_{ij}^n$ is obtained from $A$ by swapping the $i$th and $j$th columns.
  \item $AE_{Ij}^n(\lambda)$ is obtained by adding $\lambda\times$ column $i$ to column $j$.
  \item $AT_i^n (\lambda)$ is obtained from $A$ by rescaling the $i$th column by $\lambda$.
\end{enumerate}
Multiplying on the left instead of the right would result in the same operations performed on the rows instead of the columns.
These can be trivially shown to not affect the rank.

Q: Equivalence classes of matrices
A: \begin{prop}
  If $A\in \Mat_{n, m}(\F)$, then there exist invertible matrices $P \in \GL_m(\F), Q\in \GL_n(\F)$ so that
  \[
    Q^{-1}AP =
    \begin{pmatrix}
      I_r & 0\\
      0 & 0
    \end{pmatrix}
  \]
  for some $0 \leq r \leq \min(m, n)$.
\end{prop}
\begin{proof}
  We show by induction there are elementary matrices $E_1^m, \cdots, E_a^m$ and $F_1^n, \cdots, F_b^n$ such that
  \[
    E_1^m \cdots E_a^m AF_1^n \cdots F_b^n =
    \begin{pmatrix}
      I_r & 0\\
      0 & 0
    \end{pmatrix}
  \]
  This suffices since the $E_i^m \in \GL_M(\F)$ and $F_j^n \in \GL_n(\F)$.
If $A = 0$, then done. If not, there is some $i, j$ such that $A_{ij} \not= 0$. By swapping row $1$ and row $i$; and then column $1$ and column $j$, we can assume $A_{11} \not= 0$. By rescaling row $1$ by $\frac{1}{A_{11}}$, we can further assume $A_{11} = 1$.
  Now we can add $-A_{1j}$ times column $1$ to column $j$ for each $j \not= 1$, and then add $-A_{i1}$ times row $1$ to row $i \not= 1$. Then we now have
  \[
    A =
    \begin{pmatrix}
      1 & 0 & \cdots & 0\\
      0 \\
      \vdots & & B\\
      0 &
    \end{pmatrix}
  \]
  where $B$ is smaller than $A$.
\end{proof}

Q: Dual space
A: Let $V$ be a vector space over $\F$. The \emph{dual} of $V$ is defined as
  \[
    V^* = \mathcal{L}(V, \F) = \{\theta: V \to \F \ | \ \theta\text{ linear}\}.
  \]
  Elements of $V^*$ are called \emph{linear functionals} or \emph{linear forms}.

Q: Dual basis
A: If $V$ is a finite-dimensional vector space over $f$ with basis $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$, then there is a unique basis $(\varepsilon_1, \cdots, \varepsilon_n)$ for $V^*$ (called the \emph{dual basis} to $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$) such that
  \[
    \varepsilon_i(\mathbf{e}_j) = \delta_{ij}.
  \]
In particular, $\dim V = \dim V^*$. Hence we can regard elements of $V^*$ as just row vectors $(a_1, \cdots, a_n) = \sum_{j = 1}^n a_j\varepsilon_j$ wrt the dual basis such that
\[
  \left(\sum a_j \varepsilon_j\right)\left(\sum_{x_i}\mathbf{e}_i\right) = \sum_{i, j} a_j x_i \delta_{ij} = \sum_{i = 1}^n a_i x_i = \mathbf{a}\cdot\mathbf{x}.
\]
\begin{proof}
\textbf{Uniqueness}. Immediate by basis determination of linear maps.
\textbf{Existence}.
\begin{itemize}
\item \emph{Span}. Given $\theta \in V^*$, we have
\begin{align*}
\exists (\lambda_i): \theta &= \sum_{i = 1}^n \lambda_i \varepsilon_i \\
\iff \forall j: \theta(\mathbf{e}_j) &= \sum_{i = 1}^n \lambda_i\varepsilon_i(\mathbf{e}_j) \\
\iff \forall j:  \theta(\mathbf{e}_j)&=\lambda_j.
\end{align*}
\item \emph{Linear independence}$^\dagger$.  Suppose $\sum_{i = 1}^n \lambda_i \varepsilon_i=0$. Then $\forall j$: \vspace{-1cm}
\begin{align*}
0&=\sum_{i = 1}^n \mu_i\varepsilon_i(\mathbf{e}_j) \\
&=\mu_j.
\end{align*}
\end{itemize}
\end{proof}
($^\dagger$) True for all vector spaces. So $\dim V^* \geq \dim V$.

Q: Dual space transformation law
A: Let $V$ be a finite-dimensional vector space over $\F$ with bases $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$ and $(\mathbf{f}_1, \cdots, \mathbf{f}_n)$, and that $P$ is the change of basis matrix such that
  \[
    \mathbf{f}_i = \sum_{k = 1}^n P_{ki}\mathbf{e}_k.
  \]
  Let $(\varepsilon_1, \cdots, \varepsilon_n)$ and $(\eta_1, \cdots, \eta_n)$ be the corresponding dual bases so that
  \[
    \varepsilon_i (\mathbf{e}_j) = \delta_{ij} = \eta_i (\mathbf{f}_j).
  \]
  Then the change of basis matrix from $(\varepsilon_1, \cdots, \varepsilon_n)$ to $(\eta_1, \cdots, \eta_n)$ is $(P^{-1})^T$, ie.
  \[
    \varepsilon_i = \sum_{\ell = 1}^n P_{\ell i}^T \eta_\ell.
  \]
\begin{proof}
Write $Q = P^{-1}$ so that
  \[
    \mathbf{e}_j = \sum_{k = 1}^n Q_{kj}\mathbf{f}_k.
  \]
  So we can compute
  \begin{align*}
    \left(\sum_{\ell = 1}^\infty P_{i\ell}\eta_\ell\right)(\mathbf{e}_j) &= \left(\sum_{\ell = 1}^\infty P_{i\ell}\eta_\ell\right)\left(\sum_{k = 1}^n Q_{kj}\mathbf{f}_k\right)\\
    &= \sum_{k, \ell} P_{i\ell}\delta_{\ell k} Q_{kj}\\
    &= \sum_{k, \ell} P_{i\ell} Q_{\ell j}\\
    &= [PQ]_{ij}\\
    &= \delta_{ij}.
  \end{align*}
  So $\varepsilon_i = \sum_{\ell = 1}^n P_{\ell i}^T \eta_\ell$.
\end{proof}

Q: Annihilator
A: Let $U\subseteq V$. Then the \emph{annihilator} of $U$ is
  \[
    U^0 = \{\theta\in V^* : \theta(\mathbf{u}) = 0, \forall \mathbf{u}\in U\}.
  \]
  If $W \subseteq V^*$, then the \emph{annihilator} of $V$ is
  \[
    W^0 = \{\mathbf{v}\in V: \theta(\mathbf{v}) = 0,\forall \theta \in W\}.
  \]

Q: Dimension of the annihilator
A: Let $V$ be a vector space over $\F$ and $U$ a subspace. Then
  \[
    \dim U + \dim U^0 = \dim V.
  \]
\begin{proof}
  Let $(\mathbf{e}_1, \cdots, \mathbf{e}_k)$ be a basis for $U$ and extend to $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$ a basis for $V$. Consider the dual basis $(\varepsilon_1, \cdots, \varepsilon_n)$ for $V^*$. Then ets
  \[
    U^0 = \bra \varepsilon_{k + 1}, \cdots, \varepsilon_{n}\ket.
  \]
\begin{itemize}
\item $\bra \varepsilon_{k + 1}, \cdots, \varepsilon_{n}\ket\subseteq U^0$.
$\forall j > k, \forall i\leq k: \varepsilon_j(\mathbf{e}_i) = 0$. So $\varepsilon_{k + 1}, \cdots, \varepsilon_n \in U^0$.
\item $U^0\subseteq\bra \varepsilon_{k + 1}, \cdots, \varepsilon_{n}\ket$.
Given $\theta \in U^0$, we can write
  \[
    \theta = \sum_{j = 1}^n \lambda_j \varepsilon_j.
  \]
  But then $\forall i \leq k: 0 = \theta (\mathbf{e}_i) = \lambda_i$. So $\theta\in\bra \varepsilon_{k + 1}, \cdots, \varepsilon_{n}\ket.$
\end{itemize}
\end{proof}
\begin{proof}
  Consider the restriction map $V^* \to U^*$, given by $\theta \mapsto \theta|_U$. Since every linear map $U \to \F$ can be extended to $V\to \F$, this is a linear surjection. Moreover, $\ker r=U^0$. So by rank-nullity theorem,
  \begin{align*}
    \dim V^* &= \dim U^0 + \dim U^* \\
\dim V &= \dim U^0 + \dim U.
  \end{align*}
\end{proof}
\begin{proof}
The map $(V/U)^*\to U^0$ given by
\[
\theta:(V/U \to\F)\mapsto \phi:(V\to\F)
\]
where $\forall\mathbf{v}\in V: \phi(\mathbf{v})=\theta(\mathbf{v}+U)$ is an isomorphism so
\[
\dim U_0 =\dim_(V/U)^* = \dim (V/U) = \dim V - \dim U.
\]
\end{proof}

Q: Dual map
A: Let $V, W$ be vector spaces over $\F$ and $\alpha: V\to W \in \mathcal{L}(V, W)$. The \emph{dual map} to $\alpha$, written $\alpha^*: W^* \to V^*$ is given by $\theta \mapsto \theta \circ \alpha$. Since the composite of linear maps is linear, $\alpha^*(\theta) \in V^*$.

Q: Dual maps are linear
A: Let $\alpha \in \mathcal{L}(V, W)$ be a linear map. Then $\alpha^* \in \mathcal{L}(W^*, V^*)$ is a linear map.
\begin{proof}
  Let $\lambda, \mu \in \F$ and $\theta_1, \theta_2 \in W^*$. $\forall\mathbf{v}\in V:$
  \begin{align*}
    \alpha^*(\lambda \theta_1 + \mu \theta_2)(\mathbf{v}) &= (\lambda \theta_1 + \mu \theta_2)(\alpha \mathbf{v}) \\
    &= \lambda \theta_1 (\alpha (\mathbf{v})) + \mu \theta_2 (\alpha(\mathbf{v})) \\
    &= (\lambda \alpha^*(\theta_1)+ \mu \alpha^*(\theta_2))(\mathbf{v}).
  \end{align*}
\end{proof}

Q: Matrix representation of the dual map
A: Let $V, W$ be finite-dimensional vector spaces over $\F$ and $\alpha: V\to W$ be a linear map. Let $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$ be a basis for $V$ and $(\mathbf{f}_1, \cdots, \mathbf{f}_m)$ be a basis for $W$; $(\varepsilon_1, \cdots, \varepsilon_n)$ and $(\eta_1, \cdots, \eta_m)$ the corresponding dual bases.
  Suppose $\alpha$ is represented by $A$ with respect to $(\mathbf{e}_i)$ and $(\mathbf{f}_i)$ for $V$ and $W$. Then $\alpha^*$ is represented by $A^T$ with respect to the corresponding dual bases.
\begin{proof}
  Since
  \[
    \alpha (\mathbf{e}_i) = \sum_{k = 1}^m A_{ki}\mathbf{f}_k,
  \]
 we have
  \begin{align*}
    \alpha^*(\eta_i)(\mathbf{e}_j) &= \eta_i(\alpha(\mathbf{e}_j)) \\
&= \eta_i\left(\sum_{k = 1}^m A_{kj}\mathbf{f}_k\right)\\
& = \sum_{k = 1}^m A_{kj} \delta_{ik} \\
&= A_{ij} \\
&= \sum_{k = 1}^n A_{ik} \varepsilon_k (\mathbf{e}_j) \\
&= \sum_{k = 1}^n A_{ki}^T \varepsilon_k (\mathbf{e}_j) \\
 \alpha^*(\eta_i)&= \sum_{k = 1}^n A_{ki}^T \varepsilon_k.
  \end{align*}
\end{proof}

Q: Kernel and image of dual map
A: Let $\alpha \in \mathcal{L}(V, W)$ with $V, W$ finite dimensional vector spaces over $\F$. Then
  \begin{enumerate}
    \item $\ker \alpha^* = (\im \alpha)^0$.
    \item $r(\alpha) = r(\alpha^*)$ (which is another proof that row rank is equal to column rank).
    \item $\im \alpha^* = (\ker \alpha)^0$.
  \end{enumerate}
\begin{proof}\leavevmode
  \begin{enumerate}
    \item If $\theta \in W^*$, then
      \begin{align*}
        \theta \in \ker \alpha^* &\Leftrightarrow \alpha^*(\theta) = 0 \\
        &\Leftrightarrow (\forall \mathbf{v}\in V)\; \theta \alpha(\mathbf{v}) = 0 \\
        &\Leftrightarrow (\forall \mathbf{w}\in \im \alpha)\; \theta(\mathbf{w}) = 0\\
        &\Leftrightarrow \theta \in (\im \alpha)^0.
      \end{align*}
    \item As $\im \alpha \leq W$, we have that
      \[
        \dim \im \alpha + \dim (\im \alpha)^0 = \dim W.
      \]
From (i) we have
      \[
        n(\alpha^*) = \dim (\im \alpha)^0.
      \]
   Hence
      \[
        r(\alpha) + n(\alpha^*) = \dim W = \dim W^*.
      \]
      By the rank-nullity theorem, we have $r(\alpha) = r(\alpha^*)$.
    \item Let $\theta \in \im \alpha^*$. Then $\theta = \phi \alpha$ for some $\phi \in W^*$. If $\mathbf{v}\in \ker\alpha$, then
      \[
        \theta(\mathbf{v}) = \phi(\alpha(\mathbf{v})) = \phi(\mathbf{0}) = \mathbf{0}.
      \]
      So $\im \alpha^* \subseteq (\ker\alpha)^0$.
      But we know
      \[
        \dim (\ker \alpha)^0 + \dim \ker \alpha = \dim V,
      \]
      So we have
      \begin{align*}
        \dim (\ker \alpha)^0 &= \dim V - n(\alpha) \\
&= r(\alpha) \\
&= r(\alpha^*) \\
&= \dim \im \alpha^*.
      \end{align*}
      Hence we must have $\im \alpha^* = (\ker \alpha)^0$.
  \end{enumerate}
\end{proof}

Q: Evaluation map
A: Let $V$ be a vector space over $\F$. Then there is a canonical linear map $\ev: V\to (V^*)^*$ given by
  \[
    \ev (\mathbf{v})(\theta) = \theta(\mathbf{v}).
  \]
\begin{proof}
\textbf{Well-defined}. $\forall\lambda, \mu\in \F$, $\theta_1, \theta_2 \in V^*, \mathbf{v} \in V$:
  \begin{align*}
    \ev(\mathbf{v})(\lambda\theta_1 + \mu\theta_2) &= (\lambda\theta_1 + \mu\theta_2)(\mathbf{v}) \\
    &= \lambda\theta_1(\mathbf{v}) + \mu\theta_2(\mathbf{v}) \\
    &= \lambda\ev(\mathbf{v})(\theta_1) + \mu \ev(\mathbf{v})(\theta_2).
  \end{align*}
So $\ev(\mathbf{v})\in \mathcal{L}(V^*, \F)=V^{**}$.
\textbf{Linear}. $\forall\lambda, \mu\in \F$, $\mathbf{v}_1, \mathbf{v}_2 \in V\theta \in V^*$:
  \begin{align*}
    \ev(\lambda \mathbf{v}_1 + \mu \mathbf{v}_2)(\theta) &= \theta(\lambda\mathbf{v}_1 + \mu \mathbf{v}_2) \\
    &= \lambda\theta(\mathbf{v}_1) + \mu \theta(\mathbf{v}_2) \\
    &= \lambda \ev(\mathbf{v}_1)(\theta) + \mu \ev(\mathbf{v}_2)(\theta) \\
    &= (\lambda \ev(\mathbf{v}_1) + \mu \ev(\mathbf{v}_2))(\theta).
  \end{align*}
\end{proof}

Q: Annihilator of annihilator
A: Let $V, W$ be finite-dimensional vector spaces over $\F$ after identifying ($V$ and $V^{**}$) and ($W$ and $W^{**}$) by the evaluation map. Let $U\leq V$. Then $U^{00} = U$.
\begin{proof}\leavevmode
Given $\mathbf{u} \in U$, $\forall \theta \in U^0: \mathbf{u}(\theta) = \theta(\mathbf{u}) = 0$. So $\mathbf{u} \in U^{00}$. Hence $U \subseteq U^{00}$. We also know that
      \[
        \dim U = \dim V - \dim U^0 = \dim V - (\dim V - \dim U^{00}) = \dim U^{00}.
      \]
      So we must have $U = U^{00}$.
\end{proof}

Q: Dual of the dual map
A: If $\alpha\in \mathcal{L}(V, W)$, then $\alpha^{**} = \alpha$.
\begin{proof}\leavevmode
Let $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$ be a basis for $V$ and $(\mathbf{f}_1, \cdots, \mathbf{f}_m)$ be a basis for $W$, and let $(\varepsilon_1, \cdots, \varepsilon_n)$ and $(\eta_1, \cdots, \eta_n)$ be the corresponding dual bases. Since
      \[
        \mathbf{e}_i(\varepsilon_j) = \delta_{ij} = \varepsilon_j(\mathbf{e}_i),\quad \mathbf{f}_i(\eta_j) = \delta_{ij} = \eta_j(\mathbf{f}_i),
      \]
the converse dualities hold.
      If $\alpha$ is represented by $A$, then $\alpha^*$ is represented by $A^T$. So $\alpha^{**}$ is represented by $(A^T)^T = A$. So done.
\end{proof}

Q: Annihilator of sum and intersection
A: Let $V$ be a finite-dimensional vector space $\F$ and $U_1$, $U_2$ are subspaces of $V$. Then
  \begin{enumerate}
    \item $(U_1 + U_2)^0 = U_1^0 \cap U_2^0$
    \item $(U_1 \cap U_2)^0 = U_1^0 + U_2^0$.
  \end{enumerate}
\begin{proof}\leavevmode
  \begin{enumerate}
    \item $\forall\theta\in V^*$:
      \begin{align*}
        \theta \in (U_1 + U_2)^0 &\Leftrightarrow \forall \mathbf{u}_1 \in U_1,\mathbf{u}_2 \in U_2: \theta (\mathbf{u}_1 + \mathbf{u}_2) = 0\\
        &\Leftrightarrow \forall \mathbf{u} \in U_1 \cup U_2: \theta (\mathbf{u}) = 0\\
        &\Leftrightarrow \theta \in U_1^0 \cap U_2^0.
      \end{align*}
    \item
      \begin{align*}
        (U_1 \cap U_2)^0 &= ((U_1^0)^0 \cap (U_2^0)^0)^0 \\
&= (U_1^0 + U_2^0)^{00} \\
&= U_1^0 + U_2^0.
      \end{align*}
  \end{enumerate}
\end{proof}

Q: Matrix transformation law for bilinear forms
A: Suppose $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$ and $(\mathbf{v}_1, \cdots, \mathbf{v}_n)$ are basis for $V$ such that
  \[
    \mathbf{v}_i = \sum P_{ki}\mathbf{e}_k\text{ for all }i = 1,\cdots, n;
  \]
  and $(\mathbf{f}_1, \cdots, \mathbf{f}_m)$ and $(\mathbf{w}_1, \cdots, \mathbf{w}_m)$ are bases for $W$ such that
  \[
    \mathbf{w}_i = \sum Q_{\ell j} \mathbf{f}_\ell\text{ for all }j = 1, \cdots, m.
  \]
  Let $\psi: V\times W \to \F$ be a bilinear form represented by $A$ with respect to $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$ and $(\mathbf{f}_1, \cdots, \mathbf{f}_m)$, and by $B$ with respect to the bases $(\mathbf{v}_1, \cdots, \mathbf{v}_n)$ and $(\mathbf{w}_1, \cdots, \mathbf{w}_m)$. Then
  \[
    B = P^T AQ.
  \]
\begin{proof}
  We have
  \begin{align*}
    B_{ij} &= \phi(\mathbf{v}_i, \mathbf{w}_j)\\
    &= \phi\left(\sum P_{ki}\mathbf{e}_k, \sum Q_{\ell j}\mathbf{f}_\ell\right)\\
    &= \sum P_{ki}Q_{\ell j}\phi(\mathbf{e}_k, \mathbf{f}_\ell)\\
    &= \sum_{k, \ell} P^T_{ik} A_{k\ell} Q_{\ell j}\\
    &= (P^T AQ)_{ij}.
  \end{align*}
\end{proof}
Note the equivalence classes are the same since if $B = P^{-1} AQ$, then $B = ((P^{-1})^T)^T AQ$.

Q: Dimension of a subspace
A: \begin{lemma}
  If $V$ is a finite dimensional vector space over $\F$, $U\leq V$ is a subspace, then $U$ is finite dimensional and $\dim U \leq \dim V$. Furthermore if $U$ is a proper subspace, then $\dim U < \dim V$.
\end{lemma}
\begin{proof}
  Every LI subset of $V$ has size at most $\dim V$. So let $S \subseteq U$ be a LI subset of largest size.
If $\bra S\ket \neq U$, then $\exists\mathbf{v}\in V\setminus \bra S\ket$ such that $S\cup \{\mathbf{v}\}$ is LI, contradicting maximality. So $S$ is a basis for $U$.
Furthermore, if $U\not= V$, $\exists\mathbf{v}\in V\setminus U = V\setminus \bra S\ket$. Then $S\cup \{\mathbf{v}\}\leq V$ so by the first result $|S| + 1 \leq \dim V$. In particular, $\dim U = |S| < \dim V$.
\end{proof}

Q: Injective vs surjective linear maps
A: Suppose $\alpha: U\to V$ is a linear map betwee vector spaces over $\F$ both of dimension $n < \infty$. Then the following are equivalent $\alpha$ is injective $\iff$ $\alpha$ is surjective.
\begin{proof}
By the rank-nullity theorem
\begin{align*}
\alpha \text{ is injective} &\iff n(\alpha) = 0 \\
&\iff r(\alpha) = \dim V = n \\
&\iff \alpha \text{ is surjective}.
\end{align*}
\end{proof}

Q: Dual of the dual space
A: If $V$ is finite-dimensional, then $\ev: V \to V^{**}$ is an isomorphism. In general, it is injective.
\begin{proof}
\textbf{Injective} (via kernels). Suppose $\exists\mathbf{v}\in V: \ev(\mathbf{v}) = \mathbf{0}$. Then $\forall \theta \in V^*: \theta (\mathbf{v}) = \ev (\mathbf{v})(\theta) = \mathbf{0}$. So $\dim \bra \mathbf{v}\ket^0 = \dim V^* = \dim V$. Then $\dim \bra \mathbf{v} \ket = \dim V - \dim \bra \mathbf{v} \ket^0 =0 $. So $\mathbf{v} = \mathbf{0}$.
\textbf{Surjective}. Immediate since $V$ and $V^{**}$ have the same dimension.
\end{proof}

Q: Evaluation of the annihilator
A: Suppose $V$ is a fd vsp and $U\leq V$. Then
\[
\ev(U^0)=\ev(U)^0.
\]
\begin{proof}
\begin{align*}
\ev(U^0) &= (U^0)^{00} \\
&= (U^{00})^0 \\
&=\ev(U)^0.
\end{align*}
\end{proof}

Q: Matrix representation of a bilinear form
A: Let $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$ be a basis for $U$ and $(\mathbf{f}_1, \cdots, \mathbf{f}_m)$ be a basis for $V$, and $\phi: U\times V \to \F$. Then the \emph{matrix $A$ representing $\phi$} with respect to the basis is defined to be
  \[
    A_{ij} = \phi(\mathbf{e}_i, \mathbf{f}_j).
  \]
We claim that $A$ determines $\phi$.
\begin{proof}
Given $u\in U, v\in V$ we have
\begin{align*}
\phi(u,v) &= \phi\left(\sum_{i=1}^n u_i e_i, \sum_{j=1}^m v_j f_j\right) \\
&= \sum_{i=1}^n u_i \phi\left(e_i, \sum_{j=1}^m v_j f_j\right) \\
&= \sum_{i=1}^n \sum_{j=1}^m u_iv_j\phi(e_i,  f_j) \\
&= \sum_{i=1}^n \sum_{j=1}^m u_iA_{ij}v_j\\
&= u^T A v.
\end{align*}
\end{proof}

Q: Bilinear form
A: Let $V, W$ be vector spaces over $\F$. Then a function $\phi: V\times W \to \F$ is a \emph{bilinear form} if it is linear in each variable, ie. for each $\mathbf{v} \in V$, $\phi(\mathbf{v}, \ph): W \to \F$ is linear; for each $\mathbf{w} \in W$, $\phi(\ph, \mathbf{w}): V\to \F$ is linear.

Q: Left and right maps
A: If we are given a bilinear form $\psi: V\times W \to \F$, we immediately get two linear maps:
\[
  \psi_L: V\to W^*,\quad \psi_R: W \to V^*,
\]
defined by $\psi_L(\mathbf{v})(\mathbf{w}) = \psi(\mathbf{v}, \mathbf{w}) = \psi_R(\mathbf{w})(\mathbf{v})$.

Q: Matrix representation of left and right maps
A: \begin{lemma}
  Let $(\varepsilon_1,\cdots, \varepsilon_n)$ be a basis for $V^*$ dual to $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$ of $V$; $(\eta_1,\cdots, \eta_n)$ be a basis for $W^*$ dual to $(\mathbf{f}_1, \cdots, \mathbf{f}_n)$ of $W$.
  If $A$ represents $\psi$ with respect to $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$ and $(\mathbf{f}_1, \cdots, \mathbf{f}_m)$, then $A$ also represents $\psi_R$ with respect to $(\mathbf{f}_1,\cdots, \mathbf{f}_m)$ and $(\varepsilon_1, \cdots, \varepsilon_n)$; and $A^T$ represents $\psi_L$ with respect to $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$ and $(\eta_1, \cdots, \eta_m)$.
\end{lemma}
\begin{proof}
  We just have to compute
  \[
    \psi_L(\mathbf{e}_i)(\mathbf{f}_j) = A_{ij} = \left(\sum A_{i\ell} \eta_\ell\right) (\mathbf{f}_j).
  \]
  So we get
  \[
    \psi_L(\mathbf{e}_i) = \sum A_{\ell i}^T\eta_\ell.
  \]
  So $A^T$ represents $\psi_L$.
  We also have
  \[
    \psi_R(\mathbf{f}_j)(\mathbf{e}_i) = A_{ij}.
  \]
  So
  \[
    \psi_R(\mathbf{f}_j) = \sum A_{kj}\varepsilon_k.
  \]
\end{proof}

Q: Left and right kernel
A: The kernel of $\psi_L$ is \emph{left kernel} of $\psi$, while the kernel of $\psi_R$ is the \emph{right kernel} of $\psi$.
Then by definition, $\mathbf{v}$ is in the left kernel if $\psi(\mathbf{v}, \mathbf{w}) = 0$ for all $\mathbf{w} \in W$.
More generally, if $T\subseteq V$, then we write
\[
  T^\bot = \{\mathbf{w} \in W: \psi(\mathbf{t}, \mathbf{w}) = 0\text{ for all }\mathbf{t} \in T\}.
\]
Similarly, if $U\subseteq W$, then we write
\[
  ^\bot U = \{\mathbf{v} \in V: \psi(\mathbf{v}, \mathbf{u}) = 0\text{ for all }\mathbf{u}\in U\}.
\]
In particular, $V^\bot = \ker \psi_R$ and $^\bot W = \ker \psi_L$.

Q: Non-degenerate bilinear form
A: $\psi$ is \emph{non-degenerate} if the left and right kernels are both trivial. We say $\psi$ is \emph{degenerate} otherwise.
\begin{lemma}
  Let $V$ and $W$ be finite-dimensional vector spaces over $\F$ with bases $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$ and $(\mathbf{f}_1, \cdots, \mathbf{f}_m)$ be their basis respectively.
  Let $\psi: V\times W \to \F$ be a bilinear form represented by $A$ with respect to these bases. Then $\phi$ is non-degenerate if and only if $A$ is (square and) invertible. In particular, $V$ and $W$ have the same dimension.
\end{lemma}
\begin{proof}
\begin{align*}
\psi \text{ is non-degenerate} &\iff \ker \psi_L=0 \text{ and } \ker\psi_R=0 \\
&\iff r(A^T)=n \text{ and }r(A)=m \\
&\iff m=n=r(A) \\
&\iff A \text{ is invertible}.
\end{align*}
\end{proof}

Q: Change of basis for bilinear form
A: \begin{prop}
  Suppose $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$ and $(\mathbf{v}_1, \cdots, \mathbf{v}_n)$ are basis for $V$ such that
  \[
    \mathbf{v}_i = \sum P_{ki}\mathbf{e}_k\text{ for all }i = 1,\cdots, n;
  \]
  and $(\mathbf{f}_1, \cdots, \mathbf{f}_m)$ and $(\mathbf{w}_1, \cdots, \mathbf{w}_m)$ are bases for $W$ such that
  \[
    \mathbf{w}_i = \sum Q_{\ell j} \mathbf{f}_\ell\text{ for all }j = 1, \cdots, m.
  \]
  Let $\psi: V\times W \to \F$ be a bilinear form represented by $A$ with respect to $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$, and $(\mathbf{f}_1, \cdots, \mathbf{f}_m)$ by $B$ with respect to $(\mathbf{v}_1, \cdots, \mathbf{v}_n)$ and $\mathbf{w}_1, \cdots, \mathbf{w}_n)$. Then
  \[
    B = P^T AQ.
  \]
In particular, the matrices are similar and $r(\phi):=r(A)=r(\phi_L)=r(\phi_R)$ is well-defined.
\end{prop}
\begin{proof}
  We have
  \begin{align*}
    B_{ij} &= \phi(\mathbf{v}_i, \mathbf{w}_j)\\
    &= \phi\left(\sum P_{ki}\mathbf{e}_k, \sum Q_{\ell j}\mathbf{f}_\ell\right)\\
    &= \sum P_{ki}Q_{\ell j}\phi(\mathbf{e}_k, \mathbf{f}_\ell)\\
    &= \sum_{k, \ell} P^T_{ik} A_{k\ell} Q_{\ell j}\\
    &= (P^T AQ)_{ij}.
  \end{align*}
\end{proof}

Q: Determinant of the transpose
A: \begin{lemma}
  $\det A = \det A^T$.
\end{lemma}
\begin{proof}
  \begin{align*}
    \det A^T &= \sum_{\sigma \in S_n} \varepsilon(\sigma) \prod_{i = 1}^n A_{\sigma(i)i}\\
    &= \sum_{\sigma \in S_n} \varepsilon (\sigma) \prod_{j = 1}^n A_{j \sigma^{-1}(j)}\\
    &= \sum_{\tau \in S_n} \varepsilon (\tau^{-1}) \prod_{j = 1}^n A_{j \tau (j)}\\
    &= \sum_{\tau \in S_n} \varepsilon (\tau) \prod_{j = 1}^n A_{j \tau (j)}\\
    &= \det A.
  \end{align*}
\end{proof}

Q: Volume form
A: A \emph{volume form} on $\F^n$ is a function $d: \F^n \times \cdots \times \F^n \to \F$ that is
  \begin{enumerate}
    \item Multilinear, ie. for all $i$ and all $\mathbf{v}_1, \cdots, \mathbf{v}_{i - 1}, \mathbf{v}_{i + 1}, \cdots, \mathbf{v}_n \in \F^n$, we have
      \[
        \d (\mathbf{v}_1, \cdots, \mathbf{v}_{i - 1}, \ph, \mathbf{v}_{i + 1}, \cdots, \mathbf{v}_n) \in (\F^n)^*.
      \]
    \item Alternating, ie. if $\mathbf{v}_i = \mathbf{v}_j$ for some $i \not= j$, then
      \[
        d(\mathbf{v}_1, \cdots, \mathbf{v}_n) = 0.
      \]
  \end{enumerate}

Q: Determinant is a volume form
A: \begin{lemma}
  $\det $ is a volume form, i.e.
\begin{align*}
\F^n \times \ldots \F^n &\to \F \\
(A^{(1)}, \ldots A^{(n)} &\mapsto \det A
\end{align*}
is a volume form.
\end{lemma}
\begin{proof}
 \textbf{Multilinear} Each product
  \[
    \prod_{i = 1}^n A_{i \sigma(i)}
  \]
for $\sigma\in S_n$ contains precisely one entry from each column and so is multilinear. Then $\det A$ is a linear combination of multilinear forms so multilinear.
 \textbf{Alternating}. Suppose,  there are some $k, \ell$ distinct such that $A^{(k)} = A^{(\ell)}$. We let $\tau$ be the transposition $(k\; \ell)$. By Lagrange's theorem, we can write
  \[
    S_n = A_n \amalg \tau A_n,
  \]
  where $A_n = \ker \varepsilon$ and $\amalg$ is the disjoint union. We also know that
  \[
    \sum_{\sigma \in A_n} \prod_{i = 1}^n A_{i \sigma (i)} = \sum_{\sigma \in A_n} \prod_{i = 1}^n A_{i, \tau\sigma(i)}.
  \]
 So we get
  \[
    \sum_{\sigma \in A_n} \prod_{i = 1}^n A_{i \sigma (i)} = \sum_{\sigma' \in \tau A_n} \prod_{i = 1}^n A_{i\sigma'(i)},
  \]
  But we know that
  \[
    \det A = \text{LHS} - \text{RHS} = 0.
  \].
\end{proof}

Q: Volume form of a permutation
A: \begin{lemma}
  Let $d$ be a volume form on $\F^n$. Swapping two entries changes the sign, ie.
  \[
    d (\mathbf{v}_1, \cdots, \mathbf{v}_i, \cdots, \mathbf{v}_j,\cdots, \mathbf{v}_n) = -d(\mathbf{v}_1, \cdots, \mathbf{v}_j, \cdots, \mathbf{v}_i, \cdots, \mathbf{v}_n).
  \]
\end{lemma}
\begin{proof}
  By linearity, we have
  \begin{align*}
    0 &= d(\mathbf{v}_1, \cdots, \mathbf{v}_i + \mathbf{v}_j, \cdots, \mathbf{v}_i + \mathbf{v}_j, \cdots,\mathbf{v}_n) \\
    &= d(\mathbf{v}_1, \cdots, \mathbf{v}_i, \cdots, \mathbf{v}_i, \cdots, \mathbf{v}_n)\\
    &\quad\quad+ d(\mathbf{v}_1, \cdots, \mathbf{v}_i, \cdots, \mathbf{v}_j, \cdots, \mathbf{v}_n)\\
    &\quad\quad+ d(\mathbf{v}_1, \cdots, \mathbf{v}_j, \cdots, \mathbf{v}_i, \cdots, \mathbf{v}_n)\\
    &\quad\quad+ d(\mathbf{v}_1, \cdots, \mathbf{v}_j, \cdots, \mathbf{v}_j, \cdots, \mathbf{v}_n)\\
    &= d(\mathbf{v}_1, \cdots, \mathbf{v}_i, \cdots, \mathbf{v}_j, \cdots, \mathbf{v}_n)\\
    &\quad\quad+ d(\mathbf{v}_1, \cdots, \mathbf{v}_j, \cdots, \mathbf{v}_i, \cdots, \mathbf{v}_n).
  \end{align*}
  So done.
\end{proof}
\begin{cor}
  If $\sigma \in S_n$, then
  \[
    d(\mathbf{v}_{\sigma(1)}, \cdots, \mathbf{v}_{\sigma(n)}) = \varepsilon(\sigma) d(\mathbf{v}_1,\cdots, \mathbf{v}_n)
  \]
  for any $\mathbf{v}_i \in \F^n$.
\end{cor}

Q: Volume form of the image of the unit cube
A: \begin{thm}
  Let $d$ be any volume form on $\F^n$, and let $A = (A^{(1)}\;\cdots \;A^{(n)}) \in \Mat_n(\F)$. Then
  \[
    d(A^{(1)}, \cdots, A^{(n)}) = (\det A) d(\mathbf{e}_1, \cdots, \mathbf{e}_n),
  \]
  where $\{\mathbf{e}_1, \cdots, \mathbf{e}_n\}$ is the standard basis.
\end{thm}
\begin{proof}
  We can compute
  \begin{align*}
    d(A^{(1)}, \cdots, A^{(n)}) &= d\left(\sum_{i = 1}^n A_{i1} \mathbf{e}_i, A^{(2)}, \cdots, A^{(n)}\right)\\
    &= \sum_{i = 1}^n A_{i1} d(\mathbf{e}_1, A^{(2)}, \cdots, A^{(n)})\\
    &= \sum_{i, j = 1}A_{i1}A_{j2}d(\mathbf{e}_i, \mathbf{e}_j, A^{(3)}, \cdots, A^{(n)})\\
    &= \sum_{i_1, \cdots, i_n} \prod_{j = 1}^n A_{i_j j}d(\mathbf{e}_{i_1}, \cdots, \mathbf{e}_{i_n}) \\
    &= \sum_{\sigma \in S_n} \prod_{j = 1}^n A_{\sigma(j)j} d(\mathbf{e}_{\sigma(1)}, \cdots, \mathbf{e}_{\sigma(n)}) \\
    &= \sum_{\sigma \in S_n} \prod_{j = 1}^n A_{\sigma(j)j} \varepsilon(\sigma) d(\mathbf{e}_1, \cdots, \mathbf{e}_n) \\
    &= (\det A^T) d(\mathbf{e}_1, \cdots, \mathbf{e}_n) \\
    &= (\det A) d(\mathbf{e}_1, \cdots, \mathbf{e}_n).
\end{align*}
\end{proof}

Q: Determinant of a product
A: \begin{thm}
  Let $A, B \in \Mat_n(\F)$. Then $\det(AB) = \det(A)\det(B)$.
\end{thm}
\begin{proof}
  Let $d$ be a non-zero volume form on $\F^n$ (eg. det). Define $d_A: \F^n \times \ldots \F^n \to \F$ given by
\[
d_A(v_1,v_2, \ldots v_n) = d(Av_1, \ldots Av_n).
\]
$d_A$ is multilinear (since $v\mapsto Av$ is linear) and alternating (since $v_i=v_j\implies Av_i=Av_j$) so is a volume form.
Then we can compute
  \begin{align*}
    d_A(B\mathbf{e}_1,\cdots , B\mathbf{e}_n)&= d(AB\mathbf{e}_1,\cdots , AB\mathbf{e}_n) \\
&= (\det AB) d(\mathbf{e}_1,\cdots, \mathbf{e}_n),
  \end{align*}
  but we also have
  \begin{align*}
    d_A(B\mathbf{e}_1,\cdots , B\mathbf{e}_n)&= (\det B) d_A(\mathbf{e}_1, \cdots, \mathbf{e}_n)\\
& =  (\det B) d(A\mathbf{e}_1, \cdots, A\mathbf{e}_n)\\
&=(\det A)(\det B)d(\mathbf{e}_1, \cdots, \mathbf{e}_n).
  \end{align*}
  Since $d$ is non-zero, we must have $\det AB = \det A \det B$.
\end{proof}
\begin{proof}
  \begin{align*}
    \det AB &= \sum_\sigma \varepsilon(\sigma)(AB)_{\sigma(1)1}(AB)_{\sigma(2)2}\cdots (AB)_{\sigma(n)}\\
    &= \sum_\sigma \varepsilon(\sigma) \sum_{k_1,k_2,\cdots,k_n} A_{\sigma(1)k_1}B_{k_11}\cdots A_{\sigma(n)k_n}B_{k_nn}\\
    &= \sum_{k_1,\cdots,k_n}B_{k_11}\cdots B_{k_nn}\underbrace{\sum_\sigma \varepsilon(\sigma) A_{\sigma(1)k_1}A_{\sigma(2)k_2}\cdots A_{\sigma(n)k_n}}_{S}
    \intertext{If $k_i=k_j$ for $i\neq j$, then $S$ is a determinant of a matrix with two columns the same i.e. $S = 0$. So only $k_i =\rho (i)$ for some $\rho\in S_n$ contributes. Then we can write}
    \det AB &= \sum_\rho B_{\rho(1)1}\cdots B_{\rho(n)n} \sum_\sigma \varepsilon(\sigma) A_{\sigma(1)\rho(1)} \cdots A_{\sigma(n)\rho(n)}\\
    &= \sum_\rho B_{\rho(1)1}\cdots B_{\rho(n)n} (\varepsilon(\rho)\det A)\\
    &= \det A\sum_\rho \varepsilon(\rho) B_{\rho(1)1}\cdots B_{\rho(n)n}\\
    &= \det A\det B.
  \end{align*}
\end{proof}

Q: Volume form under a linear transformation
A: If $d$ is any volume form, $v_1,\ldots v_n\in\F^n$, $A\in\Mat_n(\F)$, then
\[
d(Av_1, \ldots Av_n) = (\det A) d(v_1, \ldots v_n).
\]
\begin{proof}
Let $B\in\Mat_n(\F)$ such that $Be_i=v_i$. Then from the determinant product formula
\begin{align*}
d(Av_1, \ldots Av_n) &= d(ABe_1, \ldots ABe_n) \\
&= (\det AB )d(e_1, \ldots e_n) \\
&= (\det A \det B) d(e_1, \ldots e_n) \\
&= (\det A) d(Be_1, \ldots Be_n) \\
&= (\det A) d(v_1, \ldots v_n).
\end{align*}
\end{proof}

Q: Determinant of an invertible matrix
A: If $A$ is invertible, then $A$ is non-singular and $\det A^{-1} = 1/\det A$.
\begin{proof}
From the determinant product formula
\[
    1 = \det I = \det(AA^{-1}) = \det A\det A^{-1}.
  \]
So $\det A \neq 0$ and $\det A^{-1} = 1/\det A$.
\end{proof}

Q: Definitions of invertible
A: \begin{thm}
  Let $A \in \Mat_n(\F)$. Then TFAE:
  \begin{enumerate}
    \item $A$ is invertible.
    \item $\det A \not= 0$.
    \item $r(A) = n$.
  \end{enumerate}
\end{thm}
\begin{proof}
(i) $\implies 1=\det A \det A^{-1}\implies \det A \neq 0\implies$ (ii).
By rank-nullity: (iii) $\Rightarrow$ (i).
$\neg\text{(iii)}\implies\neg\text{(ii)}$: Suppose $r(A) < n$. By rank-nullity theorem, $n(A) > 0$. So there is some $\mathbf{x} = \begin{pmatrix}\lambda_1\\\vdots\\\lambda_n\end{pmatrix}$ such that $A\mathbf{x} = \mathbf{0}$ with $\lambda_k \not= 0$. Define $B$ as follows:
  \[
    B =
    \begin{pmatrix}
      1 & & & \lambda_1\\
      & \ddots & & \vdots\\
      & & 1 & \lambda_{k - 1}\\
      & & & \lambda_k\\
      & & & \lambda_{k + 1} & 1\\
      & & & \vdots & & \ddots\\
      & & & \lambda_n & & & 1
    \end{pmatrix}
  \]
  So $AB$ has the $k$th column identically zero and thus $\det(AB) = 0$. Since $\det B =\lambda_k \not= 0$, we have $\det A = \frac{\det AB}{\det B} =0$.
\end{proof}

Q: Determinant formula
A: Let $A \in \Mat_n(\F)$. Then
      \begin{align*}
        \det A &= \sum_{i = 1}^n (-1)^{i + j} A_{ij} \det \hat{A}_{ij} \\
&= \sum_{j = 1}^n (-1)^{i + j} A_{ij} \det \hat{A}_{ij}.
      \end{align*}
\begin{proof}
  Since $\det A = \det A^T$, these are equivalent. Let $d$ be the volume form induced by the determinant. Then
  \begin{align*}
 \det A &= d(A^{(1)}, \cdots, A^{(n)}) \\
 &= d\left(A^{(1)}, \cdots, \sum_{j = 1}^n A_{ij} \mathbf{e}_i, \cdots, A^{(n)}\right)\\
    &= \sum_{i = 1}^n A_{ij} d(A^{(1)}, \cdots, \mathbf{e}_{i}, \cdots, A^{(n)}) \\
&= \sum_{i = 1}^n A_{ij} (-1)^{n - j} (-1)^{n - i}\det B \\
&= \sum_{i = 1}^n A_{ij} (-1)^{i + j} \det \hat{A}_{ij}
  \end{align*}
 where we made $n - j$ column transpositions and $n - i$ row transpositions to obtain
  \[
    B =
    \begin{pmatrix}
      \hat{A}_{ij} & 0\\
      \cdots & 1
    \end{pmatrix}
  \]
with
\begin{align*}
\det B &= \sum_{\sigma\in S_n} \varepsilon(\sigma) \prod_{k=1}^n B_{k\sigma(k)} \\
&= \sum_{\sigma\in S_n} \varepsilon(\sigma) \prod_{k=1}^{n-1} \hat{A}^{ij}_{k\sigma(k)} \\
&= \det \hat{A}^{ij}
\end{align*}
since $\sigma(n)=n$ such that $B_{n\sigma(n)}=1$ if $\sigma$ contributes to the sum.
\end{proof}

Q: Inverse formula
A: \begin{thm}
  If $A \in \Mat_n(\F)$, then
\[
A(\adj A) = (\det A) I_n = (\adj A)A.
\]
 In particular, if $\det A \not= 0$, then
  \[
    A^{-1} = \frac{1}{\det A}\adj A.
  \]
\end{thm}
\begin{proof}
  We compute
  \[
    [(\adj A)A]_{ij} = \sum_{k = 1}^n (\adj A)_{ik} A_{kj} = \sum_{k = 1}^n (-1)^{i + k} (\det\hat{A}_{ki}) A_{kj}.
  \]
Now if $i = j$, then $[(\adj A)A]_{ij} = \det A$.
If $i \neq j$, let $B\in\Mat_n(\F)$ be obtained from $A$ by replacing the $i$th column with the $j$th column. Then RHS$=\det B=0$. So
  \[
    [(\adj A)A]_{ij} = \det A \delta_{ij}
  \]
For the reverse $(A\adj A)^T = (\adj A)^T A^T = (\adj (A^T)) A^T = (\det A^T) I_n = (\det A) I_n$ so $(A\adj A)=(\det A) I_n$.
\end{proof}

Q: Determinant of a block matrix
A: \begin{lemma}
  Let $A\in \Mat_k(\F)$, and $B\in \Mat_{\ell}(\F)$. Then for any $C \in \Mat_{l, \ell}(\F)$:
  \begin{align*}
    \det
    \begin{pmatrix}
      A & C\\
      0 & B
    \end{pmatrix}
    = (\det A) (\det B).
  \end{align*}
\end{lemma}
\begin{proof}
Let
  \[
    X =
    \begin{pmatrix}
      A & C\\
      0 & B
    \end{pmatrix}.
  \]
  Then by definition, we have
  \[
    \det X = \sum_{\sigma \in S_{k + \ell}}\varepsilon(\sigma) \prod_{i = 1}^{k + \ell} X_{i\sigma(i)}.
  \]
  If $j \leq k$ and $i > k$, then $X_{ij} = 0$. So only the $\sigma$ such that $\sigma(i) > k$ if $i > k$ contribute, i.e. $\sigma=\sigma_1\sigma_2$ with $\sigma_1\in S_k$ and $\sigma_2\in S_\ell$. Hence
  \begin{align*}
    \det X &= \sum_{\sigma = \sigma_1\sigma_2}\varepsilon(\sigma_1\sigma_2) \prod_{i = 1}^k X_{i\sigma_1(i)} \prod_{j = 1}^\ell X_{k + j\; \sigma(k + j)}\\
    &= \left(\sum_{\sigma_1 \in S_k} \varepsilon(\sigma_1) \prod_{i = 1}^k A_{i\sigma_1(i)}\right)\left(\sum_{\sigma_2 \in S_\ell} \varepsilon(\sigma_2) \prod_{j = 1}^k B_{j\sigma_2(j)}\right)\\
    &= (\det A)(\det B)
  \end{align*}
\end{proof}
\begin{cor}
  \[
    \det
    \begin{pmatrix}
      A_1 & & & \mathrm{stuff}\\
      & A_2\\
      & & \ddots\\
      0 & & & A_n
    \end{pmatrix} = \prod_{i = 1}^n \det A_i
  \]
\end{cor}
\begin{proof}
Immediate by induction.
\end{proof}
However
 \begin{align*}
    \det
    \begin{pmatrix}
      A & B\\
      C & D
    \end{pmatrix}
    = (\det A) (\det D)-(\det B) (\det C)
  \end{align*}
is false in general.

Q: Similar matrices
A: We say matrices $A$ and $B$ are \emph{similar} or \emph{conjugate} if there is some $P$ invertible such that $B = P^{-1}AP$.
$\GL_n(\F)$ acts on $\Mat_n(\F)$ by conjugation:
\[
  (P, A) \mapsto PAP^{-1}.
\]
such that $A$ and $B$ are similar iff they are in the same orbit. Since orbits always partition the set, this is an equivalence relation.

Q: Trace is commutative
A: If $A \in \Mat_{m, n}(\F)$ and $B\in \Mat_{n, m}(\F)$, then
      \[
        \tr AB = \tr BA.
      \]
\begin{proof}
We compute
      \begin{align*}
        \tr AB &= \sum_{i = 1}^m (AB)_{ii} \\
&= \sum_{i = 1}^m \sum_{j = 1}^n A_{ij}B_{ji} \\
&= \sum_{j = 1}^n \sum_{i = 1}^m B_{ji}A_{ij} \\
&= \tr BA.
      \end{align*}
\end{proof}

Q: Trace of an endomorphism
A: If $A, B \in \Mat_n(\F)$ are similar, then $\tr A = \tr B$. So we can define $\tr \alpha=\tr A$ if $A$ represents $\alpha$.
\begin{proof}
Suppose $B = P^{-1}AP$. Then we have
      \[
        \tr B = \tr (P^{-1}(AP)) = \tr ((AP)P^{-1}) = \tr A.
      \]
\end{proof}

Q: Determinant of an endomorphism
A: If $A, B \in \Mat_n(\F)$ are similar, then $\det A = \det B$. So we can define $\det(\alpha)=\det(A)$ if $A$ represents $\alpha$.
\begin{proof}
We compute
      \begin{align*}
        \det (P^{-1}AP) &= \det P^{-1} \det A \det P \\
&= (\det P)^{-1} \det A \det P \\
&= \det A.
      \end{align*}
\end{proof}

Q: Trace and determinant of a dual endomorphism
A: If $\alpha \in \End(V)$, then $\alpha^*\in\End(V^*)$ satisfies
\[
\tr(\alpha^*)=\tr(\alpha), \quad \det \alpha^*=\det\alpha.
\]
\begin{proof}
If $A$ is a matrix representation of $\alpha$, then $A^T$ is a matrix representation of $\alpha^*$. So
\[
\tr(\alpha^*)=\tr(A^T)=\tr(A)=\tr(\alpha)
\]
and
\[
 \det \alpha^*=\det A^T=\det A=\det\alpha.
\]
\end{proof}

Q: Roots of the characteristic polynomial
A: Let $\alpha \in \End(V)$ with \emph{characteristic polynomial}
  \[
    \chi_\alpha(t) = \det (t\iota - \alpha).
  \]
Then the roots of $\chi_\alpha(t)$ are exactly the eigenvalues of $\alpha$.
\begin{proof}
\begin{align*}
\lambda\text{ is an eigenvalue of $\alpha$} &\iff E_\alpha(\lambda) \neq 0 \\
&\iff \ker(\alpha-\lambda\iota) \neq 0 \\
&\iff n(\alpha - \lambda \iota) > 0\\
& \iff r(\alpha - \lambda \iota) < \dim V\\
& \iff  \det(\lambda \iota - \alpha) = 0 \\
& \iff \chi_\alpha(\lambda) =0.
\end{align*}
\end{proof}

Q: Characteristic polynomial of an endomorphism
A: The \emph{characteristic polynomial} of $\alpha$ is defined by
  \[
    \chi_\alpha(t) = \det (tI- A)= \det (t\iota - \alpha)
  \]
where $A$ is a matrix representation of $\alpha$.
\begin{lemma}
  If $A$ and $B$ are similar, then they have the same characteristic polynomial.
\end{lemma}
\begin{proof}
  \[
    \det (tI - P^{-1}AP) = \det(P^{-1}(tI - A)P) = \det(tI - A).
  \]
\end{proof}

Q: Sum of eigenspaces
A: \begin{lemma}
  Let $\alpha \in \End(V)$ and $\lambda_1, \cdots, \lambda_k$ distinct eigenvalues of $\alpha$. Then
  \[
    E(\lambda_1) + \cdots + E(\lambda_k) = \bigoplus_{i = 1}^k E(\lambda_i)
  \]
  is a direct sum.
\end{lemma}
\begin{proof}
  Suppose
  \[
    \sum_{i = 1}^k \mathbf{x}_i = \sum_{i = 1}^k \mathbf{y}_i,
  \]
  with $\mathbf{x}_i, \mathbf{y}_i \in E(\lambda_i)$. Define $\beta_j \in \End(V)$ by
  \[
    \beta_j = \prod_{r \not= j} (\alpha - \lambda_r \iota).
  \]
  Then
  \begin{align*}
    \beta_j\left(\sum_{i = 1}^i \mathbf{x}_k\right) &= \sum_{i = 1}^k \prod_{r \not= j}(\alpha - \lambda_{r}\iota)(\mathbf{x}_i)\\
    &= \sum_{i = 1}^k \prod_{r\not= j} (\lambda_i - \lambda_r)(\mathbf{x}_i) \\
    \beta_j\left(\sum_{i = 1}^i \mathbf{x}_k\right) &= \prod_{r \not= j}(\lambda_j - \lambda_r) (\mathbf{x}_j).
  \end{align*}
 Combining with the symmetric result for $\mathbf{y}$:
  \[
    \prod_{r \not= j}(\lambda_j - \lambda_r) \mathbf{x}_j = \prod_{r \not= j} (\lambda_j- \lambda_r)\mathbf{y}_j.
  \]
  Since $\prod_{r \not= j} (\lambda_j - \lambda_r) \not= 0$, we must have $\mathbf{x}_i = \mathbf{y}_i$ for all $i$.
\end{proof}
\begin{cor}
Any set of non-zero eigenvectors with distinct eigenvalues is linearly independent.
\end{cor}

Q: Characterisation of diagonalisability
A: \begin{thm}
  Let $\alpha \in \End(V)$ and $\lambda_1, \cdots, \lambda_k$ be distinct eigenvalues of $\alpha$. Write $E_i$ for $E(\lambda_i)$ and $B_i$ for a basis of $E_i$. Then TFAE
  \begin{enumerate}
    \item $\alpha$ is diagonalisable
    \item $V$ has a basis of eigenvectors for $\alpha$.
    \item $V = \sum_{i = 1}^k E_i$.
    \item $\dim V = \sum_{i = 1}^k \dim E_i$.
  \end{enumerate}
\end{thm}
\begin{proof}
  \begin{itemize}
    \item (i) $\Leftrightarrow$ (ii): Let $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$ is a basis for $V$. Then
      \[
        \alpha(\mathbf{e}_i) = \sum_{i=1}^nA_{ji} \mathbf{e}_j,
      \]
      where $A$ represents $\alpha$. So $A_{ji}=\lambda_i\delta_{ji}\iff \alpha(\mathbf{e}_i)=\lambda_i \mathbf{e}_i$, i.e. $A$ is diagonal $\iff\{\mathbf{e}_i\}$ are eigenvectors.
    \item (ii) $\Leftrightarrow$ (iii): By definition (ii) $\iff\bigoplus E_i = V$ and by lemma $\bigoplus E_i = V \iff \sum \dim E_i=V$.
    \item (iii) $\implies$ (iv): If $V = \sum_i E_i$, then by lemma $V=\bigoplus_i E_i$ and hence $\dim V=\dim \bigoplus_i E_i = \sum_i \dim E_i$.
\item (iv) $\implies$ (iii): Suppose $\dim V = \sum_{i = 1}^k \dim E_i$. Since they correspond to distinct eigenvalues, $\{B_i\}$ are pairwise disjoint and linearly independent (by Lemma). By sizes $\bigcup_{i=1}^k B_i$ is a basis for $V$. So $V=\bigoplus_i E_i$.
  \end{itemize}
\end{proof}

Q: Factorising polynomials by roots
A: \begin{lemma}
  If $\lambda$ is a root of $f \in \F$, ie. $f(\lambda) = 0$, then there is some $g$ such that
  \[
    f(t) = (t - \lambda) g(t).
  \]
\end{lemma}
\begin{proof}
  By polynomial division, let
  \[
    f(t) = (t - \lambda)g(t) + r(t)
  \]
  for some $g(t), r(t) \in \F[t]$ with $\deg r < \deg (t - \lambda) = 1$. So $r=$ constant. Hence
  \[
    0 = f(\lambda) = (\lambda - \lambda)g(\lambda) + r(0) = r.
  \]
 So $r = 0$.
\end{proof}
By induction any non-zero $f \in \F[t]$ can be written as
\[
  f = g(t) \prod_{i = 1}^k (t - \lambda_i)^{a_i},
\]
where $\lambda_1, \cdots, \lambda_k$ are all distinct, $a_i \geq 1$, and $g$ is a polynomial with no roots in $\F$.

Q: Multiplicity of a root
A: Let $f \in \F[t]$ and $\lambda$ a root of $f$. We say $\lambda$ has \emph{multiplicity} $k$ if $(t - \lambda)^k$ is a factor of $f$ but $(t - \lambda)^{k + 1}$ is not, ie.
  \[
    f(t) = (t - \lambda)^k g(t)
  \]
  for some $g(t) \in \F[t]$ with $g(\lambda) \not= 0$.

Q: Polynomials which agree at $n$ points
A: Let $f, g \in \F[t]$ have degree $<n$. If there are $\lambda_1, \cdots, \lambda_n$ distinct such that $f(\lambda_i) = g(\lambda_i)$ for all $i$, then $f = g$.
\begin{proof}
$\deg (f - g)<n$ and $(f - g)(\lambda_i) = 0$ for $i = 1, \cdots, n$. Since it has at least $n \geq \deg(f - g)$ roots, we must have $f - g = 0$. So $f = g$.
\end{proof}

Q: Diagonalisability theorem
A: \begin{thm}
  Suppose $\alpha \in \End(V)$. Then $\alpha$ is diagonalizable $\iff\exists p(t) \in \F[t]\setminus\{0\}$ such that $p(\alpha) = 0$ and $p(t)$ can be factored as a product of \emph{distinct} linear factors.
\end{thm}
\begin{proof}
  Suppose $\alpha$ is diagonalizable. Let $\lambda_1, \cdots, \lambda_k$ be the distinct eigenvalues of $\alpha$. Then $V = \bigoplus_{i = 1}^n E(\lambda_i)$ such that $\forall\mathbf{v}\in V: \exists\mathbf{v}_i$ with $ \mathbf{v} = \sum_{i = 1}^n \mathbf{v}_i$ and $\alpha(\mathbf{v}_i) = \lambda_i \mathbf{v}_i$.
 Now let $p(t) = \prod_{i = 1}^k (t - \lambda_i)$. Then $\forall\mathbf{v}\in V$:
  \[
    p(\alpha) (\mathbf{v}) = \sum_{i = 1}^k p(\alpha) (\mathbf{v}_i) = \sum_{i = 1}^k p(\lambda_i)( \mathbf{v}_i) = \mathbf{0}.
  \]
  Conversely, suppose $p(t) = \prod_{i = 1}^k (t - \lambda_i)$ with $\lambda_1$, $\cdots$, $\lambda_k \in \F$ distinct, $p(\alpha) = 0$ and wlog $p$ is monic.
Define the degree $k-1$ polynomial $q_j$ by
  \[
    q_j(t) = \prod_{i \not= j} \frac{t - \lambda_i}{\lambda_j - \lambda_i}.
  \]
such that $q_j(\lambda_i) = \delta_{ij}$. Next define
  \[
    q(t) = \sum_{i = 1}^k q_j(t)
  \]
 such that $\deg q \leq k - 1$ and $q(\lambda_i) = 1$ for any $i$. Since $q$ and $1$ agree on $k$ points, we must have $q = 1$.
  Let $\pi_j: V\to V$ be given by $\pi_j = q_j(\alpha)$. Then the above says that
  \[
    \sum_{j = 1}^k \pi_j = \iota.
  \]
  Hence $\forall\mathbf{v} \in V:\mathbf{v} = \sum \pi_j \mathbf{v}$ where $\pi_j \mathbf{v} \in E (\lambda_j)$ since
  \begin{align*}
    (\alpha - \lambda_j\iota) \pi_j \mathbf{v} &=\frac{1}{\prod_{i \not= j}(\lambda_j - \lambda_i)} \prod_{i = 1}^k (\alpha - \lambda_\iota) (\mathbf{v})\\
& = \frac{1}{\prod_{i \not= j}(\lambda_j - \lambda_i)} p(\alpha) (\mathbf{v}) \\
&= \mathbf{0}.
  \end{align*}
\end{proof}

Q: Existence of minimal polynomials
A: The \emph{minimal polynomial} of $\alpha \in \End(V)$ is the non-zero monic polynomial $M_\alpha(t)$ of least degree such that $M_\alpha(\alpha) = 0$. If $\dim V < n$, then the minimal polynomial exists and $\deg M_\alpha \leq n^2$.
\begin{proof}
Since $\dim V = n < \infty$, we know $\dim \End(V) = n^2$. So $\iota, \alpha, \alpha^2, \cdots, \alpha^{n^2}$ are linearly dependent. Hence there are some $\lambda_1, \cdots, \lambda_n \in \F$ not all zero such that
\[
  \sum_{i = 0}^{n^2} \lambda_i \alpha^i = 0.
\]
So the minimal polynomial exists and $\deg M_\alpha \leq n^2$.
\end{proof}

Q: Uniqueness of minimal polynomials
A: \begin{lemma}
  Let $\alpha \in \End(V)$, and $p \in \F[t]$. If $p(\alpha) = 0$, then $M_\alpha(t)$ is a factor of $p(t)$ (the converse is trivial). In particular, $M_\alpha$ is unique.
\end{lemma}
\begin{proof}
  We can write $p(t) = q(t) M_\alpha(t) + r(t)$ for some $r$ with $\deg r < \deg M_\alpha$. Hence
  \[
   0= p(\alpha) = q(\alpha) M_\alpha(\alpha) + r(\alpha) = r(\alpha).
  \]
By the minimality of $M_\alpha$, we must have $r = 0$. So $M_\alpha(t) \mid p(t)$.
Now if $M_1$ and $M_2$ are both minimal polynomials for $\alpha$, then $M_1|M_2$ and $M_2|M_1$. But $M_1$ and $M_2$ are monic. So $M_1=M_2$.
\end{proof}

Q: Diagonalizability theorem in terms of minimal polynmials
A: Let $\alpha \in \End(V)$. Then $\alpha$ is diagonalisable if and only if $M_\alpha(t)$ is a product of its distinct linear factors.
\begin{proof}
  $(\Leftarrow)$ Since $M_\alpha(\alpha)=0$ and $M_\alpha$ is a product of its distinct linear factors, by the diagonalisability theorem $\alpha$ is diagonalisable.
  $(\Rightarrow)$ Suppose $\alpha$ is diagonalizable. Then by diagonalisability theorem $\exists p\in \F[t]\setminus\{0\}$ such that $p(\alpha) = 0$ and $p$ is a product of distinct linear factors. Since $M_\alpha$ divides $p$, $M_\alpha$ also has distinct linear factors.
\end{proof}

Q: Simultaneous diagonalisability
A: \begin{thm}
  Let $\alpha, \beta \in \End(V)$ be both diagonalizable. Then $\alpha$ and $\beta$ are simultaneously diagonalizable (ie. there exists a basis with respect to which both are diagonal) if and only if $\alpha\beta = \beta\alpha$.
\end{thm}
\begin{proof}
  $(\Rightarrow)$ If there exists a basis $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$ for $V$ such that $\alpha$ and $\beta$ are represented by diagonal matrices $A$ and $B$, then $AB = BA$ and hence $\alpha\beta=\beta\alpha$.
  $(\Leftarrow)$ Since $\alpha$ is diagonalizable, we can write
  \[
    V = \bigoplus_{i = 1}^k E_i\alpha(\lambda_i)
  \]
  where $\lambda_i$ are the eigenvalues of $V$ and $E_i=E_\alpha (\lambda_i)$. So $\forall\mathbf{v} \in E_i$:
  \[
    \alpha(\beta(\mathbf{v})) = \beta(\alpha(\mathbf{v})) = \beta(\lambda_i \mathbf{v}) = \lambda_i \beta(\mathbf{v}),
  \]
  i.e. $\beta(\mathbf{v})\in E_i$. So $\beta(E_i)\subseteq E_i$ and $\beta|_{E_i}\in\End E_i$.
Since $\beta$ is diagonalisable, $M_\beta(t)$ is a product of its distinct linear factors and hence
  \[
    M_\beta(\beta|_{E_i}) = M_\beta(\beta)|_{E_i} = 0
  \]
  where $M_\beta(\beta|_{E_i})$ is a product of distinct linear factors. So $\beta|_{E_i}$ is diagonalizable, i.e. there exists a basis of eigenvectors $B_i$.
  Then $B_1, \ldots B_k$ are bases for $E_1, \ldots E_k$ and thus are eigenvectors of $\alpha$ and $\beta$.
\end{proof}

Q: Triangulability
A: An endomorphism $\alpha$ is triangulable if and only if $\chi_\alpha(t)$ can be written as a product of linear factors.
\begin{proof}
  Suppose that $\alpha$ is triangulable and represented by
  \[
    \begin{pmatrix}
      \lambda_1 & * & \cdots & *\\
      0 & \lambda_2 & \cdots & *\\
      \vdots & \vdots & \ddots & \vdots\\
      0 & 0 & \cdots & \lambda_n
    \end{pmatrix}.
  \]
  Then
  \[
    \chi_\alpha(t) = \det
    \begin{pmatrix}
      t - \lambda_1 & * & \cdots & *\\
      0 & t - \lambda_2 & \cdots & *\\
      \vdots & \vdots & \ddots & \vdots\\
      0 & 0 & \cdots & t - \lambda_n
    \end{pmatrix} =
    \prod_{i = 1}^n (t - \lambda_i)
  \]
is a product of linear factors.
Conversely, induct on $\dim V$. $\dim V=1$ is trivial. Now let $\alpha \in \End(V)$ with $\dim V = n$ and $\chi_\alpha(t)$ a product of linear factors. Let $\lambda \in \F$ be a root of $\chi_\alpha(t)$. Then $E(\lambda) \not= 0$ and $\alpha(E(\lambda))\subseteq E(\lambda)$. So $\alpha$ induces $\bar{\alpha}\in\End(V/E(\lambda))$ by $\bar{\alpha}(v+E(\lambda))=\alpha(v)+E(\lambda)$. Let $\{v_1,\ldots v_k\}$ be a basis for $E(\lambda)$ and extend to a basis $\{v_1,\ldots v_n\}$ for $V$. Then $\alpha$ is represented by
  \[
    \begin{pmatrix}
      \lambda I_k & *\\
      0 & B
    \end{pmatrix}
  \]
where $B$ represents $\bar{\alpha}$ wrt $\{v_{k + 1}+E(\lambda), \cdots, v_n+E(\lambda)\}$. So $\chi_\alpha(t) = (t - \lambda)^r \chi_B(t)$ and thus $\chi_B(t)$ is also a product of linear factors. By induction hypothesis, there exists a basis $f_{k+1} + E(\lambda), \ldots f_n+E(\lambda)$ wrt which $\bar{\alpha}$ is represented by an upper triangular matrix $C$. Then $\alpha$ is represented by
  \[
    \begin{pmatrix}
      \lambda I_r & \text{stuff}\\
      0 & C
    \end{pmatrix}
  \]
  wrt $\{v_1,\ldots v_k, f_{k+1}, \ldots f_n\}$, which is upper triangular.
\end{proof}

Q: Cayley-Hamilton for an algebraically closed field
A: Let $V$ be a finite dimensional vector space on a subfield of an algebraically closed field $\F$ and $\alpha \in \End(V)$. Then $\chi_\alpha(\alpha) = 0$, ie. $M_\alpha(t) \mid \chi_\alpha(t)$. In particular, $\deg M_\alpha \leq n$.
\begin{proof}
By closedness, we can choose a basis $\{\mathbf{e}_1, \cdots, \mathbf{e}_n\}$ wrt which $\alpha$ is represented by an upper triangular matrix
\[
    A =
    \begin{pmatrix}
      \lambda_1 & * & \cdots & *\\
      0 & \lambda_2 & \cdots & *\\
      \vdots & \vdots & \ddots & \vdots\\
      0 & 0 & \cdots & \lambda_n
    \end{pmatrix}
  \]
such that
 \[
    \alpha(\mathbf{e}_j) = \sum_{k = 1}^j A_{kj} \mathbf{e}_k = \lambda_j\mathbf{e}_j+\sum_{k = 1}^{j-1} A_{kj} \mathbf{e}_k.
  \]
Write $V_i = \bra \mathbf{e}_1, \cdots, \mathbf{e}_i\ket$ such that $\alpha(V_i)\subseteq V_i$ for $0\leq i \leq n$. Then
  \[
    (\alpha - \lambda_j\iota)(\mathbf{e}_j) = \sum_{k = 1}^{j - 1} A_{kj}\mathbf{e}_k \subseteq V_{j - 1}
  \]
  s.t. $(\alpha - \lambda_j\iota)(V_j)\subseteq V_{j-1}$ for all $1\leq j \leq n$. By induction
  \[
    \prod_{i = 1}^n (\alpha - \lambda_i \iota) (V_n) \subseteq V_{0}=0.
  \]
\end{proof}

Q: Cayley-Hamilton theorem for an arbitrary field
A: \begin{thm}
  Let $V$ be a finite-dimensional vector space and $\alpha \in \End(V)$. Then $\chi_\alpha(\alpha) = 0$, ie. $M_\alpha(t) \mid \chi_\alpha(t)$. In particular, $\deg M_\alpha \leq n$.
\end{thm}
\begin{proof}
Let $\alpha$ be represented by $A$, and $B = tI_n - A$. Then
  \[
    B\adj B = \det B I_n = \chi_\alpha(t) I_n
  \]
where
  \[
    \adj B = B_{n - 1}t^{n - 1} + B_{n - 2}t^{n - 2} + \cdots + B_0
  \]
for some $B_i \in \Mat_n (\F)$ and
  \[
    \chi_\alpha(t) = t^n + a_{n - 1}t^{n - 1} + \cdots + a_0.
  \]
for some $a_i\in\F$. Substituting gives
  \[
    (tI_n - A) (B_{n - 1}t^{n - 1} + B_{n - 2} t^{n - 2} + \cdots + B_0) = [t^n + a_{n - 1} t^{n - 1} + \cdots + a_0]I_n.
  \]
Equating coefficients in $t^k$, we have
  \begin{align*}
    -A B_0 &= a_0I_n\\
    B_0 - AB_1 &= a_1I_n\\
    &\vdots\\
    B_{n - 2} - AB_{n - 1} &= a_{n - 1}I_n\\
    B_{n - 1} + 0 &= I_n
  \end{align*}
Multiplying the rows by $A^0, \ldots A^n$:
  \begin{align*}
    -A B_0 &= a_0 I_n\\
    A B_0 - A^2B_1 &= a_1 A\\
    &\;\;\vdots\\
    A^{n - 1}B_{n - 2} - A^n B_{n - 1} &= a_{n - 1} A^{n - 1}\\
    A^{n}B_{n - 1} + 0 &= A^n.
  \end{align*}
  Summing this up the LHS telescopes and we obtain $\chi_\alpha(A) = 0$.
\end{proof}

Q: Roots of the minimal polynomial
A: Let $\alpha \in \End(V), \lambda \in \F$. Then $\lambda$ is a root of $M_\alpha(t)$ $\iff$ $\lambda$ is an eigenvalue of $\alpha$.
\begin{proof}
  $(\Rightarrow)$. By Cayley-Hamilton $M_\alpha |\chi_\alpha$. S $\lambda$ is a root of $M_\alpha(t)\implies$ $\lambda$ is a root of $\chi_\alpha(t)$ $\implies$ $\lambda$ is an eigenvalue of $\alpha$.
$(\Rightarrow)$ (alternative). If $\lambda$ is a root of $M_\alpha(t)$, then $M_\alpha(t) = (t - \lambda) g(t)$ for some $g \in \F[t]$ with $\deg g < \deg M_\alpha$. By minimality of $M_\alpha$, $g(\alpha) \not= 0$ and thus $\exists\mathbf{v}\in V$ such that $g(\alpha)(\mathbf{v}) \not=0$. Then
      \[
        (\alpha - \lambda\iota)g(\alpha)(\mathbf{v}) = M_\alpha(\alpha)\mathbf{v} = 0.
      \]
So $\lambda$ is an eigenvalue.
$(\Leftarrow)$. Let $\lambda$ be an eigenvalue and $\mathbf{v}$ a corresponding eigenvector.
Then by definition of $M_\alpha$
      \[
       0= 0(\mathbf{v})= M_\alpha(\alpha)\mathbf{v} =M_\alpha(\lambda)\mathbf{v}.
      \]
      Since $\mathbf{v}\neq 0$, we must have $M_\alpha(\lambda) =0$.
\end{proof}

Q: Comparison of multiplicities of eigenvalues
A: Let $\alpha \in \End (V)$ and $\lambda$ an eigenvalue of $\alpha$. Then
  \begin{enumerate}
    \item The \emph{algebraic multiplicity} of $\lambda$, written $a_\lambda$, is the multiplicity of $\lambda$ as a root of $\chi_\alpha(t)$.
    \item The \emph{geometric multiplicity} of $\lambda$, written $g_\lambda$, is $\dim E_\alpha(\lambda)$.
    \item $c_\lambda$ is the multiplicity of $\lambda$ as a root of $m_\alpha(t)$.
  \end{enumerate}
\begin{lemma}
  If $\lambda$ is an eigenvalue of $\alpha$, then
  \begin{enumerate}
    \item $1 \leq g_\lambda \leq a_\lambda$
    \item $1 \leq c_\lambda \leq a_\lambda$.
  \end{enumerate}
\end{lemma}
\begin{proof}
  \begin{enumerate}
    \item If $\lambda$ is an eigenvalue, then $E(\lambda) \neq 0$. So $g_\lambda = \dim E(\lambda) \geq 1$. If $\mathbf{v}_1, \cdots, \mathbf{v}_{g_\lambda}$ is a basis for $E(\lambda)$, then we can extend it to a basis for $V$, and then $\alpha$ is represented by
      \[
        \begin{pmatrix}
          \lambda I_{g_\lambda} & *\\
          0 & B
        \end{pmatrix}
      \]
      So $\chi_\alpha(t) = (t - \lambda)^{g_\lambda} \chi_B(t)$. Hence $a_\lambda \geq g_\lambda$.
    \item Immediately $M_\alpha(\lambda) = 0\implies 1 \leq c_\lambda$ and $M_\alpha(t) \mid \chi_\alpha(t) \implies c_\lambda \leq a_\lambda$.
  \end{enumerate}
\end{proof}

Q: Diagonalisability by multiplicity
A: Suppose $\F = \C$ and $\alpha \in \End(V)$. Then TFAE
  \begin{enumerate}
    \item $\alpha$ is diagonalizable.
    \item $g_\lambda = a_\lambda$ for all eigenvalues of $\alpha$.
    \item $c_\lambda = 1$ for all eigenvalues of $\alpha$.
  \end{enumerate}
\begin{proof}
  \begin{itemize}
    \item (i) $\Leftrightarrow$ (ii): $\alpha$ is diagonalizable iff $\dim V = \sum \dim E (\lambda_i)$. But
      \[
        \sum \dim E (\lambda_i) = \sum g_{\lambda_i} \leq \sum a_{\lambda_i} = \deg \chi_\alpha = \dim V.
     \]
     So $\alpha$ is diagonalizable iff $\sum g_{\lambda_i} = \sum a_{\lambda_i}$. Since each $g_{\lambda_i}$ is at most $a_{\lambda_i}$, this holds iff all are individually equal.
   \item (i) $\Leftrightarrow$ (iii): $\alpha$ is diagonalizable iff $M_\alpha(t)$ is a product of distinct linear factors if and only if $c_\lambda = 1$ for all eigenvalues $\lambda$.
  \end{itemize}
\end{proof}

Q: Jordan normal form
A: We say $A \in \Mat_N(\C)$ is in \emph{Jordan normal form} if it is a block diagonal of the form
  \[
    \begin{pmatrix}
      J_{n_1}(\lambda_1) & & & 0\\
      & J_{n_2}(\lambda_2)\\
      & & \ddots\\\
      0 & & & J_{n_k} (\lambda_k)
    \end{pmatrix}
  \]
  where $k \geq 1$, $n_1, \cdots, n_k \in \N$ such that $n = \sum n_i$, $\lambda_1, \cdots, \lambda_k$ not necessarily distinct, and
  \[
    J_m (\lambda) =
    \begin{pmatrix}
      \lambda & 1 & \cdots & 0\\
      0 & \lambda & \ddots & \vdots\\
      \vdots & \vdots & \ddots & 1\\
      0 & 0 & \cdots & \lambda
    \end{pmatrix}
  \]
 is a Jordan block. Note that $J_m(\lambda) = \lambda I_m + J_m(0)$.
\begin{thm}
  Every matrix $A \in \Mat_n(\C)$ is similar to a matrix in Jordan normal form. Moreover, this Jordan normal form matrix is unique up to permutation of the blocks.
\end{thm}
Note that if two matrices in Jordan normal form differ only by a rearrangement of blocks, then they are similar, by permuting the basis.

Q: Classes of $2\times 2$ matrices
A: Every $2\times 2$ matrix in Jordan normal form is one of the three types:
  \begin{center}
    \begin{tabular}{cccc}
      \toprule
      Jordan normal form & $\chi_A$ & $M_A$\\
      \midrule
      $\begin{pmatrix} \lambda & 0\\ 0 & \lambda \end{pmatrix}$ & $(t - \lambda)^2$ & $(t - \lambda)$\\\addlinespace
      $\begin{pmatrix} \lambda & 0\\ 0 & \mu \end{pmatrix}$ & $(t - \lambda)(t - \mu)$ & $(t - \lambda)(t - \mu)$\\\addlinespace
      $\begin{pmatrix} \lambda & 1\\ 0 & \lambda \end{pmatrix}$ & $(t - \lambda)^2$ & $(t - \lambda)^2$\\
      \bottomrule
    \end{tabular}
  \end{center}
  with $\lambda, \mu \in \C$ distinct. We see that $M_A$ determines the Jordan normal form of $A$, but $\chi_A$ does not.

Q: Classes of $3\times 3$ matrices
A: Every $3\times 3$ matrix in Jordan normal form is one of the six types. Here $\lambda_1, \lambda_2$ and $\lambda_3$ are distinct complex numbers.
  \begin{center}
    \begin{tabular}{ccccccc}
      \toprule
      Jordan normal form & $\chi_A$ & $M_A$\\
      \midrule
      $\begin{pmatrix} \lambda_1 & 0 & 0\\ 0 & \lambda_2 & 0\\ 0 & 0 & \lambda_3 \end{pmatrix}$ & $(t - \lambda_1)(t - \lambda_2)(t- \lambda_3)$ & $(t - \lambda_1)(t - \lambda_2)(t- \lambda_3)$\\\addlinespace
      $\begin{pmatrix} \lambda_1 & 0 & 0\\ 0 & \lambda_1 & 0\\ 0 & 0 & \lambda_2 \end{pmatrix}$ & $(t - \lambda_1)^2 (t - \lambda_2)$ & $(t - \lambda_1) (t - \lambda_2)$\\\addlinespace
      $\begin{pmatrix} \lambda_1 & 1 & 0\\ 0 & \lambda_1 & 0\\ 0 & 0 & \lambda_2 \end{pmatrix}$ & $(t - \lambda_1)^2 (t - \lambda_2)$ & $(t - \lambda_1)^2 (t - \lambda_2)$\\\addlinespace
      $\begin{pmatrix} \lambda_1 & 0 & 0\\ 0 & \lambda_1 & 0\\ 0 & 0 & \lambda_1 \end{pmatrix}$ & $(t - \lambda_1)^3$ & $(t - \lambda_1)$\\\addlinespace
      $\begin{pmatrix} \lambda_1 & 1 & 0\\ 0 & \lambda_1 & 0\\ 0 & 0 & \lambda_1 \end{pmatrix}$ & $(t - \lambda_1)^3$ & $(t - \lambda_1)^2$\\\addlinespace
      $\begin{pmatrix} \lambda_1 & 1 & 0\\ 0 & \lambda_1 & 1\\ 0 & 0 & \lambda_1 \end{pmatrix}$ & $(t - \lambda_1)^3$ & $(t - \lambda_1)^3$\\
      \bottomrule
    \end{tabular}
  \end{center}
  Notice that $\chi_A$ and $M_A$ together determine the Jordan normal form of a $3\times 3$ complex matrix.

Q: Multiplicities and polynomials of Jordan blocks
A: Recall the definition
\[
  J_n(\lambda) =
  \begin{pmatrix}
    \lambda & 1 & \cdots & 0\\
    0 & \lambda & \ddots & \vdots\\
    \vdots & \vdots & \ddots & 1\\
    0 & 0 & \cdots & \lambda
  \end{pmatrix} = \lambda I_n + J_n(0).
\]
If $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$ is the standard basis for $\C^n$, we have
\[
  J_n(0)(\mathbf{e}_1) = 0, \quad J_n(0) (\mathbf{e}_i) = \mathbf{e}_{i - 1}\text{ for } 2\leq i \leq n.
\]
Thus we know
\[
  J_n(0)^k(\mathbf{e}_i) =
  \begin{cases}
    0 & i \leq k\\
    \mathbf{e}_{i - k} & k < \leq n
  \end{cases}
\]
In other words, for $k < n$, we have
\[
  (J_n(\lambda) - \lambda I)^k = J_n(0)^k =
  \begin{pmatrix}
    0 & I_{n - k}\\
    0 & 0
  \end{pmatrix}.
\]
If $k \geq n$, then we have $(J_n(\lambda) - \lambda I)^k = 0$.
Hence we can summarize this as
\[
  n((J_m(\lambda) - \lambda I_m)^r) = \min\{r, m\}.
\]
Note that if $A = J_n(\lambda)$, then $\chi_A(t) = M_A(t) = (t - \lambda)^n$. So $\lambda$ is the only eigenvalue of $A$. So $a_\lambda = c_\lambda = n$. We also know that $n(A - \lambda I) = n - r(A - \lambda I) = 1$. So $g_\lambda = 1$.

Q: Polynomials and multiplicities of Jordan Normal Form
A: Let $A$ be the block diagonal matrix
\[
  A =
  \begin{pmatrix}
    A_1\\
    & A_2\\
    & & \ddots\\
    & & & A_k
  \end{pmatrix},
\]
where $A_i=J_{n_i}(\lambda_i)$. Then
\[
  \chi_A(t) = \prod_{i = 1}^k \chi_{A_i}(k).
\]
Moreover, if $p \in \F[t]$, then
\[
 p(A) =
  \begin{pmatrix}
    p(A_1)\\
    & p(A_2)\\
    & & \ddots\\
    & & & p(A_k)
  \end{pmatrix}.
\]
Hence
\[
  M_A(t) = \lcm (M_{A_1}(t), \cdots, M_{A_k} (t))
\]
and
\[
  n(p(A)) = \sum_{i = 1}^k n(p(A_i)).
\]
The multiplicities correspond to
\begin{itemize}
  \item $g_\lambda$ is the number of Jordan blocks in $A$ with eigenvalue $\lambda$.
  \item $a_\lambda$ is the sum of sizes of the Jordan blocks of $A$ with eigenvalue $\lambda$.
  \item $c_\lambda$ is the size of the largest Jordan block with eigenvalue $\lambda$.
\end{itemize}

Q: Uniqueness of Jordan Normal Form
A: \begin{thm}
  Let $\alpha \in \End(V)$, and $A$ represent $\alpha$ in JNF. Then the number of Jordan blocks $J_n(\lambda)$ in $A$ with $1\leq r\leq n$ is
  \[
    n((\alpha - \lambda\iota)^r) - n((\alpha - \lambda\iota)^{r - 1}).
  \]
\end{thm}
\begin{proof}
  We work blockwise for
  \[
    A =
    \begin{pmatrix}
      J_{n_1}(\lambda_1)\\
      & J_{n_2}(\lambda_2)\\
      & & \ddots\\\
      & & & J_{n_k} (\lambda_k)
    \end{pmatrix}.
  \]
  We know that
  \[
    n((J_m(\lambda) - \lambda I_m)^r) = \min\{r, m\}.
  \]
Also for $\mu \not= \lambda$
  \[
    n((J_m(\mu) - \lambda I_m)^r) = n(J_m(\mu - \lambda)^r) = 0.
  \]
 Adding up each block, for $r \geq 1$, we have
  \begin{align*}
    n((\alpha - \lambda \iota)^r) - n((\alpha - \lambda \iota)^{r - 1}) &= n((A - \lambda I)^r) - n((A - \lambda I)^{r - 1})\\
    &= \sum_{i = 1, \lambda_i = \lambda}^k \min\{r, n_i\} - \min\{r - 1, n_i\}.
  \end{align*}
  Note that if $n_i \geq r$, then
  \[
    \min \{r, n_i\} - \min\{r - 1, n_i\} = r - (r - 1) = 1,
  \]
  while if $n_i < r$, then
  \[
    \min\{r, n_i\} - \min\{r - 1,n_i\} = n_i - n_i = 0.
  \]
  Hence it follows that this sum is exactly the number of Jordan blocks $J_{n_i}(\lambda_i)$ such that $\lambda_i = \lambda$ and $n_i \geq r$.
\end{proof}

Q: Generalized eigenspace decomposition
A: \begin{thm}
  Let $V$ be a finite-dimensional vector space over $\C$ such that $\alpha \in \End(V)$. Suppose that
  \[
    M_\alpha(t) = \prod_{i = 1}^k (t - \lambda_i)^{c_i},
  \]
  with $\lambda_1, \cdots, \lambda_k \in \C$ distinct. Then
  \[
    V = V_1 \oplus \cdots \oplus V_k,
  \]
  where $V_i = \ker((\alpha - \lambda_i \iota)^{c_i})$ is the \emph{generalized eigenspace}.
\end{thm}
\begin{proof}
  Let
  \[
    p_j(t) = \prod_{i \not= j} (t - \lambda_i)^{c_i}.
  \]
  Then $p_1, \cdots, p_k$ are coprime. Thus by Euclid's algorithm, there exists $q_1, \cdots, q_k \in \C[t]$ such that
  \[
    \sum p_i q_i = 1.
  \]
  We now define the endomorphisms
  \[
    \pi_j = q_j(\alpha) p_j(\alpha)
  \]
  for $j = 1, \cdots, k$ s.t. $\sum \pi_j = \iota$.
\textbf{Sum}. Since $M_\alpha(\alpha) = 0$ and $M_\alpha(t) = (t - \lambda_j \iota)^{c_j} p_j(t)$, we obtain
  \[
    (\alpha - \lambda_j \iota)^{c_j} \pi_j =q_j(\alpha)M_\alpha(\alpha)= 0.
  \]
  So $\im \pi_j \subseteq V_j$. Hence for any $\mathbf{v}\in V$:
  \[
    \mathbf{v} = \iota (\mathbf{v}) = \sum_{j = 1}^k \pi_j (\mathbf{v}) \in \sum V_j.
  \]
\textbf{Direct}. Note that $\pi_i \pi_j = 0$  for $i\neq j$ since $M_\alpha(\alpha)$ is a factor. So $\iota_{V_j}=\pi_j|_{V_j}$ and $\pi$ is a projection such that $\forall \mathbf{v}_i\in V_i: \mathbf{v} = \sum \mathbf{v}_i \implies \mathbf{v}_i=\pi_i(\mathbf{v})$.
\end{proof}

Q: Nilpotent endomorphisms
A: We say $\alpha \in \End(V)$ is nilpotent if there is some $r$ such that $\alpha^r = 0$.
For any $\alpha\in \End(V)$, by considering $V$ as a sum of generalized eigenspaces, we can reduce the existence part of the Jordan normal form theorem to the case $M_\alpha(t) = (t - \lambda)^c$. Further by replacing $\alpha$ by $\alpha - \lambda \iota$, we can reduce this to the case where $0$ is the only eigenvalue. Over $\C$, this is equivalent to $M_\alpha(t)=t^r$ for some $r$, i.e. $\alpha$ is nilpotent.

Q: Symmetric bilinear forms vs symmetric matrices
A: \begin{lemma}
  Let $V$ be a finite-dimensional vector space over $\F$, and $\phi: V\times V \to \F$ a symmetric bilinear form. Let $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$ be a basis for $V$ and $M_{ij} = \phi(\mathbf{e}_i, \mathbf{e}_j)$. Then $\phi$ is symmetric if and only if $M$ is symmetric.
\end{lemma}
\begin{proof}
  If $\phi$ is symmetric, then
  \[
    M_{ij} = \phi(\mathbf{e}_i, \mathbf{e}_j) = \phi(\mathbf{e}_j, \mathbf{e}_i) = M_{ji}.
  \]
  So $M^T = M$. So $M$ is symmetric.
 Conversely, if $M$ is symmetric, then
  \begin{align*}
    \phi(\mathbf{x}, \mathbf{y}) &= \phi\left(\sum x_i \mathbf{e}_i, \sum y_j \mathbf{e}_j\right)\\
    &= \sum_{i, j} x_i M_{ij} y_j\\
    &= \sum_{i, j}^n y_j M_{ji} x_i\\
    &= \phi(\mathbf{y}, \mathbf{x}).
  \end{align*}
\end{proof}

Q: Congruent matrices
A: Two square matrices $A, B$ are \emph{congruent} if there exists some invertible $P$ such that
  \[
    B = P^T AP.
  \]
This is an orbit of $\GL_n$ acting on $\Mat_n$ and so is an equivalence relation. Two matrices are congruent if and only if represent the same bilinear form with respect to different bases.

Q: Quadratic form
A: A \emph{function} $q: V \to \F$ is a \emph{quadratic form} if there exists some bilinear form $\phi$ such that
  \[
    q(\mathbf{v}) = \phi(\mathbf{v}, \mathbf{v})
  \]
  for all $\mathbf{v} \in V$.

Q: Polarisation identity for symmetric bilinear forms
A: \begin{prop}
  Suppose that $\Char \F \not= 2$. If $q: V\to \F$ is a quadratic form, then there exists a \emph{unique} symmetric bilinear form $\phi: V \times V\to \F$ such that
  \[
    q(\mathbf{v}) = \phi(\mathbf{v}, \mathbf{v}).
  \]
\end{prop}
\begin{proof}
\textbf{Existence}.  Let $\psi: V \times V\to \F$ be a bilinear form such that $\psi(\mathbf{v}, \mathbf{v}) = q(\mathbf{v})$. Then we can define the symmetric bilinear form $\phi: V \times V\to \F$ by
  \[
    \phi(\mathbf{v}, \mathbf{w}) = \frac{1}{2}(\psi(\mathbf{v}, \mathbf{w}) + \psi(\mathbf{w}, \mathbf{v}))
  \]
  for all $\mathbf{v}, \mathbf{w} \in \F$.
\textbf{Uniqueness}. If $\phi$ is such a symmetric bilinear form, then
  \begin{align*}
    q(\mathbf{v} + \mathbf{w}) &= \phi(\mathbf{v} + \mathbf{w}, \mathbf{v} + \mathbf{w}) \\
&= \phi(\mathbf{v} + \mathbf{w}, \mathbf{v} + \mathbf{w}) \\
    &= \phi(\mathbf{v}, \mathbf{v}) + \phi(\mathbf{v}, \mathbf{w}) + \phi(\mathbf{w}, \mathbf{v}) + \phi(\mathbf{w}, \mathbf{w})\\
    &= q(\mathbf{v}) + 2\phi(\mathbf{v}, \mathbf{w}) + q(\mathbf{w}).
  \end{align*}
  So $\phi$ is uniquely determined by $q$ as
  \[
    \phi(\mathbf{v}, \mathbf{w}) = \frac{1}{2}(q(\mathbf{v} + \mathbf{w}) - q(\mathbf{v}) - q(\mathbf{w})).
  \]
\end{proof}

Q: Diagonalisability of Hermitian forms
A: \begin{thm}
  Let $V$ be a finite-dimensional vector space over $\F$, and $\phi: V\times V \to \F$ a Hermitian (real symmetric) bilinear form. Then there exists a basis $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$ for $V$ such that $\phi$ is represented by a diagonal matrix with respect to this basis.
\end{thm}
\begin{proof}
  We induct over $n = \dim V$. The cases $n = 0$ and $n = 1$ are trivial, since all matrices in $\Mat_1(\F)$ are diagonal.
Assume true for dimension less than $n$. If $\phi=0$, then this is diagonal wrt any basis. Otherwise, by the polarisation identity, $\exists\mathbf{e}_1 \in V$ such that $\phi(\mathbf{e}_1, \mathbf{e}_1) \neq 0$. Let
  \[
    U = \ker \phi(\mathbf{e}_1, \ph) = \{\mathbf{u} \in V: \phi(\mathbf{e}_1, \mathbf{u}) = 0\}.
  \]
  Since $\phi(\mathbf{e}_1, \ph) \in V^* \setminus \{0\}$, we know that $\dim U = n - 1$ by the rank-nullity theorem. As also $\mathbf{e}_1\not\in U$, we have that $V=\bra \mathbf{e}_1 \ket \bigoplus U$.
 Now consider $\phi|_{U\times U}: U\times U \to \F$, a Hermitian (real symmetric) bilinear form. By the induction hypothesis, we can find a basis $\mathbf{e}_2, \cdots, \mathbf{e}_n$ for $U$ such that $\phi|_{U\times U}$ is represented by a diagonal matrix with respect to this basis.
By construction, $\phi(\mathbf{e}_i, \mathbf{e}_j) = 0$ for all $1 \leq i \not= j \leq n$ and $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$ is a basis for $V$.
\end{proof}

Q: Congruence classes of symmetric complex matrices
A: \begin{thm}
  Let $\phi$ be a symmetric bilinear form over a complex vector space $V$. Then there exists a basis $(\mathbf{v}_1, \cdots, \mathbf{v}_m)$ for $V$ such that $\phi$ is represented by
  \[
    \begin{pmatrix}
      I_r & 0\\
      0 & 0
    \end{pmatrix}
  \]
  with respect to this basis, where $r = r(\phi)$. Equivalently for the corresponding quadratic form $q$, we have
\[
  q\left(\sum_{i = 1}^n a_i \mathbf{v}_i\right) = \sum_{i = 1}^r a_i^2.
\]
\end{thm}
\begin{proof}
By diagonalisability, there exists a basis $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$ such that $\phi(\mathbf{e}_i, \mathbf{e}_j) = \lambda_i \delta_{ij}$ for some $\lambda_{i}$. By reordering the $\mathbf{e}_i$, we can assume that $\lambda_1, \cdots, \lambda_r \not= 0$ and $\lambda_{r + 1},\cdots, \lambda_n = 0$.
  For each $1 \leq i \leq r$, there exists some $\mu_i\neq 0$ such that $\mu_i^2 = \lambda_i$. For $r + 1 \leq i \leq n$, we let $\mu_i = 1$. Then define
  \[
    \mathbf{v}_i = \frac{\mathbf{e}_i}{\mu_i}
  \]
such that
  \[
    \phi(\mathbf{v}_i, \mathbf{v}_j) = \frac{1}{\mu_i \mu_j} \phi(\mathbf{e}_i, \mathbf{e}_j) =
    \begin{cases}
      0 & i\not= j\text{ or }i = j > r\\
      1 & i = j < r.
    \end{cases}
  \]
\end{proof}
\begin{cor}
  Every symmetric $A \in \Mat_n(\C)$ is congruent to a unqiue matrix of the form
  \[
    \begin{pmatrix}
      I_r & 0\\
      0 & 0
    \end{pmatrix}.
  \]
\end{cor}
\begin{proof}
Follows from basis indepence of $r(\phi)$.
\end{proof}

Q: Congruence classes of Hermitian matrices
A: \begin{thm}
  Let $\phi$ be a Hermitian (real symmetric bilinear) form of a finite-dimensional vector space. Then there exists a basis $(\mathbf{v}_1, \cdots, \mathbf{v}_n)$ for $V$ such that $\phi$ is represented
  \[
    \begin{pmatrix}
      I_k\\
      & -I_\ell\\
      & & 0
    \end{pmatrix},
  \]
  with $k + \ell = r(\phi)$, $k, \ell \geq 0$. Equivalently, the corresponding quadratic form is given by
  \[
    q\left(\sum_{i = 1}^n a_i \mathbf{v}_i\right) = \sum_{i = 1}^k a_i^2 - \sum_{i = k + 1}^{k + \ell} a_i^2.
  \]
\end{thm}
\begin{proof}
 By diagonalisability, there exists a basis $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$ such that $\phi(\mathbf{e}_i, \mathbf{e}_j) = \lambda_i \delta_{ij}$ for some $\lambda_1, \cdots, \lambda_n \in \R$. By reordering, we may assume
  \[
    \begin{cases}
      \lambda_i > 0 & 1 \leq i \leq k\\
      \lambda_i < 0 & p + 1 \leq i \leq r\\
      \lambda_i = 0 & i > r.
    \end{cases}
  \]
Now define
  \[
    \mu_i =
    \begin{cases}
      \sqrt{\lambda_i} & 1 \leq i \leq k\\
      \sqrt{-\lambda_i} & k + 1 \leq i \leq r\\
      1 & i > r
    \end{cases}
  \]
and
  \[
    \mathbf{v}_i = \frac{1}{\mu_i}\mathbf{e}_i.
  \]
 Then wrt $\{\mathbf{v}_i\}$, $\phi$ is represented by
  \[
    \begin{pmatrix}
      I_k\\
      & -I_\ell\\
      & & 0
    \end{pmatrix},
  \]
\end{proof}

Q: Sylvester's law of inertia
A: \begin{thm}
Let $\phi$ be a Hermitian (real symmetric bilinear) form on a finite-dimensional real vector space $V$. Then there $\exists !$ $p, q \geq 0$ such that $\phi$ is represented by
  \[
    \begin{pmatrix}
      I_p & 0 & 0\\
      0 & -I_q & 0\\
      0 & 0 & 0,
    \end{pmatrix}
  \]
wrt some basis $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$.
\end{thm}
\begin{proof}
  Since $p + q = r(\phi)$, it's ets $p$ is unique. So it's ets $p=\max \{|P| : \phi|_{P\times P} \text{ is positive definite}\}$.
\textbf{Existence}. Take $P=\bra \mathbf{e}_1, \cdots, \mathbf{e}_p\ket$.
\textbf{Maximality}. Suppose $P$ is any subspace of $V$ such that $\phi|_{P \times P}$ is positive definite. Let $Q = \bra \mathbf{e}_{p + 1}, \cdots, \mathbf{e}_n\ket$. Then $\phi|_{Q\times Q}$ is represented by
  \[
    \begin{pmatrix}
      -I_q& 0\\
      0 & 0
    \end{pmatrix}.
  \]
 Now $\forall \mathbf{v} \in P\cap Q \setminus \{0\}$:
\begin{align*}
\mathbf{v}\in P\setminus \{0\}&\implies \phi(\mathbf{v}, \mathbf{v}) > 0 \\
\mathbf{v}\in Q&\implies \phi(\mathbf{v}, \mathbf{v}) \leq 0.
\end{align*}
So $P\cap Q = 0$. Hence
  \[
    \dim V \geq \dim (P + Q) = \dim P + \dim Q = \dim P + (n - p).
  \]
  Rearranging gives
  \[
    \dim P \leq p.
\]
\end{proof}
\begin{cor}
  Every Hermitian (real symmetric) matrix is congruent to precisely one matrix of the form
  \[
    \begin{pmatrix}
      I_p & 0 & 0\\
      0 & -I_q & 0\\
      0 & 0 & 0
    \end{pmatrix}.
  \]
\end{cor}

Q: Signature
A: The \emph{signature} of a real symmetric bilinear form $\phi$ is the number $p - q$, where $\phi$ is congruent to
\[
    \begin{pmatrix}
      I_p & 0 & 0\\
      0 & -I_q & 0\\
      0 & 0 & 0
    \end{pmatrix}.
  \]

Q: Sesquilinear form
A: Let $V, W$ be complex vector spaces. Then a \emph{sesquilinear form} is a function $\phi: V \times W \to \C$ such that
  \begin{enumerate}
    \item $\phi(\lambda \mathbf{v}_1 + \mu \mathbf{v}_2, \mathbf{w}) = \bar{\lambda} \phi(\mathbf{v}_1, \mathbf{w}) + \bar{\mu}\phi(\mathbf{v}_2, \mathbf{w})$.
    \item $\phi(\mathbf{v}, \lambda \mathbf{w}_1 + \mu \mathbf{w}_2) = \lambda \phi(\mathbf{v}, \mathbf{w}_1) + \mu \phi(\mathbf{v} \mathbf{w}_2)$.
  \end{enumerate}
  for all $\mathbf{v}, \mathbf{v}_1, \mathbf{v}_2 \in V$, $\mathbf{w}, \mathbf{w}_1, \mathbf{w}_2 \in W$ and $\lambda, \mu \in \C$.

Q: Representation of sesquilinear form
A: Let $V, W$ be finite-dimensional complex vector spaces with bases $(\mathbf{v}_1, \cdots, \mathbf{v}_n)$ and $(\mathbf{w}_1, \cdots, \mathbf{w}_m)$ respectively, and $\phi: V \times W \to \C$ be a sesquilinear form. Then the matrix representing $\phi$ wrt these bases is
  \[
    A_{ij} = \phi(\mathbf{v}_i, \mathbf{w}_j).
  \]
  for $1 \leq i \leq n, 1 \leq j \leq m$.
Then for $\mathbf{v} = \sum \lambda_i \mathbf{v}_i$ and $\mathbf{w} = \sum \mu_j \mathbf{w}_j$, we have
\[
  \phi(\mathbf{v}, \mathbf{w}) = \sum_{i, j} \overline{\lambda}_i \mu_j \phi(\mathbf{v}_i, \mathbf{w}_j) = \lambda^\dagger A \mu.
\]

Q: Hermitian sesquilinear form
A: A sesquilinear form on $V\times V$ is \emph{Hermitian} if
  \[
    \phi(\mathbf{v}, \mathbf{w}) = \overline{\phi(\mathbf{w}, \mathbf{v})}.
  \]
Observe $\phi(\mathbf{v}, \mathbf{v}) = \overline{\phi(\mathbf{v}, \mathbf{v})} \in \R$ for any $\mathbf{v} \in V$. So it makes sense to talk about positive (semi-)definite and negative (semi-)definite Hermitian forms.

Q: Hermitian matrices vs sesquilinear forms
A: \begin{lemma}
  Let $\phi: V \times V\to \C$ be a sesquilinear form on a finite-dimensional vector space over $\C$, and $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$ a basis for $V$. Then $\phi$ is Hermitian if and only if the matrix $A$ representing $\phi$ is Hermitian.
\end{lemma}
\begin{proof}
  If $\phi$ is Hermitian, then
  \[
    A_{ij} = \phi(\mathbf{e}_i, \mathbf{e}_j) = \overline{\phi(\mathbf{e}_j, \mathbf{e}_i)} = A^{\dagger}_{ij}.
  \]
  If $A$ is Hermitian, then
  \begin{align*}
    \phi\left(\mathbf{x},\mathbf{y}\right) &= \mathbf{x}^\dagger A \mathbf{y} \\
&= \left[(\mathbf{x}^\dagger A \mathbf{y})^\dagger\right]^* \\
&= \overline{\mathbf{y}^\dagger A^\dagger \mathbf{x}} \\
&= \overline{\mathbf{y}^\dagger A \mathbf{x}} \\
&= \overline{\phi\left(\mathbf{y}, \mathbf{x}\right)}.
  \end{align*}
\end{proof}

Q: Change of basis
A: \begin{prop}
  Let $\phi$ be a Hermitian form on a finite dimensional vector space $V$, $(\mathbf{e}_1, \cdots, \mathbf{e}_n)$ and $(\mathbf{f}_1, \cdots, \mathbf{f}_n)$ are bases for $V$ such that
  \[
    \mathbf{f}_i = \sum_{k = 1}^n P_{ki} \mathbf{e}_k.
  \]
Let $A, B$ represent $\phi$ with respect to $(\mathbf{e}_1, \ldots, \mathbf{e}_n)$ and $(\mathbf{f}_1, \cdots, \mathbf{f}_n)$ respectively. Then
  \[
    B = P^\dagger AP.
  \]
\end{prop}
\begin{proof}
  We expand
  \begin{align*}
    B_{ij} &= \phi(\mathbf{f}_i, \mathbf{f}_j) \\
    &= \phi\left(\sum P_{ki} \mathbf{e}_k, \sum P_{\ell j} \mathbf{e}_\ell\right)\\
    &= \sum_{k, \ell = 1}^n \bar{P}_{ki} P_{\ell j} A_{k\ell}\\
    &= (P^\dagger AP)_{ij}.
  \end{align*}
\end{proof}

Q: Polarisation identity for Hermitian forms
A: \begin{lemma}
  If $q: V\to \F$ is a quadratic form, then there exists a \emph{unique} Hermitian form $\phi: V \times V\to \F$ such that
  \[
    q(\mathbf{v}) = \phi(\mathbf{v}, \mathbf{v}).
  \]
\end{lemma}
\begin{proof}
For any $\mathbf{x},\mathbf{y}\in V$
  \begin{align*}
    q(\mathbf{x} + \mathbf{y}) &= \phi(\mathbf{x}, \mathbf{x}) + \phi(\mathbf{x}, \mathbf{y}) + \phi(\mathbf{y}, \mathbf{x}) + \phi(\mathbf{y}, \mathbf{y})\\
   -q(\mathbf{x} - \mathbf{y}) &= -\phi(\mathbf{x}, \mathbf{x}) + \phi(\mathbf{x}, \mathbf{y}) + \phi(\mathbf{y}, \mathbf{x}) - \phi(\mathbf{y}, \mathbf{y})\\
   iq(\mathbf{x} -i\mathbf{y}) &= i\phi(\mathbf{x}, \mathbf{x}) + \phi(\mathbf{x}, \mathbf{y}) - \phi(\mathbf{y}, \mathbf{x}) +i\phi(\mathbf{y}, \mathbf{y})\\
  -iq(\mathbf{x} +i\mathbf{y}) &=-i\phi(\mathbf{x}, \mathbf{x}) + \phi(\mathbf{x}, \mathbf{y}) - \phi(\mathbf{y}, \mathbf{x}) -i\phi(\mathbf{y}, \mathbf{y})
  \end{align*}
  So we determine uniquely a Hermitian form
  \[
    \phi(\mathbf{x}, \mathbf{y}) = \frac{1}{4}(q(\mathbf{x} + \mathbf{y}) - q(\mathbf{x} - \mathbf{y}) + iq(\mathbf{x} - i\mathbf{y}) - i q(\mathbf{x} + i\mathbf{y})).
  \]
\end{proof}