Skip to main content

Section FS Four Subsets

There are four natural subsets associated with a matrix. We have met three already: the null space, the column space and the row space. In this section we will introduce a fourth, the left null space. The objective of this section is to describe one procedure that will allow us to find linearly independent sets that span each of these four sets of column vectors. Along the way, we will make a connection with the inverse of a matrix, so Theorem FS will tie together most all of this chapter (and the entire course so far).

Subsection LNS Left Null Space

Definition LNS. Left Null Space.

Suppose \(A\) is an \(m\times n\) matrix. Then the left null space is defined as \(\lns{A}=\nsp{\transpose{A}}\subseteq\complex{m}\text{.}\)

The left null space will not feature prominently in the sequel, but we can explain its name and connect it to row operations. Suppose \(\vect{y}\in\lns{A}\text{.}\) Then by Definition LNS, \(\transpose{A}\vect{y}=\zerovector\text{.}\) We can then write

\begin{align*} \transpose{\zerovector} &=\transpose{\left(\transpose{A}\vect{y}\right)}&& \knowl{./knowl/definition-LNS.html}{\text{Definition LNS}}\\ &=\transpose{\vect{y}}\transpose{\left(\transpose{A}\right)}&& \knowl{./knowl/theorem-MMT.html}{\text{Theorem MMT}}\\ &=\transpose{\vect{y}}A&& \knowl{./knowl/theorem-TT.html}{\text{Theorem TT}}\text{.} \end{align*}

The product \(\transpose{\vect{y}}A\) can be viewed as the components of \(\vect{y}\) acting as the scalars in a linear combination of the rows of \(A\text{.}\) And the result is a row vector, \(\transpose{\zerovector}\) that is totally zeros. When we apply a sequence of row operations to a matrix, each row of the resulting matrix is some linear combination of the rows. These observations tell us that the vectors in the left null space are scalars that record a sequence of row operations that result in a row of zeros in the row-reduced version of the matrix. We will see this idea more explicitly in the course of proving Theorem FS.

We will find the left null space of

\begin{equation*} A= \begin{bmatrix} 1 & -3 & 1 \\ -2 & 1 & 1 \\ 1 & 5 & 1 \\ 9 & -4 & 0 \end{bmatrix}\text{.} \end{equation*}

We transpose \(A\) and row-reduce,

\begin{equation*} \transpose{A}= \begin{bmatrix} 1 & -2 & 1 & 9 \\ -3 & 1 & 5 & -4 \\ 1 & 1 & 1 & 0 \end{bmatrix} \rref \begin{bmatrix} \leading{1} & 0 & 0 & 2 \\ 0 & \leading{1} & 0 & -3 \\ 0 & 0 & \leading{1} & 1 \end{bmatrix}\text{.} \end{equation*}

Applying Definition LNS and Theorem BNS we have

\begin{equation*} \lns{A}=\nsp{\transpose{A}}= \spn{\set{ \colvector{-2\\3\\-1\\1} }}\text{.} \end{equation*}

If you row-reduce \(A\) you will discover one zero row in the reduced row-echelon form. This zero row is created by a sequence of row operations, which in total amounts to a linear combination, with scalars \(a_1=-2\text{,}\) \(a_2=3\text{,}\) \(a_3=-1\) and \(a_4=1\text{,}\) on the rows of \(A\) and which results in the zero vector (check this!). So the components of the vector describing the left null space of \(A\) provide a relation of linear dependence on the rows of \(A\text{.}\)

Similar to (right) null spaces, a left null space can be computed in Sage with the matrix method .left_kernel(). For a matrix \(A\text{,}\) elements of the (right) null space are vectors \(\vect{x}\) such that \(A\vect{x}=\zerovector\text{.}\) If we interpret a vector placed to the left of a matrix as a 1-row matrix, then the product \(\vect{x}A\) can be interpreted, according to our definition of matrix multiplication (Definition MM), as the entries of the vector \(\vect{x}\) providing the scalars for a linear combination of the rows of the matrix \(A\text{.}\) So you can view each vector in the left null space naturally as the entries of a matrix with a single row, \(Y\text{,}\) with the property that \(YA=\zeromatrix\text{.}\)

Given Sage's preference for row vectors, the simpler name .kernel() is a synonym for .left_kernel(). Given your text's preference for column vectors, we will continue to rely on the .right_kernel(). Left kernels in Sage have the same options as right kernels and produce vector spaces as output in the same manner. Once created, a vector space all by itself (with no history) is neither left or right. Here is a quick repeat of Example LNS.

Subsection CCS Computing Column Spaces

We have three ways to build the column space of a matrix. First, we can use just the definition, Definition CSM, and express the column space as a span of the columns of the matrix. A second approach gives us the column space as the span of some of the columns of the matrix, and additionally, this set is linearly independent (Theorem BCS). Finally, we can transpose the matrix, row-reduce the transpose, kick out zero rows, and write the remaining rows as column vectors. Theorem CSRST and Theorem BRS tell us that the resulting vectors are linearly independent and their span is the column space of the original matrix.

We will now demonstrate a fourth method by way of a rather complicated example. Study this example carefully, but realize that its main purpose is to motivate a theorem that simplifies much of the apparent complexity. So other than an instructive exercise or two, the procedure we are about to describe will not be a usual approach to computing a column space.

Let us find the column space of the matrix \(A\) below with a new approach.

\begin{equation*} A= \begin{bmatrix} 10 & 0 & 3 & 8 & 7 \\ -16 & -1 & -4 & -10 & -13 \\ -6 & 1 & -3 & -6 & -6 \\ 0 & 2 & -2 & -3 & -2 \\ 3 & 0 & 1 & 2 & 3 \\ -1 & -1 & 1 & 1 & 0 \end{bmatrix}\text{.} \end{equation*}

By Theorem CSCS we know that the column vector \(\vect{b}\) is in the column space of \(A\) if and only if the linear system \(\linearsystem{A}{\vect{b}}\) is consistent. So let us try to solve this system in full generality, using a vector of variables for the vector of constants. In other words, which vectors \(\vect{b}\) lead to consistent systems? Begin by forming the augmented matrix \(\augmented{A}{\vect{b}}\) with a general version of \(\vect{b}\)

\begin{equation*} \augmented{A}{\vect{b}}= \begin{bmatrix} 10 & 0 & 3 & 8 & 7 & b_1 \\ -16 & -1 & -4 & -10 & -13 & b_2 \\ -6 & 1 & -3 & -6 & -6 & b_3 \\ 0 & 2 & -2 & -3 & -2 & b_4 \\ 3 & 0 & 1 & 2 & 3 & b_ 5\\ -1 & -1 & 1 & 1 & 0 & b_ 6 \end{bmatrix}\text{.} \end{equation*}

To identify solutions we will bring this matrix to reduced row-echelon form. Despite the presence of variables in the last column, there is nothing to stop us from doing this, except numerical computational routines cannot be used, and even some of the symbolic algebra routines do some unexpected maneuvers with this computation. So do it by hand. Yes, it is a bit of work. But worth it. We'll still be here when you get back. Notice along the way that the row operations are exactly the same ones you would do if you were just row-reducing the coefficient matrix alone, say in connection with a homogeneous system of equations. The column with the \(b_i\) acts as a sort of bookkeeping device. There are many different possibilities for the result, depending on what order you choose to perform the row operations, but shortly we will all be on the same page. If you want to match our work right now, use row 5 to remove any occurrence of \(b_1\) from the other entries of the last column, and use row 6 to remove any occurrence of \(b_2\) from the last columns. We have

\begin{align*} \begin{bmatrix} \leading{1} & 0 & 0 & 0 & 2 & b_3 - b_4 + 2 b_5 - b_6\\ 0 & \leading{1} & 0 & 0 & -3 & -2 b_3 + 3 b_4 - 3 b_5 + 3 b_6\\ 0 & 0 & \leading{1} & 0 & 1 & b_3 + b_4 + 3 b_5 + 3 b_6\\ 0 & 0 & 0 & \leading{1} & -2 & -2 b_3 + b_4 - 4 b_5\\ 0 & 0 & 0 & 0 & 0 & b_1 + 3 b_3 - b_4 + 3 b_5 + b_6\\ 0 & 0 & 0 & 0 & 0 & b_2 - 2 b_3 + b_4 + b_5 - b_6 \end{bmatrix}\text{.} \end{align*}

Our goal is to identify those vectors \(\vect{b}\) which make \(\linearsystem{A}{\vect{b}}\) consistent. By Theorem RCLS we know that the consistent systems are precisely those without a pivot column in the last column. Are the expressions in the last column of rows 5 and 6 equal to zero, or are they leading 1's? The answer is: maybe. It depends on \(\vect{b}\text{.}\) With a nonzero value for either of these expressions, we would scale the row and produce a leading 1. So we get a consistent system, and \(\vect{b}\) is in the column space, if and only if these two expressions are both simultaneously zero. In other words, members of the column space of \(A\) are exactly those vectors \(\vect{b}\) that satisfy

\begin{align*} b_1 + 3 b_3 - b_4 + 3 b_5 + b_6 & = 0\\ b_2 - 2 b_3 + b_4 + b_5 - b_6 & = 0\text{.} \end{align*}

