Linear Algebra

This is not a beginners guide to linear algebra. It is a breviloquent collection of pertinent facts about vector spaces and the linear transformations between them. Although it is complete and self-contained you should already be familiar with basic linear algebra before reading this. Statements and proofs are concise, so read them twice. Do the exercises to confirm your understanding.

I make no apologies for the shamelessly mathematical exposition and hope it engenders an appeciation for the thrill of literally ‘doing the math’ to unequivocally establish absolute truth.

Introduction

Vector spaces occupy a sweet spot in the menagerie of mathematical structures. They are completely classified up to isomorphism by their dimension. A vector space is an abelian group with a scalar multiplication that satisfies a distributive law with respect to the vector addition. A vector is not just a list of numbers, it is a mathematical object that satisfies these axioms. For example, functions are vectors and linear transformations between vector spaces are also vectors.

A linear transformation is a function between vector spaces that preserves the vector space structure. They are completely classified up to similarity for finite dimensional vector spaces by their eigenvalues and the multiplicity of each eigenvalue

Vector Space

The ingredients of a vector space are a set V of vectors and a binary addition that satisfies the abelian group axioms:

Associative: x + (y + z) = (x + y) + z for x,y,z\in V.
Commutative: x + y = y + x for x,y\in V.
Identity: There is a 0\in V with x + 0 = x for x\in V.
Inverse: Every vector has an additive inverse -x with x + (-x) = 0.

A vector space also specifies a field of scalars \bm{F} (usually the real \bm{R} or complex \bm{C} numbers) and a scalar multiplication that satisfies

Distributive: \alpha (x + y) = \alpha x + \alpha y, for \alpha\in\bm{F} and x,y\in V.

Lemma. For any vector x, x + x = x implies x = 0. \begin{aligned} x + x &= x & & \\ (x + x) + (-x) &= x + (-x) &\mathrm{substitution} \\ x + (x + (-x)) &= x + (-x) &\mathrm{associative} \\ x + 0 &= 0 &\mathrm{inverse} \\ x &= 0 &\mathrm{identity} \\ \end{aligned}

By substitution we mean that if P(x) is a logical statement containing the symbol x we can replace each occurence of x by any other symbol y, x\mapsto y, as long as y does not occur in P(x). Using the true statement a = b \Rightarrow a + c = b + c we make the substitutions a \mapsto x + x, b \mapsto x, and c \mapsto (-x) then use modus ponens.

Exercise. Show the additive identity is unique.

Hint. If 0' is another identity then 0 = 0 + 0'. Your proof can be used for any group, abelian or not.

Exercise. Show for x\in V that (-1)x = -x.

Hint. The left hand side is the scalar multiplication of -1\in\bm{F} by x. The right hand side is the additive inverse of x. You need to show x + (-1)x = 0. Use the distributed law.

Exercise. Show for x\in V that -(-x) = x.

If \bm{F}^X = \{f\colon X\to \bm{F}\} is the set of all functions from X to \bm{F} we can define (f + g)(x) = f(x) + g(x) and (\alpha f)(x) = \alpha f(x) for f,g\in\bm{F}^X and \alpha\in\bm{F}. It is customary to write c(X) for this space.

Exercise. Show c(X) is a vector space.

The functions in c(X) that are zero except at a finite number of elements of X is customarily written c_{00}(X). If X is finite then \bm{F}^X = c_{00}(X). If X has n elements it is customary to write \bm{F}^n = \{(x_1,\ldots,x_n):x_j\in\bm{F}, 1\le j\le n\}.

Exercise. Show c_{00}(X) is a vector space.

If X = \bm{N} is the set of natural numbers define c_0(\bm{N}) = c_0 to be the functions v\in c(\bm{N}) such that \lim_{n\to\infty} v(n) = 0.

Exercise. Show c_0 is a vector space.

The vector space c_{00}(X) has an inner product defined by v\cdot w = \sum_{x\in X} v(x) w(x) = \sum_{x\in X} v_x w_x for v,w\in c_{00}(X). Since multiplication in \bm{F} is commutative v\cdot w = w\cdot v.

Exercise. Show (\alpha u + \beta v)\cdot w = \alpha(u\cdot w) + \beta(v\cdot w) for \alpha, \beta\in\bm{F} and u,v,w\in c_{00}(X).

Exercise. Show v\cdot v = 0 implies v = 0 for v\in c_{00}(X).

