Subspaces of \(\RR ^n\) Associated with Matrices

Row Space of a Matrix

Recall that in Gaussian Elimination and Rank, we claimed that every row-echelon form of a given matrix has the same number of nonzero rows. This result suggests that there are certain characteristics associated with the rows of a matrix that are not affected by elementary row operations. We are now in the position to examine this question and to supply the proof we omitted earlier.

Consider the matrix
\[A=\begin{bmatrix}-2&2&1\\4&-2&1\end{bmatrix}\]
Let \(\vec {r}_1\) and \(\vec {r}_2\) be the rows of \(A\):
\[\vec {r}_1=\begin{bmatrix}-2&2&1\end{bmatrix},\quad \vec {r}_2=\begin{bmatrix}4&-2&1\end{bmatrix}\]

Then \(\mbox {row}(A)=\mbox {span}(\vec {r}_1, \vec {r}_2)\) is a plane through the origin containing \(\vec {r}_1\) and \(\vec {r}_2\).

[Picture]

We will use elementary row operations to reduce \(A\) to \(\mbox {rref}(A)\).

\[\begin{bmatrix}-2&2&1\\4&-2&1\end{bmatrix}\rightsquigarrow \begin{bmatrix}1&0&1\\0&1&3/2\end{bmatrix}\]
Let \(\vec {\rho }_1\) and \(\vec {\rho }_2\) be the rows of \(\mbox {rref}(A)\):
\[\vec {\rho }_1=\begin{bmatrix}1&0&1\end{bmatrix},\quad \vec {\rho }_2=\begin{bmatrix}0&1&3/2\end{bmatrix}\]
What do you think \(\mbox {span}(\vec {\rho }_1, \vec {\rho }_2)\) looks like?

The following video will help us visualize \(\mbox {span}(\vec {\rho }_1, \vec {\rho }_2)\) and compare it to \(\mbox {span}(\vec {r}_1, \vec {r}_2)\).

Based on what we observed in the video, we may conjecture that

\[\mbox {span}(\vec {\rho }_1, \vec {\rho }_2)=\mbox {span}(\vec {r}_1, \vec {r}_2)\]

[Picture]

But why does this make sense? Vectors \(\vec {\rho }_1\) and \(\vec {\rho }_2\) were obtained from \(\vec {r}_1\) and \(\vec {r}_2\) by repeated applications of elementary row operations. At every stage of the row reduction process, the rows of the matrix are linear combinations of \(\vec {r}_1\) and \(\vec {r}_2\). Thus, at every stage of the row reduction process, the rows of the matrix lie in the span of \(\vec {r}_1\) and \(\vec {r}_2\). Our next video shows a step-by-step row reduction process accompanied by sketches of vectors.

Exploration makes a convincing case for the following theorem.

Let \(\vec {r}_1,\ldots ,\vec {r}_m\) be the rows of \(A\).

There are three elementary row operations. Clearly, switching the order of vectors in \(\mbox {span}(\vec {r}_1,\ldots ,\vec {r}_m)\) will not affect the span.

Suppose that \(B\) was obtained from \(A\) by multiplying the \(i^{th}\) row of \(A\) by a non-zero constant \(k\). We need to show that

\[\mbox {span}(\vec {r}_1,\ldots ,k\vec {r}_i,\ldots ,\vec {r}_m)=\mbox {span}(\vec {r}_1,\ldots ,\vec {r}_i,\ldots ,\vec {r}_m)\]

To do this we will assume that some vector \(\vec {v}\) is in \(\mbox {span}(\vec {r}_1,\ldots ,k\vec {r}_i,\ldots ,\vec {r}_m)\), and show that \(\vec {v}\) is in \(\mbox {span}(\vec {r}_1,\ldots ,\vec {r}_i,\ldots ,\vec {r}_m)\). We will then assume that some vector \(\vec {w}\) is in \(\mbox {span}(\vec {r}_1,\ldots ,\vec {r}_i,\ldots ,\vec {r}_m)\) and show that \(\vec {w}\) must be in \(\mbox {span}(\vec {r}_1,\ldots ,k\vec {r}_i,\ldots ,\vec {r}_m)\).