Hmmm. Looks suspiciously like a homogeneous system of two equations with six variables. If you have been playing along (and we hope you have) then you may have a slightly different system, but you should have just two equations. Form the coefficient matrix and row-reduce (notice that the system above has a coefficient matrix that is already in reduced row-echelon form). We should all be together now with the same matrix

\begin{equation*} L= \begin{bmatrix} \leading{1} & 0 & 3 & -1 & 3 & 1 \\ 0 & \leading{1} & -2 & 1 & 1 & -1 \end{bmatrix}\text{.} \end{equation*}

So, \(\csp{A}=\nsp{L}\) and we can apply Theorem BNS to obtain a linearly independent set to use in a span construction

\begin{equation*} \csp{A}=\nsp{L}=\spn{\set{ \colvector{-3\\2\\1\\0\\0\\0},\, \colvector{1\\-1\\0\\1\\0\\0},\, \colvector{-3\\-1\\0\\0\\1\\0},\, \colvector{-1\\1\\0\\0\\0\\1} }}\text{.} \end{equation*}

Whew! As a postscript to this central example, you may wish to convince yourself that the four vectors above really are elements of the column space. Do they create consistent systems with \(A\) as coefficient matrix? Can you recognize the constant vector in your description of these solution sets?

OK, that was so much fun, let us do it again. But simpler this time. And we will all get the same results all the way through. Doing row operations by hand with variables can be a bit error prone, so let us see if we can improve the process some. Rather than row-reduce a column vector \(\vect{b}\) full of variables, let us write \(\vect{b}=I_6\vect{b}\) and we will row-reduce the matrix \(I_6\) and when we finish row-reducing, then we will compute the matrix-vector product. You should first convince yourself that we can operate like this (this is the subject of a future homework exercise). Rather than augmenting \(A\) with \(\vect{b}\text{,}\) we will instead augment it with \(I_6\) (does this feel familiar?).

\begin{equation*} M= \begin{bmatrix} 10 & 0 & 3 & 8 & 7 & 1 & 0 & 0 & 0 & 0 & 0 \\ -16 & -1 & -4 & -10 & -13 & 0 & 1 & 0 & 0 & 0 & 0 \\ -6 & 1 & -3 & -6 & -6 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 2 & -2 & -3 & -2 & 0 & 0 & 0 & 1 & 0 & 0 \\ 3 & 0 & 1 & 2 & 3 & 0 & 0 & 0 & 0 & 1 & 0 \\ -1 & -1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} \end{equation*}

We want to row-reduce the left-hand side of this matrix, but we will apply the same row operations to the right-hand side as well. And once we get the left-hand side in reduced row-echelon form, we will continue on to put leading 1's in the final two rows, as well as making pivot columns that contain these two additional leading 1's. It is these additional row operations that will ensure that we all get to the same place, since the reduced row-echelon form is unique (Theorem RREFU).

\begin{equation*} N= \begin{bmatrix} 1 & 0 & 0 & 0 & 2 & 0 & 0 & 1 & -1 & 2 & -1 \\ 0 & 1 & 0 & 0 & -3 & 0 & 0 & -2 & 3 & -3 & 3 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 3 & 3 \\ 0 & 0 & 0 & 1 & -2 & 0 & 0 & -2 & 1 & -4 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 3 & -1 & 3 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & -2 & 1 & 1 & -1 \end{bmatrix} \end{equation*}

We are after the final six columns of this matrix, which we will multiply by \(\vect{b}\text{.}\)

\begin{equation*} J= \begin{bmatrix} 0 & 0 & 1 & -1 & 2 & -1 \\ 0 & 0 & -2 & 3 & -3 & 3 \\ 0 & 0 & 1 & 1 & 3 & 3 \\ 0 & 0 & -2 & 1 & -4 & 0 \\ 1 & 0 & 3 & -1 & 3 & 1 \\ 0 & 1 & -2 & 1 & 1 & -1 \end{bmatrix} \end{equation*}

so

\begin{equation*} J\vect{b}= \begin{bmatrix} 0 & 0 & 1 & -1 & 2 & -1 \\ 0 & 0 & -2 & 3 & -3 & 3 \\ 0 & 0 & 1 & 1 & 3 & 3 \\ 0 & 0 & -2 & 1 & -4 & 0 \\ 1 & 0 & 3 & -1 & 3 & 1 \\ 0 & 1 & -2 & 1 & 1 & -1 \end{bmatrix} \colvector{b_1\\b_2\\b_3\\b_4\\b_5\\b_6} = \colvector{ b_3 - b_4 + 2 b_5 - b_6\\ -2 b_3 + 3 b_4 - 3 b_5 + 3 b_6\\ b_3 + b_4 + 3 b_5 + 3 b_6\\ -2 b_3 + b_4 - 4 b_5\\ b_1 + 3 b_3 - b_4 + 3 b_5 + b_6\\ b_2 - 2 b_3 + b_4 + b_5 - b_6\\ } \end{equation*}

So by applying the same row operations that row-reduce \(A\) to the identity matrix (which we could do computationally once \(I_6\) is placed alongside of \(A\)), we can then arrive at the result of row-reducing a column of symbols where the vector of constants usually resides. Since the row-reduced version of \(A\) has two zero rows, for a consistent system we require that

\begin{align*} b_1 + 3 b_3 - b_4 + 3 b_5 + b_6 & = 0\\ b_2 - 2 b_3 + b_4 + b_5 - b_6 & = 0 \end{align*}

Now we are exactly back where we were on the first go-round. Notice that we obtain the matrix \(L\) as simply the last two rows and last six columns of \(N\text{.}\)

This example motivates the remainder of this section, so it is worth careful study. You might attempt to mimic the second approach with the coefficient matrices of Archetype I and Archetype J. We will see shortly that the matrix \(L\) contains more information about \(A\) than just the column space.

Sage can very nearly reproduce the reduced row-echelon form we obtained from the augmented matrix with variables present in the final column. The first line below is a bit of advanced Sage. It creates a number system R mixing the rational numbers with the variables b1 through b6. It is not important to know the details of this construction right now. B is the reduced row-echelon form of A, as computed by Sage, where we have displayed the last column separately so it will all fit. You will notice that B is different than what we used in Example CSANS, where all the differences are in the final column.

However, we can perform row operations on the final two rows of B to bring Sage's result in line with what we used above for the final two entries of the last column, which are the most critical. Notice that since the final two rows are almost all zeros, any sequence of row operations on just these two rows will preserve the zeros (and we need only display the final column to keep track of our progress).

Notice that the last two entries of the final column now have just a single b1 and a single b2. We could continue to perform more row operations by hand, using the last two rows to progressively eliminate b1 and b2 from the other four expressions of the last column. Since the two last rows have zeros in their first five entries, only the entries in the final column would change. You will see that much of this section is about how to automate these final calculations.

Subsection EEF Extended Echelon Form

The final matrix that we row-reduced in Example CSANS should look familiar in most respects to the procedure we used to compute the inverse of a nonsingular matrix, Theorem CINM. We will now generalize that procedure to matrices that are not necessarily nonsingular, or even square. First a definition.

Definition EEF. Extended Echelon Form.

Suppose \(A\) is an \(m\times n\) matrix. Extend \(A\) on its right side with the addition of an \(m\times m\) identity matrix to form an \(m\times (n + m)\) matrix \(M\text{.}\) Use row operations to bring \(M\) to reduced row-echelon form and call the result \(N\text{.}\) \(N\) is the extended reduced row-echelon form of \(A\text{,}\) and we will standardize on names for five submatrices (\(B\text{,}\) \(C\text{,}\) \(J\text{,}\) \(K\text{,}\) \(L\)) of \(N\text{.}\)

Let \(B\) denote the \(m\times n\) matrix formed from the first \(n\) columns of \(N\) and let \(J\) denote the \(m\times m\) matrix formed from the last \(m\) columns of \(N\text{.}\) Suppose that \(B\) has \(r\) nonzero rows. Further partition \(N\) by letting \(C\) denote the \(r\times n\) matrix formed from all of the nonzero rows of \(B\text{.}\) Let \(K\) be the \(r\times m\) matrix formed from the first \(r\) rows of \(J\text{,}\) while \(L\) will be the \((m-r)\times m\) matrix formed from the bottom \(m-r\) rows of \(J\text{.}\) Pictorially,

\begin{equation*} M=[A\vert I_m] \rref N=[B\vert J] = \left[\begin{array}{c|c}C&K\\\hline\zeromatrix&L\end{array}\right]\text{.} \end{equation*}

We illustrate Definition EEF with the matrix \(A\text{.}\)

\begin{equation*} A= \begin{bmatrix} 1 & -1 & -2 & 7 & 1 & 6 \\ -6 & 2 & -4 & -18 & -3 & -26 \\ 4 & -1 & 4 & 10 & 2 & 17 \\ 3 & -1 & 2 & 9 & 1 & 12 \end{bmatrix} \end{equation*}

Augmenting with the \(4\times 4\) identity matrix,

