Linear Algebra

Vector Space

Definition

Motivation: properties of addition and scalar multiplication in $ \mathbf{F}^n $

flowchart LR
	subgraph addGroup["$$u + v$$"]
		direction TB
		addSet["abelian group under addition"]
	end
	subgraph scalarGroup["$$\lambda v$$"]
		direction TB
		scalarSet["&bull; associativity<br/>&bull; 1"]
	end
	addSet <-->|distributive<br/>properties| scalarSet
	style addGroup fill:transparent,stroke:transparent
	style scalarGroup fill:transparent,stroke:transparent

Examples

• $ \mathbf{F}^S $
• $ \mathcal{P}(\mathbf{F}) $
• $ \mathcal{P}_m(\mathbf{F}) $
• $ \mathcal{L}(V, W) $ ($ \dim = (\dim V)(\dim W) $)
• $ \mathbf{F}^{m,n} $ ($ \dim = mn $)
• $ V_1 \times \dots \times V_m $ ($ \dim = \dim V_1 + \dots + \dim V_m $)
• $ V/U $ ($ \dim = \dim V - \dim U $)

Subspace

Examples

• $ V_1 \cap \dots \cap V_m $
• $ V_1 \cup V_2 $ ($ \Leftrightarrow V1 \subseteq V2 $ or $ V1 \supseteq V2 $)
• $ V_1 + \dots + V_m $ (Smallest containing subspace)
• $ U^0 $ ($ \dim = \dim V - \dim U $)

Suppose $V$ is finite-dimensional. $ U $ is a subspace of $ V $:

• $ \dim U \leq \dim V $
• $ \dim U = \dim V \Leftrightarrow U = V $

Sum

Analogy between sets and vector spaces:

• Cardinality: Dimension
• Union: Sum
• Union of disjoint sets: Direct sum

Number of Vectors

The number of vectors equals the number of choices of the coefficient tuple $(a_1, \dots, a_n)$:

