Linear Independence, Span, Basis, and Dimension

Introduction

In our previous lesson, we went under the hood of matrix multiplication, implementing it from scratch to understand its mechanical core. This gave us a practical feel for how vectors and matrices are manipulated computationally. Today, we elevate our perspective from computation to conception. We will introduce four of the most fundamental concepts in linear algebra: linear independence, span, basis, and dimension.

These terms form the essential vocabulary for describing vector spaces. Understanding them is not an abstract mathematical exercise; it is the prerequisite for grasping core ideas in both graphics and AI. Concepts like the "rank" of a matrix, the nature of solutions to linear systems, and the principles behind dimensionality reduction all rest on this foundation. Our goal is to move from simply calculating with vectors to reasoning about their relationships and the spaces they define.

Linear Combinations and Span: The Building Blocks of a Space

At the heart of linear algebra are two operations you already know: vector addition and scalar multiplication. A linear combination is simply the act of scaling a set of vectors and adding them together. For a set of vectors $\{{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_k\}$ and a set of scalars $\{c_1,c_2,\dots ,c_k\}$, a linear combination is the resulting vector $\mathbf{v}$:

$$\mathbf{v}=c_1{\mathbf{v}}_1+c_2{\mathbf{v}}_2+\dots +c_k{\mathbf{v}}_k$$

This is the most fundamental way of constructing new vectors from old ones. To build a strong visual intuition for this, let's turn to an excellent video from 3Blue1Brown.

As the video illustrates, the span of a set of vectors is the set of all possible vectors you can create through their linear combinations. It answers the question: "What parts of space can I reach using only these vectors and the operations of scaling and adding?"

• The span of a single non-zero vector is a line through the origin.
• The span of two non-collinear vectors is a plane through the origin.

This idea extends naturally into higher dimensions. In 3D space, what do you think the span of two non-collinear vectors would be?

It would again be a plane, but this plane is now a "slice" of 3D space.

What happens when we introduce a third vector? The situation becomes more interesting.

This brings us to a crucial distinction: the difference between vectors that add new "reach" to our span and those that are redundant.

Linear Independence: The Concept of Non-Redundancy

As we just saw, sometimes adding a vector to a set doesn't expand its span. This happens when the new vector is already a linear combination of the existing ones. This idea of redundancy is formalized by the concept of linear dependence.

A set of vectors is linearly dependent if at least one vector in the set can be written as a linear combination of the others. In the 3D example, if the third vector ${\mathbf{v}}_3$ lies in the plane spanned by ${\mathbf{v}}_1$ and ${\mathbf{v}}_2$, the set $\{{\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3\}$ is linearly dependent.

Conversely, a set of vectors is linearly independent if no vector in the set can be written as a linear combination of the others. Each vector adds a new direction, or a new dimension, to the span.

For a deeper and more formal understanding, let's look at the mathematical definition. A set of vectors $\{{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_k\}$ is linearly independent if the only way to get the zero vector from their linear combination is by using all zero scalars:

$$c_1{\mathbf{v}}_1+c_2{\mathbf{v}}_2+\dots +c_k{\mathbf{v}}_k=0\text{if and only if}{c}_1=c_2=\dots =c_k=0$$

If you can find a set of scalars where at least one is non-zero that makes the combination equal to the zero vector, the vectors are linearly dependent.

From your systems programming perspective, this abstract definition has a very concrete computational interpretation. If we arrange a set of column vectors into a matrix $\mathbf{A}=[{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_k]$, the equation above is simply $\mathbf{Ac}=0$. So, asking if the vectors are linearly independent is identical to asking: "Does the equation $\mathbf{Ac}=0$ have any non-trivial solutions?" In other words, is the null space of $\mathbf{A}$ limited to only the zero vector?

Professor Gilbert Strang provides a masterclass on this connection.

Basis and Dimension: Describing a Space Efficiently

We now have two key concepts:

1. Span: A set of vectors spans a space if their linear combinations can reach every vector in that space.
2. Linear Independence: A set of vectors is linearly independent if it contains no redundant vectors.

When a set of vectors has both of these properties, it is called a basis for that space.

A basis is a linearly independent set of vectors that spans the space.

Think of a basis as a "perfect" set of vectors for describing a space. It's:

• Complete: It spans the whole space, so no part is unreachable.
• Minimal: It's linearly independent, so there are no wasteful, redundant vectors.

The standard basis in ${\mathbb{R}}^3$ is composed of the vectors $\mathbf{i}=[1,0,0{]}^T$, $\mathbf{j}=[0,1,0{]}^T$, and $\mathbf{k}=[0,0,1{]}^T$. It's easy to see they are linearly independent and that their combinations can form any vector $[x,y,z{]}^T$. However, a space can have infinitely many different bases. For example, any three non-coplanar vectors in ${\mathbb{R}}^3$ form a basis for ${\mathbb{R}}^3$.

While the bases themselves can vary, they all share one remarkable property: they have the same number of vectors. This fundamental number is an intrinsic property of the space itself. We call it the dimension of the space.

The dimension of a vector space is the number of vectors in any of its bases.

• A line is a 1-dimensional space.
• A plane is a 2-dimensional space.
• ${\mathbb{R}}^n$ is an n-dimensional space.

Prof. Strang's lecture continues to clarify these final, crucial definitions.

For a quick textual review of these definitions, you can consult these slides.

Conclusion

In this lesson, we have established the foundational vocabulary of linear algebra. You now understand the key concepts that allow us to describe and reason about vector spaces.

Our key takeaways are:

• Linear Combination: The fundamental operation of scaling and adding vectors.
• Span: The set of all reachable vectors from a given set of vectors using linear combinations. It defines the subspace they "live" in.
• Linear Independence: A property of a set of vectors with no redundancy; each vector contributes a new dimension to the span. Computationally, this is linked to the null space of a matrix containing only the zero vector.
• Basis: A minimal, complete set of vectors that is both linearly independent and spans the space. It provides a unique "coordinate system" for that space.
• Dimension: The number of vectors in any basis for a space. This is an intrinsic, constant property of the space.

These ideas are not just abstract. The dimension of a matrix's column space is its rank, a concept we will explore deeply. The dimension of the null space tells us about the number of solutions to a linear system. These are the tools that unlock the deeper, more powerful aspects of linear algebra.

In our next lesson, we will return to the properties of matrices themselves. We will explore the determinant, a single number that reveals a great deal about a matrix, including a beautiful geometric interpretation as the factor by which a transformation scales area or volume.