\begin{equation*} M= \begin{bmatrix} 1 & -1 & -2 & 7 & 1 & 6 & 1 & 0 & 0 & 0 \\ -6 & 2 & -4 & -18 & -3 & -26 & 0 & 1 & 0 & 0 \\ 4 & -1 & 4 & 10 & 2 & 17 & 0 & 0 & 1 & 0 \\ 3 & -1 & 2 & 9 & 1 & 12 & 0 & 0 & 0 & 1 \end{bmatrix} \end{equation*}

and row-reducing, we obtain

\begin{equation*} N= \begin{bmatrix} \leading{1} & 0 & 2 & 1 & 0 & 3 & 0 & 1 & 1 & 1\\ 0 & \leading{1} & 4 & -6 & 0 & -1 & 0 & 2 & 3 & 0 \\ 0 & 0 & 0 & 0 & \leading{1} & 2 & 0 & -1 & 0 & -2 \\ 0 & 0 & 0 & 0 & 0 & 0 & \leading{1} & 2 & 2 & 1 \end{bmatrix}\text{.} \end{equation*}

So we then obtain

\begin{align*} B&= \begin{bmatrix} \leading{1} & 0 & 2 & 1 & 0 & 3 \\ 0 & \leading{1} & 4 & -6 & 0 & -1 \\ 0 & 0 & 0 & 0 & \leading{1} & 2 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}\\ C&= \begin{bmatrix} \leading{1} & 0 & 2 & 1 & 0 & 3 \\ 0 & \leading{1} & 4 & -6 & 0 & -1 \\ 0 & 0 & 0 & 0 & \leading{1} & 2 \end{bmatrix}\\ J&= \begin{bmatrix} 0 & 1 & 1 & 1\\ 0 & 2 & 3 & 0 \\ 0 & -1 & 0 & -2 \\ \leading{1} & 2 & 2 & 1 \end{bmatrix}\\ K&= \begin{bmatrix} 0 & 1 & 1 & 1\\ 0 & 2 & 3 & 0 \\ 0 & -1 & 0 & -2 \end{bmatrix}\\ L&= \begin{bmatrix} \leading{1} & 2 & 2 & 1 \end{bmatrix}\text{.} \end{align*}

You can observe (or verify) the properties of the following theorem with this example.

\(J\) is the result of applying a sequence of row operations to \(I_m\text{,}\) and therefore \(J\) and \(I_m\) are row-equivalent. \(\homosystem{I_m}\) has only the zero solution, since \(I_m\) is nonsingular (Theorem NMRRI). Thus, \(\homosystem{J}\) also has only the zero solution (Theorem REMES, Definition ESYS) and \(J\) is therefore nonsingular (Definition NM).

To prove the second part of this conclusion, first convince yourself that row operations and the matrix-vector product are associative operations. By this we mean the following. Suppose that \(F\) is an \(m\times n\) matrix that is row-equivalent to the matrix \(G\text{.}\) Apply to the column vector \(F\vect{w}\) the same sequence of row operations that converts \(F\) to \(G\text{.}\) Then the result is \(G\vect{w}\text{.}\) So we can do row operations on the matrix, then do a matrix-vector product, or do a matrix-vector product and then do row operations on a column vector, and the result will be the same either way. Since matrix multiplication is defined by a collection of matrix-vector products (Definition MM), the matrix product \(FH\) will become \(GH\) if we apply the same sequence of row operations to \(FH\) that convert \(F\) to \(G\text{.}\) (This argument can be made more rigorous using elementary matrices from the upcoming Subsection DM.EM and the associative property of matrix multiplication established in Theorem MMA.) Now apply these observations to \(A\text{.}\)

Write \(AI_n=I_mA\) and apply the row operations that convert \(M\) to \(N\text{.}\) \(A\) is converted to \(B\text{,}\) while \(I_m\) is converted to \(J\text{,}\) so we have \(BI_n=JA\text{.}\) Simplifying the left side gives the desired conclusion.

For the third conclusion, we now establish the two equivalences

\begin{align*} A\vect{x}&=\vect{y} & &\iff & JA\vect{x}&=J\vect{y} & &\iff & B\vect{x}&=J\vect{y} \end{align*}

The forward direction of the first equivalence is accomplished by multiplying both sides of the matrix equality by \(J\text{,}\) while the backward direction is accomplished by multiplying by the inverse of \(J\) (which we know exists by Theorem NI since \(J\) is nonsingular). The second equivalence is obtained simply by the substitutions given by \(JA=B\text{.}\)

The first \(r\) rows of \(N\) are in reduced row-echelon form, since any contiguous collection of rows taken from a matrix in reduced row-echelon form will form a matrix that is again in reduced row-echelon form (Exercise RREF.T12). Since the matrix \(C\) is formed by removing the last \(n\) entries of each these rows, the remainder is still in reduced row-echelon form. By its construction, \(C\) has no zero rows. \(C\) has \(r\) rows and each contains a leading 1, so there are \(r\) pivot columns in \(C\text{.}\)

The final \(m-r\) rows of \(N\) are in reduced row-echelon form, since any contiguous collection of rows taken from a matrix in reduced row-echelon form will form a matrix that is again in reduced row-echelon form. Since the matrix \(L\) is formed by removing the first \(n\) entries of each these rows, and these entries are all zero (they form the zero rows of \(B\)), the remainder is still in reduced row-echelon form. \(L\) is the final \(m-r\) rows of the nonsingular matrix \(J\text{,}\) so none of these rows can be totally zero, or \(J\) would not row-reduce to the identity matrix. \(L\) has \(m-r\) rows and each contains a leading 1, so there are \(m-r\) pivot columns in \(L\text{.}\)

Notice that in the case where \(A\) is a nonsingular matrix we know that the reduced row-echelon form of \(A\) is the identity matrix (Theorem NMRRI), so \(B=I_n\text{.}\) Then the second conclusion above says \(JA=B=I_n\text{,}\) so \(J\) is the inverse of \(A\text{.}\) Thus this theorem generalizes Theorem CINM, though the result is a “left-inverse” of \(A\) rather than a “right-inverse.”

The third conclusion of Theorem PEEF is the most telling. It says that \(\vect{x}\) is a solution to the linear system \(\linearsystem{A}{\vect{y}}\) if and only if \(\vect{x}\) is a solution to the linear system \(\linearsystem{B}{J\vect{y}}\text{.}\) Or said differently, if we row-reduce the augmented matrix \(\augmented{A}{\vect{y}}\) we will get the augmented matrix \(\augmented{B}{J\vect{y}}\text{.}\) The matrix \(J\) tracks the cumulative effect of the row operations that converts \(A\) to reduced row-echelon form, here effectively applying them to the vector of constants in a system of equations having \(A\) as a coefficient matrix. When \(A\) row-reduces to a matrix with zero rows, then \(J\vect{y}\) should also have zero entries in the same rows if the system is to be consistent.

Subsection FS Four Subsets

With all the preliminaries in place we can state our main result for this section. In essence this result will allow us to say that we can find linearly independent sets to use in span constructions for all four subsets (null space, column space, row space, left null space) by analyzing only the extended echelon form of the matrix, and specifically, just the two submatrices \(C\) and \(L\text{,}\) which will be ripe for analysis since they are already in reduced row-echelon form (Theorem PEEF).

First, \(\nsp{A}=\nsp{B}\) since \(B\) is row-equivalent to \(A\) (Theorem REMES). The zero rows of \(B\) represent equations that are always true in the homogeneous system \(\homosystem{B}\text{,}\) so the removal of these equations will not change the solution set. Thus, in turn, \(\nsp{B}=\nsp{C}\text{.}\)

Second, \(\rsp{A}=\rsp{B}\) since \(B\) is row-equivalent to \(A\) (Theorem REMRS). The zero rows of \(B\) contribute nothing to the span that is the row space of \(B\text{,}\) so the removal of these rows will not change the row space. Thus, in turn, \(\rsp{B}=\rsp{C}\text{.}\)

Third, we prove the set equality \(\csp{A}=\nsp{L}\) with Definition SE. Begin by showing that \(\csp{A}\subseteq\nsp{L}\text{.}\) Choose \(\vect{y}\in\csp{A}\subseteq\complex{m}\text{.}\) Then there exists a vector \(\vect{x}\in\complex{n}\) such that \(A\vect{x}=\vect{y}\) (Theorem CSCS). Then for \(1\leq k\leq m-r\text{,}\)

\begin{align*} \vectorentry{L\vect{y}}{k} &=\vectorentry{J\vect{y}}{r+k}&& L\text{ a submatrix of }J\\ &=\vectorentry{B\vect{x}}{r+k}&& \knowl{./knowl/theorem-PEEF.html}{\text{Theorem PEEF}}\\ &=\vectorentry{\zeromatrix\vect{x}}{k}&& \text{Zero matrix a submatrix of } B\\ &=\vectorentry{\zerovector}{k}&& \knowl{./knowl/theorem-MMZM.html}{\text{Theorem MMZM}}\text{.} \end{align*}

So, for all \(1\leq k\leq m-r\text{,}\) \(\vectorentry{L\vect{y}}{k}=\vectorentry{\zerovector}{k}\text{.}\) So by Definition CVE we have \(L\vect{y}=\zerovector\) and thus \(\vect{y}\in\nsp{L}\text{.}\)