Define the Kronecker delta function \delta_x\in c_{00}(X) by \delta_x(y) = 1 if y = x and \delta_x(y) = 0 if y \not= x.

Exercise. Show v = \sum_{x\in X} (v\cdot\delta_x) \delta_x for v\in c_{00}(X).

This shows the set \{\delta_x:x\in X\} spans c_{00}(X).

Span

If x\in V then \bm{F}\{x\} = \{\alpha x:\alpha \in\bm{F}\} is the one-dimensional subspace spanned by x.

Exercise. Show \bm{F}\{x\} is the smallest subspace of V containing x.

More generally, let X be any collection of vectors in V. The span of the collection is the smallest subspace of V containing X and is denoted \operatorname{span}X or \vee X.

A linear combination of vectors is a finite sum \sum_j \alpha_j x_j where \alpha_j\in\bm{F} and x_j\in V.

Exercise. Show the span of X is the set of all linear combinations of vectors from X.

Exercise. Show the span of X is a vector space.

Subspace

A subset U of a vector space V is a subspace if U is also a vector space.

Exercise. Show U\subseteq V is a subspace if and only if \bm{F} U\subseteq U and U + U\subseteq U.

We use the notation \bm{F} U = \{\alpha x:\alpha \in\bm{F}, x\in U\} and U + U = \{x + y:x\in U, y\in U\}.

Exercise. If U and W are subspaces then U + W and U\cap W are also subspaces.

If U\cap W = \{0\} then U + W is called an interal sum.

Exercise. Let U and W be subspaces of V with U\cap W = \{0\}. If u + w = u' + w' with u,u'\in U and w,w'\in W show u = u' and w = w'.

Hint. u - u'\in U and w' - w\in W.

This shows every vector v\in U + W has a unique decomposition v = u + w with u\in U and w\in W whenever U\cap W = \{0\}.

Lattice of Subspaces

Subspaces of a vector space form a lattice where + is the join and \cap is the meet. Since U + V = V for all subspaces U, V is the identity element of the join. Since U \cap \{0\} = \{0\} for all subspaces U, \{0\} is the identity element of the meet.

Exercise. (Absorbtion laws) If U and W are subspaces then U + (U \cap W) = U and U\cap(U + W) = U.

The lattice of subspaces is also distributive.

Exercise. (Distributive laws) If U, V, and W are subspaces then U \cap (V + W) = (U \cap V) + (U \cap W) and U + (V\cap W) = (U + V)\cap(U + W).

Either of these implies the other in any lattice. This was not noticed until some time after the the invention of lattice theory. [cite??]

Subspaces of V form a bounded lattice with top element V and bottom element \{0\}.

The lattice structure of subspaces is used in Quantum Mechanics. [cite?]

Independent

A key property of a collection of vectors is independence. A collection of vectors X in the vector space V are independent if every linear combination \sum_j \alpha_j x_j = 0 where \alpha_j\in\bm{F} and x_j\in X implies \alpha_j = 0 for all j. Note that the empty set is independent.

Exercise. If X is independent and \sum_j \alpha_j x_j = \sum_j \beta_j x_j where \alpha_j,\beta_j\in\bm{F} and x_j\in X show \alpha_j = \beta_j for all j.

Independence ensures unique representations of linear combinations.

If \sum_j \alpha_j x_j = 0 and \alpha_k\not = 0 for some k then x_k = -(1/\alpha_k)\sum_{j\not=k} \alpha_j x_j is a linear combination of vectors in X\setminus \{x_k\}. In this case X is linearly dependent and X\setminus\{x_k\} has the same span as X. We use reverse solidus for A\setminus B = \{x\in A: x\notin B\}, the set difference.

Basis

A basis of V is an independent set X\subseteq V that spans V. Every vector space has a basis. In fact, they have lots of basis’. The cardinality of the basis is the dimension of the vector space. To show dimension is well-defined we must show the cardinality of any two basis’ are equal. Neither of these facts are trivial.

Exercise. Show \{\delta_x:x\in X\} is a basis of c_{00}(X).

Exercise. If X\subseteq V is independent and y\not\in\vee X show X\cup\{y\} is independent.

If an independent set does not span a vector space we can always add an element to the set to get a larger independent set. This process eventually stops if the vector space is finite dimensional. The proof for (possibly) infinite dimensional spaces requires more machinery.

Let \mathcal{C} be a collection of independent subsets of V that is totally ordered by inclusion, that is, given X,Y\in\mathcal{C} either X\subseteq Y or Y\subseteq X. Any such collection is a chain.

