Pre-Class Warmup

Example

Let \(\mathbf{u} = (2, 3).\) If I have some other vector \(\mathbf{v} \in \mathbb{R}^2\), what are the possibilities for \(\text{span}(\mathbf{u}, \mathbf{v})\)? When does each possibility occur?

On Monday, we introduced the concepts of linear combinations and span. We saw one way to tell if one vector is in the span of a set of vectors, and how to visualize span geometrically. Today we will finish our discussion of span and then begin to talk about linear independence.

Spanning sets

An important case of span is when we have some vectors \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\) in \(\mathbb{R}^n\) such that \(\text{span}(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m)\) is the entirety of \(\mathbb{R}^n\). In other words, every vector can be written as a linear combination of \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\).

In this case, we say that \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\) span (all of) \(\mathbb{R}^n\), or that \(\{\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\}\) is a spanning set for \(\mathbb{R}^n\).

Example

Consider the two vectors \(\mathbf{u} = \begin{pmatrix} 2 \\ 1 \\ 0 \end{pmatrix}\) and \(\mathbf{v} = \begin{pmatrix} 1 \\ -3 \\ -2 \end{pmatrix}\). Is it true that \(\text{span}(\mathbf{u}, \mathbf{v}) = \mathbb{R}^3\)?

To figure this out, we can consider a general vector in \(\mathbb{R}^3\), say

\[\mathbf{b} = \begin{pmatrix} b_1 \\ b_2 \\ b_3 \end{pmatrix}.\]

Remember that, to tell if \(\mathbf{b}\) is a linear combination of \(\mathbf{u}\) and \(\mathbf{v}\), we should see if the system / augmented matrix

\[\left\{ \begin{array}\ 2x_1 &+& x_2 &=& b_1 \\ x_1 &-& 3x_2 &=& b_2 \\ &-& 2x_2 &=& b_3 \end{array} \right. \qquad \longleftrightarrow \qquad \left( \begin{matrix} 2 & 1 \\ 1 & -3 \\ 0 & -2 \end{matrix} \; \left| \; \begin{matrix} b_1 \\ b_2 \\ b_3 \end{matrix} \right. \right)\]

is consistent. To do that, we can use Gaussian elimination (or Gauss-Jordan elimination), treating \(b_1, b_2, b_3\) as unknown parameters. Luckily it only takes two (somewhat messy) steps to get to echelon form:

\[\begin{aligned} \left( \begin{matrix} 2 & 1 \\ 1 & -3 \\ 0 & -2 \end{matrix} \; \left| \; \begin{matrix} b_1 \\ b_2 \\ b_3 \end{matrix} \right. \right) \quad\stackrel{-\frac{1}{2}R_1+R_2 \to R_2}\longrightarrow\quad \left( \begin{matrix} 1 & 1 \\ 0 & -\frac{7}{2} \\ 0 & -2 \end{matrix} \; \left| \; \begin{matrix} b_1 \\ -\frac{1}{2}b_1 + b_2 \\ b_3 \end{matrix} \right. \right) \stackrel{-\frac{4}{7}R_2+R_3 \to R_3}\longrightarrow\quad &\left( \begin{matrix} 1 & 1 \\ 0 & -4 \\ 0 & 0 \end{matrix} \; \left| \; \begin{matrix} b_1 \\ -b_1 + b_2 \\ \frac{2}{7}b_1 - \frac{4}{7}b_2 + b_3 \end{matrix} \right. \right). \end{aligned}\]

Is this system consistent? Well, it depends on the values of \(b_1, b_2, b_3\). The issue is the bottom row, which has all zeros to the left of the bar. If \(\frac{2}{7}b_1 - \frac{4}{7}b_2 + b_3\) is nonzero, then the bottom row gives a contradictory equation, and we won't have any solutions. On the other hand, if \(\frac{2}{7}b_1 - \frac{4}{7}b_2 + b_3 = 0\), then the bottom row can be ignored, and the rest of the system can be solved to get a (unique) solution.
Putting it all together, we have shown that

\[\text{span}(\mathbf{u}, \mathbf{v}) = \{ (b_1, b_2, b_3) \in \mathbb{R}^3 : \frac{2}{7}b_1 - \frac{4}{7}b_2 + b_3 = 0 \}.\]
In other words, a vector \((b_1, b_2, b_3)\) is in the span of \(\mathbf{u}\) and \(\mathbf{v}\) if and only if \(\frac{2}{7}b_1 - \frac{4}{7}b_2 + b_3 = 0\). This is the equation for a plane in \(\mathbb{R}^3\), which is a reasonable result because we started with two nonzero vectors, which in general will span a "two-dimensional" object, namely a plane (unless they lie on the same line).

Also, you may remember that we looked at these two vectors in Monday's class, when we found that the vector \(\mathbf{w} = (0, 7, 4)\) is in the span of \(\mathbf{u}\) and \(\mathbf{v}\). We can check that this makes sense, because \(\frac{2}{7}(0) - \frac{4}{7}(7) + 4 = 0.\)

In fact, we can follow the above example to get a general procedure for determining when a set of vectors spans \(\mathbb{R}^n\). Let \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\) be vectors in \(\mathbb{R}^n\). Then, given any vector \(\mathbf{w}\) in \(\mathbb{R}^n\), we know we want to try to solve the linear system with the augmented matrix

