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}) $

	$ \dim $
$ \mathcal{L}(V, W) $	$ (\dim V)(\dim W) $
$ \mathbf{F}^{m,n} $	$ mn $
$ V_1 \times \dots \times V_m $	$ \dim V_1 + \dots + \dim V_m $
$ V’ $	$ \dim V $
$ \mathcal{B}(V, W) $	$ (\dim V)(\dim W) $

Subspace

Examples

• $ V_1 \cap \dots \cap V_m $
• $ V_1 \cup V_2 $ ($ \Leftrightarrow V_1 \subseteq V_2 $ or $ V_1 \supseteq V_2 $)
• $ V_1 + \dots + V_m $ (Smallest containing subspace)

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

	$ \dim $
$ U $	$ \leq \dim V $ ($ = \dim V \iff U = V $)
$ V/U $	$ \dim V - \dim U $
$ U^0 $	$ \dim V - \dim U $
$ U^{\perp} $	$ \dim V - \dim U $
$ E(\lambda, T) $	algebraic multiplicity
$ G(\lambda, T) $	geometric multiplicity

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$
#{ordered bases}	$\infty$	\(\lvert GL_n(\mathbf{F}_q) \rvert = \prod_{k=0}^{n-1}(q^n - q^k)\)

Bases

Suppose we allow infinite families, read “spans/independent” in the finite-linear-combination sense, and read “length $= \dim V$” as “cardinality equals $\dim V$” (a Hamel basis).

(a) Take $V = \mathcal P(\mathbb F)$, polynomials, with basis $1, x, x^2, \dots$ so $\dim V = \aleph_0$. Then ${x, x^2, x^3, \dots}$ (drop the constant) is linearly independent with cardinality $\aleph_0 = \dim V$, yet it can’t produce the constant $1$, so it doesn’t span — independent, right size, not a basis.

(b) ${1, x, x^2, \dots} \cup {1+x}$ spans and still has cardinality $\aleph_0$, but it’s dependent — spanning, right size, not a basis.

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

$ \dim (V_1 + \dots + V_m) \le \dim V_1 + \dots + \dim V_m $

A sum is a direct sum iff dimensions add up.

Direct Sum Decomposition

• Suppose $T \in \mathcal{L}(V)$. $V = \dim \operatorname{null} T^m = \dim \operatorname{null} T^{m + 1} $.
• Suppose $\mathbf{F} = \mathbb{C}$ and $T \in \mathcal{L}(V)$. $ V = \oplus G(\lambda, T)$.
• Suppose $V$ is finite-dimensional, $T \in \mathcal{L}(V)$ and $T$ is diagonalizable. $ V = \oplus E(\lambda, T)$.

Suppose $\mathbf{F} = \mathbb{C}$ and $T \in \mathcal{L}(V)$. Then

There does not exist a direct sum decomposition of $V$ into two nonzero subspaces invariant under $T$ $iff$ the minimal polynomial of $T$ is of the form $(z - \lambda)^{\dim V}$ for some $\lambda \in \mathbb{C}$.

If $v_1,\dots,v_n$ is a basis, then replacing $v_i$ by $v_i + c\,v_j$ for any $j \neq i$ and any scalar $c$ again gives a basis. (

It’s an elementary column operation; invertibility is obvious because you can undo it.

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:

Suppose $ v_1, \dots, v_n \in V $ is a basis of $ V $ and $ 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$

$ T(c_1v_1 + \dots + c_nv_n) = c_1w_1 + \dots + c_nw_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)\]

Cokernel

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

\[\operatorname{coker}T = W/\operatorname{range}T.\]

Cokernel is the dual of the null space: $\operatorname{null}T$ measures failure of injectivity, $\operatorname{coker}T$ measures failure of surjectivity, and $T$ is onto iff $\operatorname{coker}T = 0$.

Injectivity, Surjectivity and Invertibility

Inveritibility Triangle