\[\#(\text{vectors}) = \lvert \mathbf{F} \rvert ^n\]

Finite fields exist precisely for prime-power sizes $q = p^k$.

	over $\mathbb{R}$ or $\mathbb{C}$	over $\mathbf{F}_q$
trivial space	$1$	$1$
dimension $n \geq 1$	$\infty$	$q^n$

Bases

A list is a basis if it satisfies any two of the following three conditions:

• It is linearly independent
• It spans $V$
• Its length equals $ \dim(V) $

A direct-sum decomposition of $ V $ is the same thing as a partition of a basis of $ V $.

A sum is a direct sum iff dimensions add up.

---

Linear Maps

Examples

• $ T : V \to W $
• $ \Gamma : V_1 \times \dots \times V_m \to V_1 + \dots + V_m $ (Invertible iff $ V_1, \dots, V_m $ is a direct sum)
• Quotient map: $ \pi : V \to V/U $, $ \pi(v) = v + U $
  • $ \tilde{T} ∶ V/(\operatorname{null} T) \to W $, $ \tilde{T}(v + \operatorname{null} T) = Tv $
  • $ \tilde{T} \circ \pi = T $
• $ T \to T’ $
• $ P_U \in \mathcal{L}(V) $
• $ (\operatorname{null} T)^{\perp} \to \operatorname{range} T $ (Invertable)
• $ T^{\ast} $

A linear map may be prescribed freely on a basis:

$ \forall \ \text{basis} \ v_1, \dots, v_n \in V $ and $ \forall w_1, \dots, w_n \in W $, $ \exists! T \in \mathcal{L}(V, W) \ \text{s.t.} $

\[Tv_k = w_k\]

for each $k = 1, \dots, n$

Extension

$ V $ is finite-dimensional:

$ U $ is a subspace of $ V $, $ S \in \mathcal{L}(U, W) \Rightarrow \exists T \in \mathcal{L}(V, W) \ \text{s.t.} \ T \vert _U = S $

Extend a basis $ u_1,\dots,u_m$ of $U $ to a basis $ u_1,\dots,u_m,\,v_1,\dots,v_n $ of $ V $. Define $ T u_i = S u_i $ and $ T v_j = $ anything in $ W $; extend linearly.

Algebraic Operations

• $ \mathcal{L}(V, W) $ is a vector space
• Product of linear maps is a bilinear map

Null Spaces and Ranges

Fundamental theorem of linear maps

Suppose $V$ is finite-dimensional. $ T \in \mathcal{L}(V, W) $:

\[\dim V = \dim \operatorname{null} T + \dim \operatorname{range} T\]

Generalization

Suppose $V$ is finite-dimensional. $ T \in \mathcal{L}(V, W) $, $ U $ is a subspace of $ W $:

\[\dim \{ v \in V : Tv \in U \} = \dim \operatorname{null} T + \dim (U \cap \operatorname{range} T)\]

Injectivity, Surjectivity and Invertibility

Suppose $ T \in \mathcal{L}(V, W) $.

(a) If $ T $ is injective, then it’s invertible from $ V $ to $ \operatorname{range} T $.

(b) Decompose $ V = \operatorname{null} T \oplus U $, then $(\left. T \right\rvert_{U})$ is invertible.

$ \Leftrightarrow $

$ T \in \mathcal{L}(V, W) $	Injective	Surjective	Invertible (Isomorphic)
Definition	$ \operatorname{null} T = {0} $	$ \operatorname{range} T = W $	$ T $ is injective and $ T $ is surjective
Preservation	linear independence	spanning	basis
Inverse	$ T $ has a left inverse: $ ST = I $	$ T $ has a right inverse: $ TS = I $	$ T $ has the inverse: $ ST = I $ and $ TS = I $

$ \Rightarrow $

$ T \in \mathcal{L}(V, W) $	Injective	Surjective	Invertible (Isomorphic)
Dimensions (Finite)	$ \dim V \leq \dim W $	$ \dim V \geq \dim W $	$ \dim V = \dim W $
$\dim V = \dim W$	(all three coincide)	(all three coincide)	(all three coincide)
Pseudoinverse	$ TT^{\dagger} = I $	$ T^{\dagger}T = I $	$ TT^{\dagger} = T^{\dagger}T = I $

Product

Suppose $U$ and $V$ are finite-dimensional. $ S \in \mathcal{L}(V, W) $ and $ T \in \mathcal{L}(U, V) $:

• $ \operatorname{null} T \subseteq \operatorname{null} ST $
• $ \operatorname{range} ST \subseteq \operatorname{range} S $

Suppose $ U $ and $ V $ are finite-dimensional. $ S \in \mathcal{L}(V, W) $ and $ T \in \mathcal{L}(U, V) $:

• $ \dim \operatorname{null} ST \leq \dim \operatorname{null} S + \dim \operatorname{null} T $
• $ \dim \operatorname{range} ST \leq \min(\dim \operatorname{range} S + \dim \operatorname{range} T) $

Suppose $ V $ is finite-dimensional and $ S, T \in \mathcal{L}(V, W) $:

• $ ST $ is invertible $\Leftrightarrow$ $ S $ and $ T $ are invertible.

Translate

Re-basing

Suppose $ U $ is a subspace of $ V $ and $ v,w \in V $. Then

\[x \in v + U \Leftrightarrow x + U = v + U.\]

Corollary: Two translates of a subspace are equal or disjoint.

\[v - w \in U \Leftrightarrow v + U = w + U \Leftrightarrow (v + U) \cap (w + U) \ne \emptyset\] \[v \in U \Leftrightarrow v + U = 0 + U.\]

Suppose $ A_1 = v + U_1 $ and $ A_2 = w + U_2 $ for some $ v,w \in V $ and some subspaces $ U_1,U_2 $ of $ V $.

\[\forall x \in A_1 \cap A_2, \ A_1 \cap A_2 = (x + U_1) \cap (x + U_2) = x + (U_1 \cap U_2).\]

Suppose $ T \in \mathcal{L}(V,W) $ and $ c \in W $:

$ {x \in V : Tx = c} $ is either the empty set or is a translate of $ \operatorname{null} T $.

Special case: system of linear equations

general solution = particular solution + homogeneous solution

$ V/\operatorname{null} T \cong_\tilde{T} \operatorname{range} T $

Bases

Suppose $ U $ and $ W $ are subspaces of $ V $ and $ V = U \oplus W $. $\pi|_W : W \to V/U$ is an isomorphism.

Duality (Project, function)

Suppose $ U $ and $ W $ are subspaces of $ V $ and $ V = U \oplus W $. Suppose $ w_1, \dots, w_m $ is a basis of $ W $. Then $ w_1 + U, \dots, w_m + U $ is a basis of $ V/U $.

Duality (Lift, one-to-many)

Suppose that $ U $ is a subspace of $ V $ such that $ V/U $ is finite-dimensional. There exists a finite-dimensional subspace $ W $ of $ V $ such that $ \dim W = \dim V/U $ and $ V = U \oplus W $.

Since $V/U$ is finite-dimensional, pick a basis

\[v_1 + U,\ \dots,\ v_m + U \quad (m = \dim V/U),\]

with chosen representatives $v_1, \dots, v_m \in V$. Define

\[W := \operatorname{span}(v_1, \dots, v_m).\]

We show this $W$ works: it’s finite-dimensional, $\dim W = m = \dim V/U$, and $V = U \oplus W$.

The $v_k$ are linearly independent (so $\dim W = m$). Suppose $\sum_k a_k v_k = 0$. Apply $\pi$:

\[0 + U = \pi\Big(\sum_k a_k v_k\Big) = \sum_k a_k (v_k + U).\]

Since $v_1 + U, \dots, v_m + U$ is a basis of $V/U$, it’s independent, so all $a_k = 0$. Thus $v_1, \dots, v_m$ is independent and $\dim W = m = \dim V/U$.

$U + W = V$. Let $v \in V$. Expand its coset in the basis: $v + U = \sum_k a_k (v_k + U) = \big(\sum_k a_k v_k\big) + U$. Equal cosets differ by an element of $U$:

\[v - \sum_k a_k v_k \in U \quad\Longrightarrow\quad v = \underbrace{\Big(v - \sum_k a_k v_k\Big)}_{\in\, U} + \underbrace{\sum_k a_k v_k}_{\in\, W} \in U + W.\]

$U \cap W = {0}$. Let $x \in U \cap W$. Since $x \in W$, write $x = \sum_k a_k v_k$. Since $x \in U$, $\pi(x) = 0$:

\[0 + U = \pi(x) = \sum_k a_k (v_k + U).\]

Independence of the basis forces all $a_k = 0$, so $x = 0$.

Therefore $V = U \oplus W$ with $\dim W = \dim V/U$. $\blacksquare$

Suppose $ U $ is a subspace of $ V $ and $ v_1 + U, \dots, v_m + U $ is a basis of $ V/U $ and $ u_1, \dots, u_n $ is a basis of $ U $. Then $ v_1, \dots, v_m, u_1, \dots, u_n $ is a basis of 𝑉.

Isomorphism

• $ V/\operatorname{null} T \cong_\tilde{T} \operatorname{range} T $
• $ \mathcal{L}(V, W) \cong \mathbf{F}^{m,n} $
• $ V \cong \mathcal{L}(\mathbf{F}, V) $
• $ V^m \cong \mathcal{L}(\mathbf{F}^m, V) $
• $ V \cong U \times V/U $

---

Matrices

$ \mathcal{M}(T,(v_1,\dots,v_n),(w_1,\dots,w_m)) \in \mathbf{F}^{m,n} $ is the matrix representation of $ T $ with respect to the chosen bases.

\[Tv_k = \sum_{j=1}^m {A_{j,k}w_j}\]

$ T \in \mathcal{L}(\mathbf{F}^n, \mathbf{F}^m) $, $ \mathcal{M}(T,(e_1, \dots, e_n), (e_1, \dots, e_m))_{\cdot,k} = Te_k $

Column of matrix product equals matrix times column

Linear combination of columns

$ \dim \operatorname{range} S = \text{rank} \, \mathcal{M}(T) $

Column–row factorization

$ C $ is a basis of the column space.

$ A \mapsto A^T $ is a linear map

Change-of-basis

\[\mathcal{M}(I,(u_1,\dots,u_n),(v_1,\dots,v_n))\mathcal{M}(I,(v_1,\dots,v_n),(u_1,\dots,u_n)) = I\]

$ T \in \mathcal{L}(V) $, $ A = \mathcal{M}(T,(u_1,\dots,u_n)), B = \mathcal{M}(T,(v_1,\dots,v_n)), C = \mathcal{M}(I,(u_1,\dots,u_n),(v_1,\dots,v_n))$:

\[A = C^{-1}BC\]

Dual Space and Dual Map

• $ T $ is injective $ \Leftrightarrow $ $ T’ $ is surjective

• $ T $ is surjective $ \Leftrightarrow $ $ T’ $ is injective

• $ \operatorname{null} T’ = (\operatorname{range} T)^0 $

• $ \operatorname{range} T’ = (\operatorname{null} T)^0 $

• $ \dim \operatorname{null} T’ = \dim \operatorname{null} T + \dim W - \dim V $
• $ \dim \operatorname{range} T’ = \dim \operatorname{range} T $