\[\left( \begin{matrix} | & | & & | \\ \mathbf{v}_1 & \mathbf{v}_2 & \dotsm & \mathbf{v}_m \\ | & | & & | \end{matrix} \; \left| \; \begin{matrix} | \\ \mathbf{w} \\ | \end{matrix} \right. \right)\]

to figure out whether \(\mathbf{w}\) is in the span of \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\). Let \(A\) be the part of the matrix to the left of the bar. Then, Gaussian elimination will turn \(A\) into some matrix \(A'\) in echelon form, and it will turn the right side (the vector \(\mathbf{w}\)) into some other vector \(\mathbf{w}'\):

\[\left( \begin{matrix} | & | & & | \\ \mathbf{v}_1 & \mathbf{v}_2 & \dotsm & \mathbf{v}_m \\ | & | & & | \end{matrix} \; \left| \; \begin{matrix} | \\ \mathbf{w} \\ | \end{matrix} \right. \right) = \left( A\; |\; \mathbf{w} \right) \quad \stackrel{\text{Gaussian elimination}}\longrightarrow \quad \left( A'\; |\; \mathbf{w'} \right).\]

(A technical detail: because Gaussian elimination operates using the leftmost entries as pivots, the process will always work the same way on the left part of the augmented matrix, no matter what \(\mathbf{w}\) is.)