Now, show that \(\nsp{L}\subseteq\csp{A}\text{.}\) Choose \(\vect{y}\in\nsp{L}\subseteq\complex{m}\text{.}\) Form the vector \(K\vect{y}\in\complex{r}\text{.}\) The linear system \(\linearsystem{C}{K\vect{y}}\) is consistent since \(C\) is in reduced row-echelon form and has no zero rows (Theorem PEEF). Let \(\vect{x}\in\complex{n}\) denote a solution to \(\linearsystem{C}{K\vect{y}}\text{.}\)

Then for \(1\leq j\leq r\text{,}\)

\begin{align*} \vectorentry{B\vect{x}}{j} &=\vectorentry{C\vect{x}}{j}&& C\text{ a submatrix of }B\\ &=\vectorentry{K\vect{y}}{j}&& \vect{x}\text{ a solution to }\linearsystem{C}{K\vect{y}}\\ &=\vectorentry{J\vect{y}}{j}&& K\text{ a submatrix of }J\text{.} \end{align*}

And for \(r+1\leq k\leq m\text{,}\)

\begin{align*} \vectorentry{B\vect{x}}{k} &=\vectorentry{\zeromatrix\vect{x}}{k-r}&& \text{Zero matrix a submatrix of }B\\ &=\vectorentry{\zerovector}{k-r}&& \knowl{./knowl/theorem-MMZM.html}{\text{Theorem MMZM}}\\ &=\vectorentry{L\vect{y}}{k-r}&& \vect{y}\in\nsp{L}\\ &=\vectorentry{J\vect{y}}{k}&& L\text{ a submatrix of }J\text{.} \end{align*}

So for all \(1\leq i\leq m\text{,}\) \(\vectorentry{B\vect{x}}{i}=\vectorentry{J\vect{y}}{i}\) and by Definition CVE we have \(B\vect{x}=J\vect{y}\text{.}\) From Theorem PEEF we know then that \(A\vect{x}=\vect{y}\text{,}\) and therefore \(\vect{y}\in\csp{A}\) (Theorem CSCS). By Definition SE we now have \(\csp{A}=\nsp{L}\text{.}\)

Fourth, we prove the set equality \(\lns{A}=\rsp{L}\) with Definition SE. Begin by showing that \(\rsp{L}\subseteq\lns{A}\text{.}\) Choose \(\vect{y}\in\rsp{L}\subseteq\complex{m}\text{.}\) Then there exists a vector \(\vect{w}\in\complex{m-r}\) such that \(\vect{y}=\transpose{L}\vect{w}\) (Definition RSM, Theorem CSCS). Then for \(1\leq i\leq n\text{,}\)

\begin{align*} \vectorentry{\transpose{A}\vect{y}}{i} &=\sum_{k=1}^{m}\matrixentry{\transpose{A}}{ik}\vectorentry{\vect{y}}{k}&& \knowl{./knowl/theorem-EMP.html}{\text{Theorem EMP}}\\ &=\sum_{k=1}^{m}\matrixentry{\transpose{A}}{ik}\vectorentry{\transpose{L}\vect{w}}{k}&& \text{Definition of }\vect{w}\\ &=\sum_{k=1}^{m}\matrixentry{\transpose{A}}{ik}\sum_{\ell=1}^{m-r}\matrixentry{\transpose{L}}{k\ell}\vectorentry{\vect{w}}{\ell}&& \knowl{./knowl/theorem-EMP.html}{\text{Theorem EMP}}\\ &=\sum_{k=1}^{m}\sum_{\ell=1}^{m-r}\matrixentry{\transpose{A}}{ik}\matrixentry{\transpose{L}}{k\ell}\vectorentry{\vect{w}}{\ell}&& \knowl{./knowl/property-DCN.html}{\text{Property DCN}}\\ &=\sum_{\ell=1}^{m-r}\sum_{k=1}^{m}\matrixentry{\transpose{A}}{ik}\matrixentry{\transpose{L}}{k\ell}\vectorentry{\vect{w}}{\ell}&& \knowl{./knowl/property-CACN.html}{\text{Property CACN}}\\ &=\sum_{\ell=1}^{m-r}\left(\sum_{k=1}^{m}\matrixentry{\transpose{A}}{ik}\matrixentry{\transpose{L}}{k\ell}\right)\vectorentry{\vect{w}}{\ell}&& \knowl{./knowl/property-DCN.html}{\text{Property DCN}}\\ &=\sum_{\ell=1}^{m-r}\left(\sum_{k=1}^{m}\matrixentry{\transpose{A}}{ik}\matrixentry{\transpose{J}}{k,r+\ell}\right)\vectorentry{\vect{w}}{\ell}&& L\text{ a submatrix of }J\\ &=\sum_{\ell=1}^{m-r}\matrixentry{\transpose{A}\transpose{J}}{i,r+\ell}\vectorentry{\vect{w}}{\ell}&& \knowl{./knowl/theorem-EMP.html}{\text{Theorem EMP}}\\ &=\sum_{\ell=1}^{m-r}\matrixentry{\transpose{\left(JA\right)}}{i,r+\ell}\vectorentry{\vect{w}}{\ell}&& \knowl{./knowl/theorem-MMT.html}{\text{Theorem MMT}}\\ &=\sum_{\ell=1}^{m-r}\matrixentry{\transpose{B}}{i,r+\ell}\vectorentry{\vect{w}}{\ell}&& \knowl{./knowl/theorem-PEEF.html}{\text{Theorem PEEF}}\\ &=\sum_{\ell=1}^{m-r}0\vectorentry{\vect{w}}{\ell}&& \text{Zero rows in } B\\ &=0&& \knowl{./knowl/property-ZCN.html}{\text{Property ZCN}}\\ &=\vectorentry{\zerovector}{i}&& \knowl{./knowl/definition-ZCV.html}{\text{Definition ZCV}}\text{.} \end{align*}

Since \(\vectorentry{\transpose{A}\vect{y}}{i}=\vectorentry{\zerovector}{i}\) for \(1\leq i\leq n\text{,}\) Definition CVE implies that \(\transpose{A}\vect{y}=\zerovector\text{.}\) This means that \(\vect{y}\in\nsp{\transpose{A}}\text{.}\)

Now, show that \(\lns{A}\subseteq\rsp{L}\text{.}\) Choose \(\vect{y}\in\lns{A}\subseteq\complex{m}\text{.}\) The matrix \(J\) is nonsingular (Theorem PEEF), so \(\transpose{J}\) is also nonsingular (Theorem MIT) and therefore the linear system \(\linearsystem{\transpose{J}}{\vect{y}}\) has a unique solution. Denote this solution as \(\vect{x}\in\complex{m}\text{.}\) We will need to work with two “halves” of \(\vect{x}\text{,}\) which we will denote as \(\vect{z}\) and \(\vect{w}\) with formal definitions given by

\begin{align*} \vectorentry{z}{j}&=\vectorentry{x}{i} & &1\leq j\leq r,&&& \vectorentry{w}{k}&=\vectorentry{x}{r+k} & &1\leq k\leq m-r\text{.} \end{align*}

Now, for \(1\leq j\leq r\text{,}\)

