Last time, we defined basis and dimension, and we saw two methods to take a subspace given in the form \(S = \text{span}(\mathbf{v}_1, \dots, \mathbf{v}_m)\) and produce a basis for \(S\):
Let's see both of these in action:
Example (basis for column space and row space)
Let \(A\) be the matrix \(\begin{bmatrix} 2 & 4 & 3 & -1 \\ 1 & 2 & -1 & 2 \\ 1 & 2 & 0 & 1 \end{bmatrix}.\) Given that \(\text{rref}(A) = \begin{bmatrix} 1 & 2 & 0 & 1 \\ 0 & 0 & 1 & -1 \\ 0 & 0 & 0 & 0 \end{bmatrix},\) find a basis for \(\text{col}(A)\) and a basis for \(\text{row}(A).\)
For the column space, we notice that the pivots of \(\text{rref}(A)\) are in columns 1 and 3. This means that the first and third columns of \(A\) are linearly independent, and span \(\text{col}(A),\) so we can take them as a basis: \[\text{col}(A) \quad \text{has basis} \quad \begin{bmatrix} 2 \\ 1 \\ 1 \end{bmatrix}, \; \begin{bmatrix} 3 \\ -1 \\ 0 \end{bmatrix}.\] For the row space we can simply take the nonzero rows of \(\text{rref}(A),\) so that \[\text{row}(A) \quad \text{has basis} \quad \begin{bmatrix} 1 \\ 2 \\ 0 \\ 1 \end{bmatrix}, \; \begin{bmatrix} 0 \\ 0 \\ 1 \\ -1 \end{bmatrix}.\]
Note: if you'd like, you can compute a basis for \(\text{col}(A)\) by using the rows method instead of the columns method. In other words, you can "flip" (take the transpose) of the matrix \(A,\) so that the columns become the rows, and then work with that matrix instead. Similarly, you can compute a basis for \(\text{row}(A)\) by taking the transpose of \(A\) and using the columns method instead of the rows method. The advantage of doing it this way is that by doing one row reduction, we get bases for both \(\text{col}(A)\) and \(\text{row}(A).\)
The third and remaining space associated to a matrix \(A\), as we saw on Monday, is the null space of \(A\): the set of all vectors \(\mathbf{x}\) such that \(A\mathbf{x} = \mathbf{0}.\) (Remember: the null space of a matrix equals the kernel of the corresponding linear transformation!) Therefore, finding a basis for \(\text{null}(A)\) amounts to solving a homogeneous linear system. We already know how to do this, but let's see how to get a basis from the solution set of the system.
Example (basis for null space)
Let \(A\) be the matrix \(\begin{bmatrix} 2 & 4 & 3 & -1 \\ 1 & 2 & -1 & 2 \\ 1 & 2 & 0 & 1 \end{bmatrix}\) (same as above). Find a basis for \(\text{null}(A).\)
Because of how row reduction works, we know that the system \(A\mathbf{x} = \mathbf{0}\) has the same solution set as \(B\mathbf{x} = \mathbf{0}\) where \(B = \text{rref}(A).\) To solve the latter system, we can use the usual method of setting free parameters and then solving for the pivot variables. In our case, we have the system \[\begin{array}\ x_1 &+& 2x_2 && &+& x_4 &=& 0 \\ && && x_3 &-& x_4 &=& 0 \end{array}\] Here, \(x_2\) and \(x_4\) are free variables, and we can solve for the other variables in terms of them: \(x_3 = x_4\) and \(x_1 = -2x_2 - x_4.\) So, our solution set, which is \(\text{null}(A),\) is parametrized by \[\begin{bmatrix} -2x_2 - x_4 \\ x_2 \\ x_4 \\ x_4 \end{bmatrix} \qquad \text{for } x_2, x_4 \in \mathbb{R}.\] To get a basis for \(\text{null}(A),\) we can write this expression as a linear combination with coefficients \(x_2\) and \(x_4\): \[\begin{bmatrix} -2x_2 - x_4 \\ x_2 \\ x_4 \\ x_4 \end{bmatrix} = x_2 \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} + x_4 \begin{bmatrix} -1 \\ 0 \\ 1 \\ 1 \end{bmatrix}.\] It follows that \(\text{null}(A)\) equals the span of the two vectors \[\begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} \qquad \text{and} \qquad \begin{bmatrix} -1 \\ 0 \\ 1 \\ 1 \end{bmatrix}.\] Because these vectors are also linearly independent, they form a basis for \(\text{null}(A).\)
Here is the general method that this example points to:
Method (basis from a homogeneous system)
Given a homogeneous system \(A\mathbf{x} = \mathbf{0},\) we can find a basis for the solution set (AKA \(\text{null}(A)\)) as follows:
- Use row reduction to transform \(A\) into echelon form.
- Identify the free variables and write the other variables in terms of the free variables. This gives a parametrization of the solution set in terms of the free variables.
- Write this parametrization as a linear combination of certain vectors, with the free variables (or free parameters) as coefficients.
- These vectors will form a basis for the solution set.
Note: the vectors we obtain using this method will always be linearly independent, so they will automatically form a basis. This is because, for each free variable \(x_i\), the corresponding vector will have \(1\) in the \(i\)th position, whereas all the other vectors will have \(0\) in the \(i\)th position. Thus, to have a linear combination of these vectors equal \(\mathbf{0}\), each coefficient must be \(0\) (in order to make the \(i\)th component zero).
Therefore, by row reducing a matrix, we can easily extract bases for all three of its associated subspaces: the column space, the row space, and the null space! Lovely.
Let's now take a look at some more theory about bases and dimension.
We now know that a basis of a subspace of \(\mathbb{R}^n\) is a set of vectors that is simultaneously a spanning set and a linearly independent set. We also know intuitively that adding vectors to a set will get it "closer" to a spanning set, and removing vectors from a set will get it "closer" to being linearly independent. In fact, this corresponds to two ways to build a basis of a given subspace:
Theorem (building a basis in two ways)
Let \(S\) be a subspace of \(\mathbb{R}^n\) and let \(d = \text{dim}(S).\) Suppose we have vectors \(\mathbf{v}_1, \dots, \mathbf{v}_m \in S.\)
(i) If \(\mathbf{v}_1, \dots, \mathbf{v}_m\) span \(S,\) then it is possible to delete some of the \(\mathbf{v}_i\) from the list (possibly none) to get a basis for \(S.\)
(ii) If \(\mathbf{v}_1, \dots, \mathbf{v}_m\) are linearly independent, then it is possible to add some other vectors in \(S\) to the list (possibly none) to get a basis for \(S.\)
Notice that (i) is essentially what the columns method does: it throws away some of the vectors from a spanning set so that the remaining vectors form a basis.
In order to perform (ii), we can take some known basis \((\mathbf{w}_1, \dots, \mathbf{w}_d)\) for \(S\) and add it to the end of our list, to get \(\mathbf{v}_1, \dots, \mathbf{v}_m, \mathbf{w}_1, \dots, \mathbf{w}_d.\) This vectors span \(S\) because we added an entire basis for \(S,\) so now we can use the columns method to remove redundant vectors and get a basis: form the matrix \[A = \begin{bmatrix} | & & | & | & & | \\ \mathbf{v}_1 & \dotsm & \mathbf{v}_m & \mathbf{w}_1 & \dotsm & \mathbf{w}_d \\ | & & | & | & & | \end{bmatrix},\] put it into echelon form, and use the locations of the pivots to choose which columns of \(A\) to keep.
The key is: because \(\mathbf{v}_1, \dots, \mathbf{v}_m\) are linearly independent, when \(A\) is put into echelon form, the first \(m\) columns will all have pivots. Therefore, this process won't throw away any of \(\mathbf{v}_1, \dots, \mathbf{v}_m.\)
Example (extending a list of vectors to a basis)
Again, let \(A = \begin{bmatrix} 2 & 4 & 3 & -1 \\ 1 & 2 & -1 & 2 \\ 1 & 2 & 0 & 1 \end{bmatrix}.\) Find a basis for \(\text{col}(A)\) that contains the vector \(\begin{bmatrix} 5 \\ 0 \\ 1 \end{bmatrix}\).
From earlier, we know that \[\begin{bmatrix} 2 \\ 1 \\ 1 \end{bmatrix} \qquad \text{and} \qquad \begin{bmatrix} 3 \\ -1 \\ 0 \end{bmatrix}\] form a basis for \(\text{col}(A).\) So, let's now row-reduce the matrix \[A' = \begin{bmatrix} 5 & 2 & 3 \\ 0 & 1 & -1 \\ 1 & 1 & 0 \end{bmatrix} \longrightarrow \dotsm \longrightarrow B' = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & -1 \\ 0 & 0 & 0 \end{bmatrix}.\] Since the first two columns of \(B'\) have pivots, this means that we can take the first two columns of \(A'\) as a basis for \(\text{col}(A).\) In other words, we can add \(\begin{bmatrix} 2 \\ 1 \\ 1 \end{bmatrix}\) to our list to get a basis.
Note: Because the first and third columns of \(B'\) are also linearly independent, we could also take the first and third columns of \(A'\) as a basis for \(\text{col}(A).\) That is, we could add \(\begin{bmatrix} 3 \\ -1 \\ 0 \end{bmatrix}\) instead.
As a consequence of this Theorem, we can prove a large number of facts about bases and the dimension of a subspace of \(\mathbb{R}^n.\) (Take some time to make sure that each of these facts "makes sense" intuitively.)
Corollary (dimension, spanning sets, and linearly independent sets)
Let \(S\) be a subspace of \(\mathbb{R}^n\) and let \(d = \text{dim}(S).\) Suppose we have vectors \(\mathbf{v}_1, \dots, \mathbf{v}_m \in S.\)
(i) If \(m < d,\) then \(\mathbf{v}_1, \dots, \mathbf{v}_m\) cannot span \(S.\)
(ii) If \(m > d,\) then \(\mathbf{v}_1, \dots, \mathbf{v}_m\) cannot be linearly independent.
To prove (i), suppose that \(m < d\) and \(\mathbf{v}_1, \dots, \mathbf{v}_m\) span \(S\). By the above theorem, we can delete some of these vectors (possibly none) to get a basis for \(S.\) But that basis of \(S\) would have at most \(m\) vectors, therefore strictly less than \(d\) vectors. But every basis of \(S\) must have size \(d,\) so this is a contradiction.
The proof of (ii) is similar. Suppose that \(m > d\) and \(\mathbf{v}_1, \dots, \mathbf{v}_m\) are linearly independent. Then, by the above theorem, we can add some vectors (possibly none) to get a basis for \(S.\) But then we would get a basis for \(S\) with strictly more than \(d\) vectors, which is again a contradiction.
Note: In the case that \(S = \mathbb{R}^n,\) we recover a fact we already knew: fewer than \(n\) vectors cannot span \(\mathbb{R}^n,\) and more than \(n\) vectors in \(\mathbb{R}^n\) cannot be linearly independent.
Corollary (\(d\) vectors in a dimension-\(d\) subspace)
Let \(S\) be a subspace of \(\mathbb{R}^n\) and let \(d = \text{dim}(S).\) Suppose we have vectors \(\mathbf{v}_1, \dots, \mathbf{v}_d \in S.\) Then, the following are equivalent:
(i) \(\mathbf{v}_1, \dots, \mathbf{v}_d\) span \(S.\)
(ii) \(\mathbf{v}_1, \dots, \mathbf{v}_d\) are linearly independent.
(iii) \(\mathbf{v}_1, \dots, \mathbf{v}_d\) form a basis for \(S.\)
To see why this is true, suppose that \(\mathbf{v}_1, \dots, \mathbf{v}_d\) span \(S.\) By the above theorem, we can delete some of these vectors (possibly none) to get a basis for \(S.\) But a basis for \(S\) must have exactly \(d\) vectors, so none of the vectors can be deleted. This means that \(\mathbf{v}_1, \dots, \mathbf{v}_d\) must already be a basis for \(S\). Therefore, (i) implies (iii). A similar argument using the other half of the theorem shows that (ii) implies (iii). Finally, by definition, (iii) implies both (i) and (ii). Therefore, all three of these are equivalent.
Note: In the case that \(S = \mathbb{R}^n,\) we recover (part of) the unifying theorem: given \(n\) vectors in \(\mathbb{R}^n,\) they span \(\mathbb{R}^n\) if and only if they are linearly independent.
Corollary (nested subspaces)
Suppose that \(S_1\) and \(S_2\) are subspaces of \(\mathbb{R}^n,\) and \(S_1 \subseteq S_2.\) Then \(\text{dim}(S_1) \le \text{dim}(S_2).\) Furthermore, \(\text{dim}(S_1) = \text{dim}(S_2)\) if and only if \(S_1 = S_2.\)
To prove this, let \(\text{dim}(S_1) = d,\) and \(\mathbf{v}_1, \dots, \mathbf{v}_d\) be a basis for \(S_1.\) This is a list of linearly independent vectors, and they all lie in \(S_2\) because \(S_1 \subseteq S_2.\) Therefore, we can add some vectors from \(S_2\) to the list to get a basis for \(S_2.\) This means that the dimension of \(S_2\) is at least \(d,\) as we wanted.
If the dimension of \(S_2\) is exactly \(d,\) then this original list \(\mathbf{v}_1, \dots, \mathbf{v}_d\) must already be a basis for \(S_2.\) Then \(S_1\) and \(S_2\) must be the same, since they are both equal to the span of \(\mathbf{v}_1, \dots, \mathbf{v}_d.\)
Note: In the case that \(S = \mathbb{R}^n,\) we see that the only \(n\)-dimensional subspace of \(\mathbb{R}^n\) is \(\mathbb{R}^n\) itself; all other subspaces have dimension strictly less than \(n.\)