Linear Algebra: Kernel, Image, Injectivity, and Isomorphisms

Proof: Kernel of a Linear Transformation as a Subspace

• Consider a linear transformation $t$ from a vector space $V$ to $W$. The kernel of $t$, denoted $\text{kernel}(t)$, is a subset of $V$.
• Verification of the Subspace Property:     * To show that the kernel is a subspace, we use the one-step subspace test.     * Assuming $c$ is a scalar and $v$ and $w$ are elements in the $\text{kernel}(t)$, we check if the linear combination $cv - w$ is also in the $\text{kernel}(t)$.     * Since $t$ is linear, $t(cv - w) = c \cdot t(v) - t(w)$.     * Since $v$ and $w$ are in the kernel by assumption, we know that $t(v) = 0$ and $t(w) = 0$.     * Therefore, $t(cv - w) = c(0) - 0 = 0$.     * By definition, because the result is the zero vector, $cv - w \in \text{kernel}(t)$.
• Conclusion: The $\text{kernel}(t)$ is a subspace of $V$ by the one-step subspace test.
• Exercise for Students: Prove the equivalent part of the lemma: the image of $t$ in $W$ is a subspace of $W$. The proof is similar and involves recalling the definition of the image as the set of things in $W$ that are mapped to under $t$.

Definitions of Injectivity and Surjectivity

• Let $f: X \rightarrow Y$ be a set function where $X$ and $Y$ are sets.
• Injective: $f$ is injective if $f(x_1) = f(x_2) \implies x_1 = x_2$ for all $x_1, x_2 \in X$. Conceptually, this means if you find something in the image, there is only one thing in the domain that maps to it.
• Surjective: $f$ is surjective if for all $y \in Y$, there exists an $x \in X$ such that $f(x) = y$. Conceptually, this means the image is the entire codomain ($W$).

Lemmas on Injectivity, Surjectivity, Kernel, and Image

• For a linear transformation $t: V \rightarrow W$:     * Part 1: $t$ is injective if and only if the $\text{kernel}(t) = \{0\}$.     * Part 2: $t$ is surjective if and only if the $\text{image}(t) = W$.
• The lecturer notes that the second part regarding surjectivity is a general fact about set functions and does not strictly depend on the properties of vector spaces.

The Rigor of Mathematics: Russell and Whitehead

• The lecturer references the Principia Mathematica by Bertrand Russell and Alfred North Whitehead (1800s/early 1900s).
• The Problem of Consistency: Mathematicians in that era questioned the consistency of their proofs. Russell and Whitehead attempted to boil mathematics down to approximately eight axioms and build the entire system from them.
• Level of Rigor: To illustrate how rigorous this was, they proved that $1 + 1 = 2$ only after reaching page 330 of the text.

Proof of Surjectivity Lemma

• Direction 1 ($t$ is surjective $\implies$ image(t) = W$):     * Assume $t$ is surjective. Let $w \in W$.     * Since $t$ is surjective, there exists at least one $v \in V$ such that $t(v) = w$.     * By definition, this implies $w \in \text{image}(t)$. Therefore, $W \subseteq \text{image}(t)$.     * Since $\text{image}(t) \subseteq W$ by definition, iterating both inclusions proves $W = \text{image}(t)$.
• Direction 2 (image(t) = W $\implies$ $t$ is surjective):     * Assume that the $\text{image}(t) = W$.     * Then for all $w \in W$, because $W$ is equal to the image, there exists a $v \in V$ such that $t(v) = w$.     * Thus, $t$ is surjective by definition.

Proof of Injectivity Lemma

• Direction 1 ($t$ is injective $\implies$ kernel(t) = {0}):     * Assume $t$ is injective. Let $v \in \text{kernel}(t)$.     * By definition, $t(v) = 0$.     * We know that for any linear transformation, $t(0) = 0$.     * Thus, $t(v) = t(0)$. Since $t$ is injective, the images being the same implies the inputs must be the same: $v = 0$.
• Direction 2 (kernel(t) = {0} $\implies$ $t$ is injective):     * Assume the $\text{kernel}(t)$ consists only of the zero vector. We want to show that if $t(v) = t(w)$, then $v = w$.     * Assume $t(v) = t(w)$ for some $v, w$.     * Because $t$ is linear, $0 = t(v) - t(w) = t(v - w)$.     * This implies $v - w \in \text{kernel}(t)$.     * Since we assumed the $\text{kernel}(t) = \{0\}$, the vector $v - w$ must be the zero vector.     * Therefore, $v - w = 0$, which implies $v = w$. Thus, $t$ is injective.

Questions & Discussion: Linear Transformation Examples