Suppose that \(\vec {v}\) is in \(\mbox {span}(\vec {r}_1,\ldots ,k\vec {r}_i,\ldots ,\vec {r}_m)\). Then

\[\vec {v}=a_1\vec {r}_1+\ldots +a_i(k\vec {r}_i)+\ldots +a_m\vec {r}_m\]
But then
\[\vec {v}=a_1\vec {r}_1+\ldots +(a_ik)\vec {r}_i+\ldots +a_m\vec {r}_m\]
So \(\vec {v}\) is in \(\mbox {span}(\vec {r}_1,\ldots ,\vec {r}_i,\ldots ,\vec {r}_m)\).

Now suppose \(\vec {w}\) is in \(\mbox {span}(\vec {r}_1,\ldots ,\vec {r}_i,\ldots ,\vec {r}_m)\), then

\[\vec {w}=b_1\vec {r}_1+\ldots +b_i\vec {r}_i+\ldots +b_m\vec {r}_m\]
But because \(k\neq 0\), we can do the following:
\[\vec {w}=b_1\vec {r}_1+\ldots +\frac {b_i}{k}(k\vec {r}_i)+\ldots +b_m\vec {r}_m\]
So \(\vec {w}\) is in \(\mbox {span}(\vec {r}_1,\ldots ,k\vec {r}_i,\ldots ,\vec {r}_m)\).

We leave it to the reader to verify that adding a multiple of one row of \(A\) to another does not change the row space.

This follows from repeated applications of Theorem 2.

Our observations in Example 7 can be generalized to all matrices. Given any matrix \(A\),

(a)
The nonzero rows of \(\mbox {rref}(A)\) are linearly independent (Why?) and span \(\mbox {row}(A)\) (Corollary 6).
(b)
The nonzero rows of any row-echelon form of \(A\) are linearly independent (Why?) and span \(\mbox {row}(A)\) (Corollary 4).

Therefore nonzero rows of \(\mbox {rref}(A)\) or the nonzero rows of any row-echelon form of \(A\) constitute a basis of \(\mbox {row}(A)\). Since all bases for \(\mbox {row}(A)\) must have the same number of elements (Theorem ??), we have just proved the following theorem.

This result was first introduced without proof in Gaussian Elimination and Rank where we used it to define the rank of a matrix as the number of nonzero rows in its row-echelon forms. We can now update the definition of rank as follows.

Column Space of a Matrix

Let
\[B=\begin{bmatrix}2&-1&3&1\\1&-1&2&2\\1&3&-2&-3\end{bmatrix}\]
Our goal is to find a basis for \(\mbox {col}(B)\). To do this we need to find a linearly independent subset of the columns of \(B\) that spans \(\mbox {col}(B)\).

Consider the linear relation:

\begin{equation}\label {eq:init:colspaceB} a_1\begin{bmatrix}2\\1\\1\end{bmatrix}+a_2\begin{bmatrix}-1\\-1\\3\end{bmatrix}+a_3\begin{bmatrix}3\\2\\-2\end{bmatrix}+a_4\begin{bmatrix}1\\2\\-3\end{bmatrix}=\vec {0}\end{equation}

Solving this equation amounts to finding \(\mbox {rref}(B)\).

\[\begin{bmatrix}2&-1&3&1\\1&-1&2&2\\1&3&-2&-3\end{bmatrix}\rightsquigarrow \begin{bmatrix}1&0&1&0\\0&1&-1&0\\0&0&0&1\end{bmatrix}=\mbox {rref}(B)\]
We see that (1) has infinitely many solutions. This means that the columns of \(B\) are linearly dependent, and contain a redundant vector. Which vector can we remove from the set without changing the span?

Choosing a non-zero value for the free variable \(a_3\), we can express the third column as a linear combination of the other columns. We conclude that

\[\mbox {col}(B)=\mbox {span}\left (\begin{bmatrix}2\\1\\1\end{bmatrix},\begin{bmatrix}-1\\-1\\3\end{bmatrix}, \begin{bmatrix}3\\2\\-2\end{bmatrix}, \begin{bmatrix}1\\2\\-3\end{bmatrix}\right )=\mbox {span}\left (\begin{bmatrix}2\\1\\1\end{bmatrix},\begin{bmatrix}-1\\-1\\3\end{bmatrix}, \begin{bmatrix}1\\2\\-3\end{bmatrix}\right )\]

