An Unintuitive Guide to Linear Algebra

A relational structure $(S, \set{R_\alpha}_{\alpha \in A})$ is a set $S$ along with subsets $R_\alpha \subseteq S^{n_\alpha}$, where $n_\alpha \in \N$. A homomorphism of relational structures $f : (S, \set{R_\alpha}_{\alpha \in A}) \to (S', \set{R'_\alpha}_{\alpha \in A})$ is a function $f : S \to S'$ such that for all $\alpha \in A$, if $(x_1, \dots, x_{n_\alpha}) \in R_\alpha$ then $(f(x_1), \dots, f(x_{n_\alpha})) \in R'_\alpha$.

For a relation $R \subseteq S^n$ and subset $S' \subseteq S$, we denote $R \cap S'^n$ by $R\rvert_{S'}$, called the restriction of $R$ to $S'$.

A monoid $(M, \set{E, T})$ is a relational structure where

1. $E \subseteq M$;
2. $T \subseteq M \times M \times M$

satisfying:

1. there exists a unique $1_M \in M$ such that $1_M \in E$;
2. for all $x \in M$, $(1_M, x, x) \in T$ and $(x, 1_M, x) \in T$;
3. for all $x, y \in M$, there exists a unique $z \in M$ such that $(x, y, z) \in T$;
4. for all $x, y, z, u, v, w \in M$, if $(x, y, u) \in T$, $(u, z, w) \in T$, $(y, z, v) \in T$ then $(x, v, w) \in T$.

A group $(G, \set{E, T})$ is a monoid further satisfying:

• for all $x \in G$, there exists $y \in G$ such that $(x, y, 1_G) \in T$ and $(y, x, 1_G) \in T$.

An abelian group $(G, \set{E, T})$ is a group further satisfying:

• for all $x, y, z \in G$, if $(x, y, z) \in T$ then $(y, x, z) \in T$.

A ring $(R, \set{Z, O, A, M})$ is a relational structure where

1. $(R, \set{Z, A})$ is an abelian group;
2. $(R, \set{O, M})$ is a monoid;

satisfying:

1. for all $x, y, z, p, q, r, s \in R$, if $(y, z, s) \in A$, $(x, y, p) \in M$, $(x, z, q) \in M$, $(p, q, r) \in A$ then $(x, s, r) \in M$;
2. for all $x, y, z, p, q, r, s \in R$, if $(x, y, s) \in A$, $(x, z, p) \in M$, $(y, z, q) \in M$, $(p, q, r) \in A$ then $(s, z, r) \in M$.

A field is a ring where $(R \setminus \set0, \set{O\rvert_{R \setminus \set0}, M\rvert_{R \setminus \set0}})$ is a group.

A monoid $(M,*)$ is a set $M$ equipped with a binary operation $*: M\times M\to M$ satisfying the following axioms:

1. Identity: There exists $1_M\in M$ such that $1_M*m=m*1_M=m$ for all $m \in M$, called the identity of $M$.
2. Associativity: For all $x,y,z\in M$, $x*(y*z)=(x*y)*z$.

Often, we refer to the monoid with the same name as its underlying set, which is $M$ in this case. It is also common to represent the monoid operation by concatenation. Due to associativity, parentheses are not needed. For example $xyz=x*(y*z)=(x*y)*z$.

A monoid is commutative if it also obeys the following:

3. Commutativity: For all $x,y\in M$, $x*y=y*x$.

A group is a monoid with inverses:

4. Inverses: For all $x \in M$, there exists $x^{-1}\in M$ such that $x*x^{-1}=x^{-1}*x=1_M$.

An abelian group is a commutative group.

Typically the binary operation in a commutative monoid $M$ is denoted by the addition symbol $+$, and the identity element is denoted by $0_M$ instead of $1_M$. In an abelian group, inverses are then denoted by $-x$ instead of $x^{-1}$.

An algebra $(A,+,*)$ is a set $A$ equipped with two binary operations such that:

1. $(A,+)$ is an abelian group; $+$ is called the additive operation, or simply addition.
2. $(A,*)$ is a monoid; $*$ is called the multiplicative operation, or simply multiplication.
3. Distributivity: For all $a,b,c\in A$, $a*(b+c)=a*b+a*c$ and $(a+b)*c = a*c + b*c$.

Typically, we call the additive identity $0_A$ and the multiplicative identity $1_A$.

A ring $(R,+,*)$ is an algebra such that $(R,*)$ is a commutative monoid.

A field is a ring $(R,+,*)$ for which $(R\setminus\set0,*)$ is a group.

Let $(R, +_R, *_R)$ be a ring. The polynomial ring in one indeterminate $x$ with coefficients in $R$ is the ring denoted $R[x]$ whose elements are polynomials \[ p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \dots + a_nx^n, \quad n \in \N, a_i \in R, \] and the operations are defined as follows:

1. The symbol $x^0$ is defined to be $1_R$.
2. $\sum_{i = 0}^n a_i x^i + \sum_{i = 0}^n b_i x^i = \sum_{i = 0}^n (a_i +_R b_i) x^i$.
3. $\bigl(\sum_{i = 0}^n a_i x^i\bigr) * \bigl(\sum_{i = 0}^n b_i x^i\bigr) = \sum_{i = 0}^{2n} c_ix^i$, where $c_i = \sum_{j = 0}^i a_j *_R b_{i - j}$.

1. Let $R = (R, +, *)$ be a ring. Prove that $R[x]$ has infinitely many elements.
2. Prove that there are finitely many functions $f : R \to R$ if $R$ is a finite set.

If $(M, *_M)$ and $(N, *_N)$ are monoids, then a monoid homomorphism from $M$ to $N$ is a function $\varphi:M\to N$ such that

1. $\varphi(1_M)=1_N$.
2. $\varphi(a*_Mb)=\varphi(a)*_N\varphi(b)$ for all $a, b \in M$.

A monoid homomorphism between groups is a group homomorphism. A function between algebras that is a homomorphism of both the additive groups and multiplicative monoids is called an algebra homomorphism, and an algebra homomorphism of rings is called a ring homomorphism. Naturally, a ring homomorphism between fields is a field homomorphism.

A monoid, group, algebra, ring, or field homomorphism is an isomorphism if it is a bijection.

Let $\Phi : M \to N$ be a monoid isomorphism. Prove that the inverse $\Phi^{-1} : N \to M$ is also a monoid isomorphism.

The identity function $\id_M : M \to M$ of a monoid $M$ given by $\id_M(a) = a$ is always a homomorphism, called the identity homomorphism.

Let $\varphi : M \to N$ be a monoid homomorphism.

1. The kernel of $\varphi$ is $\ker\varphi = \set {\, m \in M \mid \varphi(m) = 1_N \,}$.
2. The image of $\varphi$ is $\im\varphi = \set {\, n \in N \mid \exists m \in M, \varphi(m) = n \,}$.

Kernels and images of group homomorphisms are defined analogously. Kernels and images of algebra homomorphisms are taken using the additive structure.

Let $R$ be a ring. The evaluation homomorphism at $t \in R$ is the homomorphism \[ \ev_t : R[x] \to R, \quad \ev_t(a_0 + a_1x + \dots + a_nx^n) = a_0 + a_1t + \dots + a_nt^n. \] For a polynomial $p(x) \in R[x]$, we write $p(t) \coloneq \ev_t(p(x))$.

Let $X$ be a set. We write $R^X$ for the set of functions $X \to R$. It is a ring when given the operations

1. $(f + g)(x) = f(x) + g(x)$,
2. $(f * g)(x) = f(x) * g(x)$.

Prove that the function $\Phi : R[x] \to R^R, \Phi(p(x))(t) = p(t)$ is a homomorphism of rings.

A homomorphism $\varphi : S \to S$ from an algebraic structure to itself is called an endomorphism of that structure.

The endomorphism algebra of an abelian group $M=(M,+)$ is the set of all endomorphisms of $M$, and is denoted $\End(M)$. The addition operation is $(\varphi+\psi)(x)=\varphi(x)+\psi(x)$, and the multiplication operation is $(\varphi*\psi)(x)=\varphi(\psi(x))$.

A submonoid of a monoid $M$ is a subset $N \subseteq M$ which satisfies:

1. Identity: $1_M \in N$.
2. Closure: For all $x, y \in N$, $x * y \in N$.

A submonoid of a group which is also a group is called a subgroup. A subring is a subset of a ring which is both a subgroup under the addition operation and submonoid under the multiplication operation, and a subfield is a field which is a subring of another field.

The trivial monoid is the monoid with only the identity element $\set{1}$. This is also a group, called the trivial group. The trivial ring is the ring with only one element $\set{0}$.

When using multiplicative notation, the trivial monoid and trivial group are often denoted by $1$, without the curly braces. When using additive notation, the trivial monoid and trivial group are often denoted by $0$, without the curly braces. The trivial ring is often denoted by $0$.

Let $(A, +_A)$ and $(B, +_B)$ be abelian groups. Their direct sum, denoted by $A \oplus B$, is the abelian group whose underlying set is $A \times B$ and addition operation is $(a_1, b_1) + (a_2, b_2) = (a_1 +_A a_2, b_1 +_B b_2)$.

Given a sequence of abelian groups $(A_1, +_{A_1}), \dots, (A_n, +_{A_n})$, their direct sum, denoted $A_1 \oplus A_2 \oplus \dots \oplus A_n$, is the abelian group whose underlying set is $A_1 \times A_2 \times \dots \times A_n$ and addition operation is \[ (a_1, a_2, \dots, a_n) + (a_1', a_2', \dots, a_n') = (a_1 +_{A_1} a_1', a_2 +_{A_2} a_2', \dots, a_n +_{A_n} a_n'). \]

The $n$-fold direct sum of an abelian group $(A, +_A)$ with itself will be denoted $A^{\oplus n}$, i.e., $A^{\oplus n} = A \oplus A \oplus \dots \oplus A$, where $A$ appears $n$ times. Its underlying set is the $n$-fold cartesian product $A^n$.

Given a direct sum $A \oplus B$, there are always four homomorphisms:

• The inclusions $i_A : A \to A \oplus B, i_A(a) = (a, 0)$ and $i_B : B \to A \oplus B, i_B(b) = (0, b)$.
• The projections $p_A : A \oplus B \to A, p_A(a, b) = a$ and $p_B : A \oplus B \to B, p_B(a, b) = b$.

Notice that the compositions $p_A \circ i_A : A \to A$ and $p_B \circ i_B : B \to B$ are identity maps, therefore making both $i_A$ and $i_B$ injective, and $p_A$ and $p_B$ surjective.

Let $A$ and $B$ be abelian groups. Show the following:

1. For any abelian group $C$ and homomorphisms $\varphi_A : C \to A$ and $\varphi_B : C \to B$, there exists a unique homomorphism $\Phi : C \to A \oplus B$ such that $p_A \circ \Phi = \varphi_A$ and $p_B \circ \Phi = \varphi_B$. The unique homomorphism $\Phi : C \to A \oplus B$ is denoted $\varphi_A \times \varphi_B$, called the product of $\varphi_A$ and $\varphi_B$.
2. For any abelian group $C$ and homomorphisms $\psi_A : A \to C$ and $\psi_B : B \to C$, there exists a unique homomorphism $\Psi : A \oplus B \to C$ such that $\Psi \circ i_A = \psi_A$ and $\Psi \circ i_B = \psi_B$. The unique homomorphism $\Psi : A \oplus B \to C$ is denoted $\psi_A \amalg \psi_B$, called the coproduct of $\psi_A$ and $\psi_B$.

Let $(A, +_A)$ be an abelian group, and let $B \subseteq A$ be a subgroup. A translate of $B$ by an element $a \in A$ is the subset \[ a +_A B = \set{\,a +_A b \mid b \in B\,}. \] Notice that for any $b \in B$, $(a +_A b) +_A B = a +_A B$. The set of all translates of $B$ is denoted $A/B$.

The set of all translates $A/B$ can be made into an abelian group, called the quotient of $A$ by $B$, or $A$ mod $B$, by defining the addition operation between two translates $a_1 +_A B$ and $a_2 +_A B$ to be \[ (a_1 +_A B) +_{A/B} (a_2 +_A B) = (a_1 +_A a_2) +_A B. \]

Check that the above definition actually does make $A/B$ into an abelian group.

Given a quotient $A/B$, there is always a quotient homomorphism $q_{A/B} : A \to A/B, q(a) = a +_A B$. Notice that this is always surjective.

Let $A$ be an abelian group and $B \subseteq A$ a subgroup. Prove that for any abelian group $C$ and homomorphism $\varphi : A \to C$ such that $B \subseteq \ker\varphi$, there exists a unique homomorphism $\ol\varphi : A/B \to C$ such that $\ol\varphi \circ q_{A/B} = \varphi$. The homomorphism $\ol\varphi$ is often called the induced homomorphism on the quotient $A/B$.

Let $\varphi : A \to B$ be a homomorphism of abelian groups. The cokernel of $\varphi$ is the quotient $\coker\varphi = B/{\im\varphi}$.

Let $F$ be a field. An $F$-vector space $(V, \rho)$ is an abelian group $V$ equipped with an algebra homomorphism $\rho: F \to \End(V)$. Often, we refer to the whole vector space simply as $V$, and we say that an $F$-vector space is over $F$.

For brevity, $\rho(a)(v)$ for $a \in F$ and $v \in V$ is typically denoted $av$, with $\rho$ left implicit. This operation is called scalar multiplication, because one typically calls $F$ the field of scalars.

Note that because $V$ is an abelian group, we will use $0_V$ to denote its identity element, and use additive notation. So a typical equation involving elements of $V$ and $F$ might look like $ax + by = 0$, where $a, b \in F$ and $x, y \in V$.

Let $V$ and $W$ be $F$-vector spaces. A linear transformation (or simply, linear map) from $(V, \rho_V)$ to $(W, \rho_W)$ is an abelian group homomorphism $f:V\to W$ such that for all $a\in F$, \[ f\circ\rho_V(a)=\rho_W(a)\circ f. \]

A category theorist would say that this means that the following diagram commutes for all $a \in F$.

This is a visual way to show that applying $f$ and then $\rho_W(a)$ is the same as applying $\rho_V(a)$ and then $f$.

A linear transformation between vector spaces is an isomorphism if it is an isomorphism of abelian groups.

Prove that the inverse of an isomorphism of vector spaces is also a linear transformation.

A subspace of a vector space $(V, \rho_V)$ over $F$ is a subgroup of $V$ which is closed under application of $\rho_V(a)$ for all $a \in F$.

Let $V$ be a vector space. A flag of $V$ is a sequence of subspaces $V_0, V_1, \dots, V_n \subseteq V$ such that \[ 0 = V_0 \subsetneq V_1 \subsetneq \dots \subsetneq V_n = V. \] The integer $n$ is called the length of the flag. Notice that the indices start from $0$.

The dimension of a vector space $V$ is the maximum length of a flag of $V$, if it exists; or is said to be infinite otherwise. This is denoted by $\dim V$, or $\dim_F V$ to emphasize the field.

When the dimension of $V$ is finite, we say that $V$ is finite-dimensional. Otherwise, we say it is infinite-dimensional, and we write $\dim V = \infty$.

A sequence of elements $v_1, v_2, \dots, v_n \in V$ is linearly independent if there exists a flag $V_0, V_1, \dots, V_n \subseteq V$ with $v_i \in V_i \setminus V_{i - 1}$ for all $i = 1, \dots, n$. Otherwise, we say that $v_1, v_2, \dots, v_n$ are linearly dependent.

A basis of $V$ is a linearly independent sequence $v_1, v_2, \dots, v_n \in V$ such that $n = \dim V$.

Let $v_1, v_2, \dots, v_n \in V$ be a sequence of elements. Their span, denoted $\spn\set{v_1, v_2, \dots, v_n}$, is the smallest subspace of $V$ that contains the subset $\set {v_1, v_2, \dots, v_n}$. The span of $v \in V$ may be denoted $Fv$.

Given a subspace $W \subseteq V$, the elements $v_1, v_2, \dots, v_n$ are said to span $W$, or be spanning $W$, if their span equals $W$. If $W = V$, one may simply say that they span, or are spanning.

Here, a subspace $U \subseteq V$ is said to be smaller than another subspace $W \subseteq V$ if $U \subsetneq W$.

Consider the vector space $(F^{\oplus n}, \rho)$ over $F$ with the field action $\rho(a)(x_1, x_2, \dots, x_n) = (ax_1, ax_2, \dots, ax_n)$. The standard basis of $F^{\oplus n}$ is the sequence $e_1, e_2, \dots, e_n$, where $e_i = (0, \dots, 0, 1, 0, \dots, 0)$ is the element whose coordinates are all $0$ except for a single $1$ in the $i$th slot.

The $i$th coordinate map of $F^{\oplus n}$ is the linear transformation $e_i^\dual : F^{\oplus n} \to F$ defined by $e_i^\dual(x_1, x_2, \dots, x_n) = x_i$. Therefore, \[ e_i^\dual(e_j) = \begin{dcases} 1 & \text{if } i = j, \\ 0 & \text{if } i \ne j. \end{dcases} \]

Let $V$ be a vector space and $v_1, v_2, \dots, v_n \in V$. We define $\Phi_{(v_1, v_2, \dots, v_n)} : F^{\oplus n} \to V$ to be the linear map given by $(x_1, x_2, \dots, x_n) \mapsto x_1v_1 + x_2v_2 + \dots + x_n v_n$.

Let $v_1, v_2, \dots, v_n \in V$, and let $\Phi_{(v_1, v_2, \dots, v_n)} : F^{\oplus n} \to V$ be the linear map defined above.

1. Prove that $\Phi_{(v_1, v_2, \dots, v_n)}$ is injective if and only if $v_1, v_2, \dots, v_n$ is linearly independent.
2. Prove that $\Phi_{(v_1, v_2, \dots, v_n)}$ is surjective if and only if $v_1, v_2, \dots, v_n$ spans $V$.
3. Prove that $\Phi_{(v_1, v_2, \dots, v_n)}$ is an isomorphism if and only if $v_1, v_2, \dots, v_n$ is a basis of $V$.

Let $B = (v_1, v_2, \dots, v_n)$ be a basis of $V$, and let $\Phi_{(v_1, v_2, \dots, v_n)} : F^{\oplus n} \to V$ be the resulting isomorphism. The coordinate vector of an element $v \in V$ with respect to the basis $B$ is the element of $F^{\oplus n}$ denoted $[v]_B \coloneq \Phi_{(v_1, v_2, \dots, v_n)}^{-1}(v)$.

The $i$th coordinate map with respect to $B$ is the composition $v_i^\dual \coloneq e_i^\dual \circ \Phi_{(v_1, v_2, \dots, v_n)}^{-1} : V \to F$. The $i$th coordinate of an element $v \in V$ with respect to $B$ is $v_i^\dual(v)$. Therefore, \[ v_i^\dual(v_j) = \begin{dcases} 1 & \text{if } i = j, \\ 0 & \text{if } i \ne j. \end{dcases} \]

Let $V=(V, \rho_V)$ and $W=(W, \rho_W)$ be vector spaces. The (external) direct sum of $V$ and $W$, denoted $V \oplus W$, is the abelian group $V \oplus W$ equipped with a field action $\rho(a)(v,w) = (\rho_V(a)(v), \rho_W(a)(w))$.

Let $V$ be a vector space and $W_1, W_2, \dots, W_n \subseteq V$ be subspaces. There is a linear transformation \[ \Phi : W_1 \oplus W_2 \oplus \dots \oplus W_n \to W_1 + W_2 + \dots + W_n, \quad \Phi(w_1, w_2, \dots, w_n) = w_1 + w_2 + \dots + w_n. \] The subspaces $W_1, W_2, \dots, W_n$ are said to be in internal direct sum if $\Phi$ is an isomorphism, and we write $W_1 \oplus W_2 \oplus \dots \oplus W_n$ for the subspace $W_1 + W_2 + \dots + W_n$ of $V$.

Technically, we have now defined $W_1 \oplus W_2 \oplus \dots \oplus W_n$ to mean two different things. But because there is an obvious isomorphism between the external and internal direct sums, no confusion shall arise.

Let $V = (V, \rho_V)$ be a vector space and $W \subseteq V$ a subspace. The quotient of $V$ by $W$, denoted $V/W$, is the abelian group $V/W$ equipped with a field action $\rho(a)(v + W) = \rho_V(a)(v) + W$.

Let $V=(V, \rho_V)$ and $W=(W, \rho_W)$ be vector spaces. The homset between $V$ and $W$ is the set of all linear transformations $V \to W$, and is denoted $\Hom(V, W)$. This is an abelian group with addition operation $(f + g)(v) = f(v) + g(v)$, and the field action is $(\rho(a)f)(v) = f(\rho_V(a)(v)) = \rho_W(a)f(v)$. We write $\End(V)$ for $\Hom(V, V)$.

Given vector spaces $U$, $V$, and $W$, and linear transformations $f : U \to V$ and $g : V \to W$, we define the following induced maps on the homsets:

1. $f^* : \Hom(V, W) \to \Hom(U, W)$, where $f^*(\varphi) = \varphi \circ f$.
2. $g_* : \Hom(U, V) \to \Hom(U, W)$, where $g_*(\varphi) = g \circ \varphi$.

Prove that $f^*$ and $g_*$ are linear transformations.

Let $V$ be a vector space over the field $F$. The dual of $V$ is the homset $\Hom(V, F)$, denoted $V^\dual$.

Given vector spaces $V$ and $W$, and a linear transformation $f : V \to W$, we define its dual to be the linear transformation $f^\dual : W^\dual \to V^\dual, f^\dual(\varphi) = \varphi \circ f$.

Prove that $f^\dual$ is a linear transformation.

Let $V$ and $W$ be finite-dimensional vector spaces. The tensor product of $V$ and $W$, denoted $V \otimes W$, is the homset $\Hom(V^\dual, W)$. For two elements $v \in V$ and $w \in W$, we write $v \otimes w \in V \otimes W$ to mean the element defined by $(v \otimes w)(\varphi) = \varphi(v)w$.

Given vector spaces $U$, $V$, and $W$, and linear transformations $f : U \to V$ and $g : V \to W$, we define the following induced maps on the tensor products:

1. $f \otimes W : U \otimes W \to V \otimes W$, where $(f \otimes W)(\varphi) = \varphi \circ f^\dual$.
2. $U \otimes g : U \otimes V \to U \otimes W$, where $(U \otimes g)(\varphi) = g \circ \varphi$.

More generally, given linear transformations $f_i : V_i \to W_i$, $i = 1, 2$, we define $f_1 \otimes f_2 : V_1 \otimes V_2 \to W_1 \otimes W_2$, where $(f_1 \otimes f_2)(\varphi) = f_2 \circ \varphi \circ f_1^\dual$. So $f \otimes W = f \otimes \id_W$ and $U \otimes g = \id_U \otimes g$.

Prove that $f_1 \otimes f_2$ is a linear transformation.

Let $V_0, V_1, \dots, V_n \subseteq V$ be a flag. The $i$th filtration quotient of the flag is the quotient $V_i/V_{i - 1}$ for $i = 1, \dots, n$. The $0$th filtration quotient is conventionally taken to be $V_0 = 0$.

The associated graded of a flag $\FF = (V_0, V_1, \dots, V_n)$ is the direct sum of the filtration quotients $V_1/V_0 \oplus V_2/V_1 \oplus \dots \oplus V_n/V_{n - 1}$, denoted $\gr_\FF V$.

Let $f : V \to W$ be a linear transformation. Then the induced linear transformation on the quotient $\ol f : V/{\ker f} \to W$ gives an isomorphism $\ol f : V/{\ker f} \to \im f$.

Prove this theorem.

Let $V$ be a vector space and $U, W \subseteq V$ be subspaces of $V$. Then

1. $W$ is a subspace of $U + W$;
2. $U \cap W$ is a subspace of $U$; and

the linear transformation defined $f : (U + W)/W \to U/(U \cap W), f((u + w) + W) = u + U \cap W$ is an isomorphism.

Prove this theorem.

Let $V$ be a vector space and $U \subseteq W \subseteq V$ be subspaces. Then

1. $U$ is a subspace of $W$;
2. $W/U$ is a subspace of $V/U$; and

the linear transformation defined $f : V/W \to (V/U)/(W/U), f(v + W) = (v + U) + W/U$ is an isomorphism.

Prove this theorem.

Let $V$ be a vector space and $W \subseteq V$ be a subspace.

1. Let $\VV$ denote the set of all subspaces of $V$ containing $W$.
2. Let $\WW$ denote the set of all subspaces of $V/W$.

Then there is a bijection $\Phi : \VV \to \WW, \Phi(U) = U/W$ such that if $U_1 \subseteq U_2$ then $\Phi(U_1) \subseteq \Phi(U_2)$.

Prove this theorem.

The sequence is said to be exact at $V_i$, $1 \le i \le n - 1$, if $\ker f_i = \im f_{i - 1}$. The sequence is said to be exact if it is exact at $V_i$ for all $1 \le i \le n - 1$.

A short exact sequence is an exact sequence of $5$ vector spaces \[ 0 \to U \xto{f} V \xto{g} W \to 0. \] The maps $f$ and $g$ may be omitted if no confusion may arise.

Prove that the sequence $0 \to U \xto f V \xto g W \to 0$ is short exact if and only if

1. $f : U \to V$ is injective.
2. $g : V \to W$ is surjective.
3. $\ker g = \im f$.

Let $X$ and $Y$ be sets. We write $Y^X$ for the set of functions $X \to Y$.

★Suppose $X$ has $n$ elements and $Y$ has $m$ elements. Prove that $Y^X$ has $m^n$ elements.

Let $V$ and $W$ be vector spaces, with $V$ finite-dimensional.

1. Let $v_1, v_2, \dots, v_n \in V$ be a basis of $V$.
2. Let $w_1, w_2, \dots, w_n \in W$ be any sequence of elements of $W$.

Let $f : \set {v_1, v_2, \dots, v_n} \to W$ be the function $f(v_i) = w_i$ for each $1 \le i \le n$. There exists a unique linear transformation $\wt f : V \to W$ extending $f$ to $V$. Furthermore, the function $\Phi : W^{\set {v_1, v_2, \dots, v_n}} \to \Hom(V, W) , \Phi(f) = \wt f$ is a bijection.

Prove this theorem.

Consider the homset $\Hom(F^{\oplus n}, F^{\oplus m})$. For each $(i, j)$ with $1 \le i \le n$ and $1 \le j \le m$, we define the linear transformation $e_j e_i^\dual : F^{\oplus n} \to F^{\oplus m}, (e_j e_i^\dual)(v) = e_j e_i^\dual(v)$. The standard basis of $\Hom(F^{\oplus n}, F^{\oplus m})$ is the sequence $e_1 e_1^\dual, e_2 e_1^\dual, \dots, e_m e_n^\dual$.

The $(i, j)$th coordinate map of $\Hom(F^{\oplus n}, F^{\oplus m})$ is the linear transformation $(e_j e_i^\dual)^\dual : \Hom(F^{\oplus n}, F^{\oplus m}) \to F$. Therefore, \[ (e_j e_i^\dual)^\dual(e_{j'} e_{i'}^\dual) = \begin{dcases} 1 & \text{if } (i, j) = (i', j') \\ 0 & \text{if } (i, j) \ne (i', j'). \end{dcases} \]

Let $V$ and $W$ be finite-dimensional vector spaces. Let $B = (v_1, v_2, \dots, v_n)$ be a basis of $V$ and $C = (w_1, w_2, \dots, w_m)$ be a basis of $W$. Hence, we get an isomorphism $\Phi_{B, C} \coloneq \Phi_{C*} \circ (\Phi_B^*)^{-1} : \Hom(F^{\oplus n}, F^{\oplus m}) \to \Hom(V, W)$. The coordinate matrix of a linear transformation $f : V \to W$ with respect to the bases $B$ and $C$ is the element of $\Hom(F^{\oplus n}, F^{\oplus m})$ denoted by $[f]_{C \from B} \coloneq \Phi_{B, C}^{-1}(f)$.

For each $(i, j)$ with $1 \le i \le n$ and $1 \le j \le m$, we define the linear transformation $w_j v_i^\dual : V \to W, (w_j v_i^\dual)(v) = w_j v_i^\dual(v)$. We call the linear transformation $(w_j v_i^\dual)^\dual : \Hom(V, W) \to F$ the $(i, j)$th coordinate map of $\Hom(V, W)$ with respect to $B$ and $C$. The $(i, j)$th coordinate of a linear transformation $f \in \Hom(V, W)$ with respect to $B$ and $C$ is $(w_j v_i^\dual)^\dual(f)$.

Prove that $(w_j v_i^\dual)^\dual = (e_j e_i^\dual)^\dual \circ \Phi_{B, C}^{-1}$.

Let $f : U \to V$ and $g : V \to W$ be linear transformations. Let $B = (u_i)_{1 \le i \le n}$, $C = (v_i)_{1 \le i \le p}$, and $D = (w_i)_{1 \le i \le m}$ be bases of $U$, $V$, and $W$ respectively. Then \[ (w_ju_i^\dual)^\dual(g \circ f) = \sum_{k = 1}^p (v_ku_i^\dual)^\dual(f) (w_jv_k^\dual)^\dual(g). \]

Prove this theorem.

Let $f : V \to W$ be a linear transformation. Let $B = (v_i)_{1 \le i \le n}$ and $C = (w_i)_{1 \le i \le m}$ be bases of $V$ and $W$ respectively. Let $v \in V$. Then \[ w_j^\dual(f(v)) = \sum_{i = 1}^n (w_jv_i^\dual)^\dual(f) v_i^\dual(v). \]

Prove this theorem.

Let $V$ be a finite-dimensional vector space and $B = (v_1, v_2, \dots, v_n)$ be a basis of $V$. For an element $f = \sum_{i, j = 1}^n a_{i, j} v_jv_i^\dual \in \End(V)$, its trace is the element of $F$ given by $\tr(f) = \sum_{i, j = 1}^n a_{i, j} v_i^\dual(v_j)$.

Prove the following properties about the trace:

1. $\tr : \Hom(V, V) \to F$ is a linear transformation.
2. For $f : V \to W$ and $g : W \to V$ linear transformations of finite-dimensional $V$ and $W$, $\tr(f \circ g) = \tr(g \circ f)$.
3. $\tr(f) = \tr([f]_{B \from B})$.

Let $V$ be a vector space over $F$. The evaluation homomorphism at $f \in \End(V)$ is the homomorphism \[ \ev_f : F[x] \to \End(V), \quad \ev_f(a_0 + a_1x + \dots + a_nx^n) = a_0 \id_V + a_1 f + \dots + a_n f^n. \] For a polynomial $p(x) \in F[x]$, we write $p(f) \coloneq \ev_f(p(x))$.

Let $V$ be a finite-dimensional vector space over $F$, and $f : V \to V$ be an endomorphism. Then there exists a nonzero polynomial $p(x) \in F[x]$ such that $p(f) = 0$.

Let $n = \dim V$. The vector space $\End(V)$ has dimension $n^2$, so the sequence $\id_V, f, f^2, f^3, \dots, f^{n^2}$ is linearly dependent. Therefore, there exists a nonzero $p(x) \in F[x]$ with $\deg p(x) \le n^2$ such that $p(f) = 0$.

For an endomorphism $f : V \to V$ of a finite-dimensional vector space $V$, the minimal polynomial of $f$ is the monic polynomial $p(x) \in F[x]$ of least degree such that $p(f) = 0$. We denote the minimal polynomial by $\irr(f, F)$.

Let $p(x) \in F[x]$ be a polynomial such that $p(f) = 0$. Prove that $\irr(f, F) \mid p(x)$.

Let $f : V \to V$ be an endomorphism. An $f$-invariant subspace of $V$ is a subspace $W \subseteq V$ such that $f$ restricts to an endomorphism $f\rvert_W : W \to W$. One may omit the endomorphism and simply say invariant subspace if no confusion may arise.

Prove that the above definition amounts to saying that if $w \in W$ then $f(w) \in W$.

Let $\ol f : V/W \to V/W$ denote the induced endomorphism on the quotient. Prove that $\lcm\set{\irr(f\rvert_W, F), \irr(\ol f, F)}$ divides $\irr(f, F)$, and that $\irr(f, F)$ divides $\irr(f\rvert_W, F)\,\irr(\ol f, F)$.

Let $f : V \to V$ be an endomorphism of a finite-dimensional vector space $V$. Let $p(x) \mid \irr(f, F)$ be an irreducible factor. The $p(x)$-primary component of $V$ with respect to $f$ is the subspace $\bigcup_{n \in \N} \ker(p(f)^n)$. For any irreducible $p(x) \in F[x]$, we define $V_p(f) \coloneq \bigcup_{n \in \N} \ker(p(f)^n)$.

Let $p(x) \in F[x]$ be an irreducible polynomial.

1. Check that $V_p(f)$ actually is a subspace of $V$.
2. Prove that $V_p(f) \ne 0$ if and only if $p(x) \mid \irr(f, F)$.
3. Prove that $\ker(p(f)^n)$ is an $f$-invariant subspace for all $n \in \N$.

Let $f : V \to V$ be an endomorphism. An $f$-cyclic subspace of $V$ is a subspace spanned by the infinite sequence $v, f(v), f^2(v), \dots$ for some $v \in V$. This $f$-cyclic subspace is denoted $F[f]v$.

Prove that $f$-cyclic subspaces are $f$-invariant.

Let $f : V \to V$ be an endomorphism of a finite-dimensional vector space $V$. Let \[ \irr(f, F) = p_1(x)^{e_1} p_2(x)^{e_2} \dots p_n(x)^{e_n}, \quad p_i(x) \in F[x], e_i \in \N \] be a factorization of $\irr(f, F)$ into irreducible factors. Then:

1. $V_{p_i}(f) = \ker(p_i(f)^{e_i}) \supsetneq \ker(p_i(f)^{e_i - 1})$.
2. $V = V_{p_1}(f) \oplus V_{p_2}(f) \oplus \dots \oplus V_{p_n}(f)$ as an internal direct sum of $f$-invariant subspaces.
3. There exist $v_{i,1}, v_{i,2}, \dots, v_{i,r_i} \in V_{p_i}(f)$ such that $V_{p_i}(f) = F[f]v_{i,1} \oplus F[f]v_{i,2} \oplus \dots \oplus F[f]v_{i, r_i}$.
4. If $e_{i, j}$ is the smallest positive integer such that $p_i(f)^{e_{i, j}}(v_{i, j}) = 0$, then $F[f]v_{i, j} = \spn\set {\, f^a p_i(f)^b(v_{i,j}) \mid 0 \le a < \deg p_i(x), 0 \le b < e_{i, j} \,}$, and $e_i = \max \set {e_{i,1}, e_{i,2}, \dots, e_{i, r_i}}$.
5. For each $1 \le i \le n$, the multiset $\set {e_{i,1}, e_{i,2}, \dots, e_{i, r_i}}$ is uniquely determined by $f$.

1. There exist polynomials $a(x), b(x) \in F[x]$ such that \[ a(x) \irr(f, F) + b(x) p_i(x)^{e_i + 1} = p_i(x)^{e_i}. \] Letting $v \in \ker(p_i(f)^{e_i + 1})$, \[ 0 = (a(f) \irr(f, F)(f) + b(f) p_i(f)^{e_i + 1})(v) = p_i(f)^{e_i}(v). \] So $v \in \ker(p_i(f)^{e_i})$. However, since $g \coloneq p_i(f)^{e_i - 1} \prod_{j \ne i} p_j(f)^{e_j} \ne 0$, there exists $v \in V$ such that $g(v) \ne 0$, but clearly $(p_i(f) g)(v) = 0$. So $\ker(p_i(f)^{e_i - 1}) \ne \ker(p_i(f)^{e_i})$.
2. For each $1 \le i \le n$, let $q_i(x) = \irr(f, F)/p_i(x)^{e_i}$. There exist polynomials $a_i(x), b_i(x) \in F[x]$ such that \[ a_i(x) p_i(x)^{e_i} + b_i(x) q_i(x) = 1. \] Define the endomorphisms $P_i = b_i(f) q_i(f) : V \to V$. They satisfy:
   1. If $v \in V_{p_i}(f)$ then $v = a_i(f)p_i(f)^{e_i}(v) + P_i(v) = P_i(v)$.
   2. $P_i^2 = b_i(f) q_i(f) (1 - a_i(f) p_i(f)^{e_i}) = P_i$.
   3. For $i \ne j$, $P_iP_j = b_i(f) q_i(f) b_j(f) q_j(f) = 0$.
   4. For each $1 \le i \le n$, $\sum_{j = 1}^n b_j(x) q_j(x) - 1 = -a_i(x) p_i(x)^{e_i} + \sum_{j \ne i} b_j(x) q_j(x)$ is divisible by $p_i(x)^{e_i}$. Therefore $\sum_{j = 1}^n b_j(x) q_j(x) - 1$ is divisible by $\irr(f, F)$, and $\sum_{j = 1}^n P_j = \id_V$.
   From the above, we conclude that $\im P_i = V_{p_i}(f)$ and $\ker P_i = \bigoplus_{j \ne i} V_{p_j}(f)$. Now $V = V_{p_1}(f) + V_{p_2}(f) + \dots + V_{p_n}(f)$ because if $v \in V$ then \[ v = \id_V(v) = P_1(v) + P_2(v) + \dots + P_n(v). \] The sum is direct because if $v = v_1 + v_2 + \dots + v_n = 0$ for $v_i \in V_{p_i}(f)$, then $P_i(v) = v_i = 0$.

3. We may assume that $V = V_p(f)$, $p(x) = p_1(x)$, $e = e_1$. We induct on $e$. We must have $e > 0$, so our base case is when $\irr(f, F) = p(x)$. For this, we also induct on $\dim V$.

   When $\dim V = 0$, there is nothing to do, so assume that $\dim V > 0$. Let $d = \deg p(x)$. Then there exists $v_1 \in V$ such that the sequence $v_1, f(v_1), \dots, f^{d - 1}(v_1)$ is linearly independent. Let $W_1 = F[f]v_1$, and consider the induced map $\ol f : V/W_1 \to V/W_1$ on the quotient. Because $\dim V/W_1 < \dim V$, the induction hypothesis applies so that $V/W_1 = F[\ol f]\ol v_2 \oplus F[\ol f]\ol v_3 \oplus \dots \oplus F[\ol f]\ol v_r$. Indeed, each $\ol v_i \in V/W_1$ may be chosen so that $\ol v_i, \ol f(\ol v_i), \dots, \ol f{}^{d - 1}(\ol v_i)$ is linearly independent. Choosing $v_i \in V$ such that $q_{V/W_1}(v_i) = \ol v_i$, and writing $W_i = F[f]v_i$, we find that \[ q_{V/W_1}\rvert_{W_i} : W_i = \spn\set{v_i, f(v_i), \dots, f^{d - 1}(v_i)} \to \ol W_i \coloneq F[\ol f]\ol v_i = \spn\set{\ol v_i, \ol f(\ol v_i), \dots, \ol f{}^{d - 1}(\ol v_i)} \] is an isomorphism for each $i \ge 2$. So $V = W_1 \oplus W_2 \oplus \dots \oplus W_r$.

   Now when $e > 1$, we consider the flag \[ 0 \subset \ker(p(f)) \subset \ker(p(f)^2) \subset \dots \subset \ker(p(f)^e) = V. \] Write $V_i = \ker(p(f)^i)$. Notice that $V_{i - 1} = p(f)(V_i)$. So $\ol f : V_e/V_{e - 1} \to V_e/V_{e - 1}$ has minimal polynomial $p(x)$, and the base case applies to yield $V_e/V_{e - 1} = F[\ol f]\ol v_1 \oplus F[\ol f]\ol v_2 \oplus \dots \oplus F[\ol f]\ol v_r$. Again, choose $v_i \in V_e$ such that $q_{V_e/V_{e - 1}}(v_i) = \ol v_i$. Let $W = F[f]v_1 \oplus F[f]v_2 \oplus \dots \oplus F[f]v_r$. We wish to show that $V = W$. It is certainly true from construction that $V = W + p(f)(V)$. But now, notice that we have \[ V = W + p(f)(W + p(f)(V)) = W + p(f)^2(V) = \dots = W + p(f)^e(V). \] However, since $V = \ker(p(f)^e)$, it follows that $V = W$.

4. This follows from the previous part, and is left as an exercise for the reader.
5. Indeed, the direct summands $V_{p_i}(f)$ are uniquely determined by $f$. Now considering a single $V_{p_i}(f) = V_p(f)$, $p(x) = p_i(x)$, $e = e_i$, we have seen that the filtration quotients $V_i/V_{i - 1}$ of the flag $V_i = \ker(p(f)^i)$ are each equal to $\bigoplus_{j = 1}^{s_i} F[\ol f]\ol v_{i, j}$ for some $\ol v_{i, j} \in V_i$, $s_i \in \N$, and $\ol f : V_i/V_{i - 1} \to V_i/V_{i - 1}$ the induced map, with \[ F[\ol f]\ol v_{i, j} = \spn\set{\ol v_{i, j}, \ol f(\ol v_{i, j}), \dots, \ol f{}^{d - 1}(\ol v_{i, j})}. \] Therefore, $\dim V_i/V_{i - 1} = ds_i$. The sequence $0 = s_0, s_1, s_2, \dots, s_e$ is increasing, and the number of times each number $1 \le e_{i, j} \le e$ appears in the multiset is precisely $s_{e_{i, j}} - s_{e_{i, j} - 1}$.

Let $f : V \to V$ be an endomorphism. An eigenvalue of $f$ is an element $\lambda \in F$ such that $f - \lambda \id_V$ is not injective.

Prove the following if $V$ is finite-dimensional:

1. $\lambda \in F$ is an eigenvalue of $f$ if and only if $\lambda$ is a root of $\irr(f, F)$.
2. Let $n = \dim V$. There are at most $n$ eigenvalues of $f$.

Let $f : V \to V$ be an endomorphism and $\lambda \in F$ an eigenvalue of $f$. The $\lambda$-eigenspace of $f$ is the subspace $\ker(f - \lambda \id_V)$. For any $\lambda \in F$, we define $E_\lambda(f) \coloneq \ker(f - \lambda \id_V)$.

The generalized $\lambda$-eigenspace of $f$ is the subspace $\bigcup_{n \in \N} \ker((f - \lambda \id_V)^n)$. For any $\lambda \in F$, we define $V_\lambda(f) \coloneq \bigcup_{n \in \N} \ker((f - \lambda \id_V)^n)$.

Let $\lambda \in F$.

1. Check that $V_\lambda(f)$ actually is a subspace of $V$.
2. Prove that $V_\lambda(f) \ne 0$ if and only if $\lambda$ is an eigenvalue of $f$.
3. Prove that $\ker((f - \lambda \id_V)^n)$ is an $f$-invariant subspace for all $n \in \N$.

Let $f : V \to V$ be an endomorphism of a finite-dimensional vector space $V$. Suppose that $\irr(f, F)$ factorizes into linear factors as follows: \[ \irr(f, F) = (x - \lambda_1)^{e_1} (x - \lambda_2)^{e_2} \dots (x - \lambda_n)^{e_n}, \quad \lambda_i \in F, e_i \in \N. \] Then:

1. $V_{\lambda_i}(f) = \ker((f - \lambda_i \id_V)^{e_i}) \supsetneq \ker((f - \lambda_i \id_V)^{e_i - 1})$.
2. $V = V_{\lambda_1}(f) \oplus V_{\lambda_2}(f) \oplus \dots \oplus V_{\lambda_n}(f)$ as an internal direct sum of $f$-invariant subspaces.
3. There exist $v_{i,1}, v_{i,2}, \dots, v_{i,r_i} \in V_{\lambda_i}(f)$ such that $V_{\lambda_i}(f) = F[f]v_{i,1} \oplus F[f]v_{i,2} \oplus \dots \oplus F[f]v_{i, r_i}$.
4. $F[f]v_{i, j} = \spn\set {v_{i,j}, (f - \lambda_i \id_V)(v_{i, j}), \dots, (f - \lambda_i \id_V)^{e_{i,j} - 1}(v_{i, j})}$, and $e_i = \max \set {e_{i,1}, e_{i,2}, \dots, e_{i, r_i}}$.
5. For each $1 \le i \le n$, the multiset $\set {e_{i,1}, e_{i,2}, \dots, e_{i, r_i}}$ is uniquely determined by $f$.

A function $f : U \times V \to W$, where $U$, $V$, and $W$ are vector spaces, is bilinear if

1. for all $u \in U$, the function $f_u : V \to W, f_u(v) = f(u, v)$ is linear; and
2. for all $v \in V$, the function $f^v : U \to W, f^v(u) = f(u, v)$ is linear.

A bilinear form on $V$, a vector space over $F$, is a bilinear function $f : V \times V \to F$.

A bilinear form $f : V \times V \to F$ is

1. symmetric if $f(u, v) = f(v, u)$ for all $u, v \in V$;
2. alternating if $f(v, v) = 0$ for all $v \in V$;
3. skew if $f(u, v) = -f(v, u)$ for all $u, v \in V$.