Section CRS Column and Row Spaces
A matrix-vector product (Definition MVP) is a linear combination of the columns of the matrix and this allows us to connect matrix multiplication with systems of equations via Theorem SLSLC. Row operations are linear combinations of the rows of a matrix, and of course, reduced row-echelon form (Definition RREF) is also intimately related to solving systems of equations. In this section we will formalize these ideas with two key definitions of sets of vectors derived from a matrix.
Subsection CSSE Column Spaces and Systems of Equations
Theorem SLSLC showed us that there is a natural correspondence between solutions to linear systems and linear combinations of the columns of the coefficient matrix. This idea motivates the following important definition.
Definition CSM. Column Space of a Matrix.
Suppose that \(A\) is an \(m\times n\) matrix with columns \(\vectorlist{A}{n}\text{.}\) Then the column space of \(A\text{,}\) written \(\csp{A}\text{,}\) is the subset of \(\complex{m}\) containing all linear combinations of the columns of \(A\text{,}\)
Some authors refer to the column space of a matrix as the range, but we will reserve this term for use with linear transformations (Definition RLT).
Upon encountering any new set, the first question we ask is what objects are in the set, and which objects are not? Here is an example of one way to answer this question, and it will motivate a theorem that will then answer the question precisely.
Example CSMCS. Column space of a matrix and consistent systems.
Archetype D and Archetype E are linear systems of equations, with an identical \(3\times 4\) coefficient matrix, which we call \(A\) here. However, Archetype D is consistent, while Archetype E is not. We can explain this difference by employing the column space of the matrix \(A\text{.}\)
The column vector of constants, \(\vect{b}\text{,}\) in Archetype D is given below, and one solution listed for \(\linearsystem{A}{\vect{b}}\) is \(\vect{x}\)
By Theorem SLSLC, we can summarize this solution as a linear combination of the columns of \(A\) that equals \(\vect{b}\text{,}\)
This equation says that \(\vect{b}\) is a linear combination of the columns of \(A\text{,}\) and then by Definition CSM, we can say that \(\vect{b}\in\csp{A}\text{.}\)
On the other hand, Archetype E is the linear system \(\linearsystem{A}{\vect{c}}\text{,}\) where the vector of constants is
and this system of equations is inconsistent. This means \(\vect{c}\not\in\csp{A}\text{,}\) for if it were, then it would equal a linear combination of the columns of \(A\) and Theorem SLSLC would lead us to a solution of the system \(\linearsystem{A}{\vect{c}}\text{.}\)
So if we fix the coefficient matrix, and vary the vector of constants, we can sometimes find consistent systems, and sometimes inconsistent systems. The vectors of constants that lead to consistent systems are exactly the elements of the column space. This is the content of the next theorem, and since it is an equivalence, it provides an alternate view of the column space.
Theorem CSCS. Column Spaces and Consistent Systems.
Suppose \(A\) is an \(m\times n\) matrix and \(\vect{b}\) is a vector of size \(m\text{.}\) Then \(\vect{b}\in\csp{A}\) if and only if \(\linearsystem{A}{\vect{b}}\) is consistent.
Proof.
(⇒)
Suppose \(\vect{b}\in\csp{A}\text{.}\) Then we can write \(\vect{b}\) as some linear combination of the columns of \(A\text{.}\) By Theorem SLSLC we can use the scalars from this linear combination to form a solution to \(\linearsystem{A}{\vect{b}}\text{,}\) so this system is consistent.
(⇐)
If \(\linearsystem{A}{\vect{b}}\) is consistent, there is a solution that may be used with Theorem SLSLC to write \(\vect{b}\) as a linear combination of the columns of \(A\text{.}\) This qualifies \(\vect{b}\) for membership in \(\csp{A}\text{.}\)
This theorem tells us that asking if the system \(\linearsystem{A}{\vect{b}}\) is consistent is exactly the same question as asking if \(\vect{b}\) is in the column space of \(A\text{.}\) Or equivalently, it tells us that the column space of the matrix \(A\) is precisely those vectors of constants, \(\vect{b}\text{,}\) that can be paired with \(A\) to create a system of linear equations \(\linearsystem{A}{\vect{b}}\) that is consistent.
Employing Theorem SLEMM we can form the chain of equivalences.
Thus, an alternative (and popular) definition of the column space of an \(m\times n\) matrix \(A\) is
We recognize this as saying create all the matrix-vector products possible with the matrix \(A\) by letting \(\vect{x}\) range over all of the possibilities. By Definition MVP we see that this means take all possible linear combinations of the columns of \(A\) — precisely the definition of the column space (Definition CSM) we have chosen.
Notice how this formulation of the column space looks very much like the definition of the null space of a matrix (Definition NSM), but for a rectangular matrix the column vectors of \(\csp{A}\) and \(\nsp{A}\) have different sizes, so the sets are very different.
Given a vector \(\vect{b}\) and a matrix \(A\) it is now very mechanical to test if \(\vect{b}\in\csp{A}\text{.}\) Form the linear system \(\linearsystem{A}{\vect{b}}\text{,}\) row-reduce the augmented matrix, \(\augmented{A}{\vect{b}}\text{,}\) and test for consistency with Theorem RCLS. Here is an example of this procedure.
Example MCSM. Membership in the column space of a matrix.
Consider the question of membership in the column space of the \(3\times 4\) matrix \(A\text{,}\) for the vector \(\vect{v}\text{.}\) Is \(\vect{v}\in\csp{A}\text{?}\)
Theorem CSCS says we need only check the consistency of \(\linearsystem{A}{\vect{v}}\text{.}\) Form the augmented matrix and row-reduce,
Since the final column is not a pivot column, Theorem RCLS tells us the system is consistent and therefore by Theorem CSCS, \(\vect{v}\in\csp{A}\text{.}\)
If we wished to demonstrate explicitly that \(\vect{v}\) is a linear combination of the columns of \(A\text{,}\) we can find a solution (any solution) of \(\linearsystem{A}{\vect{v}}\) and use Theorem SLSLC to construct the desired linear combination. For example, set the free variables to \(x_3=2\) and \(x_4=1\text{.}\) Then a solution has \(x_2=1\) and \(x_1=6\text{.}\) Then by Theorem SLSLC
Now we show that the vector \(\vect{w}\) is not in the column space of \(A\text{,}\) \(\vect{w}\not\in\csp{A}\text{.}\)
Theorem CSCS says we need only check the consistency of \(\linearsystem{A}{\vect{w}}\text{.}\) Form the augmented matrix and row-reduce
since the final column is a pivot column, Theorem RCLS tells us the system is inconsistent and therefore by Theorem CSCS, \(\vect{w}\not\in\csp{A}\text{.}\)
Sage CSCS. Column Space and Consistent Systems.
We could compute the column space of a matrix with a span of the set of columns of the matrix, much as we did back in Sage CSS when we were checking consistency of linear systems using spans of the set of columns of a coefficent matrix. However, Sage provides a convenient matrix method to construct this same span: .column_space(). Here is a check.
In Sage CSS we discussed solutions to systems of equations and the membership of the vector of constants in the span of the columns of the coefficient matrix. This discussion turned on Theorem SLSLC. We can now be slightly more efficient with Theorem CSCS, while still using the same ideas. We recycle the computations from Example CSMCS that use Archetype D and Archetype E.
Theorem CSCS completes a collection of three theorems, and one definition, that deserve comment. Many questions about spans, linear independence, null space, column spaces and similar objects can be converted to questions about systems of equations (homogeneous or not), which we understand well from our previous results, especially those in Chapter SLE. These previous results include theorems like Theorem RCLS which allows us to quickly decide consistency of a system, and Theorem BNS which allows us to describe solution sets for homogeneous systems compactly as the span of a linearly independent set of column vectors.
The table below lists these four definitions and theorems along with a brief reminder of the statement and an example of how the statement is used.
| Definition NSM | |
| Synopsis | Null space is solution set of homogeneous system |
| Example | General solution sets described by Theorem PSPHS |
| Theorem SLSLC | |
| Synopsis | Solutions for linear combinations with unknown scalars |
| Example | Deciding membership in spans |
| Theorem SLEMM | |
| Synopsis | System of equations represented by matrix-vector product |
| Example | Solution to \(\linearsystem{A}{\vect{b}}\) is \(\inverse{A}\vect{b}\) when \(A\) is nonsingular |
| Theorem CSCS | |
| Synopsis | Column space vectors create consistent systems |
| Example | Deciding membership in column spaces |
Subsection CSSOC Column Space Spanned by Original Columns
So we have a foolproof, automated procedure for determining membership in \(\csp{A}\text{.}\) While this works just fine a vector at a time, we would like to have a more useful description of the set \(\csp{A}\) as a whole. The next example will preview the first of two fundamental results about the column space of a matrix.
Example CSTW. Column space, two ways.
Consider the \(5\times 7\) matrix \(A\text{.}\)
According to the definition (Definition CSM), the column space of \(A\) is
While this is a concise description of an infinite set, we might be able to describe the span with fewer than seven vectors. This is the substance of Theorem BS. So we take these seven vectors and make them the columns of a matrix, which is simply the original matrix \(A\) again. Now we row-reduce
The pivot columns are \(D=\set{1,\,3,\,4,\,5}\text{,}\) so we can create the set
and know that \(\csp{A}=\spn{T}\) and \(T\) is a linearly independent set of columns from the set of columns of \(A\text{.}\)
We will now formalize the previous example, which will make it trivial to determine a linearly independent set of vectors that will span the column space of a matrix, and is constituted of just columns of \(A\text{.}\)
Theorem BCS. Basis of the Column Space.
Suppose that \(A\) is an \(m\times n\) matrix with columns \(\vectorlist{A}{n}\text{,}\) and \(B\) is a row-equivalent matrix in reduced row-echelon form with \(r\) pivot columns. Let \(D=\{d_1,\,d_2,\,d_3,\,\ldots,\,d_r\}\) be the set of indices for the pivot columns of \(B\text{.}\) Let \(T=\set{\vect{A}_{d_1},\,\vect{A}_{d_2},\,\vect{A}_{d_3},\,\ldots,\,\vect{A}_{d_r}}\text{.}\) Then
- \(T\) is a linearly independent set.
- \(\csp{A}=\spn{T}\text{.}\)
Proof.
Definition CSM describes the column space as the span of the set of columns of \(A\text{.}\) Theorem BS tells us that we can reduce the set of vectors used in a span. If we apply Theorem BS to \(\csp{A}\text{,}\) we would collect the columns of \(A\) into a matrix (which would just be \(A\) again) and bring the matrix to reduced row-echelon form, which is the matrix \(B\) in the statement of the theorem. In this case, the conclusions of Theorem BS applied to \(A\text{,}\) \(B\) and \(\csp{A}\) are exactly the conclusions we desire.
This is a nice result since it gives us a handful of vectors that describe the entire column space (through the span), and we believe this set is as small as possible because we cannot create any more relations of linear dependence to trim it down further. Furthermore, we defined the column space (Definition CSM) as all linear combinations of the columns of the matrix, and the elements of the set \(T\) are still columns of the matrix (we will not be so lucky in the next two constructions of the column space).
Procedurally this theorem is extremely easy to apply. Row-reduce the original matrix, identify the \(r\) pivot columns of the row-reduced matrix, and grab the columns of the original matrix with the same indices as the pivot columns. But it is still important to study the proof of Theorem BS and its motivation in Example COV which lie at the root of this theorem. We will trot through an example all the same.
Example CSOCD. Column space, original columns, Archetype D.
Let us determine a compact expression for the entire column space of the coefficient matrix of the system of equations that is Archetype D. Notice that in Example CSMCS we were only determining if individual vectors were in the column space or not, now we are describing the entire column space.
To start with the application of Theorem BCS, call the coefficient matrix \(A\) and row-reduce it to reduced row-echelon form \(B\)
Since columns 1 and 2 are pivot columns, \(D=\{1,\,2\}\text{.}\) To construct a set that spans \(\csp{A}\text{,}\) just grab the columns of \(A\) with indices in \(D\text{,}\) so
That's it.
In Example CSMCS we determined that the vector
was not in the column space of \(A\text{.}\) Try to write \(\vect{c}\) as a linear combination of the first two columns of \(A\text{.}\) What happens?
Also in Example CSMCS we determined that the vector
was in the column space of \(A\text{.}\) Try to write \(\vect{b}\) as a linear combination of the first two columns of \(A\text{.}\) What happens? Did you find a unique solution to this question? Hmmmm.
Sage CSOC. Column Space, Original Columns.
It might be worthwhile for Sage to create a column space using actual columns of the matrix as a spanning set. But we can do it ourselves fairly easily. A discussion follows the example.
We see that A has four pivot columns, numbered 0,1,2,4. The matrix B is just a convenience to hold the pivot columns of A. However, the column spaces of A and B should be equal, as Sage verifies. Also B will row-reduce to the same 0-1 pivot columns of the reduced row-echelon form of the full matrix A. So it is no accident that the reduced row-echelon form of B is a full identity matrix, followed by sufficiently many zero rows to give the matrix the correct size.
The vector space method .span_of_basis() is new to us. It creates a span of a set of vectors, as before, but we now are responsible for supplying a linearly independent set of vectors. Which we have done. We know this because Theorem BCS guarantees the set we provided is linearly independent (and spans the column space), while Sage would have given us an error if we had provided a linearly dependent set. In return, Sage will carry this linearly independent spanning set along with the vector space, something Sage calls a “user basis.”
Notice how cs has two linearly independent spanning sets now. Our set of “original columns” is obtained via the standard vector space method .basis() and we can obtain a linearly independent spanning set that looks more familiar with the vector space method .echelonized_basis(). For a vector space created with a simple .span() construction these two commands would yield identical results — it is only when we supply a linearly independent spanning set with the .span_of_basis() method that a “user basis” becomes relevant.
Finally, we check that cs is indeed the column space of A (we knew it would be) and then we provide a one-line, totally general construction of the column space using original columns.
This is an opportunity to make an interesting observation, which could be used to substantiate several theorems. When we take the original columns that we recognize as pivot columns, and use them alone to form a matrix, this new matrix will always row-reduce to an identity matrix followed by zero rows. This is basically a consequence of reduced row-echelon form. Evaluate the compute cell below repeatedly. The number of columns could in theory change, though this is unlikely since the columns of a random matrix are unlikely to be linearly dependent. In any event, the form of the result will always be an identity matrix followed by some zero rows.
With more columns than rows, we know by Theorem MVSLD that we will have a reduced number of pivot columns. Here, we will almost always see an identity matrix as the result, though we could get a smaller identity matrix followed by zero rows.
Subsection CSNM Column Space of a Nonsingular Matrix
Let us specialize to square matrices and contrast the column spaces of the coefficient matrices in Archetype A and Archetype B.
Example CSAA. Column space of Archetype A.
The coefficient matrix in Archetype A is \(A\text{,}\) which row-reduces to \(B\text{.}\)
Columns 1 and 2 are pivot columns, so by Theorem BCS we can write
We want to show in this example that \(\csp{A}\neq\complex{3}\text{.}\) So take, for example, the vector \(\vect{b}\text{.}\)
Then there is no solution to the system \(\linearsystem{A}{\vect{b}}\text{,}\) or equivalently, it is not possible to write \(\vect{b}\) as a linear combination of \(\vect{A}_1\) and \(\vect{A}_2\text{.}\) Try one of these two computations yourself. (Or try both!). Since \(\vect{b}\not\in\csp{A}\text{,}\) the column space of \(A\) cannot be all of \(\complex{3}\text{.}\) So by varying the vector of constants, it is possible to create inconsistent systems of equations with this coefficient matrix (the vector \(\vect{b}\) being one such example).
In Example MWIAA we wished to show that the coefficient matrix from Archetype A was not invertible as a first example of a matrix without an inverse. Our device there was to find an inconsistent linear system with \(A\) as the coefficient matrix. The vector of constants in that example was \(\vect{b}\text{,}\) deliberately chosen outside the column space of \(A\text{.}\)
Example CSAB. Column space of Archetype B.
The coefficient matrix in Archetype B, call it \(B\) here, is known to be nonsingular (see Example NM). By Theorem NMUS, the linear system \(\linearsystem{B}{\vect{b}}\) has a (unique) solution for every choice of \(\vect{b}\text{.}\) Theorem CSCS then says that \(\vect{b}\in\csp{B}\) for all \(\vect{b}\in\complex{3}\text{.}\) Stated differently, there is no way to build an inconsistent system with the coefficient matrix \(B\text{,}\) but then we knew that already from Theorem NMUS.
Example CSAA and Example CSAB together motivate the following equivalence, which says that nonsingular matrices have column spaces that are as big as possible.
Theorem CSNM. Column Space of a Nonsingular Matrix.
Suppose \(A\) is a square matrix of size \(n\text{.}\) Then \(A\) is nonsingular if and only if \(\csp{A}=\complex{n}\text{.}\)
Proof.
(⇒)
Suppose \(A\) is nonsingular. We wish to establish the set equality \(\csp{A}=\complex{n}\text{.}\) By Definition CSM, \(\csp{A}\subseteq\complex{n}\text{.}\) To show that \(\complex{n}\subseteq\csp{A}\) choose \(\vect{b}\in\complex{n}\text{.}\) By Theorem NMUS, we know the linear system \(\linearsystem{A}{\vect{b}}\) has a (unique) solution and therefore is consistent. Theorem CSCS then says that \(\vect{b}\in\csp{A}\text{.}\) So by Definition SE, \(\csp{A}=\complex{n}\text{.}\)
(⇐)
If \(\vect{e}_i\) is column \(i\) of the \(n\times n\) identity matrix (Definition SUV) and by hypothesis \(\csp{A}=\complex{n}\text{,}\) then \(\vect{e}_i\in\csp{A}\) for \(1\leq i\leq n\text{.}\) By Theorem CSCS, the system \(\linearsystem{A}{\vect{e}_i}\) is consistent for \(1\leq i\leq n\text{.}\) Let \(\vect{b}_i\) denote any one particular solution to \(\linearsystem{A}{\vect{e}_i}\text{,}\) \(1\leq i\leq n\text{.}\)
Define the \(n\times n\) matrix \(B=\matrixcolumns{b}{n}\text{.}\) Then
So the matrix \(B\) is a “right-inverse” for \(A\text{.}\) By Theorem NMRRI, \(I_n\) is a nonsingular matrix, so by Theorem NPNF both \(A\) and \(B\) are nonsingular. Thus, in particular, \(A\) is nonsingular. (Travis Osborne contributed to this proof.)
With this equivalence for nonsingular matrices we can update our list, Theorem NME3.
Theorem NME4. Nonsingular Matrix Equivalences, Round 4.
Suppose that \(A\) is a square matrix of size \(n\text{.}\) The following are equivalent.
- \(A\) is nonsingular.
- \(A\) row-reduces to the identity matrix.
- The null space of \(A\) contains only the zero vector, \(\nsp{A}=\set{\zerovector}\text{.}\)
- The linear system \(\linearsystem{A}{\vect{b}}\) has a unique solution for every possible choice of \(\vect{b}\text{.}\)
- The columns of \(A\) are a linearly independent set.
- \(A\) is invertible.
- The column space of \(A\) is \(\complex{n}\text{,}\) \(\csp{A}=\complex{n}\text{.}\)
Proof.
Since Theorem CSNM is an equivalence, we can add it to the list in Theorem NME3.
Sage NME4. Nonsingular Matrix Equivalences, Round 4.
Archetype A and Archetype B have square coefficient matrices that illustrate the dichotomy of singular and nonsingular matrices. Here we illustrate the latest addition to our series of equivalences, Theorem CSNM.
We can even write Theorem CSNM as a one-line Sage statement that will return True for any square matrix. Run the following repeatedly and it should always return True. We have kept the size of the matrix relatively small to be sure that some of the random matrices produced are singular.
Subsection RSM Row Space of a Matrix
The rows of a matrix can be viewed as vectors, since they are just lists of numbers, arranged horizontally. So we will transpose a matrix, turning rows into columns, so we can then manipulate rows as column vectors. As a result we will be able to make some new connections between row operations and solutions to systems of equations. OK, here is the second primary definition of this section.
Definition RSM. Row Space of a Matrix.
Suppose \(A\) is an \(m\times n\) matrix. Then the row space of \(A\text{,}\) \(\rsp{A}\text{,}\) is the column space of \(\transpose{A}\text{,}\) i.e. \(\rsp{A}=\csp{\transpose{A}}\text{.}\)
Informally, the row space is the set of all linear combinations of the rows of \(A\text{.}\) However, we write the rows as column vectors, thus the necessity of using the transpose to make the rows into columns. Additionally, with the row space defined in terms of the column space, all of the previous results of this section can be applied to row spaces.
Notice that if \(A\) is a rectangular \(m\times n\) matrix, then \(\csp{A}\subseteq\complex{m}\text{,}\) while \(\rsp{A}\subseteq\complex{n}\) and the two sets are not comparable since they do not even hold objects of the same type. However, when \(A\) is square of size \(n\text{,}\) both \(\csp{A}\) and \(\rsp{A}\) are subsets of \(\complex{n}\text{,}\) though usually the sets will not be equal (but see Exercise CRS.M20).
Example RSAI. Row space of Archetype I.
The coefficient matrix in Archetype I is
To build the row space, we transpose the matrix.
Then the columns of this matrix are used in a span to build the row space.
However, we can use Theorem BCS to get a slightly better description. First, row-reduce \(\transpose{I}\text{.}\)
Since the pivot columns have indices \(D=\set{1,\,2,\,3}\text{,}\) the column space of \(\transpose{I}\) can be spanned by just the first three columns of \(\transpose{I}\text{.}\)
The row space would not be too interesting if it was simply the column space of the transpose. However, when we do row operations on a matrix we have no effect on the many linear combinations that can be formed with the rows of the matrix. This is stated more carefully in the following theorem.
Theorem REMRS. Row-Equivalent Matrices have equal Row Spaces.
Suppose \(A\) and \(B\) are row-equivalent matrices. Then \(\rsp{A}=\rsp{B}\text{.}\)
Proof.
Two matrices are row-equivalent (Definition REM) if one can be obtained from another by a sequence of (possibly many) row operations. We will prove the theorem for two matrices that differ by a single row operation, and then this result can be applied repeatedly to get the full statement of the theorem. The row spaces of \(A\) and \(B\) are spans of the columns of their transposes. For each row operation we perform on a matrix, we can define an analogous operation on the columns. Perhaps we should call these column operations. Instead, we will still call them row operations, but we will apply them to the columns of the transposes.
Refer to the columns of \(\transpose{A}\) and \(\transpose{B}\) as \(\vect{A}_i\) and \(\vect{B}_i\text{,}\) \(1\leq i\leq m\text{.}\) The row operation that switches rows will just switch columns of the transposed matrices. This will have no effect on the possible linear combinations formed by the columns.
Suppose that \(\transpose{B}\) is formed from \(\transpose{A}\) by multiplying column \(\vect{A}_t\) by \(\alpha\neq 0\text{.}\) In other words, \(\vect{B}_t=\alpha\vect{A}_t\text{,}\) and \(\vect{B}_i=\vect{A}_i\) for all \(i\neq t\text{.}\) We need to establish that two sets are equal, \(\csp{\transpose{A}}=\csp{\transpose{B}}\text{.}\) We will take a generic element of one and show that it is contained in the other.
says that \(\csp{\transpose{B}}\subseteq\csp{\transpose{A}}\text{.}\) Similarly,
says that \(\csp{\transpose{A}}\subseteq\csp{\transpose{B}}\text{.}\) So \(\rsp{A}=\csp{\transpose{A}}=\csp{\transpose{B}}=\rsp{B}\) when a single row operation of the second type is performed.
Suppose now that \(\transpose{B}\) is formed from \(\transpose{A}\) by replacing \(\vect{A}_t\) with \(\alpha\vect{A}_s+\vect{A}_t\) for some \(\alpha\in\complexes\) and \(s\neq t\text{.}\) In other words, \(\vect{B}_t=\alpha\vect{A}_s+\vect{A}_t\text{,}\) and \(\vect{B}_i=\vect{A}_i\) for \(i\neq t\text{.}\)
says that \(\csp{\transpose{B}}\subseteq\csp{\transpose{A}}\text{.}\) Similarly,
says that \(\csp{\transpose{A}}\subseteq\csp{\transpose{B}}\text{.}\) So \(\rsp{A}=\csp{\transpose{A}}=\csp{\transpose{B}}=\rsp{B}\) when a single row operation of the third type is performed.
So the row space of a matrix is preserved by each row operation, and hence row spaces of row-equivalent matrices are equal sets.
Example RSREM. Row spaces of two row-equivalent matrices.
In Example TREM we saw that the matrices
are row-equivalent by demonstrating a sequence of two row operations that converted \(A\) into \(B\text{.}\) Applying Theorem REMRS we can say
Theorem REMRS is at its best when one of the row-equivalent matrices is in reduced row-echelon form. The vectors that are zero rows can be ignored. (Who needs the zero vector when building a span? See Exercise LI.T10.) The echelon pattern insures that the nonzero rows yield vectors that are linearly independent. Here is the theorem.
Theorem BRS. Basis for the Row Space.
Suppose that \(A\) is a matrix and \(B\) is a row-equivalent matrix in reduced row-echelon form. Let \(S\) be the set of nonzero columns of \(\transpose{B}\text{.}\) Then
- \(\rsp{A}=\spn{S}\text{.}\)
- \(S\) is a linearly independent set.
Proof.
From Theorem REMRS we know that \(\rsp{A}=\rsp{B}\text{.}\) If \(B\) has any zero rows, these are columns of \(\transpose{B}\) that are the zero vector. We can safely toss out the zero vector in the span construction, since it can be recreated from the nonzero vectors by a linear combination where all the scalars are zero. So \(\rsp{A}=\spn{S}\text{.}\)
Suppose \(B\) has \(r\) nonzero rows and let \(D=\set{d_1,\,d_2,\,d_3,\,\ldots,\,d_r}\) denote the indices of the pivot columns of \(B\text{.}\) Denote the \(r\) column vectors of \(\transpose{B}\text{,}\) the vectors in \(S\text{,}\) as \(\vectorlist{B}{r}\text{.}\) To show that \(S\) is linearly independent, start with a relation of linear dependence
Now consider this vector equality in location \(d_i\text{.}\) Since \(B\) is in reduced row-echelon form, the entries of column \(d_i\) of \(B\) are all zero, except for a leading 1 in row \(i\text{.}\) Thus, in \(\transpose{B}\text{,}\) row \(d_i\) is all zeros, excepting a 1 in column \(i\text{.}\) So, for \(1\leq i\leq r\text{,}\)
So we conclude that \(\alpha_i=0\) for all \(1\leq i\leq r\text{,}\) establishing the linear independence of \(S\) (Definition LICV).
Example IAS. Improving a span.
Suppose in the course of analyzing a matrix (its column space, its null space, its …) we encounter the following set of vectors, described by a span
Let \(A\) be the matrix whose rows are the vectors in \(X\text{,}\) so by design \(X=\rsp{A}\text{.}\)
Row-reduce \(A\) to form a row-equivalent matrix in reduced row-echelon form.
Then Theorem BRS says we can grab the nonzero columns of \(\transpose{B}\) and write
These three vectors provide a much-improved description of \(X\text{.}\) There are fewer vectors, and the pattern of zeros and ones in the first three entries makes it easier to determine membership in \(X\text{.}\)
Notice that in Example IAS all we had to do was row-reduce the right matrix and toss out a zero row. Next to row operations themselves, Theorem BRS is probably the most powerful computational technique at your disposal as it quickly provides a much improved description of a span, any span (row space, column space, …).
Theorem BRS and the techniques of Example IAS will provide yet another description of the column space of a matrix. First we state a triviality as a theorem, so we can reference it later.
Theorem CSRST. Column Space, Row Space, Transpose.
Suppose \(A\) is a matrix. Then \(\csp{A}=\rsp{\transpose{A}}\text{.}\)
Proof.
So to find another expression for the column space of a matrix, build its transpose, row-reduce it, toss out the zero rows, and convert the nonzero rows to column vectors to yield an improved set for the span construction. We will do Archetype I, then you do Archetype J.
Example CSROI. Column space from row operations, Archetype I.
To find the column space of the coefficient matrix of Archetype I, we proceed as follows. The matrix is
The transpose is
Row-reduced this becomes,
Now, using Theorem CSRST and Theorem BRS
This is a very nice description of the column space. Fewer vectors than the 7 involved in the definition, and the pattern of the zeros and ones in the first 3 slots can be used to advantage. For example, Archetype I is presented as a consistent system of equations with a vector of constants
Since \(\linearsystem{I}{\vect{b}}\) is consistent, Theorem CSCS tells us that \(\vect{b}\in\csp{I}\text{.}\) But we could see this quickly with the following computation, which really only involves any work in the 4th entry of the vectors as the scalars in the linear combination are dictated by the first three entries of \(\vect{b}\text{.}\)
Can you now rapidly construct several vectors, \(\vect{b}\text{,}\) so that \(\linearsystem{I}{\vect{b}}\) is consistent, and several more so that the system is inconsistent?
Sage RSM. Row Space of a Matrix.
Not to be outdone, and not suprisingly, Sage can compute a row space with the matrix method .row_space(). Indeed, given Sage's penchant for treating vectors as rows, much of Sage's infrastructure for vector spaces ultimately relies on Theorem REMRS. More on that in Sage SUTH0. For now, we reprise Example IAS as an illustration.
We begin with the same four vectors in Example IAS and create their span, the vector space X. The matrix A has these four vectors as rows and B is the reduced row-echelon form of A. Then the row spaces of A and B are equal to the vector space X (and each other). The way Sage describes this vector space is with a matrix whose rows are the nonzero rows of the reduced row-echelon form of the matrix A. This is Theorem BRS in action where we go with Sage's penchant for rows and ignore the text's penchant for columns.
We can illustrate a few other results about row spaces with Sage. Discussion follows.
We use the matrix A to illustrate Definition RSM, and the matrix B to illustrate Theorem CSRST. A and B were designed to have the same reduced row-echelon form, and hence be row-equivalent, so this is not a consequence of any theorem or previous computation. However, then Theorem REMRS guarantees that the row spaces of A and B are equal.
Reading Questions CRS Reading Questions
1.
Write the column space of the matrix below as the span of a set of three vectors and explain your choice of method.
2.
Suppose that \(A\) is an \(n\times n\) nonsingular matrix. What can you say about its column space?
3.
Is the vector \(\colvector{0\\5\\2\\3}\) in the row space of the following matrix? Why or why not?
Exercises CRS Exercises
C20.
For each matrix below, find a set of linearly independent vectors \(X\) so that \(\spn{X}\) equals the column space of the matrix, and a set of linearly independent vectors \(Y\) so that \(\spn{Y}\) equals the row space of the matrix.
From your results for these three matrices, can you formulate a conjecture about the sets \(X\) and \(Y\text{?}\)
C30.
Example CSOCD expresses the column space of the coefficient matrix from Archetype D (call the matrix \(A\) here) as the span of the first two columns of \(A\text{.}\) In Example CSMCS we determined that the vector
was not in the column space of \(A\) and that the vector
was in the column space of \(A\text{.}\) Attempt to write \(\vect{c}\) and \(\vect{b}\) as linear combinations of the two vectors in the span construction for the column space in Example CSOCD and record your observations.
In each case, begin with a vector equation where one side contains a linear combination of the two vectors from the span construction that gives the column space of \(A\) with unknowns for scalars, and then use Theorem SLSLC to set up a system of equations. For \(\vect{c}\text{,}\) the resulting system has no solution, as we would expect.
For \(\vect{b}\) there is a solution, as we would expect. What is interesting is that the solution is unique. This is a consequence of the linear independence of the set of two vectors in the span construction. If we wrote \(\vect{b}\) as a linear combination of all four columns of \(A\text{,}\) then there would be infinitely many ways to do this.
C31.
For the matrix \(A\) below find a set of vectors \(T\) meeting the following requirements: (1) the span of \(T\) is the column space of \(A\text{,}\) that is, \(\spn{T}=\csp{A}\text{,}\) (2) \(T\) is linearly independent, and (3) the elements of \(T\) are columns of \(A\text{.}\)
Theorem BCS is the right tool for this problem. Row-reduce this matrix, identify the pivot columns and then grab the columns of \(A\) with the same indices for the set \(T\text{.}\) The matrix \(A\) row-reduces to
So \(D=\set{1,\,2,\,4,\,5}\) and then
has the requested properties.
C32.
In Example CSAA, verify that the vector \(\vect{b}\) is not in the column space of the coefficient matrix.
C33.
Find a linearly independent set \(S\) so that the span of \(S\text{,}\) \(\spn{S}\text{,}\) is row space of the matrix \(B\text{,}\) and \(S\) is linearly independent.
Theorem BRS is the most direct route to a set with these properties. Row-reduce, toss zero rows, keep the others. You could also transpose the matrix, then look for the column space by row-reducing the transpose and applying Theorem BCS. We will do the former,
So the set \(S\) is
C34.
For the \(3\times 4\) matrix \(A\) and the column vector \(\vect{y}\in\complex{4}\) given below, determine if \(\vect{y}\) is in the row space of \(A\text{.}\) In other words, answer the question: \(\vect{y}\in\rsp{A}\text{?}\)
The augmented matrix \(\augmented{\transpose{A}}{\vect{y}}\) row reduces to
and since the final column is a pivot column Theorem RCLS tells us the linear system is inconsistent and so \(\vect{y}\not\in\rsp{A}\text{.}\)
C35.
For the matrix \(A\) below, find two different linearly independent sets whose spans equal the column space of \(A\text{,}\) \(\csp{A}\text{,}\) such that
- the elements are each columns of \(A\text{.}\)
- the set is obtained by a procedure that is substantially different from the procedure you use in part (1).
(a) By Theorem BCS we can row-reduce \(A\text{,}\) identify pivot columns with the set \(D\text{,}\) and “keep” those columns of \(A\) and we will have a set with the desired properties.
So we have the set of pivot columns \(D=\set{1,\,2}\) and we “keep” the first two columns of \(A\text{,}\)
(b) We can view the column space as the row space of the transpose (Theorem CSRST). We can get a basis of the row space of a matrix quickly by bringing the matrix to reduced row-echelon form and keeping the nonzero rows as column vectors (Theorem BRS). Here goes.
Taking the nonzero rows and tilting them up as columns gives us
An approach based on the matrix \(L\) from extended echelon form (Definition EEF) and Theorem FS will work as well as an alternative approach.
C40.
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 BCS (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
C42.
The following archetypes are either matrices or systems of equations with coefficient matrices. For each matrix, compute a set of column vectors such that (1) the vectors are columns of the matrix, (2) the set is linearly independent, and (3) the span of the set is the column space of the matrix. See Theorem BCS.
Archetype A, Archetype B, Archetype C, Archetype D/Archetype E, Archetype F, Archetype G/Archetype H, Archetype I, Archetype J, Archetype K, Archetype L
C50.
The following archetypes are either matrices or systems of equations with coefficient matrices. For each matrix, compute a set of column vectors such that (1) the set is linearly independent, and (2) the span of the set is the row space of the matrix. See Theorem BRS.
Archetype A, Archetype B, Archetype C, Archetype D/Archetype E, Archetype F, Archetype G/Archetype H, Archetype I, Archetype J, Archetype K, Archetype L
C51.
The following archetypes are either matrices or systems of equations with coefficient matrices. For each matrix, compute the column space as the span of a linearly independent set as follows: transpose the matrix, row-reduce, toss out zero rows, convert rows into column vectors. See Example CSROI.
Archetype A, Archetype B, Archetype C, Archetype D/Archetype E, Archetype F, Archetype G/Archetype H, Archetype I, Archetype J, Archetype K, Archetype L
C52.
The following archetypes are systems of equations. For each different coefficient matrix build two new vectors of constants. The first should lead to a consistent system and the second should lead to an inconsistent system. Descriptions of the column space as spans of linearly independent sets of vectors with “nice patterns” of zeros and ones might be most useful and instructive in connection with this exercise. (See the end of Example CSROI.)
Archetype A, Archetype B, Archetype C, Archetype D/Archetype E, Archetype F, Archetype G/Archetype H, Archetype I, Archetype J
M10.
For the matrix \(E\) below, find vectors \(\vect{b}\) and \(\vect{c}\) so that the system \(\linearsystem{E}{\vect{b}}\) is consistent and \(\linearsystem{E}{\vect{c}}\) is inconsistent.
Any vector from \(\complex{3}\) will lead to a consistent system, and therefore there is no vector that will lead to an inconsistent system.
How do we convince ourselves of this? First, row-reduce \(E\text{,}\)
If we augment \(E\) with any vector of constants, and row-reduce the augmented matrix, we will never find a pivot column in the final column, so by Theorem RCLS the system will always be consistent.
Said another way, the column space of \(E\) is all of \(\complex{3}\text{,}\) \(\csp{E}=\complex{3}\text{.}\) So by Theorem CSCS any vector of constants will create a consistent system (and none will create an inconsistent system).
M20.
Usually the column space and null space of a matrix contain vectors of different sizes. For a square matrix, though, the vectors in these two sets are the same size. Usually the two sets will be different. Construct an example of a square matrix where the column space and null space are equal.
The \(2\times 2\) matrix
has \(\csp{A}=\nsp{A}=\spn{\set{\colvector{1\\-1}}}\text{.}\)
M21.
We have a variety of theorems about how to create column spaces and row spaces and they frequently involve row-reducing a matrix. Here is a procedure that some try to use to get a column space. Begin with an \(m\times n\) matrix \(A\) and row-reduce to a matrix \(B\) with columns \(\vectorlist{B}{n}\text{.}\) Then form the column space of \(A\) as
This is not not a legitimate procedure, and therefore is not a theorem. Construct an example to show that the procedure will not in general create the column space of \(A\text{.}\)
Begin with a matrix \(A\) (of any size) that does not have any zero rows, but which when row-reduced to \(B\) yields at least one row of zeros. Such a matrix should be easy to construct (or find, like say from Archetype A).
\(\csp{A}\) will contain some vectors whose final slot (entry \(m\)) is nonzero, however, every column vector from the matrix \(B\) will have a zero in slot \(m\) and so every vector in \(\csp{B}\) will also contain a zero in the final slot. This means that \(\csp{A}\neq\csp{B}\text{,}\) since we have vectors in \(\csp{A}\) that cannot be elements of \(\csp{B}\text{.}\)
T40.
Suppose that \(A\) is an \(m\times n\) matrix and \(B\) is an \(n\times p\) matrix. Prove that the column space of \(AB\) is a subset of the column space of \(A\text{,}\) that is \(\csp{AB}\subseteq\csp{A}\text{.}\) Provide an example where the opposite is false, in other words give an example where \(\csp{A}\not\subseteq\csp{AB}\text{.}\) (Compare with Exercise MM.T40.)
Choose \(\vect{x}\in\csp{AB}\text{.}\) Then by Theorem CSCS there is a vector \(\vect{w}\) that is a solution to \(\linearsystem{AB}{\vect{x}}\text{.}\) Define the vector \(\vect{y}\) by \(\vect{y}=B\vect{w}\text{.}\) We are set.
This says that \(\linearsystem{A}{\vect{x}}\) is a consistent system, and by Theorem CSCS, we see that \(\vect{x}\in\csp{A}\) and therefore \(\csp{AB}\subseteq\csp{A}\text{.}\)
For an example where \(\csp{A}\not\subseteq\csp{AB}\) choose \(A\) to be any nonzero matrix and choose \(B\) to be a zero matrix. Then \(\csp{A}\neq\set{\zerovector}\) and \(\csp{AB}=\csp{\zeromatrix}=\set{\zerovector}\text{.}\)
T41.
Suppose that \(A\) is an \(m\times n\) matrix and \(B\) is an \(n\times n\) nonsingular matrix. Prove that the column space of \(A\) is equal to the column space of \(AB\text{,}\) that is \(\csp{A}=\csp{AB}\text{.}\) (Compare with Exercise MM.T41 and Exercise CRS.T40.)
From the solution to Exercise CRS.T40 we know that \(\csp{AB}\subseteq\csp{A}\text{.}\) So to establish the set equality (Definition SE) we need to show that \(\csp{A}\subseteq\csp{AB}\text{.}\)
Choose \(\vect{x}\in\csp{A}\text{.}\) By Theorem CSCS the linear system \(\linearsystem{A}{\vect{x}}\) is consistent, so let \(\vect{y}\) be one such solution. Because \(B\) is nonsingular, and linear system using \(B\) as a coefficient matrix will have a solution (Theorem NMUS). Let \(\vect{w}\) be the unique solution to the linear system \(\linearsystem{B}{\vect{y}}\text{.}\) All set, here we go,
This says that the linear system \(\linearsystem{AB}{\vect{x}}\) is consistent, so by Theorem CSCS, \(\vect{x}\in\csp{AB}\text{.}\) So \(\csp{A}\subseteq\csp{AB}\text{.}\)
T45.
Suppose that \(A\) is an \(m\times n\) matrix and \(B\) is an \(n\times m\) matrix where \(AB\) is a nonsingular matrix. Prove that
- \(\displaystyle \nsp{B}=\set{\zerovector}\)
- \(\displaystyle \csp{B}\cap\nsp{A}=\set{\zerovector}\)
Discuss the case when \(m=n\) in connection with Theorem NPNF.
First, \(\zerovector\in\nsp{B}\) trivially. Now suppose that \(\vect{x}\in\nsp{B}\text{.}\) Then
Since we have assumed \(AB\) is nonsingular, Definition NM implies that \(\vect{x}=\zerovector\text{.}\)
Second, \(\zerovector\in\csp{B}\) and \(\zerovector\in\nsp{A}\) trivially, and so the zero vector is in the intersection as well (Definition SI). Now suppose that \(\vect{y}\in\csp{B}\cap\nsp{A}\text{.}\) Because \(\vect{y}\in\csp{B}\text{,}\) Theorem CSCS says the system \(\linearsystem{B}{\vect{y}}\) is consistent. Let \(\vect{x}\in\complex{n}\) be one solution to this system. Then
Since we have assumed \(AB\) is nonsingular, Definition NM implies that \(\vect{x}=\zerovector\text{.}\) Then \(\vect{y}=B\vect{x}=B\zerovector=\zerovector\text{.}\)
When \(AB\) is nonsingular and \(m=n\) we know that the first condition, \(\nsp{B}=\set{\zerovector}\text{,}\) means that \(B\) is nonsingular (Theorem NMTNS). Because \(B\) is nonsingular Theorem CSNM implies that \(\csp{B}=\complex{m}\text{.}\) In order to have the second condition fulfilled, \(\csp{B}\cap\nsp{A}=\set{\zerovector}\text{,}\) we must realize that \(\nsp{A}=\set{\zerovector}\text{.}\) However, a second application of Theorem NMTNS shows that \(A\) must be nonsingular. This reproduces Theorem NPNF.