• Task: Come up with linear transformations that are injective, surjective, or neither. (The Identity matrix is disallowed).
• Example 1: Projection onto the x-axis (from $\mathbb{R}^2$ to $\mathbb{R}^1$):     * Defined by the matrix $\begin{pmatrix} 1 & 0 \end{pmatrix}$.     * It takes $\begin{pmatrix} x \\ y \end{pmatrix}$ and sends it to $x$.     * Surjectivity: It is surjective because any real number $x$ can be produced.     * Injectivity: It is not injective. The kernel consists of all vectors where $x = 0$ (anything in the form $\begin{pmatrix} 0 \\ y \end{pmatrix}$, which is the span of $\begin{pmatrix} 0 \\ 1 \end{pmatrix}$). Since the kernel is one-dimensional, there are infinitely many vectors mapping to zero.
• Example 2: Injective from $\mathbb{R}^1$ to $\mathbb{R}^2$:     * Defined by the matrix $\begin{pmatrix} 1 \\ 1 \end{pmatrix}$.     * It sends $x \in \mathbb{R}$ to $\begin{pmatrix} x \\ x \end{pmatrix}$.     * Kernel Calculation: The kernel is the set of $x$ such that $\begin{pmatrix} 1 \\ 1 \end{pmatrix} x = \begin{pmatrix} 0 \\ 0 \end{pmatrix}$. Clearly, only $x = 0$ works. Thus, it is injective.     * Surjectivity: It is not surjective because it only hits the diagonal in $\mathbb{R}^2$.
• Example 3: Projection onto a vector $V$:     * A student suggests projecting onto a vector $b$ in $\mathbb{R}^2$.     * If going from $\mathbb{R}^2 \rightarrow \mathbb{R}^2$ and projecting onto a vector $b$, this is neither injective nor surjective.     * It is not surjective because the output is restricted to the span of $b$. However, if you restrict the codomain to be the image (the span of $b$), it becomes surjective.
• The Zero Transformation: Between any two vector spaces, the transformation mapping everything to zero is neither injective nor surjective (unless one of the spaces is the zero space).

Definition of Isomorphism

• Bijective Function: A set function $f: X \rightarrow Y$ is bijective if it is both injective and surjective.
• Isomorphism: A linear transformation $t: V \rightarrow W$ is an isomorphism if there exists a linear transformation $t^{-1}: W \rightarrow V$ such that:     1. $t \circ t^{-1} = \text{ID}_W$     2. $t^{-1} \circ t = \text{ID}_V$
• Notation: Vector spaces $V$ and $W$ are isomorphic, written as $V \cong W$.
• Proposition: A linear transformation $t$ is an isomorphism if and only if $t$ is a bijection as a set function.
• Set Function Lemma (for exercises):     1. $f$ is injective $\iff$ there exists $s: Y \rightarrow X$ such that $s \circ f = \text{ID}_X$.     2. $f$ is surjective $\iff$ there exists $s: Y \rightarrow X$ such that $f \circ s = \text{ID}_Y$.

Basis Preservation under Injective Linear Transformations

• Lemma: Let $t: V \rightarrow W$ be an injective linear transformation. If $B = \{x_1, \dots, x_n\}$ is a basis for $V$, then $B_t = \{t(x_1), \dots, t(x_n)\}$ is a basis for $\text{image}(t)$.
• Proof (Spanning):     * Let $w \in \text{image}(t)$. Then $w = t(v)$ for some $v \in V$.     * Since $B$ is a basis, there exist unique scalars $\alpha_i$ such that $v = \alpha_1 x_1 + \dots + \alpha_n x_n$.     * By linearity, $w = t(\alpha_1 x_1 + \dots + \alpha_n x_n) = \alpha_1 t(x_1) + \dots + \alpha_n t(x_n)$.     * Thus, $w$ is in the span of $B_t$, and $\text{image}(t) \subseteq \text{span}(B_t)$.
• Proof (Linear Independence):     * Assume $\gamma_1 t(x_1) + \dots + \gamma_n t(x_n) = 0$.     * By linearity, this implies $t(\gamma_1 x_1 + \dots + \gamma_n x_n) = 0$.     * This means the vector $\gamma_1 x_1 + \dots + \gamma_n x_n \in \text{kernel}(t)$.     * Because $t$ is injective, the kernel contains only the zero vector, so $\gamma_1 x_1 + \dots + \gamma_n x_n = 0$.     * Because $B = \{x_1, \dots, x_n\}$ is a basis, it is linearly independent, meaning $\gamma_1 = \gamma_2 = \dots = \gamma_n = 0$.     * Therefore, $B_t$ is linearly independent and constitutes a basis for the image.

Extension by Linearity and Abstract Vector Spaces

• Linearization Goal: To understand abstract linear transformations computationally, we represent them as matrices. This involves finding isomorphisms between an abstract vector space $V$ (dimension $n$) and the linear space $K^n$.
• Process: Identify a basis for $V$ and map its elements to the standard basis of $K^n$.
• Extension by Linearity: A process that allows us to define a linear transformation entirely based on where it maps the basis elements. If we know the images of the basis vectors, the entire map is determined.

The Existence of a Basis: Zorn's Lemma and the Axiom of Choice

• The Logical Problem: Dimension is defined as the cardinality of a basis. However, we must first prove that every vector space actually has a basis.
• Finite-Dimensional Case: One can take a spanning set and remove dependent vectors until a minimal set remains.
• Infinite-Dimensional Case: Proving the existence of a basis requires Zorn's Lemma, which is equivalent to the Axiom of Choice.
• Axiom of Choice: If you have infinitely many sets, you can pick one element from each set to create a new set.     * Metaphor: Imagine infinitely many shoeboxes, each containing a left shoe and a right shoe. The Axiom of Choice allows you to pick all the left shoes to create an infinite collection.
• Controversy: The Axiom of Choice is controversial because it assumes a process (infinite selection) that is impossible in practice. However, it is fundamentally required to prove that every vector space has a basis.

Exam Instructions and Housekeeping

• Class Break: 10:02 AM.
• Handouts: Proof writing exercises to be released Friday. Preliminary tests distributed in class.
• Test Rules: "Honor Rule" applied—do not flip the test over until instructed.
• Correction on Points:     * Question 3, Part A: 3 points.     * Question 3, Part B: 7 points.