Vector Spaces
Definition: Vector Space
A real vector space is a nonempty set \(V\) of vectors on which are defined
addition and scalar multiplication, satisfying the following eight axioms.
For all \(\mathbf{u}, \mathbf{v}, \mathbf{w} \in V\) and scalars \(c, d \in \mathbb{R}\):
- Commutativity of vector addition: \(\mathbf{u} + \mathbf{v} = \mathbf{v} + \mathbf{u}\).
- Associativity of vector addition: \((\mathbf{u} + \mathbf{v}) + \mathbf{w} = \mathbf{u} + (\mathbf{v} + \mathbf{w})\).
- Existence of an additive identity: there is a vector \(\mathbf{0} \in V\) with \(\mathbf{u} + \mathbf{0} = \mathbf{u}\) for every \(\mathbf{u} \in V\).
- Existence of an additive inverse: for every \(\mathbf{u} \in V\) there exists \(-\mathbf{u} \in V\) such that \(\mathbf{u} + (-\mathbf{u}) = \mathbf{0}\).
- Existence of a multiplicative identity: \(1\mathbf{u} = \mathbf{u}\).
- Distributivity of scalar multiplication over vector addition: \(c(\mathbf{u} + \mathbf{v}) = c\mathbf{u} + c\mathbf{v}\).
- Distributivity of scalar multiplication over scalar addition: \((c + d)\mathbf{u} = c\mathbf{u} + d\mathbf{u}\).
- Compatibility of scalar multiplication: \(c(d\mathbf{u}) = (cd)\mathbf{u}\).
These axioms abstract the essential algebraic properties of \(\mathbb{R}^n\). By identifying which properties are fundamental, we can recognize
vector space structure in many mathematical objects beyond \(\mathbb{R}^n\), including spaces of functions, polynomials, matrices, and solutions to
differential equations. Any set satisfying these eight axioms behaves algebraically like \(\mathbb{R}^n\), allowing us to extend linear algebra
techniques to these more general settings.
From now on, the term "vector space" refers to a real vector space. If the context requires a complex vector space, where
scalars \(c, d \in \mathbb{C}\), this will be explicitly mentioned. The general case, replacing \(\mathbb{R}\) by an arbitrary field, is developed
in the upcoming section on abstract algebra, where fields and field-theoretic constructions are introduced.
The most immediate example of a vector space is \(\mathbb{R}^n\) for \(n \geq 1\). This is why the concept is introduced at this point in the
curriculum. The abstraction generalizes the familiar arithmetic of \(\mathbb{R}^n\) to a broader setting.
Several immediate consequences follow from the axioms. For every \(\mathbf{u} \in V\) and every scalar \(c\):
\[
\begin{align*}
0\mathbf{u} &= \mathbf{0} \\\\
c\mathbf{0} &= \mathbf{0} \\\\
-\mathbf{u} &= (-1)\mathbf{u} \\\\
c\mathbf{u} = \mathbf{0} &\Longrightarrow c = 0 \text{ or } \mathbf{u} = \mathbf{0}.
\end{align*}
\]
As a representative derivation, we prove the first: \(0\mathbf{u} = \mathbf{0}\). By axiom 7 (distributivity over scalar addition),
\(0\mathbf{u} = (0 + 0)\mathbf{u} = 0\mathbf{u} + 0\mathbf{u}\). Adding the additive inverse \(-(0\mathbf{u})\) (axiom 4) to both sides and using
associativity (axiom 2),
\[
\begin{align*}
\mathbf{0} &= 0\mathbf{u} + \bigl(-(0\mathbf{u})\bigr) \\\\
&= \bigl(0\mathbf{u} + 0\mathbf{u}\bigr) + \bigl(-(0\mathbf{u})\bigr) \\\\
&= 0\mathbf{u} + \bigl(0\mathbf{u} + (-(0\mathbf{u}))\bigr) \\\\
&= 0\mathbf{u} + \mathbf{0} \\\\
&= 0\mathbf{u}.
\end{align*}
\]
The remaining three consequences follow by analogous short arguments. For \(c\mathbf{0} = \mathbf{0}\) use axiom 6. For
\(-\mathbf{u} = (-1)\mathbf{u}\) combine the previous result with axioms 5 and 7. For the last, suppose \(c \neq 0\) and multiply by \(c^{-1}\).
Definition: Vector Subspace
A subspace of a vector space \(V\) is a subset \(H \subseteq V\) satisfying:
- The zero vector of \(V\) lies in \(H\): \(\mathbf{0} \in H\).
- \(H\) is closed under vector addition: for all \(\mathbf{u}, \mathbf{v} \in H\), \(\mathbf{u} + \mathbf{v} \in H\).
- \(H\) is closed under scalar multiplication: for all \(\mathbf{u} \in H\) and every scalar \(c\), \(c\mathbf{u} \in H\).
Warning:
For example, the vector space \(\mathbb{R}^2\) is not a subspace of \(\mathbb{R}^3\), because \(\mathbb{R}^2\) is not even a subset of
\(\mathbb{R}^3\). Vectors in \(\mathbb{R}^2\) have two entries, while those in \(\mathbb{R}^3\) have three.
Recall the linear combination of vectors and the
span of a set. The notation
\(\operatorname{Span}\{\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_p\}\) denotes the set of all linear combinations of
\(\mathbf{v}_1, \ldots, \mathbf{v}_p\). Since \(\mathbf{0}\) is the linear combination with all weights zero, and since sums and scalar multiples
of linear combinations of \(\mathbf{v}_1, \ldots, \mathbf{v}_p\) are again linear combinations of them, any span is automatically a subspace. We
record this formally:
Theorem: Span is a Subspace
Let \(V\) be a vector space and \(\mathbf{v}_1, \ldots, \mathbf{v}_p \in V\).
Then \(\operatorname{Span}\{\mathbf{v}_1, \ldots, \mathbf{v}_p\}\) is a subspace of \(V\).
Proof:
Write \(H = \operatorname{Span}\{\mathbf{v}_1, \ldots, \mathbf{v}_p\}\). We verify the three subspace conditions.
(1) \(\mathbf{0} \in H\). Using the consequence \(0\mathbf{v}_i = \mathbf{0}\) of the axioms (noted at the start of this
section),
\[
\mathbf{0} = 0\mathbf{v}_1 + 0\mathbf{v}_2 + \cdots + 0\mathbf{v}_p,
\]
so \(\mathbf{0}\) is a linear combination of the \(\mathbf{v}_i\) with all weights zero. Hence \(\mathbf{0} \in H\).
(2) Closure under addition. Let \(\mathbf{u}, \mathbf{w} \in H\), so
\[
\mathbf{u} = \sum_{i=1}^p c_i \mathbf{v}_i, \quad \mathbf{w} = \sum_{i=1}^p d_i \mathbf{v}_i
\]
for some scalars \(c_i, d_i\). By commutativity and associativity of vector addition (axioms 1-2) and distributivity of scalar multiplication
over scalar addition (axiom 7),
\[
\begin{align*}
\mathbf{u} + \mathbf{w} &= \sum_{i=1}^p c_i \mathbf{v}_i + \sum_{i=1}^p d_i \mathbf{v}_i \\\\
&= \sum_{i=1}^p (c_i + d_i)\mathbf{v}_i,
\end{align*}
\]
which is again a linear combination of the \(\mathbf{v}_i\). Hence \(\mathbf{u} + \mathbf{w} \in H\).
(3) Closure under scalar multiplication. Let \(\mathbf{u} = \sum c_i \mathbf{v}_i \in H\) and let \(c\) be any scalar.
By distributivity of scalar multiplication over vector addition (axiom 6) and compatibility of scalar multiplication (axiom 8),
\[
c \mathbf{u} = c \sum_{i=1}^p c_i \mathbf{v}_i = \sum_{i=1}^p (c c_i) \mathbf{v}_i,
\]
again a linear combination of the \(\mathbf{v}_i\). Hence \(c\mathbf{u} \in H\).
All three subspace conditions hold, so \(H\) is a subspace of \(V\).
Null Space
Having established the general concept of vector spaces and subspaces, we now examine two fundamental subspaces associated with any matrix \(A\):
the null space and the column space. These subspaces encode essential information about the solutions to
\(A\mathbf{x} = \mathbf{b}\) and about the linear transformation \(\mathbf{x} \mapsto A\mathbf{x}\).
Definition: Null Space
The null space of \(A \in \mathbb{R}^{m \times n}\) is the set of all solutions to the homogeneous equation
\(A\mathbf{x} = \mathbf{0}\):
\[
\operatorname{Nul} A = \{\mathbf{x} \in \mathbb{R}^n \mid A\mathbf{x} = \mathbf{0} \in \mathbb{R}^m\}.
\]
Equivalently, \(\operatorname{Nul} A\) is the set of vectors in \(\mathbb{R}^n\) mapped to the zero vector of \(\mathbb{R}^m\) by the linear
transformation \(\mathbf{x} \mapsto A\mathbf{x}\).
More generally, for a linear transformation \(T : V \to W\) between vector spaces (not necessarily a matrix transformation),
the null space is called the kernel of \(T\) and denoted \(\operatorname{Ker} T\):
\[
\operatorname{Ker} T = \{\mathbf{u} \in V \mid T(\mathbf{u}) = \mathbf{0} \in W\}.
\]
Theorem: Null Space is a Subspace
For every \(A \in \mathbb{R}^{m \times n}\), \(\operatorname{Nul} A\) is a subspace of \(\mathbb{R}^n\).
Proof:
We verify the three subspace conditions for \(H = \operatorname{Nul} A \subseteq \mathbb{R}^n\). Along the way we use the fact that
matrix-vector multiplication distributes over vector addition and scalar multiplication, that is,
\(A(\mathbf{u} + \mathbf{v}) = A\mathbf{u} + A\mathbf{v}\) and \(A(c\mathbf{u}) = c(A\mathbf{u})\). Both identities follow from the entrywise
definition of \(A\mathbf{x}\). The Linear Transformation page carries the verification.
(1) \(\mathbf{0} \in \operatorname{Nul} A\). Computing entry by entry, we find that the \(i\)-th entry of \(A\mathbf{0}\) is
\(\sum_{j=1}^n a_{ij} \cdot 0 = 0\), so \(A\mathbf{0} = \mathbf{0}\). Hence \(\mathbf{0} \in \operatorname{Nul} A\).
(2) Closure under addition. Let \(\mathbf{u}, \mathbf{v} \in \operatorname{Nul} A\),
so \(A\mathbf{u} = \mathbf{0}\) and \(A\mathbf{v} = \mathbf{0}\). Then
\[
A(\mathbf{u} + \mathbf{v}) = A\mathbf{u} + A\mathbf{v} = \mathbf{0} + \mathbf{0} = \mathbf{0},
\]
so \(\mathbf{u} + \mathbf{v} \in \operatorname{Nul} A\).
(3) Closure under scalar multiplication. Let \(\mathbf{u} \in \operatorname{Nul} A\) and let \(c\) be a scalar. Then
\[
A(c\mathbf{u}) = c(A\mathbf{u}) = c\mathbf{0} = \mathbf{0},
\]
so \(c\mathbf{u} \in \operatorname{Nul} A\).
All three conditions hold. The identical argument with \(A\) replaced by a general linear transformation \(T : V \to W\)
shows that \(\operatorname{Ker} T\) is a subspace of \(V\).
Example:
Consider the augmented matrix for \(A\mathbf{x} = \mathbf{0}\) and its reduced row echelon form:
\[
\begin{align*}
&\begin{bmatrix} 2 & 4 & 6 & 8 & 0 \\ 1 & 3 & 5 & 7 & 0 \end{bmatrix} \\\\
&\xrightarrow{\operatorname{rref}}
\begin{bmatrix} 1 & 0 & -1 & -2 & 0 \\ 0 & 1 & 2 & 3 & 0 \end{bmatrix}.
\end{align*}
\]
Here \(x_3\) and \(x_4\) are free variables, and the solution can be written as
\[
\begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix}
=
x_3 \begin{bmatrix} 1 \\ -2 \\ 1 \\ 0 \end{bmatrix}
+
x_4 \begin{bmatrix} 2 \\ -3 \\ 0 \\ 1 \end{bmatrix}.
\]
Thus a spanning set for \(\operatorname{Nul} A\) is
\[
\left\{
\begin{bmatrix} 1 \\ -2 \\ 1 \\ 0 \end{bmatrix},
\begin{bmatrix} 2 \\ -3 \\ 0 \\ 1 \end{bmatrix}
\right\}.
\]
Every linear combination of these two vectors lies in \(\operatorname{Nul} A\).
Column Space
While the null space identifies vectors mapped to zero, the column space identifies all possible outputs of the linear transformation
\(\mathbf{x} \mapsto A\mathbf{x}\). Together, the null space and column space give complementary perspectives on the behavior of \(A\). One captures
loss of information, and the other captures reach.
Definition: Column Space and Row Space
The column space of \(A \in \mathbb{R}^{m \times n}\) is the set of all linear combinations of the columns of
\(A = \begin{bmatrix} \mathbf{a}_1 & \mathbf{a}_2 & \cdots & \mathbf{a}_n \end{bmatrix}\):
\[
\begin{align*}
\operatorname{Col} A &= \operatorname{Span}\{\mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_n\} \\\\
&= \{A\mathbf{x} \mid \mathbf{x} \in \mathbb{R}^n\} \subseteq \mathbb{R}^m.
\end{align*}
\]
Equivalently, \(\operatorname{Col} A\) is the range of the linear transformation \(\mathbf{x} \mapsto A\mathbf{x}\).
The row space of \(A\), denoted \(\operatorname{Row} A\), is the column space of \(A^\top\):
\[
\operatorname{Row} A = \operatorname{Col} A^\top \subseteq \mathbb{R}^n.
\]
It is the span of the row vectors of \(A\) (viewed as vectors in \(\mathbb{R}^n\)).
Theorem: Column and Row Spaces are Subspaces
For every \(A \in \mathbb{R}^{m \times n}\), \(\operatorname{Col} A\) is a subspace of \(\mathbb{R}^m\) and \(\operatorname{Row} A\) is
a subspace of \(\mathbb{R}^n\).
Proof:
By definition, \(\operatorname{Col} A = \operatorname{Span}\{\mathbf{a}_1, \ldots, \mathbf{a}_n\}\) where \(\mathbf{a}_i \in \mathbb{R}^m\). The
Span is a Subspace theorem above, applied in \(V = \mathbb{R}^m\),
immediately gives that \(\operatorname{Col} A\) is a subspace of \(\mathbb{R}^m\). The row-space claim follows by the same argument applied to
\(A^\top \in \mathbb{R}^{n \times m}\).
Basis
When describing a subspace, we want a spanning set that contains no redundant vectors, that is, a set where each vector contributes essential
information. This leads to the notion of a basis, the most economical way to describe a subspace.
Definition: Basis
Let \(H\) be a subspace of a vector space \(V\). An indexed set of vectors
\[
\mathcal{B} = \{\mathbf{b}_1, \ldots, \mathbf{b}_p\} \subseteq V
\]
is a basis for \(H\) if
- \(\mathcal{B}\) is linearly independent, and
- \(H = \operatorname{Span}\{\mathbf{b}_1, \ldots, \mathbf{b}_p\}\).
For example, the columns of the identity matrix \(I_n\) form the standard basis for \(\mathbb{R}^n\).
More generally, the columns of any \(n \times n\) invertible matrix form a basis for \(\mathbb{R}^n\),
since by the Invertible Matrix Theorem
those columns are simultaneously linearly independent and span \(\mathbb{R}^n\).
The spanning set we found earlier for \(\operatorname{Nul} A\),
\[
\left\{
\begin{bmatrix} 1 \\ -2 \\ 1 \\ 0 \end{bmatrix},
\begin{bmatrix} 2 \\ -3 \\ 0 \\ 1 \end{bmatrix}
\right\},
\]
is in fact a basis for \(\operatorname{Nul} A\). The set is linearly independent because each basis vector has a \(1\) in its "own" free-variable
coordinate (\(x_3\) or \(x_4\)) and \(0\) in every other free-variable coordinate, so any linear relation among them forces every coefficient to be
\(0\).
For a basis of \(\operatorname{Col} A\), we need a linearly independent spanning set with no redundancy. Consider
\[
\begin{align*}
A &= \begin{bmatrix} 2 & 4 & 6 & 8 \\ 1 & 3 & 5 & 7 \end{bmatrix} \\\\
&\xrightarrow{\operatorname{rref}}
\begin{bmatrix} 1 & 0 & -1 & -2 \\ 0 & 1 & 2 & 3 \end{bmatrix} = B.
\end{align*}
\]
In \(A\), columns \(\mathbf{a}_3\) and \(\mathbf{a}_4\) are linear combinations of earlier columns:
\[
\mathbf{a}_3 = -\mathbf{a}_1 + 2\mathbf{a}_2, \quad \mathbf{a}_4 = -2\mathbf{a}_1 + 3\mathbf{a}_2.
\]
The pivot columns of \(B\) are linearly independent, and since \(A\) is row-equivalent to \(B\), the pivot columns of \(A\), namely
\(\mathbf{a}_1\) and \(\mathbf{a}_2\), form a basis for \(\operatorname{Col} A\):
\[
\left\{
\begin{bmatrix} 2 \\ 1 \end{bmatrix},
\begin{bmatrix} 4 \\ 3 \end{bmatrix}
\right\}.
\]
The representations of \(\mathbf{a}_3\) and \(\mathbf{a}_4\) in terms of \(\mathbf{a}_1\) and \(\mathbf{a}_2\) are unique.
This is a special case of the following general principle.
Theorem: Unique Representation in a Basis
Let \(\mathcal{B} = \{\mathbf{b}_1, \ldots, \mathbf{b}_n\}\) be a basis for a vector space \(V\).
Then for every \(\mathbf{x} \in V\) there exists a unique tuple of scalars \((c_1, \ldots, c_n)\) such that
\[
\mathbf{x} = c_1 \mathbf{b}_1 + \cdots + c_n \mathbf{b}_n.
\]
Proof:
Existence. Since \(\mathcal{B}\) spans \(V\), there exist scalars \(c_1, \ldots, c_n\) with
\[
\mathbf{x} = c_1 \mathbf{b}_1 + \cdots + c_n \mathbf{b}_n. \tag{1}
\]
Uniqueness. Suppose also
\[
\mathbf{x} = d_1 \mathbf{b}_1 + \cdots + d_n \mathbf{b}_n. \tag{2}
\]
Subtracting (2) from (1),
\[
\mathbf{0} = (c_1 - d_1)\mathbf{b}_1 + \cdots + (c_n - d_n)\mathbf{b}_n.
\]
By linear independence of \(\mathcal{B}\), each coefficient vanishes: \(c_i - d_i = 0\), so \(c_i = d_i\) for all \(i\).
The representation is therefore unique.
Coordinate Systems
The uniqueness guaranteed by the Unique Representation theorem means that once we fix a basis \(\mathcal{B}\) for a vector space \(V\),
each vector \(\mathbf{x} \in V\) corresponds to exactly one tuple of scalars.
This establishes a coordinate system on \(V\) relative to \(\mathcal{B}\), and turns the abstract vector space \(V\)
into something we can manipulate with arithmetic in \(\mathbb{R}^n\).
Definition: Coordinate Vector
Let \(\mathcal{B} = \{\mathbf{b}_1, \ldots, \mathbf{b}_n\}\) be a basis for a vector space \(V\), and let \(\mathbf{x} \in V\). The
\(\mathcal{B}\)-coordinates of \(\mathbf{x}\) are the unique scalars \(c_1, \ldots, c_n\) with
\[
\mathbf{x} = c_1 \mathbf{b}_1 + \cdots + c_n \mathbf{b}_n.
\]
The vector
\[
[\mathbf{x}]_{\mathcal{B}} = \begin{bmatrix} c_1 \\ \vdots \\ c_n \end{bmatrix} \in \mathbb{R}^n
\]
is called the coordinate vector of \(\mathbf{x}\) relative to \(\mathcal{B}\), and the assignment
\(\mathbf{x} \mapsto [\mathbf{x}]_{\mathcal{B}}\) is the coordinate mapping.
Theorem: The Coordinate Mapping is a Linear Isomorphism
Let \(\mathcal{B} = \{\mathbf{b}_1, \ldots, \mathbf{b}_n\}\) be a basis for a vector space \(V\). The coordinate mapping
\[
\varphi : V \to \mathbb{R}^n, \quad \varphi(\mathbf{x}) = [\mathbf{x}]_{\mathcal{B}}
\]
is linear, one-to-one, and onto. In other words, \(\varphi\) is a linear isomorphism between \(V\) and \(\mathbb{R}^n\).
Proof:
By the Unique Representation theorem above, \(\varphi\) is a
well-defined function. Each \(\mathbf{x} \in V\) has exactly one \(\mathcal{B}\)-coordinate tuple. We verify the three required properties.
Linearity. Let \(\mathbf{x}, \mathbf{y} \in V\) and let \(c\) be a scalar. Write
\[
\mathbf{x} = \sum_{i=1}^n c_i \mathbf{b}_i, \quad \mathbf{y} = \sum_{i=1}^n d_i \mathbf{b}_i,
\]
so \(\varphi(\mathbf{x}) = (c_1, \ldots, c_n)^\top\) and \(\varphi(\mathbf{y}) = (d_1, \ldots, d_n)^\top\). By the vector space axioms
(commutativity, associativity, and distributivity over scalar addition, exactly as in the
Span is a Subspace proof),
\[
\mathbf{x} + \mathbf{y} = \sum_{i=1}^n (c_i + d_i) \mathbf{b}_i.
\]
By uniqueness of basis representation, this sum is the \(\mathcal{B}\)-representation of \(\mathbf{x} + \mathbf{y}\), so
\[
\varphi(\mathbf{x} + \mathbf{y}) = (c_1 + d_1, \ldots, c_n + d_n)^\top = \varphi(\mathbf{x}) + \varphi(\mathbf{y}).
\]
Similarly, by distributivity over vector addition and compatibility (axioms 6 and 8),
\[
c\mathbf{x} = c \sum_{i=1}^n c_i \mathbf{b}_i = \sum_{i=1}^n (c c_i) \mathbf{b}_i,
\]
so \(\varphi(c\mathbf{x}) = (c c_1, \ldots, c c_n)^\top = c\, \varphi(\mathbf{x})\). Hence \(\varphi\) is linear.
One-to-one. Suppose \(\varphi(\mathbf{x}) = \varphi(\mathbf{y})\). Writing \(\mathbf{x} = \sum c_i \mathbf{b}_i\) and
\(\mathbf{y} = \sum d_i \mathbf{b}_i\), the hypothesis says \(c_i = d_i\) for each \(i\), hence \(\mathbf{x} = \mathbf{y}\). (Equivalently, by
linearity it suffices to check that \(\varphi(\mathbf{x}) = \mathbf{0}\) forces \(\mathbf{x} = \mathbf{0}\). That hypothesis means all
\(c_i = 0\), hence \(\mathbf{x} = \sum 0 \cdot \mathbf{b}_i = \mathbf{0}\) by the consequence \(0\mathbf{b}_i = \mathbf{0}\) noted earlier.)
Onto. Given any \((c_1, \ldots, c_n)^\top \in \mathbb{R}^n\), the vector \(\mathbf{x} := \sum_{i=1}^n c_i \mathbf{b}_i \in V\)
satisfies \(\varphi(\mathbf{x}) = (c_1, \ldots, c_n)^\top\). So every element of \(\mathbb{R}^n\) is in the image of \(\varphi\).
The notion of isomorphism is developed systematically in the upcoming abstract algebra series. Here it captures the idea that \(V\) and
\(\mathbb{R}^n\) are "the same" vector space up to relabeling of vectors. The practical consequence is that we can analyze any nonzero
finite-dimensional vector space via the familiar \(\mathbb{R}^n\), with all vector-space operations preserved by the coordinate mapping.
Dimension and Rank
The dimension of a subspace is a fundamental invariant that measures its "size." For matrix-associated subspaces,
this invariant has special significance and is captured by the notion of rank.
Definition: Dimension
The dimension of a vector space \(V\), written \(\dim V\), is the number of vectors in a basis for \(V\). A vector space is
finite-dimensional if it is \(\{\mathbf{0}\}\) or has a basis with finitely many vectors, and
infinite-dimensional otherwise. The zero space \(\{\mathbf{0}\}\) contains no nonempty linearly independent list of vectors
and therefore has no basis in the sense above. We assign it dimension \(0\).
For this definition to be sensible, any two bases of the same vector space must contain the same number of vectors. The theorem below proves
that they do.
Theorem: Invariance of Dimension
Let \(V\) be a vector space that has a finite basis \(\mathcal{B} = \{\mathbf{b}_1, \ldots, \mathbf{b}_n\}\).
Then every basis of \(V\) has exactly \(n\) vectors.
The core of the proof is a classical counting lemma. In a space spanned by \(n\) vectors, any collection of \(n + 1\) or more vectors must be
linearly dependent. We isolate this as a separate statement because it is of independent interest. The lemma is the germ of most of linear algebra's
dimension arguments.
Lemma: Spanning Set Bound
Let \(V\) be a vector space spanned by \(n\) vectors \(\mathbf{v}_1, \ldots, \mathbf{v}_n\).
Then any set of more than \(n\) vectors in \(V\) is linearly dependent.
Proof of Lemma:
Let \(\mathbf{w}_1, \ldots, \mathbf{w}_{n+1} \in V\). We show this set is linearly dependent. (If we are given more than \(n + 1\) vectors, the
same argument applies to any \(n + 1\) of them, and linear dependence of a subset implies linear dependence of the whole set.)
Since \(V = \operatorname{Span}\{\mathbf{v}_1, \ldots, \mathbf{v}_n\}\), each \(\mathbf{w}_j\) admits an expansion
\[
\mathbf{w}_j = \sum_{i=1}^n a_{ij} \mathbf{v}_i \quad (j = 1, \ldots, n+1)
\]
for some scalars \(a_{ij}\). Arrange the coefficients into the \(n \times (n+1)\) matrix \(A = (a_{ij})\).
Consider the homogeneous system \(A\mathbf{c} = \mathbf{0}\) in the unknown \(\mathbf{c} = (c_1, \ldots, c_{n+1})^\top \in \mathbb{R}^{n+1}\).
This is a system of \(n\) equations in \(n + 1\) unknowns. In any row echelon form of \(A\), there are at most \(n\) pivots (one per row), hence
at most \(n\) basic variables. At least one of the \(n + 1\) unknowns is therefore a free variable. Setting the free variable to \(1\) (and
solving for the basic variables) produces a nontrivial solution \(\mathbf{c} \neq \mathbf{0}\) with \(A\mathbf{c} = \mathbf{0}\).
Using this \(\mathbf{c}\), compute
\[
\begin{align*}
\sum_{j=1}^{n+1} c_j \mathbf{w}_j &= \sum_{j=1}^{n+1} c_j \sum_{i=1}^n a_{ij} \mathbf{v}_i \\\\
&= \sum_{i=1}^n \Bigg(\sum_{j=1}^{n+1} a_{ij} c_j \Bigg) \mathbf{v}_i \\\\
&= \sum_{i=1}^n (A\mathbf{c})_i\, \mathbf{v}_i \\\\
&= \sum_{i=1}^n 0 \cdot \mathbf{v}_i \\\\
&= \mathbf{0}.
\end{align*}
\]
(The interchange of sums uses commutativity and associativity of addition, and the extraction of coefficients uses distributivity, by axioms 1,
2, and 6-8.) This exhibits a nontrivial linear combination of the \(\mathbf{w}_j\) equal to \(\mathbf{0}\), so
\(\{\mathbf{w}_1, \ldots, \mathbf{w}_{n+1}\}\) is linearly dependent.
Proof of Invariance of Dimension:
First, every basis of \(V\) is finite. A set in \(V\) with more than \(n\) vectors contains \(n + 1\) vectors that are
linearly dependent by the Lemma, and a dependent subset makes the whole set dependent, so no linearly independent subset of
\(V\) has more than \(n\) elements. A basis is linearly independent, so it has at most \(n\) vectors.
Let \(\mathcal{B}' = \{\mathbf{b}'_1, \ldots, \mathbf{b}'_m\}\) be another basis of \(V\). Since
\(\mathcal{B} = \{\mathbf{b}_1, \ldots, \mathbf{b}_n\}\) spans \(V\) with \(n\) vectors, and \(\mathcal{B}'\) is a linearly independent set in
\(V\), the Lemma forbids \(\mathcal{B}'\) from having more than \(n\) elements: \(m \leq n\).
Swapping the roles of \(\mathcal{B}\) and \(\mathcal{B}'\) gives the reverse inequality. Now \(\mathcal{B}'\) spans \(V\) with \(m\) vectors and
\(\mathcal{B}\) is linearly independent, so \(n \leq m\).
Combining, \(m = n\). The cardinality of any basis for \(V\) equals \(n\), so \(\dim V\) is well-defined.
The same lemma answers a question the definition of dimension leaves open, namely which subspaces have a basis at all. In \(\mathbb{R}^n\) every
nonzero one does, and any independent set already in hand can be grown into one.
Theorem: Basis Extension
Let \(W\) be a nonzero subspace of \(\mathbb{R}^n\) and let \(\{\mathbf{w}_1, \ldots, \mathbf{w}_k\} \subseteq W\)
be linearly independent. Then there are vectors \(\mathbf{w}_{k+1}, \ldots, \mathbf{w}_p \in W\), possibly none,
such that \(\{\mathbf{w}_1, \ldots, \mathbf{w}_p\}\) is a basis for \(W\). In particular every nonzero subspace
of \(\mathbb{R}^n\) has a basis, and that basis has at most \(n\) vectors.
Proof:
If \(\operatorname{Span}\{\mathbf{w}_1, \ldots, \mathbf{w}_k\} = W\), the set is a linearly independent spanning
set and therefore already a basis for \(W\). Otherwise choose \(\mathbf{w}_{k+1} \in W\) lying outside that span.
The enlarged set stays linearly independent. In a relation
\[
c_1\mathbf{w}_1 + \cdots + c_k\mathbf{w}_k + c_{k+1}\mathbf{w}_{k+1} = \mathbf{0},
\]
a nonzero \(c_{k+1}\) would let us solve for \(\mathbf{w}_{k+1}\) as a linear combination of
\(\mathbf{w}_1, \ldots, \mathbf{w}_k\), contradicting the choice. Hence \(c_{k+1} = 0\), and independence of the
original set forces the remaining coefficients to vanish.
Repeating the step produces linearly independent subsets of \(W\) whose size grows by one each time. Since
\(\mathbb{R}^n\) is spanned by the \(n\) columns of \(I_n\) and every one of these sets sits inside
\(\mathbb{R}^n\), the
Spanning Set Bound rules out a linearly
independent set with more than \(n\) elements. The procedure therefore halts after at most \(n - k\) steps, and it
can halt only when the span of the current set is all of \(W\). At that point the set is linearly independent and
spans \(W\), so it is a basis for \(W\).
For the final statement, \(W \neq \{\mathbf{0}\}\) supplies a nonzero \(\mathbf{w}_1 \in W\), and
\(\{\mathbf{w}_1\}\) is linearly independent because \(c\mathbf{w}_1 = \mathbf{0}\) forces \(c = 0\). Applying
the result to it produces a basis of \(W\) with at most \(n\) vectors, and by
Invariance of Dimension every basis of
\(W\) has that same size.
Definition: Rank
The rank of a matrix \(A\) is the dimension of its column space:
\[
\operatorname{rank} A = \dim(\operatorname{Col} A).
\]
Equivalently (as we will see in the Rank-Nullity proof), \(\operatorname{rank} A\) is the number of pivot columns in the
reduced row echelon form of \(A\).
Two companion quantities follow immediately. Since \(\operatorname{Row} A = \operatorname{Col} A^\top\), we have
\(\dim(\operatorname{Row} A) = \operatorname{rank} A^\top\). Also, \(\dim(\operatorname{Nul} A)\) equals the number of free variables in
\(A\mathbf{x} = \mathbf{0}\), equivalently the number of non-pivot columns of \(A\). The relationship between rank and nullity is captured by the
following fundamental theorem.
Theorem: Rank-Nullity
For every \(m \times n\) matrix \(A\),
\[
\operatorname{rank} A + \dim(\operatorname{Nul} A) = n.
\]
Proof:
Let \(R\) be the reduced row echelon form of \(A\), and let \(r\) be the number of pivot columns of \(R\) (equivalently, the number of leading
\(1\)'s in \(R\)). We claim \(\operatorname{rank} A = r\) and \(\dim(\operatorname{Nul} A) = n - r\). The theorem then follows.
Throughout, we use a key invariant of row reduction. The homogeneous equation \(A\mathbf{x} = \mathbf{0}\) has exactly the same solutions as
\(R\mathbf{x} = \mathbf{0}\), since each elementary row operation is performed by left-multiplication by an invertible elementary matrix (see
the Elementary Matrices section). In particular, a linear relation
\(\sum_j c_j \mathbf{a}_j = \mathbf{0}\) among the columns of \(A\) holds if and only if the same relation
\(\sum_j c_j \mathbf{r}_j = \mathbf{0}\) holds among the columns of \(R\), because both are statements of the form \(A\mathbf{c} = \mathbf{0}\)
and \(R\mathbf{c} = \mathbf{0}\) with \(\mathbf{c} = (c_1, \ldots, c_n)^\top\).
Two boundary cases are settled directly by the convention \(\dim\{\mathbf{0}\} = 0\). If \(r = 0\), then \(R = 0\), and since
\(A\) is recovered from \(R\) by inverting the elementary matrices, \(A = 0\) and \(\operatorname{Col} A = \{\mathbf{0}\}\),
so \(\operatorname{rank} A = 0\). If \(r = n\), no variable is free and \(\operatorname{Nul} A = \{\mathbf{0}\}\), so
\(\dim(\operatorname{Nul} A) = 0\). Step 1 below therefore assumes \(r \geq 1\) and Step 2 assumes \(r \leq n - 1\).
Step 1: the pivot columns of \(A\) form a basis for \(\operatorname{Col} A\), so \(\dim(\operatorname{Col} A) = r\).
Let \(j_1 \lt j_2 \lt \cdots \lt j_r\) be the indices of the pivot columns, and let \(j_{r+1} \lt \cdots \lt j_n\) be the indices of the
non-pivot columns. In \(R\), the pivot columns are precisely the standard basis vectors
\(\mathbf{e}_1, \mathbf{e}_2, \ldots, \mathbf{e}_r \in \mathbb{R}^m\) (this is exactly the RREF condition, under which each leading \(1\) sits
in a column whose other entries are all \(0\)). These are clearly linearly independent in \(\mathbb{R}^m\). By the invariant above, the pivot
columns \(\mathbf{a}_{j_1}, \ldots, \mathbf{a}_{j_r}\) of \(A\) are also linearly independent.
Moreover, each non-pivot column \(\mathbf{r}_{j_k}\) of \(R\) (for \(k \gt r\)) is a linear combination of the preceding pivot columns of \(R\).
Its entries in rows \(1, \ldots, r\) give the coefficients, and all later rows of \(R\) are zero. Writing this relation as
\(\mathbf{r}_{j_k} = \sum_{\ell=1}^r \alpha_\ell \mathbf{e}_\ell\) and translating back to \(A\) by the same invariant (applied to the relation
\(\sum \alpha_\ell \mathbf{r}_{j_\ell} - \mathbf{r}_{j_k} = \mathbf{0}\)), we obtain
\(\mathbf{a}_{j_k} = \sum_{\ell=1}^r \alpha_\ell \mathbf{a}_{j_\ell}\). Hence every column of \(A\), pivot or not, is a linear combination of
the pivot columns of \(A\), so \(\{\mathbf{a}_{j_1}, \ldots, \mathbf{a}_{j_r}\}\) spans \(\operatorname{Col} A\).
The pivot columns of \(A\) are therefore a basis for \(\operatorname{Col} A\). The
Invariance of Dimension theorem guarantees that every basis of a
finite-dimensional space has the same cardinality, so \(\operatorname{rank} A = \dim(\operatorname{Col} A) = r\).
Step 2: \(\dim(\operatorname{Nul} A) = n - r\).
Write the \(n - r\) non-pivot columns of \(R\) as free variables \(x_{j_{r+1}}, \ldots, x_{j_n}\). Solving \(R\mathbf{x} = \mathbf{0}\)
expresses each basic variable \(x_{j_\ell}\) (for \(1 \leq \ell \leq r\)) as a linear combination of the free variables. Writing the general
solution in parametric vector form,
\[
\mathbf{x} = x_{j_{r+1}} \mathbf{h}_{r+1} + x_{j_{r+2}} \mathbf{h}_{r+2} + \cdots + x_{j_n} \mathbf{h}_n,
\]
where each \(\mathbf{h}_k \in \mathbb{R}^n\) is obtained by setting the free variable \(x_{j_k}\) to \(1\) and all other free variables to
\(0\), then reading off the resulting basic coordinates.
By the invariant, the same parametrization gives the general solution of \(A\mathbf{x} = \mathbf{0}\), so
\(\{\mathbf{h}_{r+1}, \ldots, \mathbf{h}_n\}\) spans \(\operatorname{Nul} A\).
To see linear independence, note that in \(\mathbf{h}_k\) the coordinate at position \(j_k\) (the free variable we set to \(1\)) equals \(1\),
while at position \(j_{k'}\) for \(k' \neq k\) (the other free variables set to \(0\)) it equals \(0\). Suppose
\(\sum_{k=r+1}^n t_k \mathbf{h}_k = \mathbf{0}\). Reading the coordinate at position \(j_k\) gives
\(t_k \cdot 1 + \sum_{k' \neq k} t_{k'} \cdot 0 = t_k\), so \(t_k = 0\) for each \(k\).
The vectors \(\mathbf{h}_{r+1}, \ldots, \mathbf{h}_n\) thus form a basis for \(\operatorname{Nul} A\). Combined with
Invariance of Dimension, this yields
\(\dim(\operatorname{Nul} A) = n - r\).
Combining Steps 1 and 2, \(\operatorname{rank} A + \dim(\operatorname{Nul} A) = r + (n - r) = n\).