In infinite dimensions $ST = I$ does not imply $TS = I$. The standard counterexample is the shift operators on infinite sequences: left‑shift $L$ and right‑shift $R$ satisfy $LR = I$ but $RL \ne I$, and neither is invertible.

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

(a) If $ T $ is injective, the co-restriction $ \tilde T : V \to \operatorname{range} T $, $ v \mapsto Tv $, is a bijection.

(b) Decompose $ V = \operatorname{null} T \oplus U $, then $T\rvert_U : U \to \operatorname{range} T$ is an isomorphism.

$ \iff $

$ 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 $
Complexification	$ T_{\mathbb{C}} $ is injective	$ T_{\mathbb{C}} $ is surjective	$ T_{\mathbb{C}} $ is invertible
Dual map	$ T’ $ is surjective	$ T’ $ is injective	$ T’ $ is invertible
$ \mathcal{M}(T) \in \mathbf{F}^{m,n} $	columns linearly independent; rows span $ \mathbf{F}^{1,n} $; $ \operatorname{rank} = n $	rows linearly independent; columns span $ \mathbf{F}^{m,1} $; $ \operatorname{rank} = m $	columns are a basis; rows are a basis; $ \operatorname{rank} = m = n $
$ T^m $	$ T^m $ is injective	$ T^m $ is surjective	$ T^m $ is invertible
Singular value	$ 0 $ is not a singular value of $ T $	#(positive singular values of $ T $) = $ \dim W $

$ \implies $

$ 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 $

$ \iff $

$ T \in \mathcal{L}(V) $	Invertible
Minimal polynomial	Constant term is not $0$

$ \lambda $ is an eigenvalue of $ T \iff T - \lambda I $ is not invertible

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) $, then

$ ST $ is invertible $\iff$ $ S $ and $ T $ are invertible.

Isomorphism

• $ V/\operatorname{null} T \cong_\tilde{T} \operatorname{range} T, \quad \tilde{T} ∶ V/(\operatorname{null} T) \to W $, $ \tilde{T}(v + \operatorname{null} T) = Tv $
• $ \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} T = \operatorname{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\]

$ T \in \mathcal{L}(V, W) $	Inverse	Dual Map	Adjoint
Existence	Inveritibility Triangle
Uniqueness	$ T^{-1} \in \mathcal{L}(W, V) $
Matrix	$ \mathcal{M}(T^{-1}) = (\mathcal{M}(T))^{-1} $	$ \mathcal{M}(T’) = (\mathcal{M}(T))^t $	$ \mathcal{M}(T^{*}) = (\mathcal{M}(T))^{*} $
Involution	$ (T^{-1})^{-1} = T $		$ (T^{*})^{*} = T $
Anti-homomorphism	$ (ST)^{-1} = T^{-1}S^{-1} $	$ (ST)’ = T’S’ $	$ (ST)^{*} = T^{*}S^{*} $

	$ \mathbb{C} $	$ \mathbb{R} $
Polynomial factorization (unique)	$ p(z) = c(z - \lambda_1)\dots(z - \lambda_m) $	$ p(x) = c(x - \lambda_1)\dots(x - \lambda_m)(x^2 + b_1x + c_1)\dots(x^2 + b_Mx + c_M) $
#{zeros of a polynomial} (counted with multiplicity)	$ m = \deg p $	$ \le \deg p $
Existence of eigenvalues ($ \forall T $)	Nonzero complex vector space	Odd-dimension real vector space

$ T \in \mathcal{L}(V, W) $	null space	range	$ \dim \operatorname{null} $	$ \dim \operatorname{range} $	norm
$ T’ $	$ (\operatorname{range} T)^0 $	$ (\operatorname{null} T)^0 $	$ \dim \operatorname{null} T + \dim W - \dim V $	$ \dim \operatorname{range} T $
$ T^{*} $	$ (\operatorname{range} T)^{\perp} $	$ (\operatorname{null} T)^{\perp} $			$ \left\lVert T \right\rVert $
$ T^{*}T $	$ \operatorname{null} T $	$ \operatorname{range} T^{*} $		$ \dim T = \dim T^{*} $