\begin{align*} \vectorentry{\transpose{C}\vect{z}}{j} &=\sum_{k=1}^{r}\matrixentry{\transpose{C}}{jk}\vectorentry{\vect{z}}{k}&& \knowl{./knowl/theorem-EMP.html}{\text{Theorem EMP}}\\ &=\sum_{k=1}^{r}\matrixentry{\transpose{C}}{jk}\vectorentry{\vect{z}}{k}+ \sum_{\ell=1}^{m-r}\matrixentry{\zeromatrix}{j\ell}\vectorentry{\vect{w}}{\ell}&& \knowl{./knowl/definition-ZM.html}{\text{Definition ZM}}\\ &=\sum_{k=1}^{r}\matrixentry{\transpose{B}}{jk}\vectorentry{\vect{z}}{k}+ \sum_{\ell=1}^{m-r}\matrixentry{\transpose{B}}{j,r+\ell}\vectorentry{\vect{w}}{\ell}&& C,\,\zeromatrix\text{ submatrices of }B\\ &=\sum_{k=1}^{r}\matrixentry{\transpose{B}}{jk}\vectorentry{\vect{x}}{k}+ \sum_{\ell=1}^{m-r}\matrixentry{\transpose{B}}{j,r+\ell}\vectorentry{\vect{x}}{r+\ell}&& \text{Definitions of } \vect{z}\, \vect{w}\\ &=\sum_{k=1}^{r}\matrixentry{\transpose{B}}{jk}\vectorentry{\vect{x}}{k}+ \sum_{k=r+1}^{m}\matrixentry{\transpose{B}}{jk}\vectorentry{\vect{x}}{k}&& \text{Re-index second sum}\\ &=\sum_{k=1}^{m}\matrixentry{\transpose{B}}{jk}\vectorentry{\vect{x}}{k}&& \text{Combine sums}\\ &=\sum_{k=1}^{m}\matrixentry{\transpose{\left(JA\right)}}{jk}\vectorentry{\vect{x}}{k}&& \knowl{./knowl/theorem-PEEF.html}{\text{Theorem PEEF}}\\ &=\sum_{k=1}^{m}\matrixentry{\transpose{A}\transpose{J}}{jk}\vectorentry{\vect{x}}{k}&& \knowl{./knowl/theorem-MMT.html}{\text{Theorem MMT}}\\ &=\sum_{k=1}^{m}\sum_{\ell=1}^{m}\matrixentry{\transpose{A}}{j\ell}\matrixentry{\transpose{J}}{\ell k}\vectorentry{\vect{x}}{k}&& \knowl{./knowl/theorem-EMP.html}{\text{Theorem EMP}}\\ &=\sum_{\ell=1}^{m}\sum_{k=1}^{m}\matrixentry{\transpose{A}}{j\ell}\matrixentry{\transpose{J}}{\ell k}\vectorentry{\vect{x}}{k}&& \knowl{./knowl/property-CACN.html}{\text{Property CACN}}\\ &=\sum_{\ell=1}^{m}\matrixentry{\transpose{A}}{j\ell}\left(\sum_{k=1}^{m}\matrixentry{\transpose{J}}{\ell k}\vectorentry{\vect{x}}{k}\right)&& \knowl{./knowl/property-DCN.html}{\text{Property DCN}}\\ &=\sum_{\ell=1}^{m}\matrixentry{\transpose{A}}{j\ell}\vectorentry{\transpose{J}\vect{x}}{\ell}&& \knowl{./knowl/theorem-EMP.html}{\text{Theorem EMP}}\\ &=\sum_{\ell=1}^{m}\matrixentry{\transpose{A}}{j\ell}\vectorentry{\vect{y}}{\ell}&&\text{Definition of }\vect{x}\\ &=\vectorentry{\transpose{A}\vect{y}}{j}&& \knowl{./knowl/theorem-EMP.html}{\text{Theorem EMP}}\\ &=\vectorentry{\zerovector}{j}&& \vect{y}\in\lns{A}\text{.} \end{align*}

So, by Definition CVE, \(\transpose{C}\vect{z}=\zerovector\) and the vector \(\vect{z}\) gives us a linear combination of the columns of \(\transpose{C}\) that equals the zero vector. In other words, \(\vect{z}\) gives a relation of linear dependence on the the rows of \(C\text{.}\) However, the rows of \(C\) are a linearly independent set by Theorem BRS. According to Definition LICV we must conclude that the entries of \(\vect{z}\) are all zero, i.e. \(\vect{z}=\zerovector\text{.}\)

Now, for \(1\leq i\leq m\text{,}\) we have

\begin{align*} \vectorentry{\vect{y}}{i} &=\vectorentry{\transpose{J}\vect{x}}{i}&& \text{Definition of }\vect{x}\\ &=\sum_{k=1}^{m}\matrixentry{\transpose{J}}{ik}\vectorentry{\vect{x}}{k}&& \knowl{./knowl/theorem-EMP.html}{\text{Theorem EMP}}\\ &=\sum_{k=1}^{r}\matrixentry{\transpose{J}}{ik}\vectorentry{\vect{x}}{k}+ \sum_{k=r+1}^{m}\matrixentry{\transpose{J}}{ik}\vectorentry{\vect{x}}{k}&& \text{Break apart sum}\\ &=\sum_{k=1}^{r}\matrixentry{\transpose{J}}{ik}\vectorentry{\vect{z}}{k}+ \sum_{k=r+1}^{m}\matrixentry{\transpose{J}}{ik}\vectorentry{\vect{w}}{k-r}&& \text{Definitions of }\vect{z},\,\vect{w}\\ &=\sum_{k=1}^{r}\matrixentry{\transpose{J}}{ik}0+ \sum_{\ell=1}^{m-r}\matrixentry{\transpose{J}}{i,r+\ell}\vectorentry{\vect{w}}{\ell}&& \vect{z}=\zerovector,\text{ re-index}\\ &=0+\sum_{\ell=1}^{m-r}\matrixentry{\transpose{L}}{i,\ell}\vectorentry{\vect{w}}{\ell}&& L\text{ a submatrix of }J\\ &=\vectorentry{\transpose{L}\vect{w}}{i}&& \knowl{./knowl/theorem-EMP.html}{\text{Theorem EMP}}\text{.} \end{align*}

So by Definition CVE, \(\vect{y}=\transpose{L}\vect{w}\text{.}\) The existence of \(\vect{w}\) implies that \(\vect{y}\in\rsp{L}\text{,}\) and therefore \(\lns{A}\subseteq\rsp{L}\text{.}\) So by Definition SE we have \(\lns{A}=\rsp{L}\text{.}\)

The first two conclusions of this theorem are nearly trivial. But they set up a pattern of results for \(C\) that is reflected in the latter two conclusions about \(L\text{.}\) In total, they tell us that we can compute all four subsets just by finding null spaces and row spaces. This theorem does not tell us exactly how to compute these subsets, but instead simply expresses them as null spaces and row spaces of matrices in reduced row-echelon form without any zero rows (\(C\) and \(L\)). A linearly independent set that spans the null space of a matrix in reduced row-echelon form can be found easily with Theorem BNS. It is an even easier matter to find a linearly independent set that spans the row space of a matrix in reduced row-echelon form with Theorem BRS, especially when there are no zero rows present. So an application of Theorem FS is typically followed by two applications each of Theorem BNS and Theorem BRS.

The situation when \(r=m\) deserves comment, since now the matrix \(L\) has no rows. What is \(\csp{A}\) when we try to apply Theorem FS and encounter \(\nsp{L}\text{?}\) One interpretation of this situation is that \(L\) is the coefficient matrix of a homogeneous system that has no equations. How hard is it to find a solution vector to this system? Some thought will convince you that any proposed vector will qualify as a solution, since it makes all of the equations true. So every possible vector is in the null space of \(L\) and therefore \(\csp{A}=\nsp{L}=\complex{m}\text{.}\) OK, perhaps this sounds like some twisted argument from Alice in Wonderland. Let us try another argument that might solidly convince you of this logic.

If \(r=m\text{,}\) when we row-reduce the augmented matrix of \(\linearsystem{A}{\vect{b}}\) the result will have no zero rows, and the first \(n\) columns will all be pivot columns, leaving none for the final column, so by Theorem RCLS the system will be consistent. By Theorem CSCS, \(\vect{b}\in\csp{A}\text{.}\) Since \(\vect{b}\) was arbitrary, every possible vector is in the column space of \(A\text{,}\) so we again have \(\csp{A}=\complex{m}\text{.}\) The situation when a matrix has \(r=m\) is known by the term full rank, and in the case of a square matrix coincides with nonsingularity (see Exercise FS.M50).

The properties of the matrix \(L\) described by this theorem can be explained informally as follows. A column vector \(\vect{y}\in\complex{m}\) is in the column space of \(A\) if the linear system \(\linearsystem{A}{\vect{y}}\) is consistent (Theorem CSCS). By Theorem RCLS, the reduced row-echelon form of the augmented matrix \(\augmented{A}{\vect{y}}\) of a consistent system will have zeros in the bottom \(m-r\) locations of the last column. By Theorem PEEF this final column is the vector \(J\vect{y}\) and so should then have zeros in the final \(m-r\) locations. But since \(L\) comprises the final \(m-r\) rows of \(J\text{,}\) this condition is expressed by saying \(\vect{y}\in\nsp{L}\text{.}\)

Additionally, the rows of \(J\) are the scalars in linear combinations of the rows of \(A\) that create the rows of \(B\text{.}\) That is, the rows of \(J\) record the net effect of the sequence of row operations that takes \(A\) to its reduced row-echelon form, \(B\text{.}\) This can be seen in the equation \(JA=B\) (Theorem PEEF). As such, the rows of \(L\) are scalars for linear combinations of the rows of \(A\) that yield zero rows. But such linear combinations are precisely the elements of the left null space. So any element of the row space of \(L\) is also an element of the left null space of \(A\text{.}\)

We will now illustrate Theorem FS with a few examples.

In Example SEEF we found the five relevant submatrices of the extended echelon form for the matrix

\begin{equation*} A= \begin{bmatrix} 1 & -1 & -2 & 7 & 1 & 6 \\ -6 & 2 & -4 & -18 & -3 & -26 \\ 4 & -1 & 4 & 10 & 2 & 17 \\ 3 & -1 & 2 & 9 & 1 & 12 \end{bmatrix}\text{.} \end{equation*}

To apply Theorem FS we only need \(C\) and \(L\text{,}\)

\begin{align*} C&= \begin{bmatrix} \leading{1} & 0 & 2 & 1 & 0 & 3 \\ 0 & \leading{1} & 4 & -6 & 0 & -1 \\ 0 & 0 & 0 & 0 & \leading{1} & 2 \end{bmatrix} & L&= \begin{bmatrix} \leading{1} & 2 & 2 & 1 \end{bmatrix}\text{.} \end{align*}

Then we use Theorem FS to obtain

