Linear Independence of Vectors

Hello! Welcome to your third lesson.

In our last session, we explored how to build vector spaces using the concept of span and how to identify special vector spaces called subspaces. We ended by noting that sometimes, adding a new vector to a set doesn't enlarge its span. This happens when the new vector is "redundant"—it already lies within the space spanned by the others.

Today, we will formalize this idea of redundancy. Our learning outcome is to determine the linear independence or dependence of a set of vectors. This concept is absolutely central to linear algebra and has profound implications for both of your future courses:

In deep learning, understanding linear independence helps in feature selection, analyzing model parameters, and understanding techniques like PCA which seek to find non-redundant directions of variance.
In quantum mechanics, linearly independent vectors are used to form a basis for the state space, representing distinct, non-overlapping physical states of a system.

1. The Intuitive Idea: Redundancy and Added Dimensions

Let's start by building a strong geometric intuition. A set of vectors is linearly dependent if at least one vector in the set is redundant, meaning it can be formed as a linear combination of the others. If no vector is redundant, the set is linearly independent.

The 3Blue1Brown video we watched in the previous lesson also covers this exact idea. Let's revisit it to see the visual explanation.

Linear combinations, span, and basis vectors | Chapter 2, Essence of linear algebra

This segment of the 3Blue1Brown video on span introduces the concepts of linear dependence and independence from a geometric perspective.

Please watch the segment from 8:21 to 9:09. Focus on the distinction between a vector that adds a 'new dimension' to the span versus one that lies within the existing span.

As the video illustrates:

Linearly Dependent: A set of vectors is linearly dependent if one vector is in the span of the others. This vector adds no new information or dimension to the span. For example, in $R^{3}$ , if you have two vectors spanning a plane, any third vector that also lies in that plane creates a linearly dependent set.

Visualizing Linear Independence with Vectors and Planes — This image depicts a vector $\mathbf{v_3}$ that lies in the plane spanned by $\mathbf{v_1}$ and $\mathbf{v_2}$. This means $\mathbf{v_3}$ can be written as a linear combination of $\mathbf{v_1}$ and $\mathbf{v_2}$ (like $\mathbf{v_3} = a\mathbf{v_1} + b\mathbf{v_2}$). The set $\{\mathbf{v_1}, \mathbf{v_2}, \mathbf{v_3}\}$ is therefore linearly dependent.

Linearly Independent: A set of vectors is linearly independent if each vector adds a new direction or dimension to the span. No vector can be written as a linear combination of the others.

2. The Formal Test for Independence

The intuitive definition is great, but how do we test this computationally? Checking every vector to see if it's a linear combination of the others would be tedious. Instead, we use a more elegant and powerful formal definition.

A set of vectors ${v_{1}, v_{2}, \dots, v_{p}}$ is linearly independent if and only if the vector equation:
$c_{1} v_{1} + c_{2} v_{2} + \dots + c_{p} v_{p} = 0$
has only the trivial solution, where $c_{1} = c_{2} = \dots = c_{p} = 0$ .

If there is any other solution (a non-trivial solution) where at least one $c_{i}$ is not zero, the set is linearly dependent.

Why does this work?
Suppose we find a non-trivial solution. For instance, imagine $c_{1} \neq = 0$ . Then we can rearrange the equation:
$c_{1} v_{1} = - c_{2} v_{2} - \dots - c_{p} v_{p}$
$v_{1} = - \frac{c _{2}}{c _{1}} v_{2} - \dots - \frac{c _{p}}{c _{1}} v_{p}$
This shows that $v_{1}$ is a linear combination of the other vectors, which is exactly our intuitive definition of linear dependence!

The equation $c_{1} v_{1} + \dots + c_{p} v_{p} = 0$ can be rewritten in matrix form as $A x = 0$ , where $A$ has the vectors $v_{i}$ as its columns and $x$ is the vector of weights $c_{i}$ . This is called a homogeneous system of equations. So, checking for linear independence is equivalent to checking if $A x = 0$ has only the trivial solution $x = 0$ .

The following video walks through exactly how to set up and solve this system.

Linear Independence

Professor Dave Explains shows the step-by-step process of testing for linear independence by solving a homogeneous system of equations.

Watch from 0:30 to 7:27. Pay close attention to how a set of vectors is used to form a system of equations for the unknown scalars, and how row reduction is used to determine if non-zero solutions exist.

Test your understanding!

Using the formal definition, determine if the set of vectors ${(12), (- 2 - 4)}$ is linearly independent or dependent.

Show answer

We need to solve the equation $c_{1} (12) + c_{2} (- 2 - 4) = (00)$ .
This gives us a system of two equations:

$c_{1} - 2 c_{2} = 0$
$2 c_{1} - 4 c_{2} = 0$

From the first equation, we get $c_{1} = 2 c_{2}$ . Notice that the second equation is just two times the first equation, so it provides no new information.
Since we have a relationship between $c_{1}$ and $c_{2}$ , we can find non-trivial solutions. For example, if we choose $c_{2} = 1$ , then $c_{1} = 2$ .
So, $c_{1} = 2, c_{2} = 1$ is a non-trivial solution. Therefore, the set is linearly dependent.
We can verify this: $2 (12) + 1 (- 2 - 4) = (24) + (- 2 - 4) = (00)$ .