We saw from the example that if \(A'\) has any rows of all zeros at the bottom (that is, rows without pivots), then we're in trouble: we will be able to find some value for \(\mathbf{w}\) such that the last component of \(\mathbf{w}'\) is nonzero. Then, the bottom row of \(\left( A'\; |\; \mathbf{w'} \right)\) will give a contradiction. On the other hand, if every row of \(A'\) has a pivot, then the system will always be solvable using back-substitution.

Thus, we have the following result:

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\) span \(\mathbb{R}^n\) 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 row has a pivot.

We also have an immediate consequence of this theorem (this kind of result is called 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 span \(\mathbb{R}^n\).

Why is this? Well, notice that if \(m < n,\) then the matrix \[\begin{pmatrix} | & | & & | \\ \mathbf{v}_1 & \mathbf{v}_2 & \dotsm & \mathbf{v}_m \\ | & | & & | \end{pmatrix}\]

is taller than it is wide (it has \(n\) rows and \(m\) columns). Of course, this will still be true when we reduce the matrix to echelon form. But then we cannot have a pivot in every row, because the pivots need to occupy different columns! This means that, according to the theorem, \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\) do not span \(\mathbb{R}^n\).

In other words, we need at least \(n\) vectors to span \(\mathbb{R}^n\). This makes intuitive sense because \(\mathbb{R}^n\) is \(n\)-dimensional; it has \(n\) "independent" directions that you can go in.

A word of warning

Even though we need at least \(n\) vectors to span \(\mathbb{R}^n\), this doesn't mean that any set of at least \(n\) vectors will work! For example, we could choose a bunch of vectors that all lie on the same line; no matter how many we choose, their span will only be that line. (We could even choose some or all of the vectors to be the zero vector.)

Ways of thinking about a linear system

Now that we know about span, let's take a step back and see all the different ways we can express a linear system:

1. First, every linear system is at its core a list of linear equations:
   
   \[\left\{ \begin{align*} a_{1,1}x_1 + a_{1,2}x_2 + \dotsm + a_{1,n} x_n &= b_1 \\ a_{2,1}x_1 + a_{2,2}x_2 + \dotsm + a_{2,n} x_n &= b_2 \\ &\vdots \\ a_{m,1}x_1 + a_{m,2}x_2 + \dotsm + a_{m,n} x_n &= b_m \end{align*} \right.\]
   
2. Then, last week we learned how to express a linear system as an augmented matrix and use Gaussian elimination / Gauss-Jordan elimination to solve it:
   
   \[\left( \begin{matrix} a_{11} & a_{12} & \dotsm & a_{1n} \\ a_{21} & a_{22} & \dotsm & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \dotsm & a_{mn} \end{matrix} \; \left| \; \begin{matrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{matrix} \right. \right)\]
   
3. On Monday, we discovered that solving a linear system tells us whether one vector is in the span of a set of vectors. In other words, we can write the system as a vector equation:
   
   \[x_1 \begin{pmatrix} a_{11} \\ a_{21} \\ \vdots \\ a_{m1} \end{pmatrix} + x_2 \begin{pmatrix} a_{12} \\ a_{22} \\ \vdots \\ a_{m2} \end{pmatrix} + \dotsm + x_n \begin{pmatrix} a_{1n} \\ a_{2n} \\ \vdots \\ a_{mn} \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{pmatrix}\]
   As we saw, the vectors we care about come from the columns of the augmented matrix in this situation.
   
   
4. Finally, we will introduce a way of writing a linear system in matrix form. If we have a matrix \(A = \begin{pmatrix} a_{11} & a_{12} & \dotsm & a_{1n} \\ a_{21} & a_{22} & \dotsm & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \dotsm & a_{mn} \end{pmatrix}\) and a vector \(\mathbf{x} = \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix},\) we will define \(A \mathbf{x}\) to be the vector on the left-hand side of the above vector equation:
   
   \[A \mathbf{x} = x_1 \begin{pmatrix} a_{11} \\ a_{21} \\ \vdots \\ a_{m1} \end{pmatrix} + x_2 \begin{pmatrix} a_{12} \\ a_{22} \\ \vdots \\ a_{m2} \end{pmatrix} + \dotsm + x_n \begin{pmatrix} a_{1n} \\ a_{2n} \\ \vdots \\ a_{mn} \end{pmatrix}.\]
   In other words, \(A\mathbf{x}\) is the linear combination of the columns of \(A\), with coefficients equal to the components of \(\mathbf{x}.\) Now, if we let \(\mathbf{b} = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{pmatrix},\) then our system can be written concisely as just \(A\mathbf{x} = \mathbf{b}\).
   For now, you can think of this as simply a shorthand. Later on, we will use this to actually define matrix multiplication.
   
   Note: \(A\mathbf{x}\) is only defined when the number of columns of \(A\) equals the number of components of \(\mathbf{x}.\)
   
   

Linear (in)dependence

Let's now begin our discussion of another crucial concept related to vectors, namely linear independence (or linear dependence, which is the opposite). The motivation for this idea comes from something we saw when looking at examples of span: namely, if we have two (nonzero) vectors \(\mathbf{u}, \mathbf{v}\) in \(\mathbb{R}^2\) (or in any \(\mathbb{R}^n\)) which lie on the same line, then the span of \(\mathbf{u}, \mathbf{v}\) together is the same as the span of just \(\mathbf{u}\), or the span of just \(\mathbf{v}\). Intuitively, there is some "redundancy" or "dependency" between \(\mathbf{u}\) and \(\mathbf{v}\) since they point along the same line.

In general, suppose we have a list of vectors. If we add another vector to that list, then the span of the vectors may become larger, or it may stay the same. However, if the vector we added is already in the span of the original vectors, then the span will not change. That's what the following theorem says:

Theorem

Let \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\) be vectors in \(\mathbb{R}^n\). Suppose that \(\mathbf{w}\) lies in \(\text{span}(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m).\) Then, \(\text{span}(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m, \mathbf{w}) = \text{span}(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m).\)

For this class, we won't worry about formal proofs, but let's get a sense of why this is true algebraically. First, if a vector can be written as a linear combination of \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\), then it can also be written as a linear combination of \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m, \mathbf{w}\), because we can simply "not use" \(\mathbf{w}\). (That is, we can take its coefficient in the linear combination to be \(0\).)