\begin{align*} \nsp{A}&=\nsp{C}= \spn{\set{ \colvector{-2\\-4\\1\\0\\0\\0},\, \colvector{-1\\6\\0\\1\\0\\0},\, \colvector{-3\\1\\0\\0\\-2\\1} }}&& \knowl{./knowl/theorem-BNS.html}{\text{Theorem BNS}}\\ \rsp{A}&=\rsp{C}= \spn{\set{ \colvector{1\\0\\2\\1\\0\\3 },\, \colvector{0\\1\\4\\-6\\0\\-1},\, \colvector{0\\0\\0\\0\\1\\2} }}&& \knowl{./knowl/theorem-BRS.html}{\text{Theorem BRS}}\\ \csp{A}&=\nsp{L}= \spn{\set{ \colvector{-2\\1\\0\\0},\, \colvector{-2\\0\\1\\0},\, \colvector{-1\\0\\0\\1} }}&& \knowl{./knowl/theorem-BNS.html}{\text{Theorem BNS}}\\ \lns{A}&=\rsp{L}= \spn{\set{ \colvector{1\\2\\2\\1} }}&& \knowl{./knowl/theorem-BRS.html}{\text{Theorem BRS}}\text{.} \end{align*}

Boom!

Now let us return to the matrix \(A\) that we used to motivate this section in Example CSANS

\begin{equation*} A= \begin{bmatrix} 10 & 0 & 3 & 8 & 7 \\ -16 & -1 & -4 & -10 & -13 \\ -6 & 1 & -3 & -6 & -6 \\ 0 & 2 & -2 & -3 & -2 \\ 3 & 0 & 1 & 2 & 3 \\ -1 & -1 & 1 & 1 & 0 \end{bmatrix}\text{.} \end{equation*}

We form the matrix \(M\) by adjoining the \(6\times 6\) identity matrix \(I_6\text{.}\)

\begin{equation*} M= \begin{bmatrix} 10 & 0 & 3 & 8 & 7 & 1 & 0 & 0 & 0 & 0 & 0 \\ -16 & -1 & -4 & -10 & -13 & 0 & 1 & 0 & 0 & 0 & 0 \\ -6 & 1 & -3 & -6 & -6 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 2 & -2 & -3 & -2 & 0 & 0 & 0 & 1 & 0 & 0 \\ 3 & 0 & 1 & 2 & 3 & 0 & 0 & 0 & 0 & 1 & 0 \\ -1 & -1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} \end{equation*}

and row-reduce to obtain \(N\)

\begin{equation*} N= \begin{bmatrix} \leading{1} & 0 & 0 & 0 & 2 & 0 & 0 & 1 & -1 & 2 & -1 \\ 0 & \leading{1} & 0 & 0 & -3 & 0 & 0 & -2 & 3 & -3 & 3 \\ 0 & 0 & \leading{1} & 0 & 1 & 0 & 0 & 1 & 1 & 3 & 3 \\ 0 & 0 & 0 & \leading{1} & -2 & 0 & 0 & -2 & 1 & -4 & 0 \\ 0 & 0 & 0 & 0 & 0 & \leading{1} & 0 & 3 & -1 & 3 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & \leading{1} & -2 & 1 & 1 & -1 \end{bmatrix} \end{equation*}

To find the four subsets for \(A\text{,}\) we only need identify the \(4\times 5\) matrix \(C\) and the \(2\times 6\) matrix \(L\text{.}\)

\begin{align*} C&= \begin{bmatrix} \leading{1} & 0 & 0 & 0 & 2\\ 0 & \leading{1} & 0 & 0 & -3\\ 0 & 0 & \leading{1} & 0 & 1\\ 0 & 0 & 0 & \leading{1} & -2 \end{bmatrix} & L&= \begin{bmatrix} \leading{1} & 0 & 3 & -1 & 3 & 1 \\ 0 & \leading{1} & -2 & 1 & 1 & -1 \end{bmatrix} \end{align*}

Then we apply Theorem FS

\begin{align*} \nsp{A}&=\nsp{C}= \spn{\set{ \colvector{-2\\3\\-1\\2\\1} }}&& \knowl{./knowl/theorem-BNS.html}{\text{Theorem BNS}}\\ \rsp{A}&=\rsp{C}= \spn{\set{ \colvector{1 \\ 0 \\ 0 \\ 0 \\ 2},\, \colvector{0 \\ 1 \\ 0 \\ 0 \\ -3},\, \colvector{0 \\ 0 \\ 1 \\ 0 \\ 1},\, \colvector{0 \\ 0 \\ 0 \\ 1 \\ -2} }}&& \knowl{./knowl/theorem-BRS.html}{\text{Theorem BRS}}\\ \csp{A}&=\nsp{L}= \spn{\set{ \colvector{-3\\2\\1\\0\\0\\0},\, \colvector{1\\-1\\0\\1\\0\\0},\, \colvector{-3\\-1\\0\\0\\1\\0},\, \colvector{-1\\1\\0\\0\\0\\1} }}&& \knowl{./knowl/theorem-BNS.html}{\text{Theorem BNS}}\\ \lns{A}&=\rsp{L}= \spn{\set{ \colvector{1 \\ 0 \\ 3 \\ -1 \\ 3 \\ 1},\, \colvector{0 \\ 1 \\ -2 \\ 1 \\ 1 \\ -1} }}&& \knowl{./knowl/theorem-BRS.html}{\text{Theorem BRS}}\text{.} \end{align*}

The next example is just a bit different since the matrix has more rows than columns, and a trivial null space.

Archetype G and Archetype H are both systems of \(m=5\) equations in \(n=2\) variables. They have identical coefficient matrices, which we will denote here as the matrix \(G\text{.}\)

\begin{equation*} G=\begin{bmatrix} 2 & 3\\ -1 & 4 \\ 3 & 10\\ 3 & -1\\ 6 & 9 \end{bmatrix} \end{equation*}

Adjoin the \(5\times 5\) identity matrix, \(I_5\text{,}\) to form

\begin{equation*} M= \begin{bmatrix} 2 & 3 & 1&0&0&0&0\\ -1 & 4 & 0&1&0&0&0\\ 3 & 10 & 0&0&1&0&0\\ 3 & -1 & 0&0&0&1&0\\ 6 & 9 & 0&0&0&0&1 \end{bmatrix}\text{.} \end{equation*}

This row-reduces to

\begin{equation*} N= \begin{bmatrix} \leading{1} & 0 & 0 & 0 & 0 & \frac{3}{11} & \frac{1}{33}\\ 0 & \leading{1} & 0 & 0 & 0 & -\frac{2}{11} & \frac{1}{11}\\ 0 & 0 & \leading{1} & 0 & 0 & 0 & -\frac{1}{3}\\ 0 & 0 & 0 & \leading{1} & 0 & 1 & -\frac{1}{3}\\ 0 & 0 & 0 & 0 & \leading{1} & 1 & -1 \end{bmatrix}\text{.} \end{equation*}

The first \(n=2\) columns contain \(r=2\) leading 1's, so we obtain \(C\) as the \(2\times 2\) identity matrix and extract \(L\) from the final \(m-r=3\) rows in the final \(m=5\) columns.

\begin{align*} C&= \begin{bmatrix} \leading{1} & 0\\ 0 & \leading{1} \end{bmatrix} & L&= \begin{bmatrix} \leading{1} & 0 & 0 & 0 & -\frac{1}{3}\\ 0 & \leading{1} & 0 & 1 & -\frac{1}{3}\\ 0 & 0 & \leading{1} & 1 & -1 \end{bmatrix} \end{align*}

Then we apply Theorem FS

\begin{align*} \nsp{G}=\nsp{C}&= \spn{\emptyset} =\set{\zerovector}&& \knowl{./knowl/theorem-BNS.html}{\text{Theorem BNS}}\\ \rsp{G}=\rsp{C}&= \spn{\set{ \colvector{1 \\ 0},\, \colvector{0 \\ 1} }} =\complex{2}&& \knowl{./knowl/theorem-BRS.html}{\text{Theorem BRS}}\\ \csp{G}=\nsp{L}&= \spn{\set{ \colvector{0\\-1\\-1\\1\\0},\, \colvector{\frac{1}{3}\\\frac{1}{3}\\1\\0\\1} }}&& \knowl{./knowl/theorem-BNS.html}{\text{Theorem BNS}}\\ &=\spn{\set{ \colvector{0\\-1\\-1\\1\\0},\, \colvector{1\\1\\3\\0\\3} }}\\ \lns{G}=\rsp{L}&= \spn{\set{ \colvector{1 \\ 0 \\ 0 \\ 0 \\ -\frac{1}{3}},\, \colvector{0 \\ 1 \\ 0 \\ 1 \\ -\frac{1}{3}},\, \colvector{0 \\ 0 \\ 1 \\ 1 \\ -1} }}&& \knowl{./knowl/theorem-BRS.html}{\text{Theorem BRS}}\\ &=\spn{\set{ \colvector{3 \\ 0 \\ 0 \\ 0 \\ -1},\, \colvector{0 \\ 3 \\ 0 \\ 3\ \\ -1},\, \colvector{0 \\ 0 \\ 1 \\ 1 \\ -1} }}\text{.} \end{align*}

