Example
Consider the two vectors \(\mathbf{v} = (1, 2, 3)\) and \(\mathbf{w} = (4, 5, 6)\) in \(\mathbb{R}^3\).
(a) Do they span \(\mathbb{R}^3\)?
(b) Are they linearly independent?
Today we'll see more examples of linear (in)dependence, and describe a way to tell whether any set of vectors is linearly independent or dependent.
Recall: last week, we gave two equivalent definitions of linear (in)dependence:
(1) Vectors \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m \in \mathbb{R}^n\) are linearly dependent if one of the vectors lies in the span of the other vectors.
(2) Vectors \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m \in \mathbb{R}^n\) are linearly dependent if we can find scalars \(c_1, c_2, \dots, c_m\), not all zero, such that \[c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \dotsm + c_m\mathbf{v}_m = \mathbf{0}.\]
(They are linearly independent if they are not linearly dependent.) By the end of today's class, we'll have several more ways to think about these concepts. But first, let's examine what these definitions mean in some "small cases," that is, when we only have one or two vectors.
Suppose we only have one vector \(\mathbf{v}\). Then definition (1) doesn't make much sense, since there are no "other vectors" to make a span with. So let's focus on definition (2): a single vector \(\mathbf{v}\) is linearly dependent if (and only if) we can find a scalar \(c\), not zero, such that \(c \mathbf{v} = \mathbf{0}\).
(Note: Technically, the span of no vectors is defined to be \(\{\mathbf{0}\}\), the set containing only the zero vector, but we won't really need to worry about that.)
To consider what this means, let's distinguish two cases:
Now suppose we have two vectors \(\mathbf{v}\) and \(\mathbf{w}\). For these to be linearly dependent, definition (1) says that one must lie in the span of the other, that is, \(\mathbf{v} \in \text{span}(\mathbf{w})\) or \(\mathbf{w} \in \text{span}(\mathbf{v})\) (or both). Remember that the span of a single vector looks like the line containing that vector; in other words, it consists of all scalar multiples of that vector. Therefore, \(\mathbf{v}\) and \(\mathbf{w}\) are linearly dependent if and only if one is a scalar multiple of the other.
We can also see this using definition (2). The vectors \(\mathbf{v}\) and \(\mathbf{w}\) are linearly dependent if and only if we can find some equation of the form $$c \mathbf{v} + d\mathbf{w} = \mathbf{0}$$ where \(c\) and \(d\) are not both zero. If \(c\) is nonzero, then we can rearrange this equation to get \( \mathbf{v} = -\frac{d}{c} \mathbf{w} \), which means that \( \mathbf{v}\) is a scalar multiple of \(\mathbf{w}\). On the other hand, if \(d \neq 0\), then we can rearrange to get \(\mathbf{w} = -\frac{c}{d} \mathbf{v}\), which means that \(\mathbf{w}\) is a scalar multiple of \(\mathbf{v}\). And if both are nonzero, then we can rearrange in both ways, so each vector is a scalar multiple of each other.
For a set of more than two vectors, say \( \{ \mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\} \), it gets more complicated to tell if the set is linearly independent or dependent. Definition (1) says that we should simply check whether any of these vectors is "redundant", that is, lies in the span of the other ones. However, it's hard to tell just by looking which of the vectors could be redundant, and it would be a lot of work to check each vector in this way.
Instead, we can find a systematic way to answer this question using definition (2). To see if \( \{ \mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\} \) is independent or dependent, we should set up the vector equation $$x_1 \mathbf{v}_1 + x_2 \mathbf{v}_2 + \dotsm + x_m \mathbf{v}_m = \mathbf{0}.$$ Notice that this equation always has a solution, namely, \(x_1 = x_2 = \dotsm = x_m = 0\). The definition says that if this is the only solution, then \( \{ \mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\} \) is linearly independent; otherwise, if there are other solutions, then \( \{ \mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\} \) is linearly dependent.
Like we did with span, we can now write this vector equation as a linear system: specifically, it's the one with augmented matrix $$\left( \begin{matrix} | & | & & | \\ \mathbf{v}_1 & \mathbf{v}_2 & \dotsm & \mathbf{v}_m \\ | & | & & | \end{matrix} \; \left| \; \begin{matrix} | \\ \mathbf{0} \\ | \end{matrix} \right. \right).$$ This can also be written in matrix form as \( A\mathbf{x} = \mathbf{0}\), where $$A = \begin{pmatrix} | & | & & | \\ \mathbf{v}_1 & \mathbf{v}_2 & \dotsm & \mathbf{v}_m \\ | & | & & | \end{pmatrix}$$ and \(\mathbf{x} = (x_1, x_2, \dots, x_m)\).
Let's take a small detour to discuss this kind of linear system in general. A linear system like the one above, where all the numbers on the right side of the vertical bar are zero, is called a homogeneous system. In other words, homogeneous systems are linear systems with matrix form \( A\mathbf{x} = \mathbf{0}\).
A key fact about homogeneous systems is that they are always consistent, because they always have \(\mathbf{x} = \mathbf{0}\) as a solution. Therefore, homogeneous systems either have a unique solution (which must be \(\mathbf{x} = \mathbf{0}\)) or have infinitely many solutions.
Now, this means that when a homogeneous system is transformed to echelon form, none of the bottom rows can be contradictory. Therefore, if the echelon-form system has any free variables, then it must have infinitely many solutions, since each free variable can take on any real value. If the echelon-form system has no free variables, then it will have a unique solution (which, again, must be \(\mathbf{x} = \mathbf{0}\)).
Finally, remember that in echelon form, a free variable corresponds to a column of the (augmented) matrix with no pivots. Therefore:
Fact
Consider a homogeneous system \( A\mathbf{x} = \mathbf{0}.\) When \(A\) is transformed to echelon form, if every column has a pivot, then there are no free variables, so \( A\mathbf{x} = \mathbf{0}\) has a unique solution. On the other hand, if some column has no pivots, then \( A\mathbf{x} = \mathbf{0}\) has infinitely many solutions.
We can now apply this fact to our original question about linear independence, to get the following theorem:
Theorem
Let \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\) be vectors in \(\mathbb{R}^n\). Then, \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\) are linearly independent if and only if when the matrix $$\begin{pmatrix} | & | & & | \\ \mathbf{v}_1 & \mathbf{v}_2 & \dotsm & \mathbf{v}_m \\ | & | & & | \end{pmatrix}$$ is put in echelon form, every column has a pivot.
And as a result, we also get a corollary:
Corollary
Let \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\) be vectors in \(\mathbb{R}^n\). If \(m>n\), then \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\) cannot be linearly independent. That is, they must be linearly dependent.
This is because if \(m>n\), then the matrix $$\begin{pmatrix} | & | & & | \\ \mathbf{v}_1 & \mathbf{v}_2 & \dotsm & \mathbf{v}_m \\ | & | & & | \end{pmatrix}$$ has more columns than rows. Therefore, in echelon form, we can't possibly have enough pivots to put one in every column, because pivots must also be in different rows.
You may have noticed a striking similarity between these results and the ones from last week, about when vectors form a spanning set. Let's put them both here to compare:
Theorem
Let \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\) be vectors in \(\mathbb{R}^n\). Let \(A\) be the matrix with these vectors as columns, and transform it to echelon form to get \(A'\).
Then:
(1) \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\) span \(\mathbb{R}^n\) if and only if \(A'\) has a pivot in every row.
(2) \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\) are linearly independent if and only if \(A'\) has a pivot in every column.
(3) If \(m < n\), then \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\) cannot span \(\mathbb{R}^n\).
(4) If \(m > n\), then \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\) cannot be linearly independent.
This is really beautiful: all we have to do is reduce a matrix to echelon form, and we get to answer two questions at once!
Example
Suppose I have a \(2 \times 4\) matrix \(A\) and I tell you that $$\text{rref}(A) = \begin{pmatrix} 1 & 4 & 0 & -3 \\ 0 & 0 & 1 & 2 \end{pmatrix}.$$ (Recall that \(\text{rref}(A)\) is the reduced echelon form of \(A\), which is unique, but all we need to know is that it is in echelon form.)
What can we say about the columns of the original matrix \(A\)? Well, the pivots of \(\text{rref}(A)\) are in \(A_{1,1}\) and \(A_{2,3}\). Therefore, there is a pivot in every row, but not a pivot in every column. This means that the columns of \(A\) are a spanning set for \(\mathbb{R}^2\), but are not linearly independent.
In fact, even before I told you what \(\text{rref}(A)\) is, you could have already said that the columns are not linearly independent. After all, there is no way that a \(2 \times 4\) matrix in echelon form can have a pivot in each of its 4 columns, since there can only be up to 2 pivots anyway (at most one in each row).
There is also yet another way to think about spanning sets and linearly independent sets. Remember that \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\) span \(\mathbb{R}^n\) if and only if the linear system with augmented matrix $$\left( \begin{matrix} | & | & & | \\ \mathbf{v}_1 & \mathbf{v}_2 & \dotsm & \mathbf{v}_m \\ | & | & & | \end{matrix} \; \left| \; \begin{matrix} | \\ \mathbf{b} \\ | \end{matrix} \right. \right)$$ has a solution for every vector \( \mathbf{b} \in \mathbb{R}^n \). Now that we know about matrix form, we can write this much more neatly: \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\) span \(\mathbb{R}^n\) if and only if \(A\mathbf{x} = \mathbf{b}\) has a solution for every \(\mathbf{b}\), where \(A\) is the matrix with columns \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\).
In fact, there is an "opposite" statement we can make for linearly independent sets:
Theorem
Let \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\) be vectors in \(\mathbb{R}^n\), and let \(A\) be the matrix with \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\) as columns. Then \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\) are linearly independent if and only if \(A\mathbf{x} = \mathbf{b}\) has at most one solution for every \(\mathbf{b}\).
To see why this is true, let's first suppose that \(A\mathbf{x} = \mathbf{b}\) has at most one solution for every \(\mathbf{b}\). Well, since this is true for every \(\mathbf{b}\), we can take \(\mathbf{b}\) to be the zero vector, and get that \(A\mathbf{x} = \mathbf{0}\) has at most one solution. But this is a homogeneous system, so it always has the solution \(\mathbf{x} = \mathbf{0}\). Therefore, \(A\mathbf{x} = \mathbf{0}\) has a unique solution, which we know means that \(\mathbf{v}_1, \dots, \mathbf{v}_m\) are linearly independent.
On the other hand, suppose that it is not true that \(A\mathbf{x} = \mathbf{b}\) has at most one solution for every \(\mathbf{b}\). Then, for some particular value of \(\mathbf{b}\), we have (at least) two distinct solutions to \(A\mathbf{x} = \mathbf{b},\) say \(\mathbf{x} = (x_1, \dots, x_m)\) and \(\mathbf{x'} = (x_1', \dots, x_m')\). This means that \(\mathbf{b}\) can be written as two different linear combinations of \(\mathbf{v}_1, \dots, \mathbf{v}_m\), namely $$x_1 \mathbf{v}_1 + \dotsm + x_m \mathbf{v}_m \qquad \text{and} \qquad x'_1 \mathbf{v}_1 + \dotsm + x'_m \mathbf{v}_m.$$ This means that the difference of these two linear combinations must be the zero vector. In other words, we get $$(x_1-x_1') \mathbf{v}_1 + \dotsm + (x_m-x_m') \mathbf{v}_m = \mathbf{0}.$$ This says that a linear combination of \(\mathbf{v}_1, \dots, \mathbf{v}_m\) equals the zero vector. Furthermore, because we know that \(\mathbf{x} = (x_1, \dots, x_m)\) and \(\mathbf{x}' = (x'_1, \dots, x'_m)\) are different, the coefficients \(x_1 - x_1', \dots, x_m - x_m'\) cannot all be zero! Thus, \(\mathbf{v}_1, \dots, \mathbf{v}_m\) must be linearly dependent.
To summarize all of this, here is a table.
Let \( \mathbf{v}_1, \dots, \mathbf{v}_m \in \mathbb{R}^n\) and let \(A\) be the \(n \times m\) matrix with columns \( \mathbf{v}_1, \dots, \mathbf{v}_m \). Suppose \(A'\) is an echelon-form matrix equivalent to \(A\).
| \( \mathbf{v}_1, \dots, \mathbf{v}_m \) span \( \mathbb{R}^n \) | \( \mathbf{v}_1, \dots, \mathbf{v}_m \) are linearly independent |
|---|---|
| ...if and only if every row of \(A'\) has a pivot. | ...if and only if every column of \(A'\) has a pivot. |
| ...if and only if \(A \mathbf{x} = \mathbf{b}\) has at least one solution for all \(\mathbf{b} \in \mathbb{R}^n\). | ...if and only if \(A \mathbf{x} = \mathbf{b}\) has at most one solution for all \(\mathbf{b} \in \mathbb{R}^n\). |
| This is impossible if \(m < n\). | This is impossible if \(m > n\). |
There is one glaring hole in our analysis up to now: what if \(m=n\)? Well, it turns out that's where all the magic happens!
Suppose we have \(n\) vectors \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n\) in \(\mathbb{R}^n\). Then, the matrix \(A\) with those vectors as columns is an \(n \times n\) matrix, which we call a square matrix. For a square matrix, we can say something special: when \(A\) is transformed into echelon form, it has a pivot in every row if and only if it has a pivot in every column. (Indeed, in both cases, the pivots need to go straight down the diagonal from top-left to bottom-right.) This leads us to what we'll call the unifying theorem of linear algebra: a long list of statements that are all equivalent and span the breadth of the topics in this course.
Note: The name "unifying theorem" is not standard in linear algebra! It appears to be a UW Math Department original.
The Unifying Theorem, version 1
Let \(A\) be an \(n \times n\) matrix with columns \(\mathbf{v}_1, \dots, \mathbf{v}_n\). Then, the following are equivalent:
(i) \(\mathbf{v}_1, \dots, \mathbf{v}_n\) span \(\mathbb{R}^n\).
(ii) \(\mathbf{v}_1, \dots, \mathbf{v}_n\) are linearly independent.
(iii) For all \(\mathbf{b} \in \mathbb{R}^n\), the linear system \(A\mathbf{x} = \mathbf{b}\) has exactly one solution.
("The following are equivalent" means that either all the statements are true, or all the statements are false.)