On the other hand, suppose we have a vector \(\mathbf{u}\) that is a linear combination of \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m, \mathbf{w}\). That means we can write it in the form \(\mathbf{u} = a_1 \mathbf{v}_1 + a_2 \mathbf{v}_2 + \dotsm + a_m \mathbf{v}_m + b \mathbf{w}\) for some coefficients \(a_1, a_2, \dots, a_m, b.\) However, we know that \(\mathbf{w}\) is itself a linear combination of \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\): therefore, \(\mathbf{w} = c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2 + \dotsm + c_m \mathbf{v}_m\) for some other coefficients \(c_1, c_2, \dots, c_m.\) Now, we can substitute this formula into our equation for \(\mathbf{u}\) to get

\[\mathbf{u} = a_1 \mathbf{v}_1 + a_2 \mathbf{v}_2 + \dotsm + a_m \mathbf{v}_m + b \left( c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2 + \dotsm + c_m \mathbf{v}_m \right).\]

Don't be scared! The point is just that, now when we simplify the right-hand side, we'll get a linear combination of just \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\), without any \(\mathbf{w}\)'s involved. So, any linear combination of \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m, \mathbf{w}\) is also a linear combination of \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\). Putting all this together, we can conclude that \(\text{span}(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m, \mathbf{w}) = \text{span}(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m).\)

It turns out that this is exactly the notion of linear dependency that we want to define.

Definition

Vectors \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m \in \mathbb{R}^n\) are said to be linearly dependent if (at least) one of the vectors lies in the span of all the other vectors.

If not, they are said to be linearly independent.

Your book gives a slightly different, but equivalent definition. Suppose that some \(\mathbf{v}_i\) is in the span of the other vectors; for example, we could have \(\mathbf{v}_2 = \mathbf{v}_1 - 2\mathbf{v}_3\) (when \(m=3\) and \(i=2\)). If we now move all the terms to one side, we will get something like \(-\mathbf{v}_1 + \mathbf{v}_2 + 2\mathbf{v}_3 = \mathbf{0}\). In general, we will get a linear combination of all the vectors which equals zero, but where not all the coefficients are zero. This gives us an equivalent definition of linear dependence.

Equivalent Definition

Vectors \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m \in \mathbb{R}^n\) are said to be linearly dependent if we can find scalars \(c_1, c_2, \dots, c_m\) such that not all of them are equal to zero, and \(c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \dotsm + c_m\mathbf{v}_m = \mathbf{0}\).

As an analogy, we can imagine that each of our given vectors \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\) is a direction we are allowed to "travel" in. A linear combination then represents a path where we start at the origin, travel along the \(\mathbf{v}_1\) direction (either forwards or backwards!) for some distance (possibly zero), then travel along the \(\mathbf{v}_2\) direction for some distance, and so on, eventually ending up somewhere. If the vectors are linearly dependent, then it is possible to travel in this way and end up back at the origin (back where we started).

Notice, however, that the coefficients in our linear combination cannot all be zero. This corresponds to saying that, if we choose to travel along each direction for zero distance, then of course we'll get back to the origin, because we didn't move at all! But that is true regardless of what vectors we started with, so that doesn't really tell us anything about our vectors.

An equation of the form \(c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \dotsm + c_m\mathbf{v}_m = \mathbf{0}\) is often called a linear relation between the vectors \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\). The trivial linear relation is the one where all of \(c_1, c_2, \dots, c_m\) equal zero: \(0\mathbf{v}_1 + 0\mathbf{v}_2 + \dotsm + 0\mathbf{v}_m = \mathbf{0}\). (It's called trivial because it is always true and so it doesn't tell us anything about \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\).) Any other linear relation is called nontrivial. Then:

Equivalent Definition

Vectors \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\) are said to be linearly dependent if there is a nontrivial linear relation between them.

On the other hand, they are said to be linearly independent if the only linear relation between them is the trivial one.

Next week, we'll look at how to tell if a list of vectors \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_m\) is linearly independent or linearly dependent, and how the two ideas of being linearly independent and spanning (all of) \(\mathbb{R}^n\) are related.