As mentioned earlier, Archetype G is consistent, while Archetype H is inconsistent. See if you can write the two different vectors of constants from these two archetypes as linear combinations of the two vectors that form the spanning set for \(\csp{G}\text{.}\) How about the two columns of \(G\text{?}\) Can you write each individually as a linear combination of the two vectors that form the spanning set for \(\csp{G}\text{?}\) They must be in the column space of \(G\) also. Are your answers unique? Do you notice anything about the scalars that appear in the linear combinations you are forming?

Sage will compute the extended echelon form, an improvement over what we did “by hand” in Sage MISLE. And the output can be requested as a “subdivided” matrix so that we can easily work with the pieces \(C\) and \(L\text{.}\) Pieces of subdivided matrices can be extracted with indices entirely similar to how we index the actual entries of a matrix. We will redo Example FS2 as an illustration of Theorem FS and Theorem PEEF.

Notice how we can employ the uniqueness of reduced row-echelon form (Theorem RREFU) to verify that C and L are in reduced row-echelon form. Realize too, that subdivided output is an optional behavior of the .extended_echelon_form() method and must be requested with subdivide=True.

Additionally, it is the uniquely determined matrix J that provides us with a standard version of the final column of the row-reduced augmented matrix using variables in the vector of constants, as first shown back in Example CSANS and verified here with variables defined as in Sage RRSM. (The vector method .column() converts a vector into a 1-column matrix, used here to format the matrix-vector product nicely.)

Example COV and Example CSROI each describes the column space of the coefficient matrix from Archetype I as the span of a set of \(r=3\) linearly independent vectors. It is no accident that these two different sets both have the same size. If we (you?) were to calculate the column space of this matrix using the null space of the matrix \(L\) from Theorem FS then we would again find a set of 3 linearly independent vectors that span the range. More on this later.

So we have three different methods to obtain a description of the column space of a matrix as the span of a linearly independent set. Theorem BCS is sometimes useful since the vectors it specifies are equal to actual columns of the matrix. Theorem BRS and Theorem CSRST combine to create vectors with lots of zeros, and strategically placed 1's near the top of the vector. Theorem FS and the matrix \(L\) from the extended echelon form gives us a third method, which tends to create vectors with lots of zeros, and strategically placed 1's near the bottom of the vector. If we do not care about linear independence we can also appeal to Definition CSM and simply express the column space as the span of all the columns of the matrix, giving us a fourth description.

With Theorem CSRST and Definition RSM, we can compute column spaces with theorems about row spaces, and we can compute row spaces with theorems about column spaces, but in each case we must transpose the matrix first. At this point you may be overwhelmed by all the possibilities for computing column and row spaces. Figure CSRST is meant to help. For both the column space and row space, it suggests four techniques. One is to appeal to the definition, another yields a span of a linearly independent set, and a third uses Theorem FS. A fourth suggests transposing the matrix and the dashed line implies that then the companion set of techniques can be applied. This can lead to a bit of silliness, since if you were to follow the dashed lines twice you would transpose the matrix twice, and by Theorem TT would accomplish nothing productive.

svg
Figure CSRST. Column Space and Row Space Techniques

Although we have many ways to describe a column space, notice that one tempting strategy will usually fail. It is not possible to simply row-reduce a matrix directly and then use the columns of the row-reduced matrix as a set whose span equals the column space. In other words, row operations do not preserve column spaces (however row operations do preserve row spaces, Theorem REMRS). See Exercise CRS.M21.

Reading Questions FS Reading Questions

1.

Find a nontrivial element of the left null space of \(A\text{.}\)

\begin{equation*} A= \begin{bmatrix} 2 & 1 & -3 & 4\\ -1 & -1 & 2 & -1\\ 0 & -1 & 1 & 2 \end{bmatrix} \end{equation*}
2.

Find the matrices \(C\) and \(L\) in the extended echelon form of \(A\text{.}\)

\begin{equation*} A= \begin{bmatrix} -9 & 5 & -3 \\ 2 & -1 & 1 \\ -5 & 3 & -1 \end{bmatrix} \end{equation*}

Exercises FS Exercises

C20.

Example FSAG concludes with several questions. Perform the analysis suggested by these questions.

C25.

Given the matrix \(A\) below, use the extended echelon form of \(A\) to answer each part of this problem. In each part, find a linearly independent set of vectors, \(S\text{,}\) so that the span of \(S\text{,}\) \(\spn{S}\text{,}\) equals the specified set of vectors.

  1. The row space of \(A\text{,}\) \(\rsp{A}\text{.}\)
  2. The column space of \(A\text{,}\) \(\csp{A}\text{.}\)
  3. The null space of \(A\text{,}\) \(\nsp{A}\text{.}\)
  4. The left null space of \(A\text{,}\) \(\lns{A}\text{.}\)
\begin{equation*} A= \begin{bmatrix} -5 & 3 & -1 \\ -1 & 1 & 1 \\ -8 & 5 & -1 \\ 3 & -2 & 0 \end{bmatrix} \end{equation*}
Solution

Add a \(4\times 4\) identity matrix to the right of \(A\) to form the matrix \(M\) and then row-reduce to the matrix \(N\text{,}\)

\begin{equation*} M= \begin{bmatrix} -5 & 3 & -1 & 1 & 0 & 0 & 0 \\ -1 & 1 & 1 & 0 & 1 & 0 & 0 \\ -8 & 5 & -1 & 0 & 0 & 1 & 0 \\ 3 & -2 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} \rref \begin{bmatrix} \leading{1} & 0 & 2 & 0 & 0 & -2 & -5 \\ 0 & \leading{1} & 3 & 0 & 0 & -3 & -8 \\ 0 & 0 & 0 & \leading{1} & 0 & -1 & -1 \\ 0 & 0 & 0 & 0 & \leading{1} & 1 & 3 \end{bmatrix} =N \end{equation*}

To apply Theorem FS in each of these four parts, we need the two matrices,

\begin{align*} C&= \begin{bmatrix} \leading{1} & 0 & 2 \\ 0 & \leading{1} & 3 \end{bmatrix} & L&= \begin{bmatrix} \leading{1} & 0 & -1 & -1 \\ 0 & \leading{1} & 1 & 3 \end{bmatrix} \end{align*}

(a)

\begin{align*} \rsp{A} &=\rsp{C}&& \knowl{./knowl/theorem-FS.html}{\text{Theorem FS}}\\ &=\spn{\set{\colvector{1\\0\\2},\,\colvector{0\\1\\3}}}&& \knowl{./knowl/theorem-BRS.html}{\text{Theorem BRS}} \end{align*}

(b)

\begin{align*} \csp{A} &=\nsp{L}&& \knowl{./knowl/theorem-FS.html}{\text{Theorem FS}}\\ &=\spn{\set{\colvector{1\\-1\\1\\0},\,\colvector{1\\-3\\0\\1}}}&& \knowl{./knowl/theorem-BNS.html}{\text{Theorem BNS}} \end{align*}

(c)

\begin{align*} \nsp{A} &=\nsp{C}&& \knowl{./knowl/theorem-FS.html}{\text{Theorem FS}}\\ &=\spn{\set{\colvector{-2\\-3\\1}}}&& \knowl{./knowl/theorem-BNS.html}{\text{Theorem BNS}} \end{align*}

(d)

\begin{align*} \lns{A} &=\rsp{L}&& \knowl{./knowl/theorem-FS.html}{\text{Theorem FS}}\\ &=\spn{\set{\colvector{1\\0\\-1\\-1},\,\colvector{0\\1\\1\\3}}}&& \knowl{./knowl/theorem-BRS.html}{\text{Theorem BRS}} \end{align*}
C26.

For the matrix \(D\) below use the extended echelon form to find:

  1. A linearly independent set whose span is the column space of \(D\text{.}\)
  2. A linearly independent set whose span is the left null space of \(D\text{.}\)
\begin{align*} D&= \begin{bmatrix} -7 & -11 & -19 & -15\\ 6 & 10 & 18 & 14 \\ 3 & 5 & 9 & 7 \\ -1 & -2 & -4 & -3 \end{bmatrix} \end{align*}
Solution

For both parts, we need the extended echelon form of the matrix.

\begin{align*} \begin{bmatrix} -7 & -11 & -19 & -15 & 1 & 0 & 0 & 0\\ 6 & 10 & 18 & 14 & 0 & 1 & 0 & 0 \\ 3 & 5 & 9 & 7 & 0 & 0 & 1 & 0 \\ -1 & -2 & -4 & -3 & 0 & 0 & 0 & 1 \end{bmatrix} \rref \begin{bmatrix} \leading{1} & 0 & -2 & -1 & 0 & 0 & 2 & 5 \\ 0 & \leading{1} & 3 & 2 & 0 & 0 & -1 & -3 \\ 0 & 0 & 0 & 0 & \leading{1} & 0 & 3 & 2 \\ 0 & 0 & 0 & 0 & 0 & \leading{1} & -2 & 0 \end{bmatrix} \end{align*}

From this matrix we extract the last two rows, in the last four columns to form the matrix \(L\text{,}\)

