Linear Independence, Dependence, and Span

Hello! Welcome back to our course on the mathematical foundations of AI.

In our previous lesson, we established the formal definition of a vector space—the "arena" where vectors exist and interact according to a strict set of axiomatic rules. We also learned how to identify subspaces within these larger spaces.

Today, we will build directly on that foundation to explore the relationships between vectors. This lesson addresses the learning outcome: to determine linear independence/dependence of vectors and define the span of a set of vectors. We will answer two fundamental questions:

1. Given a set of vectors, what is the entire region of the space they can "reach"? This is the concept of span.
2. Is our set of vectors efficient, or does it contain redundant information? This is the crucial distinction between linear independence and linear dependence.

These concepts are at the heart of linear algebra and are essential for understanding data representation, dimensionality reduction (like PCA, which we'll see later), and the behavior of many machine learning models.

1. Linear Combinations and Span

The most basic way to combine vectors is through a linear combination. Given a set of vectors $\{{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_k\}$ in a vector space $V$ and a set of scalars $\{c_1,c_2,\dots ,c_k\}$, the vector $\mathbf{w}$ defined as:

is a linear combination of those vectors.

The span of the set of vectors $\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_k\}$ is simply the set of all possible linear combinations of these vectors.

To get a formal introduction to this idea, let's turn to a lecture by Professor Gilbert Strang.

As Professor Strang explained, we can formally define the span as follows:

A key property is that the span of any set of vectors in a vector space $V$ is always a subspace of $V$. We can prove this using the Subspace Test from our last lesson:

1. Zero Vector: The zero vector is in the span, as we can choose all scalars $c_i=0$.
2. Closure under Addition: The sum of any two linear combinations is itself a linear combination of the same vectors.
3. Closure under Scalar Multiplication: A scalar multiple of a linear combination is also a linear combination.

Geometrically, in ${\mathbb{R}}^3$:

• The span of a single non-zero vector $\mathbf{v}$ is the line passing through the origin in the direction of $\mathbf{v}$.
• The span of two non-collinear vectors $\mathbf{u}$ and $\mathbf{v}$ is the plane passing through the origin containing both vectors.

2. Linear Independence and Dependence

Now we turn to the second, related question: is our set of vectors efficient? Or is one of the vectors "redundant" because it's already in the span of the others? This brings us to the idea of linear independence.

To explore the formal definition, we will continue with Professor Strang's lecture.

As defined in the video, a set of vectors $\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_k\}$ is linearly independent if the vector equation:

has only the trivial solution, where $c_1=c_2=\cdots =c_k=0$.

If there exists a solution where at least one scalar $c_i$ is non-zero, the set is linearly dependent. Such an equation is called a linear dependency relation.

The Equivalence of Definitions

This formal definition might seem abstract. It is, however, equivalent to the more intuitive idea that one vector is a combination of the others. Proving this equivalence is a perfect exercise in the rigorous thinking you aim to develop.

The theorem you just read is fundamental. It proves that a set of two or more vectors is linearly dependent if and only if at least one vector in the set is a linear combination of the others. This formally justifies the idea of "redundancy."

3. How to Determine Linear Independence

So, how do we check for linear independence in practice? We can transform the vector equation into a matrix equation.

Consider the vectors ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_k$ in ${\mathbb{R}}^n$. We can form a matrix $A$ where these vectors are the columns: $A=[{\mathbf{v}}_1{\mathbf{v}}_2\dots {\mathbf{v}}_k]$. The linear combination $c_1{\mathbf{v}}_1+\cdots +c_k{\mathbf{v}}_k$ is equivalent to the matrix-vector product $A\mathbf{c}$, where $\mathbf{c}=[c_1,\dots ,c_k{]}^T$.

Therefore, the independence condition $c_1{\mathbf{v}}_1+\cdots +c_k{\mathbf{v}}_k=0$ becomes:

This is a homogeneous system of linear equations. The vectors are linearly independent if and only if this system has only the trivial solution $\mathbf{c}=0$. This occurs precisely when the null space of $A$ contains only the zero vector.

The next segment of Professor Strang's lecture explains this crucial connection.

This method gives us a concrete algorithm:

1. Place the vectors as columns in a matrix $A$.
2. Solve the system $A\mathbf{c}=0$, typically by row-reducing the augmented matrix $[A|0]$.
3. If the only solution is $\mathbf{c}=0$ (i.e., there are no free variables), the vectors are linearly independent.
4. If there are non-trivial solutions (i.e., there is at least one free variable), the vectors are linearly dependent. Any non-trivial solution provides the coefficients for a linear dependency relation.

The image below shows a complete, hand-written example of this process.

Some Important Consequences

This matrix-based view leads to a very powerful and practical result. Remember that a system of linear equations with more unknowns than equations must have free variables, and therefore must have non-trivial solutions.
In our context, the unknowns are the coefficients $c_i$, and the number of unknowns is the number of vectors, $k$. The number of equations is the dimension of the space each vector lives in, $n$.

This leads to a key theorem:
Theorem: Any set of $k$ vectors in ${\mathbb{R}}^n$ is linearly dependent if $k>n$.

For example, any set of 3 (or more) vectors in ${\mathbb{R}}^2$ must be linearly dependent. Similarly, any 4 (or more) vectors in ${\mathbb{R}}^3$ must be linearly dependent.

Conclusion

In this lesson, we have explored the fundamental relationships between vectors within a vector space. These concepts are not just abstract definitions; they provide the language to describe the structure of data.

Here are the key takeaways:

• The span of a set of vectors is the subspace of all possible vectors that can be formed by their linear combinations.
• A set of vectors is linearly independent if no vector in the set can be written as a linear combination of the others. Formally, the only way to sum them to the zero vector is by using all-zero coefficients.
• A set of vectors is linearly dependent if it contains at least one "redundant" vector that is already in the span of the others.
• The standard method for determining independence is to form a matrix $A$ with the vectors as columns and test if the system $A\mathbf{c}=0$ has non-trivial solutions. The existence of free variables implies linear dependence.
• A set of $k$ vectors in ${\mathbb{R}}^n$ is guaranteed to be linearly dependent if $k>n$.

Now that we understand how to generate a space (span) and how to describe an efficient set of vectors (linear independence), the next logical step is to combine them. In our next lesson, we will define a basis for a vector space—a special set of vectors that is both linearly independent and spans the entire space. This will lead us to one of the most important concepts in linear algebra: the dimension of a vector space.