3. A Unified View: Pivots, Free Variables, and Independence

We now have multiple perspectives on linear independence: redundancy, the solution to the homogeneous equation, and the results of row reduction. Let's unify them. The process of solving $A x = 0$ by row reduction gives us the most direct computational tool.

If the system $A x = 0$ has no free variables, it means the only solution is the trivial one ( $x = 0$ ). This happens when the row-echelon form of $A$ has a pivot in every column. The vectors are linearly independent.
If the system has at least one free variable, it means there are infinitely many non-trivial solutions. This happens when at least one column in the row-echelon form of $A$ lacks a pivot. The vectors are linearly dependent.

The following resource provides a superb summary of all these equivalent ways to think about linear dependence.

Understanding Linear Algebra: Linear independence

This text connects all the ideas we've discussed: linear combinations, pivot positions, and homogeneous equations.

Read the subsections titled 'The homogeneous equation' and the following 'Proposition 2.4.5'. Focus on understanding how the existence of a non-trivial solution to A\mathbf{x} = \mathbf{0} is equivalent to having a column without a pivot, which in turn proves linear dependence.

Proposition 2.4.5 from that reading is a key result that you should bookmark in your mind. It states that for a matrix $A$ whose columns are the vectors $v_{1}, \dots, v_{n}$ , the following are all equivalent ways of saying the same thing:

The set ${v_{1}, \dots, v_{n}}$ is linearly dependent.
One of the vectors is a linear combination of the others.
The matrix $A$ has a column without a pivot position.
The homogeneous equation $A x = 0$ has a non-trivial solution.

This gives you a powerful toolkit. To check for independence, form the matrix $A$ and row-reduce it. Then, simply check if every column has a pivot.

4. Useful Properties and Shortcuts

With the main concepts established, here are a few handy shortcuts for quickly identifying linear dependence.

More Vectors than Dimensions: Any set of $p$ vectors in $R^{n}$ is linearly dependent if $p > n$ . For example, 3 vectors in $R^{2}$ or 4 vectors in $R^{3}$ .
- Why? The matrix $A$ will have more columns than rows ( $n \times p$ ). Since there can be at most one pivot per row, there can't be a pivot in every column. Thus, there must be a free variable, implying linear dependence.
A Set Containing the Zero Vector: Any set of vectors containing the zero vector ( $0$ ) is linearly dependent.
- Why? Let the set be ${v_{1}, \dots, v_{p}, 0}$ . We can easily find a non-trivial solution to the homogeneous equation: $0 v_{1} + \dots + 0 v_{p} + c 0 = 0$ for any non-zero scalar $c$ (e.g., $c = 1$ ).
Two Vectors: A set of two non-zero vectors is linearly dependent if and only if one is a scalar multiple of the other (i.e., they are collinear).
Square Matrices and the Determinant: If you have $n$ vectors in $R^{n}$ , they form a square matrix $A$ . The set of vectors is linearly dependent if and only if $det (A) = 0$ . This is a very fast check if you have a square matrix. The Professor Dave video you watched earlier also mentions this at the end (starting around 8:00).

Test your understanding!

Without doing any row reduction, determine if the following set of vectors in $R^{3}$ is linearly independent or dependent. Justify your answer.
$v_{1} = 14 - 7, v_{2} = - 2 53, v_{3} = 000, v_{4} = 3 - 1 8$

Show answer

The set is linearly dependent. There are two reasons, and either one is sufficient:

The set contains the zero vector ( $v_{3} = 0$ ).
The set contains 4 vectors in $R^{3}$ . Since the number of vectors (4) is greater than the number of dimensions (3), the set must be linearly dependent.

Conclusion

Today we demystified the crucial concept of linear independence. We started with the visual intuition of redundant vectors and progressed to a robust, computational test for determining independence.

Key Takeaways:

Intuitive Meaning: A set of vectors is linearly dependent if one vector is "redundant" (a linear combination of the others). It is linearly independent if all vectors are essential and contribute a new "direction" to the span.
Formal Test: A set of vectors ${v_{i}}$ is linearly independent if the only solution to $c_{1} v_{1} + \dots + c_{p} v_{p} = 0$ is the trivial one where all scalars $c_{i}$ are zero.
The Pivot Test: The most practical way to check is to form a matrix $A$ with the vectors as columns and row-reduce it. The vectors are linearly independent if and only if every column has a pivot position.
Shortcuts: Remember to check for easy cases: sets containing the zero vector or sets with more vectors than dimensions are always linearly dependent. For square matrices, a non-zero determinant means independence.

Preview of Next Lesson:

In the last lesson, we learned how to build a subspace using span. Today, we learned how to identify a "non-redundant" set of vectors. What happens when we combine these two ideas? We get the most efficient possible description of a vector space: a spanning set that is also linearly independent. This special set is called a basis. In our next lesson, we will define what a basis is and how to construct one.

Recommended resources

1. The Intuitive Idea: Redundancy and Added Dimensions

2. The Formal Test for Independence

3. A Unified View: Pivots, Free Variables, and Independence

4. Useful Properties and Shortcuts

Conclusion