Bases and Dimension of Vector Spaces

Hello! Welcome back to our journey into the mathematical foundations of AI.

In our last lesson, we introduced two fundamental concepts: the span of a set of vectors, which describes all the points they can "reach," and linear independence, which tells us if a set of vectors is efficient and free of redundancy.

Today, we will synthesize these two powerful ideas. This lesson focuses on the learning outcome: to define and construct a basis for a vector space and determine its dimension. We will define what constitutes a "perfect" set of vectors for describing a space and then use this to formally define and measure the "size" of that space. This concept is the bedrock of countless topics in machine learning, from dimensionality reduction to the very structure of neural network layers.

1. The Definition of a Basis

In the previous lesson, we saw that a set of vectors could be too small to span a space, or it could be too large and contain redundant, linearly dependent vectors. A basis is a set that is "just right."

Formally, a set of vectors $\mathcal{B}=\{{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n\}$ is a basis for a vector space $V$ if it satisfies two conditions:

1. The set $\mathcal{B}$ is linearly independent.
2. The set $\mathcal{B}$ spans the vector space $V$ (i.e., $\text{span}(\mathcal{B})=V$).

A basis is a maximally efficient description of a vector space. It contains the minimum number of vectors required to span the space, and every vector in that set is essential.

To begin, let's watch Professor Gilbert Strang formally introduce this crucial definition and provide some initial examples.

To complement the video, the following text provides the same formal definitions along with further examples, including bases for spaces of matrices and polynomials.

The concept of unique representation is powerful. It means that once you have chosen a basis for a vector space, you have established a coordinate system. Any vector in the space can be uniquely identified by its coordinates with respect to that basis.

2. Dimension: A Unique Size for Every Space

As Professor Strang mentioned, a vector space can have infinitely many different bases. But do all these bases have something in common? The answer is a profound yes, and it leads to one of the most important concepts in all of linear algebra.

Theorem: Any two bases of a finite-dimensional vector space have the same number of elements.

This theorem is so fundamental that it requires a formal proof. The proof relies on a "replacement" argument and is a fantastic exercise in rigorous logical thinking.

Since every basis for a vector space has the same number of vectors, this number is an intrinsic, fundamental property of the space itself. We give it a special name: dimension.

Definition: The dimension of a finite-dimensional vector space $V$, denoted $\text{dim}(V)$, is the number of vectors in any basis for $V$.

Let's hear Professor Strang summarize this idea.

For example:

• The dimension of ${\mathbb{R}}^n$ is $n$, because the standard basis $\{{\mathbf{e}}_1,\dots ,{\mathbf{e}}_n\}$ has $n$ vectors.
• The dimension of a plane through the origin in ${\mathbb{R}}^3$ is 2.
• The dimension of a line through the origin in ${\mathbb{R}}^3$ is 1.
• The dimension of the trivial vector space $\{0\}$ is 0, as its basis is the empty set.

3. Constructing a Basis

Now that we understand what a basis is and what its size (the dimension) means, how do we find one in practice? Given your background in building data pipelines, you'll appreciate that there are systematic algorithms for this.

The two main strategies are to "build up" an independent set or "reduce" a spanning set. A highly effective computational method for this involves row reduction, which connects back to concepts like rank and null space.

Let's watch a practical example of finding bases for the fundamental subspaces of a matrix.

This video establishes two crucial facts:

• $\text{dim}(\text{Col }A)=\text{rank}(A)$
• $\text{dim}(\text{Null }A)=n-\text{rank}(A)$

The sum of these dimensions is $n$, the total number of columns, which is the famous Rank-Nullity Theorem.

For a detailed breakdown of the algorithms, please read the following text.

Test your understanding!

Let $A=\left(\begin{array}{cccc}1& 2& 3& 1\\ 1& 3& 5& 2\\ 2& 5& 8& 3\end{array}\right)$.

1. Find a basis for the column space of $A$, $\text{Col}(A)$. What is its dimension?
2. Find a basis for the null space of $A$, $\text{Null}(A)$. What is its dimension?

Hint: First, find the reduced row echelon form (RREF) of A.

Show answer

First, we row-reduce $A$:

$$\left(\begin{array}{cccc}1& 2& 3& 1\\ 1& 3& 5& 2\\ 2& 5& 8& 3\end{array}\right)\stackrel{R_2-R_1,R_3-2R_1}{\to }\left(\begin{array}{cccc}1& 2& 3& 1\\ 0& 1& 2& 1\\ 0& 1& 2& 1\end{array}\right)\stackrel{R_3-R_2,R_1-2R_2}{\to }\left(\begin{array}{cccc}1& 0& -1& -1\\ 0& 1& 2& 1\\ 0& 0& 0& 0\end{array}\right)$$

The RREF of $A$ is $\left(\begin{array}{cccc}1& 0& -1& -1\\ 0& 1& 2& 1\\ 0& 0& 0& 0\end{array}\right)$.

1. Basis for the Column Space

The pivot columns in the RREF are columns 1 and 2. Therefore, a basis for the column space of $A$ is formed by columns 1 and 2 of the original matrix $A$.
A basis for $\text{Col}(A)$ is $\left\{\left(\begin{array}{c}1\\ 1\\ 2\end{array}\right),\left(\begin{array}{c}2\\ 3\\ 5\end{array}\right)\right\}$.
The dimension of the column space is the number of vectors in the basis, which is 2. So, $\text{dim}(\text{Col }A)=2$.

2. Basis for the Null Space

From the RREF, we can write the system $A\mathbf{x}=0$ as:
$x_1-x_3-x_4=0⟹x_1=x_3+x_4$
$x_2+2x_3+x_4=0⟹x_2=-2x_3-x_4$
The variables $x_3$ and $x_4$ are free. We can write the general solution as:

$$\mathbf{x}=\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\end{array}\right)=\left(\begin{array}{c}{x}_3+x_4\\ -2x_3-x_4\\ x_3\\ x_4\end{array}\right)=x_3\left(\begin{array}{c}1\\ -2\\ 1\\ 0\end{array}\right)+x_4\left(\begin{array}{c}1\\ -1\\ 0\\ 1\end{array}\right)$$

The two vectors in this linear combination form a basis for the null space.
A basis for $\text{Null}(A)$ is $\left\{\left(\begin{array}{c}1\\ -2\\ 1\\ 0\end{array}\right),\left(\begin{array}{c}1\\ -1\\ 0\\ 1\end{array}\right)\right\}$.
The dimension of the null space is the number of free variables, which is 2. So, $\text{dim}(\text{Null }A)=2$.
Note that $\text{dim}(\text{Col }A)+\text{dim}(\text{Null }A)=2+2=4$, which equals the number of columns of $A$, as expected from the Rank-Nullity Theorem.

Conclusion

Today, we've taken a significant step in our journey, moving from collections of vectors to a deep understanding of the structure of the spaces they inhabit.

Here are the key takeaways from this lesson:

• A basis is a set of vectors that is both linearly independent and spans the vector space. It is an efficient, non-redundant "skeleton" for the entire space.
• A key theorem states that while a space can have many bases, they all have the same number of vectors.
• This unique number is called the dimension of the space, a fundamental measure of its size and complexity.
• We can construct a basis for key subspaces (like the column space and null space) of a matrix by using row reduction to identify pivot columns and free variables.

In the next lesson, we will shift our focus to matrix operations, including addition, multiplication, and transposition. With your newfound understanding of bases and dimension, you'll be equipped to see these operations not just as arithmetic rules, but as powerful tools that transform vector spaces.