Removing the third column also gives us

[Picture]

This implies that the remaining columns are linearly independent, and the set

\[\left \{\begin{bmatrix}2\\1\\1\end{bmatrix},\begin{bmatrix}-1\\-1\\3\end{bmatrix}, \begin{bmatrix}1\\2\\-3\end{bmatrix}\right \}\]
is a basis for \(\mbox {col}(B)\).

The approach we took to find a basis for \(\mbox {col}(B)\) in Exploration uses the reduced row-echelon form of \(B\). It is true, however, that any row-echelon form of \(B\) could have been used in place of \(\mbox {rref}(B)\). (Why?). We generalize the steps as follows:

Let \(\vec {b}_1,\ldots ,\vec {b}_n\) be the columns of \(B\), and let \(\vec {b}'_1,\ldots ,\vec {b}'_n\) be the columns of \(\mbox {rref}(B)\) (or \(B'\)). Observe that the equations

\begin{equation}a_1\vec {b}_1+\ldots +a_n\vec {b}_n=\vec {0}\end{equation}
\begin{equation}a_1\vec {b}'_1+\ldots +a_n\vec {b}'_n=\vec {0}\end{equation}
have the same solution set. This means that any non-trivial relation among the columns of \(\mbox {rref}(B)\) (or \(B'\)) translates into a non-trivial relation among the columns of \(B\). Likewise, any collection of linearly independent columns of \(\mbox {rref}(B)\) (or \(B'\)) corresponds to linearly independent columns of \(B\).

By Problem , the pivot columns of \(\mbox {rref}(B)\) (or \(B'\)) are linearly independent. Therefore the corresponding columns of \(B\) are linearly independent. Non-pivot columns can be expressed as linear combinations of the pivot columns, therefore they contribute nothing to the span and can be removed from the spanning set. (See Problem )

The proof of Procedure 12 shows that the number of basis elements for the column space of a matrix is equal to the number of pivot columns. But the number of pivot columns is the same as the number of pivots in a row-echelon form, which is equal to the number of nonzero rows and the rank of the matrix. This gives us the following important result.

The Null Space

Example 18 allows us to make an important observation. Note that every scalar multiple of \(\begin{bmatrix}1/3\\1\end{bmatrix}\) is contained in \(\mbox {null}(A)\). This means that \(\mbox {null}(A)\) is closed under vector addition and scalar multiplication. Recall that this property makes \(\mbox {null}(A)\) a subspace of \(\RR ^n\). This result was first presented as Practice Problem ??. We now formalize it as a theorem.

To show that \(\mbox {null}(A)\) is closed under vector addition and scalar multiplication we will show that a linear combination of any two elements of \(\mbox {null}(A)\) is contained in \(\mbox {null}(A)\).

Suppose \(\vec {x}_1\) and \(\vec {x}_2\) are in \(\mbox {null}(A)\). Then \(A\vec {x}_1=\vec {0}\) and \(A\vec {x}_2=\vec {0}\). But then

\[A(a_1\vec {x}_1+a_2\vec {x}_2)=a_1A\vec {x}_1+a_2A\vec {x}_2=\vec {0}\]
We conclude that \(a_1\vec {x}_1+a_2\vec {x}_2\) is also in \(\mbox {null}(A)\).

It is not a coincidence that the steps we used in Example 22 produced linearly independent vectors, and it is worth while to try to understand why this procedure will always produce linearly independent vectors.

Take a closer look at the elements of the null space:

\[\vec {x}=\begin{bmatrix}9t-3s\\31t-5s\\{\color {red}\fbox {$s$}}\\-3t\\{\color {blue}\fbox {$t$}}\end{bmatrix}=\begin{bmatrix}-3\\-5\\{\color {red}\fbox {$1$}}\\0\\{\color {blue}\fbox {$0$}}\end{bmatrix}s+\begin{bmatrix}9\\31\\{\color {red}\fbox {$0$}}\\-3\\{\color {blue}\fbox {$1$}}\end{bmatrix}t\]

The parameter \(s\) in the third component of \(\vec {x}\) produces a \(1\) in the third component of the first vector and a \(0\) in the third component of the second vector, while parameter \(t\) in the fifth component of \(\vec {x}\) produces a \(1\) in the fifth component of the second vector and a \(0\) in the fifth component of the first vector. This makes it clear that the two vectors are linearly independent.

This pattern will hold for any number of parameters, each parameter producing a \(1\) in exactly one vector and \(0's\) in the corresponding components of the other vectors.

\[\begin{bmatrix}\vdots \\t_1\\\vdots \\t_2\\\vdots \\t_3\\\vdots \\t_n\\\vdots \end{bmatrix}=\begin{bmatrix}\vdots \\1\\\vdots \\0\\\vdots \\0\\\vdots \\0\\\vdots \end{bmatrix}t_1+\ldots +\begin{bmatrix}\vdots \\0\\\vdots \\1\\\vdots \\0\\\vdots \\0\\\vdots \end{bmatrix}t_2+\ldots +\begin{bmatrix}\vdots \\0\\\vdots \\0\\\vdots \\1\\\vdots \\0\\\vdots \end{bmatrix}t_3+\ldots +\begin{bmatrix}\vdots \\0\\\vdots \\0\\\vdots \\0\\\vdots \\1\\\vdots \end{bmatrix}t_n\]

Therefore, vectors obtained in this way will always be linearly independent.

Rank and Nullity Theorem

We know that the dimension of the row space and the dimension of the column space of a matrix are the same and are equal to the rank of the matrix (or the number of nonzero rows in any row-echelon form of the matrix).

As we observed in Example 22, the dimension of the null space of a matrix is equal to the number of free variables in the solution vector of the homogeneous system associated with the matrix. Since the number of pivots and the number of free variables add up to the number of columns in a matrix (Theorem ??) we have the following significant result.

We will see the geometric implications of this theorem when we study linear transformations.

Practice Problems

Let \(A\) be a matrix. Prove that non-zero rows of \(\text {rref}(A)\) are linearly independent.
Let \(A\) be a matrix. Prove that the pivot columns of \(\text {rref}(A)\) are linearly independent.
Let \(A\) be a matrix. Show that the non-pivot columns of \(\text {rref}(A)\) can be expressed as linear combinations of the pivot columns.
Let
\[A=\begin{bmatrix}2&0&2&4\\1&3&-2&-1\\-1&-2&1&0\end{bmatrix}\]
Find \(\mbox {rref}(A)\). (You may use technology.)
\[\mbox {rref}(A)=\begin{bmatrix}\answer {1}&\answer {0}&\answer {1}&\answer {2}\\\answer {0}&\answer {1}&\answer {-1}&\answer {-1}\\\answer {0}&\answer {0}&\answer {0}&\answer {0}\end{bmatrix}\]
Complete the statement.
\[\mbox {rank}(A)=\mbox {dim}(\mbox {row}(A))=\mbox {dim}(\mbox {col}(A))=\answer {2}\]
Use \(\mbox {rref}(A)\) and the procedure outlined in Example 7 to find a basis for \(\mbox {row}(A)\).

Basis for \(\mbox {row}(A):\quad \left \{\begin{bmatrix}\answer {1}& \answer {0}& \answer {1} & \answer {2}\end{bmatrix},\begin{bmatrix}\answer {0} & \answer {1}& \answer {-1} &\answer {-1}\end{bmatrix} \right \}\)

Use Procedure 12 to find a basis for \(\mbox {col}(A)\).

Basis for \(\mbox {col}(A):\quad \left \{ \begin{bmatrix}\answer {2}\\\answer {1}\\\answer {-1}\end{bmatrix}, \begin{bmatrix}\answer {0}\\\answer {3}\\\answer {-2}\end{bmatrix}\right \}\)

Find a basis for \(\mbox {null}(A)\).

Basis for \(\mbox {null}(A):\quad \left \{ \begin{bmatrix}\answer {-1}\\\answer {1}\\1\\0\end{bmatrix}, \begin{bmatrix}\answer {-2}\\\answer {1}\\0\\1\end{bmatrix}\right \}\)

Demonstrate that the Rank-Nullity Theorem (Theorem 25) holds for \(A\).

Explain how you can quickly tell that the two vectors you selected for your basis are linearly independent.

Let
\[B=\begin{bmatrix}1&2&3\\-1&1&3\\2&0&-2\\1&-2&-5\\0&1&2\end{bmatrix}\]
Find \(\mbox {rref}(B)\). (You may use technology.)
\[\mbox {rref}(B)=\begin{bmatrix}\answer {1}&\answer {0}&\answer {-1}\\\answer {0}&\answer {1}&\answer {2}\\\answer {0}&\answer {0}&\answer {0}\\\answer {0}&\answer {0}&\answer {0}\\\answer {0}&\answer {0}&\answer {0}\end{bmatrix}\]
Complete the statement.
\[\mbox {rank}(B)=\mbox {dim}(\mbox {row}(B))=\mbox {dim}(\mbox {col}(B))=\answer {2}\]
Use \(\mbox {rref}(B)\) and the procedure outlined in Example 7 to find a basis for \(\mbox {row}(B)\).

Basis for \(\mbox {row}(B):\quad \left \{\begin{bmatrix}\answer {1}& \answer {0}& \answer {-1}\end{bmatrix},\begin{bmatrix}\answer {0} & \answer {1}& \answer {2}\end{bmatrix} \right \}\)

Use Procedure 12 to find a basis for \(\mbox {col}(B)\).

Basis for \(\mbox {col}(B):\quad \left \{ \begin{bmatrix}\answer {1}\\\answer {-1}\\\answer {2}\\\answer {1}\\\answer {0}\end{bmatrix}, \begin{bmatrix}\answer {2}\\\answer {1}\\\answer {0}\\\answer {-2}\\\answer {1}\end{bmatrix}\right \}\)

Find a basis for \(\mbox {null}(B)\).

Basis for \(\mbox {null}(B):\quad \left \{ \begin{bmatrix}\answer {1}\\\answer {-2}\\1\end{bmatrix}\right \}\)

Demonstrate that the Rank-Nullity Theorem (Theorem 25) holds for \(B\).

Suppose matrix \(M\) is such that
\[\mbox {rref}(M)=\begin{bmatrix}1&0&2&0&3&1\\0&1&-1&0&1&-2\\0&0&0&1&-2&1\\0&0&0&0&0&0\end{bmatrix}\]
Follow the process used in Example 22 to find a basis for \(\mbox {null}(M)\). Explain why the basis elements obtained in this way are linearly independent.

Basis of \(\mbox {null}(M):\quad \left \{\begin{bmatrix}\answer {-2}\\\answer {1}\\1\\\answer {0}\\0\\0\end{bmatrix}, \begin{bmatrix}\answer {-3}\\\answer {-1}\\0\\\answer {2}\\1\\0\end{bmatrix}, \begin{bmatrix}\answer {-1}\\\answer {2}\\0\\\answer {-1}\\0\\1\end{bmatrix} \right \}\)

Let \(\vec {v}_1,\ldots ,\vec {v}_6\) denote the columns of \(M\). Express \(\vec {v}_3\) as a linear combination of \(\vec {v}_1\) and \(\vec {v}_2\).

Answer:

\[\vec {v}_3=\answer {2}\vec {v}_1+\answer {-1}\vec {v}_2\]
Suppose \(A\) is a \(3\times 5\) matrix. Which of the following statements could be true?
\(\mbox {dim}(\mbox {col}(A))=5\) \(\mbox {dim}(\mbox {row}(A))=3\) \(\mbox {dim}(\mbox {null}(A))=1\) \(\mbox {dim}(\mbox {null}(A))=2\) \(\mbox {dim}(\mbox {null}(A))=3\)
Suppose \(A\) is a \(7\times 3\) matrix. Which of the following statements could be true?
\(\mbox {dim}(\mbox {col}(A))=3\) \(\mbox {dim}(\mbox {row}(A))=3\) \(\mbox {dim}(\mbox {row}(A))=7\) \(\mbox {dim}(\mbox {null}(A))=0\) \(\mbox {dim}(\mbox {null}(A))=4\)
Complete the proof of Theorem 2 by showing that adding a scalar multiple of one row of a matrix to another row does not change the row space.
Prove that \(\mbox {rank}(A)=\mbox {rank}(A^T)\)