\begin{align*} L = \begin{bmatrix} \leading{1} & 0 & 3 & 2 \\ 0 & \leading{1} & -2 & 0 \end{bmatrix} \end{align*}

By Theorem FS and Theorem BNS we have

\begin{gather*} \csp{D}=\nsp{L}=\spn{\set{ \colvector{-3\\2\\1\\0},\, \colvector{-2\\0\\0\\1} }} \end{gather*}

By Theorem FS and Theorem BRS we have

\begin{gather*} \lns{D}=\rsp{L}=\spn{\set{ \colvector{1\\0\\3\\2},\, \colvector{0\\1\\-2\\0} }} \end{gather*}
C41.

The following archetypes are systems of equations. For each system, write the vector of constants as a linear combination of the vectors in the span construction for the column space provided by Theorem FS and Theorem BNS (these vectors are listed for each of these archetypes).

Archetype A, Archetype B, Archetype C, Archetype D, Archetype E, Archetype F, Archetype G, Archetype H, Archetype I, Archetype J

C43.

The following archetypes are either matrices or systems of equations with coefficient matrices. For each matrix, compute the extended echelon form \(N\) and identify the matrices \(C\) and \(L\text{.}\) Using Theorem FS, Theorem BNS and Theorem BRS express the null space, the row space, the column space and left null space of each coefficient matrix as a span of a linearly independent set.

Archetype A, Archetype B, Archetype C, Archetype D/Archetype E, Archetype F, Archetype G/Archetype H, Archetype I, Archetype J, Archetype K, Archetype L

C60.

For the matrix \(B\) below, find sets of vectors whose span equals the column space of \(B\) (\(\csp{B}\)) and which individually meet the following extra requirements.

  1. The set illustrates the definition of the column space.
  2. The set is linearly independent and the members of the set are columns of \(B\text{.}\)
  3. The set is linearly independent with a “nice pattern of zeros and ones” at the top of each vector.
  4. The set is linearly independent with a “nice pattern of zeros and ones” at the bottom of each vector.
\begin{equation*} B= \begin{bmatrix} 2 & 3 & 1 & 1\\ 1 & 1 & 0 & 1\\ -1 & 2 & 3 & -4 \end{bmatrix} \end{equation*}
Solution

The definition of the column space is the span of the set of columns (Definition CSM). So the desired set is just the four columns of \(B\text{,}\)

\begin{equation*} S=\set{ \colvector{2\\1\\-1},\, \colvector{3\\1\\2},\, \colvector{1\\0\\3},\, \colvector{1\\1\\-4} }\text{.} \end{equation*}

Theorem BCS suggests row-reducing the matrix and using the columns of \(B\) with the same indices as the pivot columns.

\begin{equation*} B\rref \begin{bmatrix} \leading{1} & 0 & -1 & 2\\ 0 & \leading{1} & 1 & -1\\ 0 & 0 & 0 & 0 \end{bmatrix} \end{equation*}

So the pivot columns are numbered by elements of \(D=\set{1,\,2}\text{,}\) so the requested set is

\begin{equation*} S=\set{ \colvector{2\\1\\-1},\, \colvector{3\\1\\2}}\text{.} \end{equation*}

We can find this set by row-reducing the transpose of \(B\text{,}\) deleting the zero rows, and using the nonzero rows as column vectors in the set. This is an application of Theorem CSRST followed by Theorem BRS.

\begin{equation*} \transpose{B}\rref \begin{bmatrix} \leading{1} & 0 & 3\\ 0 & \leading{1} & -7\\ 0 & 0 & 0\\ 0 & 0 & 0 \end{bmatrix} \end{equation*}

So the requested set is

\begin{equation*} S=\set{ \colvector{1\\0\\3},\, \colvector{0\\1\\-7} } \end{equation*}

With the column space expressed as a null space, the vectors obtained via Theorem BNS will be of the desired shape. So we first proceed with Theorem FS and create the extended echelon form

\begin{equation*} \augmented{B}{I_3}= \begin{bmatrix} 2 & 3 & 1 & 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 1 & 0 & 1 & 0\\ -1 & 2 & 3 & -4 & 0 & 0 & 1 \end{bmatrix} \rref \begin{bmatrix} \leading{1} & 0 & -1 & 2 & 0 & \frac{2}{3} & \frac{-1}{3}\\ 0 & \leading{1} & 1 & -1 & 0 & \frac{1}{3} & \frac{1}{3}\\ 0 & 0 & 0 & 0 & \leading{1} & \frac{-7}{3} & \frac{-1}{3} \end{bmatrix}\text{.} \end{equation*}

So, employing Theorem FS, we have \(\csp{B}=\nsp{L}\text{,}\) where

\begin{equation*} L= \begin{bmatrix} \leading{1} & \frac{-7}{3} & \frac{-1}{3} \end{bmatrix} \end{equation*}

We can find the desired set of vectors from Theorem BNS as

\begin{equation*} S=\set{ \colvector{\frac{7}{3}\\1\\0},\, \colvector{\frac{1}{3}\\0\\1} }\text{.} \end{equation*}
C61.

Let \(A\) be the matrix below, and find the indicated sets with the requested properties.

  1. A linearly independent set \(S\) so that \(\csp{A}=\spn{S}\) and \(S\) is composed of columns of \(A\text{.}\)
  2. A linearly independent set \(S\) so that \(\csp{A}=\spn{S}\) and the vectors in \(S\) have a nice pattern of zeros and ones at the top of the vectors.
  3. A linearly independent set \(S\) so that \(\csp{A}=\spn{S}\) and the vectors in \(S\) have a nice pattern of zeros and ones at the bottom of the vectors.
  4. A linearly independent set \(S\) so that \(\rsp{A}=\spn{S}\text{.}\)
\begin{equation*} A= \begin{bmatrix} 2 & -1 & 5 & -3\\ -5 & 3 & -12 & 7\\ 1 & 1 & 4 & -3 \end{bmatrix} \end{equation*}
Solution

First find a matrix \(B\) that is row-equivalent to \(A\) and in reduced row-echelon form.

\begin{equation*} B= \begin{bmatrix} \leading{1} & 0 & 3 & -2\\ 0 & \leading{1} & 1 & -1\\ 0 & 0 & 0 & 0 \end{bmatrix} \end{equation*}

By Theorem BCS we can choose the columns of \(A\) that have the same indices as the pivot columns (\(D=\set{1,2}\)) as the elements of \(S\) and obtain the desired properties. So

\begin{equation*} S=\set{\colvector{2\\-5\\1},\,\colvector{-1\\3\\1}} \end{equation*}

We can write the column space of \(A\) as the row space of the transpose (Theorem CSRST). So we row-reduce the transpose of \(A\) to obtain the row-equivalent matrix \(C\) in reduced row-echelon form.

\begin{equation*} C= \begin{bmatrix} 1 & 0 & 8\\ 0 & 1 & 3\\ 0 & 0 & 0\\ 0 & 0 & 0 \end{bmatrix} \end{equation*}

The nonzero rows (written as columns) will be a linearly independent set that spans the row space of \(\transpose{A}\text{,}\) by Theorem BRS, and the zeros and ones will be at the top of the vectors,

\begin{equation*} S=\set{\colvector{1\\0\\8},\,\colvector{0\\1\\3}} \end{equation*}

In preparation for Theorem FS, augment \(A\) with the \(3\times 3\) identity matrix \(I_3\) and row-reduce to obtain the extended echelon form.

\begin{equation*} \begin{bmatrix} 1 & 0 & 3 & -2 & 0 & -\frac{1}{8} & \frac{3}{8}\\ 0 & 1 & 1 & -1 & 0 & \frac{1}{8} & \frac{5}{8}\\ 0 & 0 & 0 & 0 & 1 & \frac{3}{8} & -\frac{1}{8} \end{bmatrix} \end{equation*}

Then since the first four columns of row 3 are all zeros, we extract

\begin{equation*} L= \begin{bmatrix} \leading{1} & \frac{3}{8} & -\frac{1}{8} \end{bmatrix} \end{equation*}

Theorem FS says that \(\csp{A}=\nsp{L}\text{.}\) We can then use Theorem BNS to construct the desired set \(S\text{,}\) based on the free variables with indices in \(F=\set{2,3}\) for the homogeneous system \(\homosystem{L}\text{,}\) so

\begin{equation*} S=\set{\colvector{-\frac{3}{8}\\1\\0},\,\colvector{\frac{1}{8}\\0\\1}} \end{equation*}

Notice that the zeros and ones are at the bottom of the vectors.

This is a straightforward application of Theorem BRS. Use the row-reduced matrix \(B\) from part (a), grab the nonzero rows, and write them as column vectors,

\begin{equation*} S=\set{\colvector{1\\0\\3\\-2},\,\colvector{0\\1\\1\\-1}} \end{equation*}
M50.

Suppose that \(A\) is a nonsingular matrix. Extend the four conclusions of Theorem FS in this special case and discuss connections with previous results (such as Theorem NME4).

M51.

Suppose that \(A\) is a singular matrix. Extend the four conclusions of Theorem FS in this special case and discuss connections with previous results (such as Theorem NME4).