Dimension of Vector Spaces

1. Dimension is Well-Defined

Our first task is to prove the cornerstone theorem that makes the definition of dimension possible.

Theorem: If a vector space $V$ has a basis with $n$ vectors, then every basis for $V$ must also have exactly $n$ vectors.

Because you have an interest in rigorous proofs, we'll dive into the complete argument for this theorem. The core idea is a proof by contradiction, using an elegant technique often called the "Replacement Lemma" or "Steinitz Exchange Lemma."

The following video provides a clear, step-by-step walkthrough of this proof.

The proof you just watched is fundamental. It assures us that dimension is an intrinsic, unambiguous property of the vector space itself, not an artifact of a particular basis we happen to choose.

2. Defining Dimension

With that proof in hand, we can now give a formal definition of dimension.

As the notes state, the dimension of a vector space $V$, denoted $\dim (V)$, is the number of vectors in any of its bases.

Examples of Dimension:

• $\dim ({\mathbb{R}}^n)=n$: The standard basis $\{{\mathbf{e}}_1,\dots ,{\mathbf{e}}_n\}$ contains $n$ vectors.
• $\dim (P_d)=d+1$: The space of polynomials of degree at most $d$ has a standard basis $\{1,x,x^2,\dots ,x^d\}$, which contains $d+1$ vectors.
• Dimension of a plane: A plane through the origin in ${\mathbb{R}}^3$ is a two-dimensional subspace. Any two non-collinear vectors that lie in the plane will form a basis for it.
• Dimension of a line: A line through the origin is a one-dimensional subspace. Any single non-zero vector on that line forms a basis.
• The zero space: The vector space containing only the zero vector, $\{0\}$, has a basis consisting of the empty set $\{\}$. Its dimension is 0.

To find the dimension of any subspace, the strategy is always the same: find a basis for the subspace and count the number of vectors in it.

3. The Dimensions of Fundamental Subspaces: Rank and Nullity

Two of the most important subspaces you'll encounter are associated with matrices. Given your computer science background, you can think of an $m\times n$ matrix $A$ as representing a function that transforms vectors from an $n$-dimensional space (${\mathbb{R}}^n$) to an $m$-dimensional space (${\mathbb{R}}^m$). The dimensions of the subspaces related to this transformation tell us a great deal about its behavior.

Let's define these subspaces and their dimensions.

From the reading, we have two key definitions:

1. Column Space & Rank: The column space of a matrix $A$, denoted $C(A)$, is the span of its column vectors. Its dimension is called the rank of $A$.
   $\text{rank}(A)=\dim (C(A))$
   The rank tells you the dimension of the output image of the transformation.

2. Null Space & Nullity: The null space of a matrix $A$, denoted $N(A)$, is the set of all vectors $\mathbf{x}$ such that $A\mathbf{x}=0$. Its dimension is called the nullity of $A$.
   $\text{nullity}(A)=\dim (N(A))$
   The nullity tells you the dimension of the input space that gets "squashed" to the zero vector.

There is a profound and elegant relationship between these two values, captured by the Rank-Nullity Theorem.

The Rank-Nullity Theorem: For any $m\times n$ matrix $A$,
$\text{rank}(A)+\text{nullity}(A)=n$
where $n$ is the number of columns of $A$.

This theorem states that the dimension of the input space ($n$) is partitioned between the dimension of the subspace that gets mapped to zero (the nullity) and the dimension of the subspace that gets mapped non-trivially into the output space (the rank).

The following video provides an excellent statement of the theorem and a complete, rigorous proof.

For an alternative, text-based proof that you can work through at your own pace, the article from mbernste.github.io also provides a very clear proof in its appendix.

Conclusion

This lesson marks the culmination of our first module. We solidified the concept of dimension by proving that it is an intrinsic, well-defined property of any vector space. This allows us to quantify the "size" or "complexity" of these abstract structures.

Key Takeaways:

• All bases for a given vector space have the same number of elements. This crucial theorem makes the definition of dimension possible.
• The dimension of a vector space is the number of vectors in any of its bases.
• To compute the dimension of a subspace, you must find a basis for it and count the vectors.
• The rank of a matrix is the dimension of its column space.
• The nullity of a matrix is the dimension of its null space.
• The Rank-Nullity Theorem provides a fundamental link: for an $m\times n$ matrix $A$, $\text{rank}(A)+\text{nullity}(A)=n$.

Preview of the next module:
We have now built the foundational theory of vector spaces. In the next module, "Linear Transformations and Matrices," we will dive deeper into the functions that operate on these spaces. The Rank-Nullity Theorem you learned today is the perfect bridge, as it connects the properties of a matrix to the dimensions of the spaces it acts upon. We will explore matrix operations, how to represent any linear transformation with a matrix, and further explore the deep connection between the properties of a transformation and its matrix representation.