Exercise. Show for any chain \mathcal{C} that \cup\mathcal{C} = \cup_{X\in\mathcal{C}} X is independent.

Exercise. Prove every vector space has a basis.

Hint: Use the previous exercises and Zorn’s lemma.

To prove any two basis’ have the same cardinality we need linear transformations.

Linear Transformation

A linear tranformation is a function from a vector space to a vector space that preserves the vector space structure.

If V and W are vector spaces over the same field \bm{F} then a function T\colon V\to W is a linear transformation if T(\alpha x + y) = \alpha Tx + T y for \alpha \in\bm{F} and x,y\in V. Note the addition and scalar multiplicate on the left-hand side of the equality are those of V and on the right-hand side are those of W.

Exercise. Show T(\alpha x + \beta y) = \alpha Tx + \beta T y for \alpha,\beta \in\bm{F} and x,y\in V.

The set of all linear transformations from V to W is denoted \mathcal{L}(V,W). The sum of T,S\in \mathcal{L}(V,W) is defined by (T + S)v = Tv + Sv for v\in V. If \alpha\in\bm{F} define \alpha T by (\alpha T)v = \alpha(T v) for v\in V.

Exercise. Show \mathcal{L}(V,W) is a vector space.

If T\in\mathcal{L}(c_{00}(X), c_{00}(Y)) then T\delta_x = \sum_{y\in Y} t_{xy} \delta_y for some t_{xy}\in\bm{F} where \{y\in Y:t_{xy}\not=0\} is finite. If S\in\mathcal{L}(c_{00}(Y), c_{00}(Z)) then S\delta_y = \sum_{z\in Z} s_{yz} \delta_z for some s_{yz}\in\bm{F} where \{z\in Z:s_{yz}\not=0\} is finite.

Exercise. Show (ST)\delta_x = \sum_{z\in Z}(\sum_{y\in Y} t_{xy} s_{yz})\delta_z.

This shows if R = ST then \sum_{y\in Y} t_{xy} s_{yz} = r_{xz}. Matrix multiplication calculates composition of linear transformations.

The kernel of a linear transformation T\colon V\to W is \ker T = \{v\in V:Tv = 0\}.

Exercise. Show the kernel of a linear transformation is a vector space.

A linear transformation is injective if Tx = Ty implies x = y.

Exercise. Show a linear transformation is injective if and only if its kernel is \{0\}.

The range of a linear transformation T\colon V\to W is \operatorname{ran}T = \{Tv\in W:v\in V\}. If \operatorname{ran}T = W we say T is surjective.

Exercise. Show the range of a linear transformation is a vector space.

A linear transformation that is bijective (injective and surjective) is an isomorphism from V to W. We write V\cong W if such an operator exists and say V is isomorphic to W.

Exercise. Show \cong is an equivalence relation on vector spaces.

This means V\cong V, V\cong W implies W\cong V, and U\cong V and V\cong W implies U\cong W for vector spaces U, V, and W.

If W = V we write \mathcal{L}(V) for \mathcal{L}(V,V) and call the tranformations endomorphisms of V. If U\subseteq V and T is an endomorphism on V then U is invariant for T if TU\subseteq U.

Exercise. Show the kernal and range of an endomorphism are invariant.

Exercise. Show for any linear transformation T\colon V\to V with T^2 = T that \ker T + \operatorname{ran}T = V and \ker T\cap\operatorname{ran}T = \{0\}.

Hint: v = (v - Tv) + Tv for all v\in V.

An endomorphism T with T^2 = T is a projection. Every vector space is the internal sum of the kernel and range of any projection.

Exercise. Every subspace is the range of a projection.

Hint: Let X be a basis of U and Y\supseteq X be a basis of V. Every vector in v can be written v = \sum_{x\in X}\alpha_x x + \sum_{y\in Y\setminus X} \beta_y y. Define Pv = \sum_{x\in X}\alpha_x x. Show U is the range of P and P^2 = P.

Exercise. If J\colon U\to V is inclusion and P\colon V\to U is a projection, show PJ is the identity operator on U.

Two endomorphisms R,T on V are similar if there exists an isomorphism S with R = S^{-1}TS. We write R\simeq T if so.

Exercise. Show similarity is an equivlence relation on endomorphisms.

Hint: S_0^{-1}S_1 = (S_1^{-1}S_0)^{-1} if S_0 and S_1 are isomorphisms.