Section CRS  Column and Row Spaces

From A First Course in Linear Algebra
Version 2.22
© 2004.
Licensed under the GNU Free Documentation License.
http://linear.ups.edu/

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 × n matrix with columns \left \{{A}_{1},\kern 1.95872pt {A}_{2},\kern 1.95872pt {A}_{3},\kern 1.95872pt \mathop{\mathop{…}},\kern 1.95872pt {A}_{n}\right \}. Then the column space of A, written C\kern -1.95872pt \left (A\right ), is the subset of {ℂ}^{m} containing all linear combinations of the columns of A,

C\kern -1.95872pt \left (A\right ) = \left \langle \left \{{A}_{1},\kern 1.95872pt {A}_{2},\kern 1.95872pt {A}_{3},\kern 1.95872pt \mathop{\mathop{…}},\kern 1.95872pt {A}_{n}\right \}\right \rangle

(This definition contains Notation CSM.)

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).

Subsection CSSE: Column Spaces and Systems of Equations

Upon encountering any new set, the first question we ask is what objects are in the set, and which objects are not? Here’s 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 × 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.

The column vector of constants, b, in Archetype D is

b = \left [\array{ 8\cr −12 \cr 4 } \right ]

One solution to ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ), as listed, is

x = \left [\array{ 7\cr 8 \cr 1\cr 3 } \right ]

By Theorem SLSLC, we can summarize this solution as a linear combination of the columns of A that equals b,

7\left [\array{ 2\cr −3 \cr 1 } \right ]+8\left [\array{ 1\cr 4 \cr 1 } \right ]+1\left [\array{ 7\cr −5 \cr 4 } \right ]+3\left [\array{ −7\cr −6 \cr −5 } \right ] = \left [\array{ 8\cr −12 \cr 4 } \right ] = b.

This equation says that b is a linear combination of the columns of A, and then by Definition CSM, we can say that b ∈C\kern -1.95872pt \left (A\right ).

On the other hand, Archetype E is the linear system ℒS\kern -1.95872pt \left (A,\kern 1.95872pt c\right ), where the vector of constants is

c = \left [\array{ 2\cr 3 \cr 2 } \right ]

and this system of equations is inconsistent. This means c∉C\kern -1.95872pt \left (A\right ), 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 ℒS\kern -1.95872pt \left (A,\kern 1.95872pt c\right ).

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 × n matrix and b is a vector of size m. Then b ∈C\kern -1.95872pt \left (A\right ) if and only if ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ) is consistent.

Proof   () Suppose b ∈C\kern -1.95872pt \left (A\right ). Then we can write b as some linear combination of the columns of A. By Theorem SLSLC we can use the scalars from this linear combination to form a solution to ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ), so this system is consistent.

() If ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ) is consistent, there is a solution that may be used with Theorem SLSLC to write b as a linear combination of the columns of A. This qualifies b for membership in C\kern -1.95872pt \left (A\right ).

This theorem tells us that asking if the system ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ) is consistent is exactly the same question as asking if b is in the column space of A. Or equivalently, it tells us that the column space of the matrix A is precisely those vectors of constants, b, that can be paired with A to create a system of linear equations ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ) that is consistent.

Employing Theorem SLEMM we can form the chain of equivalences

\eqalignno{ b ∈C\kern -1.95872pt \left (A\right )\kern 3.26288pt \mathrel{⇔}\kern 3.26288pt ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right )\text{ is consistent}\kern 3.26288pt \mathrel{⇔}\kern 3.26288pt Ax = b\text{ for some }x & & }

Thus, an alternative (and popular) definition of the column space of an m × n matrix A is

\eqalignno{ C\kern -1.95872pt \left (A\right ) & = \left \{\left .y ∈ {ℂ}^{m}\right \vert y = Ax\text{ for some }x ∈ {ℂ}^{n}\right \} = \left \{\left .Ax\right \vert x ∈ {ℂ}^{n}\right \} ⊆ {ℂ}^{m} & & }

We recognize this as saying create all the matrix vector products possible with the matrix A by letting 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 C\kern -1.95872pt \left (A\right ) and N\kern -1.95872pt \left (A\right ) have different sizes, so the sets are very different.

Given a vector b and a matrix A it is now very mechanical to test if b ∈C\kern -1.95872pt \left (A\right ). Form the linear system ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ), row-reduce the augmented matrix, \left [\left .A\kern 1.95872pt \right \vert \kern 1.95872pt b\right ], and test for consistency with Theorem RCLS. Here’s an example of this procedure.

Example MCSM
Membership in the column space of a matrix
Consider the column space of the 3 × 4 matrix A,

A = \left [\array{ 3 & 2 & 1 &−4\cr −1 & 1 &−2 & 3 \cr 2 &−4& 6 &−8 } \right ]

We first show that v = \left [\array{ 18\cr −6 \cr 12 } \right ] is in the column space of A, v ∈C\kern -1.95872pt \left (A\right ). Theorem CSCS says we need only check the consistency of ℒS\kern -1.95872pt \left (A,\kern 1.95872pt v\right ). Form the augmented matrix and row-reduce,

\left [\array{ 3 & 2 & 1 &−4&18\cr −1 & 1 &−2 & 3 &−6 \cr 2 &−4& 6 &−8&12 } \right ]\mathop{\longrightarrow}\limits_{}^{\text{RREF}}\left [\array{ \text{1}&0& 1 &−2&6\cr 0&\text{1 } &−1 & 1 &0 \cr 0&0& 0 & 0 &0 } \right ]

Without a leading 1 in the final column, Theorem RCLS tells us the system is consistent and therefore by Theorem CSCS, v ∈C\kern -1.95872pt \left (A\right ).

If we wished to demonstrate explicitly that v is a linear combination of the columns of A, we can find a solution (any solution) of ℒS\kern -1.95872pt \left (A,\kern 1.95872pt v\right ) and use Theorem SLSLC to construct the desired linear combination. For example, set the free variables to {x}_{3} = 2 and {x}_{4} = 1. Then a solution has {x}_{2} = 1 and {x}_{1} = 6. Then by Theorem SLSLC,

v = \left [\array{ 18\cr −6 \cr 12 } \right ] = 6\left [\array{ 3\cr −1 \cr 2 } \right ]+1\left [\array{ 2\cr 1 \cr −4 } \right ]+2\left [\array{ 1\cr −2 \cr 6 } \right ]+1\left [\array{ −4\cr 3 \cr −8 } \right ]

Now we show that w = \left [\array{ 2\cr 1 \cr −3 } \right ] is not in the column space of A, w∉C\kern -1.95872pt \left (A\right ). Theorem CSCS says we need only check the consistency of ℒS\kern -1.95872pt \left (A,\kern 1.95872pt w\right ). Form the augmented matrix and row-reduce,

\left [\array{ 3 & 2 & 1 &−4& 2\cr −1 & 1 &−2 & 3 & 1 \cr 2 &−4& 6 &−8&−3 } \right ]\mathop{\longrightarrow}\limits_{}^{\text{RREF}}\left [\array{ \text{1}&0& 1 &−2&0\cr 0&\text{1 } &−1 & 1 &0 \cr 0&0& 0 & 0 &\text{1} } \right ]

With a leading 1 in the final column, Theorem RCLS tells us the system is inconsistent and therefore by Theorem CSCS, w∉C\kern -1.95872pt \left (A\right ).

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 for definitions and theorems along with a brief reminder of the statement and an example of how the statement is used.







SynopsisNull space is solution set of homogeneous system


ExampleGeneral solution sets described by Theorem PSPHS






SynopsisSolutions for linear combinations with unknown scalars


ExampleDeciding membership in spans






SynopsisSystem of equations represented by matrix-vector product


ExampleSolution to ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ) is {A}^{−1}b when A is nonsingular






SynopsisColumn space vectors create consistent systems


ExampleDeciding membership in column spaces




Subsection CSSOC: Column Space Spanned by Original Columns

So we have a foolproof, automated procedure for determining membership in C\kern -1.95872pt \left (A\right ). While this works just fine a vector at a time, we would like to have a more useful description of the set C\kern -1.95872pt \left (A\right ) 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 × 7 matrix A,

\left [\array{ 2 & 4 & 1 &−1& 1 & 4 & 4\cr 1 & 2 & 1 & 0 & 2 & 4 & 7 \cr 0 & 0 & 1 & 4 & 1 & 8 & 7\cr 1 & 2 &−1 & 2 & 1 & 9 & 6 \cr −2&−4& 1 & 3 &−1&−2&−2 } \right ]

According to the definition (Definition CSM), the column space of A is

C\kern -1.95872pt \left (A\right ) = \left \langle \left \{\left [\array{ 2\cr 1 \cr 0\cr 1 \cr −2 } \right ],\kern 1.95872pt \left [\array{ 4\cr 2 \cr 0\cr 2 \cr −4 } \right ],\kern 1.95872pt \left [\array{ 1\cr 1 \cr 1\cr −1 \cr 1 } \right ],\kern 1.95872pt \left [\array{ −1\cr 0 \cr 4\cr 2 \cr 3 } \right ],\kern 1.95872pt \left [\array{ 1\cr 2 \cr 1\cr 1 \cr −1 } \right ],\kern 1.95872pt \left [\array{ 4\cr 4 \cr 8\cr 9 \cr −2 } \right ],\kern 1.95872pt \left [\array{ 4\cr 7 \cr 7\cr 6 \cr −2 } \right ]\right \}\right \rangle

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 matrix, which is simply the original matrix A again. Now we row-reduce,

\left [\array{ 2 & 4 & 1 &−1& 1 & 4 & 4\cr 1 & 2 & 1 & 0 & 2 & 4 & 7 \cr 0 & 0 & 1 & 4 & 1 & 8 & 7\cr 1 & 2 &−1 & 2 & 1 & 9 & 6 \cr −2&−4& 1 & 3 &−1&−2&−2 } \right ]\mathop{\longrightarrow}\limits_{}^{\text{RREF}}\left [\array{ \text{1}&2&0&0&0& 3 &1\cr 0&0 &\text{1 } &0 &0 &−1 &0 \cr 0&0&0&\text{1}&0& 2 &1\cr 0&0 &0 &0 &\text{1 } & 1 &3 \cr 0&0&0&0&0& 0 &0 } \right ]

The pivot columns are D = \left \{1,\kern 1.95872pt 3,\kern 1.95872pt 4,\kern 1.95872pt 5\right \}, so we can create the set

T = \left \{\left [\array{ 2\cr 1 \cr 0\cr 1 \cr −2 } \right ],\kern 1.95872pt \left [\array{ 1\cr 1 \cr 1\cr −1 \cr 1 } \right ],\kern 1.95872pt \left [\array{ −1\cr 0 \cr 4\cr 2 \cr 3 } \right ],\kern 1.95872pt \left [\array{ 1\cr 2 \cr 1\cr 1 \cr −1 } \right ]\right \}

and know that C\kern -1.95872pt \left (A\right ) = \left \langle T\right \rangle and T is a linearly independent set of columns from the set of columns of A.

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.

Theorem BCS
Basis of the Column Space
Suppose that A is an m × n matrix with columns {A}_{1},\kern 1.95872pt {A}_{2},\kern 1.95872pt {A}_{3},\kern 1.95872pt \mathop{\mathop{…}},\kern 1.95872pt {A}_{n}, and B is a row-equivalent matrix in reduced row-echelon form with r nonzero rows. Let D = \{{d}_{1},\kern 1.95872pt {d}_{2},\kern 1.95872pt {d}_{3},\kern 1.95872pt \mathop{\mathop{…}},\kern 1.95872pt {d}_{r}\} be the set of column indices where B has leading 1’s. Let T = \left \{{A}_{{d}_{1}},\kern 1.95872pt {A}_{{d}_{2}},\kern 1.95872pt {A}_{{d}_{3}},\kern 1.95872pt \mathop{\mathop{…}},\kern 1.95872pt {A}_{{d}_{r}}\right \}. Then

  1. T is a linearly independent set.
  2. C\kern -1.95872pt \left (A\right ) = \left \langle T\right \rangle .

Proof   Definition CSM describes the column space as the span of the set of columns of A. Theorem BS tells us that we can reduce the set of vectors used in a span. If we apply Theorem BS to C\kern -1.95872pt \left (A\right ), 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, B and C\kern -1.95872pt \left (A\right ) 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 S are still columns of the matrix (we won’t 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 r columns with leading 1’s in this reduced matrix, and grab the corresponding columns of the original matrix. 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’ll trot through an example all the same.

Example CSOCD
Column space, original columns, Archetype D
Let’s 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

A = \left [\array{ 2 &1& 7 &−7\cr −3 &4 &−5 &−6 \cr 1 &1& 4 &−5 } \right ].

and row-reduce it to reduced row-echelon form,

B = \left [\array{ \text{1}&0&3&−2\cr 0&\text{1 } &1 &−3 \cr 0&0&0& 0 } \right ].

There are leading 1’s in columns 1 and 2, so D = \{1,\kern 1.95872pt 2\}. To construct a set that spans C\kern -1.95872pt \left (A\right ), just grab the columns of A indicated by the set D, so

C\kern -1.95872pt \left (A\right ) = \left \langle \left \{\left [\array{ 2\cr −3 \cr 1 } \right ],\kern 1.95872pt \left [\array{ 1\cr 4 \cr 1 } \right ]\right \}\right \rangle .

That’s it.

In Example CSMCS we determined that the vector

c = \left [\array{ 2\cr 3 \cr 2 } \right ]

was not in the column space of A. Try to write c as a linear combination of the first two columns of A. What happens?

Also in Example CSMCS we determined that the vector

b = \left [\array{ 8\cr −12 \cr 4 } \right ]

was in the column space of A. Try to write b as a linear combination of the first two columns of A. What happens? Did you find a unique solution to this question? Hmmmm.

Subsection CSNM: Column Space of a Nonsingular Matrix

Let’s 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 = \left [\array{ 1&−1&2\cr 2& 1 &1 \cr 1& 1 &0 } \right ]

which row-reduces to

\left [\array{ \text{1}&0& 1\cr 0&\text{1 } &−1 \cr 0&0& 0 } \right ].

Columns 1 and 2 have leading 1’s, so by Theorem BCS we can write

C\kern -1.95872pt \left (A\right ) = \left \langle \left \{{A}_{1},\kern 1.95872pt {A}_{2}\right \}\right \rangle = \left \langle \left \{\left [\array{ 1\cr 2 \cr 1 } \right ],\kern 1.95872pt \left [\array{ −1\cr 1 \cr 1 } \right ]\right \}\right \rangle .

We want to show in this example that C\kern -1.95872pt \left (A\right )\mathrel{≠}{ℂ}^{3}. So take, for example, the vector b = \left [\array{ 1\cr 3 \cr 2 } \right ]. Thenthere is no solution to the system ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ), or equivalently, it is not possible to write b as a linear combination of {A}_{1} and {A}_{2}. Try one of these two computations yourself. (Or try both!). Since b∉C\kern -1.95872pt \left (A\right ), the column space of A cannot be all of {ℂ}^{3}. So by varying the vector of constants, it is possible to create inconsistent systems of equations with this coefficient matrix (the vector 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 b, deliberately chosen outside the column space of A.

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 ℒS\kern -1.95872pt \left (B,\kern 1.95872pt b\right ) has a (unique) solution for every choice of b. Theorem CSCS then says that b ∈C\kern -1.95872pt \left (B\right ) for all b ∈ {ℂ}^{3}. Stated differently, there is no way to build an inconsistent system with the coefficient matrix B, 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. Then A is nonsingular if and only if C\kern -1.95872pt \left (A\right ) = {ℂ}^{n}.

Proof   () Suppose A is nonsingular. We wish to establish the set equality C\kern -1.95872pt \left (A\right ) = {ℂ}^{n}. By Definition CSM, C\kern -1.95872pt \left (A\right ) ⊆ {ℂ}^{n}.

To show that {ℂ}^{n} ⊆C\kern -1.95872pt \left (A\right ) choose b ∈ {ℂ}^{n}. By Theorem NMUS, we know the linear system ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ) has a (unique) solution and therefore is consistent. Theorem CSCS then says that b ∈C\kern -1.95872pt \left (A\right ). So by Definition SE, C\kern -1.95872pt \left (A\right ) = {ℂ}^{n}.

() If {e}_{i} is column i of the n × n identity matrix (Definition SUV) and by hypothesis C\kern -1.95872pt \left (A\right ) = {ℂ}^{n}, then {e}_{i} ∈C\kern -1.95872pt \left (A\right ) for 1 ≤ i ≤ n. By Theorem CSCS, the system ℒS\kern -1.95872pt \left (A,\kern 1.95872pt {e}_{i}\right ) is consistent for 1 ≤ i ≤ n. Let {b}_{i} denote any one particular solution to ℒS\kern -1.95872pt \left (A,\kern 1.95872pt {e}_{i}\right ), 1 ≤ i ≤ n.

Define the n × n matrix B = \left [{b}_{1}|{b}_{2}|{b}_{3}|\mathop{\mathop{…}}|{b}_{n}\right ]. Then

\eqalignno{ AB & = A\left [{b}_{1}|{b}_{2}|{b}_{3}|\mathop{\mathop{…}}|{b}_{n}\right ] & & & & \cr & = [A{b}_{1}|A{b}_{2}|A{b}_{3}|\mathop{\mathop{…}}|A{b}_{n}] & &\text{@(a href="fcla-jsmath-2.22li31.html#definition.MM")Definition MM@(/a)} & & & & \cr & = \left [{e}_{1}|{e}_{2}|{e}_{3}|\mathop{\mathop{…}}|{e}_{n}\right ] & & & & \cr & = {I}_{n} & &\text{@(a href="fcla-jsmath-2.22li28.html#definition.SUV")Definition SUV@(/a)} & & & & \cr & & & & }

So the matrix B is a “right-inverse” for A. By Theorem NMRRI, {I}_{n} is a nonsingular matrix, so by Theorem NPNT 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. The following are equivalent.

  1. A is nonsingular.
  2. A row-reduces to the identity matrix.
  3. The null space of A contains only the zero vector, N\kern -1.95872pt \left (A\right ) = \left \{0\right \}.
  4. The linear system ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ) has a unique solution for every possible choice of b.
  5. The columns of A are a linearly independent set.
  6. A is invertible.
  7. The column space of A is {ℂ}^{n}, C\kern -1.95872pt \left (A\right ) = {ℂ}^{n}.

Proof   Since Theorem CSNM is an equivalence, we can add it to the list in Theorem NME3.

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 × n matrix. Then the row space of A, ℛ\kern -1.95872pt \left (A\right ), is the column space of {A}^{t}, i.e. ℛ\kern -1.95872pt \left (A\right ) = C\kern -1.95872pt \left ({A}^{t}\right ).

(This definition contains Notation RSM.)

Informally, the row space is the set of all linear combinations of the rows of A. 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 × n matrix, then C\kern -1.95872pt \left (A\right ) ⊆ {ℂ}^{m}, while ℛ\kern -1.95872pt \left (A\right ) ⊆ {ℂ}^{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, both C\kern -1.95872pt \left (A\right ) and ℛ\kern -1.95872pt \left (A\right ) are subsets of {ℂ}^{n}, 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

I = \left [\array{ 1 & 4 & 0 &−1& 0 & 7 &−9\cr 2 & 8 &−1 & 3 & 9 &−13 & 7 \cr 0 & 0 & 2 &−3&−4& 12 &−8\cr −1 &−4 & 2 & 4 & 8 &−31 & 37 } \right ].

To build the row space, we transpose the matrix,

{ I}^{t} = \left [\array{ 1 & 2 & 0 & −1\cr 4 & 8 & 0 & −4 \cr 0 & −1 & 2 & 2\cr −1 & 3 &−3 & 4 \cr 0 & 9 &−4& 8\cr 7 &−13 & 12 &−31 \cr −9& 7 &−8& 37 } \right ]

Then the columns of this matrix are used in a span to build the row space,

ℛ\kern -1.95872pt \left (I\right ) = C\kern -1.95872pt \left ({I}^{t}\right ) = \left \langle \left \{\left [\array{ 1\cr 4 \cr 0\cr −1 \cr 0\cr 7 \cr −9 } \right ],\kern 1.95872pt \left [\array{ 2\cr 8 \cr −1\cr 3 \cr 9\cr −13 \cr 7 } \right ],\kern 1.95872pt \left [\array{ 0\cr 0 \cr 2\cr −3 \cr −4\cr 12 \cr −8 } \right ],\kern 1.95872pt \left [\array{ −1\cr −4 \cr 2\cr 4 \cr 8\cr −31 \cr 37} \right ]\right \}\right \rangle .

However, we can use Theorem BCS to get a slightly better description. First, row-reduce {I}^{t},

\left [\array{ \text{1}&0&0&−{31\over 7} \cr 0&\text{1}&0& {12\over 7} \cr 0&0&\text{1}& {13\over 7} \cr 0&0&0& 0\cr 0&0 &0 & 0 \cr 0&0&0& 0\cr 0&0 &0 & 0 } \right ].

Since there are leading 1’s in columns with indices D = \left \{1,\kern 1.95872pt 2,\kern 1.95872pt 3\right \}, the column space of {I}^{t} can be spanned by just the first three columns of {I}^{t},

ℛ\kern -1.95872pt \left (I\right ) = C\kern -1.95872pt \left ({I}^{t}\right ) = \left \langle \left \{\left [\array{ 1\cr 4 \cr 0\cr −1 \cr 0\cr 7 \cr −9 } \right ],\kern 1.95872pt \left [\array{ 2\cr 8 \cr −1\cr 3 \cr 9\cr −13 \cr 7 } \right ],\kern 1.95872pt \left [\array{ 0\cr 0 \cr 2\cr −3 \cr −4\cr 12 \cr −8 } \right ]\right \}\right \rangle .

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 ℛ\kern -1.95872pt \left (A\right ) = ℛ\kern -1.95872pt \left (B\right ).

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 {A}^{t} and {B}^{t} as {A}_{i} and {B}_{i}, 1 ≤ i ≤ m. 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 {B}^{t} is formed from {A}^{t} by multiplying column {A}_{t} by α\mathrel{≠}0. In other words, {B}_{t} = α{A}_{t}, and {B}_{i} = {A}_{i} for all i\mathrel{≠}t. We need to establish that two sets are equal, C\kern -1.95872pt \left ({A}^{t}\right ) = C\kern -1.95872pt \left ({B}^{t}\right ). We will take a generic element of one and show that it is contained in the other.

\eqalignno{ {β}_{1}{B}_{1}+ &{β}_{2}{B}_{2} + {β}_{3}{B}_{3} + \mathrel{⋯} + {β}_{t}{B}_{t} + \mathrel{⋯} + {β}_{m}{B}_{m} & & \cr & = {β}_{1}{A}_{1} + {β}_{2}{A}_{2} + {β}_{3}{A}_{3} + \mathrel{⋯} + {β}_{t}\left (α{A}_{t}\right ) + \mathrel{⋯} + {β}_{m}{A}_{m} & & \cr & = {β}_{1}{A}_{1} + {β}_{2}{A}_{2} + {β}_{3}{A}_{3} + \mathrel{⋯} + \left (α{β}_{t}\right ){A}_{t} + \mathrel{⋯} + {β}_{m}{A}_{m} & & }

says that C\kern -1.95872pt \left ({B}^{t}\right ) ⊆C\kern -1.95872pt \left ({A}^{t}\right ). Similarly,

\eqalignno{ {γ}_{1}{A}_{1}+ &{γ}_{2}{A}_{2} + {γ}_{3}{A}_{3} + \mathrel{⋯} + {γ}_{t}{A}_{t} + \mathrel{⋯} + {γ}_{m}{A}_{m} & & \cr & = {γ}_{1}{A}_{1} + {γ}_{2}{A}_{2} + {γ}_{3}{A}_{3} + \mathrel{⋯} + \left ({{γ}_{t}\over α} α\right ){A}_{t} + \mathrel{⋯} + {γ}_{m}{A}_{m} & & \cr & = {γ}_{1}{A}_{1} + {γ}_{2}{A}_{2} + {γ}_{3}{A}_{3} + \mathrel{⋯} + {{γ}_{t}\over α} \left (α{A}_{t}\right ) + \mathrel{⋯} + {γ}_{m}{A}_{m} & & \cr & = {γ}_{1}{B}_{1} + {γ}_{2}{B}_{2} + {γ}_{3}{B}_{3} + \mathrel{⋯} + {{γ}_{t}\over α} {B}_{t} + \mathrel{⋯} + {γ}_{m}{B}_{m} & & }

says that C\kern -1.95872pt \left ({A}^{t}\right ) ⊆C\kern -1.95872pt \left ({B}^{t}\right ). So ℛ\kern -1.95872pt \left (A\right ) = C\kern -1.95872pt \left ({A}^{t}\right ) = C\kern -1.95872pt \left ({B}^{t}\right ) = ℛ\kern -1.95872pt \left (B\right ) when a single row operation of the second type is performed.

Suppose now that {B}^{t} is formed from {A}^{t} by replacing {A}_{t} with α{A}_{s} + {A}_{t} for some α ∈ {ℂ}^{} and s\mathrel{≠}t. In other words, {B}_{t} = α{A}_{s} + {A}_{t}, and {B}_{i} = {A}_{i} for i\mathrel{≠}t.

\eqalignno{ {β}_{1}{B}_{1}+&{β}_{2}{B}_{2} + {β}_{3}{B}_{3} + \mathrel{⋯} + {β}_{s}{B}_{s} + \mathrel{⋯} + {β}_{t}{B}_{t} + \mathrel{⋯} + {β}_{m}{B}_{m} && \cr & = {β}_{1}{A}_{1} + {β}_{2}{A}_{2} + {β}_{3}{A}_{3} + \mathrel{⋯} + {β}_{s}{A}_{s} + \mathrel{⋯} + {β}_{t}\left (α{A}_{s} + {A}_{t}\right ) + \mathrel{⋯} + {β}_{m}{A}_{m} && \cr & = {β}_{1}{A}_{1} + {β}_{2}{A}_{2} + {β}_{3}{A}_{3} + \mathrel{⋯} + {β}_{s}{A}_{s} + \mathrel{⋯} + \left ({β}_{t}α\right ){A}_{s} + {β}_{t}{A}_{t} + \mathrel{⋯} + {β}_{m}{A}_{m}&& \cr & = {β}_{1}{A}_{1} + {β}_{2}{A}_{2} + {β}_{3}{A}_{3} + \mathrel{⋯} + {β}_{s}{A}_{s} + \left ({β}_{t}α\right ){A}_{s} + \mathrel{⋯} + {β}_{t}{A}_{t} + \mathrel{⋯} + {β}_{m}{A}_{m}&& \cr & = {β}_{1}{A}_{1} + {β}_{2}{A}_{2} + {β}_{3}{A}_{3} + \mathrel{⋯} + \left ({β}_{s} + {β}_{t}α\right ){A}_{s} + \mathrel{⋯} + {β}_{t}{A}_{t} + \mathrel{⋯} + {β}_{m}{A}_{m} && }

says that C\kern -1.95872pt \left ({B}^{t}\right ) ⊆C\kern -1.95872pt \left ({A}^{t}\right ). Similarly,

\eqalignno{ {γ}_{1}&{A}_{1} + {γ}_{2}{A}_{2} + {γ}_{3}{A}_{3} + \mathrel{⋯} + {γ}_{s}{A}_{s} + \mathrel{⋯} + {γ}_{t}{A}_{t} + \mathrel{⋯} + {γ}_{m}{A}_{m} && \cr & = {γ}_{1}{A}_{1} + {γ}_{2}{A}_{2} + {γ}_{3}{A}_{3} + \mathrel{⋯} + {γ}_{s}{A}_{s} + \mathrel{⋯} + \left (−α{γ}_{t}{A}_{s} + α{γ}_{t}{A}_{s}\right ) + {γ}_{t}{A}_{t} + \mathrel{⋯} + {γ}_{m}{A}_{m} && \cr & = {γ}_{1}{A}_{1} + {γ}_{2}{A}_{2} + {γ}_{3}{A}_{3} + \mathrel{⋯} + \left (−α{γ}_{t}{A}_{s}\right ) + {γ}_{s}{A}_{s} + \mathrel{⋯} + \left (α{γ}_{t}{A}_{s} + {γ}_{t}{A}_{t}\right ) + \mathrel{⋯} + {γ}_{m}{A}_{m}&& \cr & = {γ}_{1}{A}_{1} + {γ}_{2}{A}_{2} + {γ}_{3}{A}_{3} + \mathrel{⋯} + \left (−α{γ}_{t} + {γ}_{s}\right ){A}_{s} + \mathrel{⋯} + {γ}_{t}\left (α{A}_{s} + {A}_{t}\right ) + \mathrel{⋯} + {γ}_{m}{A}_{m} && \cr & = {γ}_{1}{B}_{1} + {γ}_{2}{B}_{2} + {γ}_{3}{B}_{3} + \mathrel{⋯} + \left (−α{γ}_{t} + {γ}_{s}\right ){B}_{s} + \mathrel{⋯} + {γ}_{t}{B}_{t} + \mathrel{⋯} + {γ}_{m}{B}_{m} && }

says that C\kern -1.95872pt \left ({A}^{t}\right ) ⊆C\kern -1.95872pt \left ({B}^{t}\right ). So ℛ\kern -1.95872pt \left (A\right ) = C\kern -1.95872pt \left ({A}^{t}\right ) = C\kern -1.95872pt \left ({B}^{t}\right ) = ℛ\kern -1.95872pt \left (B\right ) 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

\eqalignno{ A & = \left [\array{ 2&−1& 3 &4\cr 5& 2 &−2 &3 \cr 1& 1 & 0 &6 } \right ] &B & = \left [\array{ 1& 1 & 0 & 6\cr 3& 0 &−2 &−9 \cr 2&−1& 3 & 4 } \right ] & & & & }

are row-equivalent by demonstrating a sequence of two row operations that converted A into B. Applying Theorem REMRS we can say

ℛ\kern -1.95872pt \left (A\right ) = \left \langle \left \{\left [\array{ 2\cr −1 \cr 3\cr 4 } \right ],\kern 1.95872pt \left [\array{ 5\cr 2 \cr −2\cr 3 } \right ],\kern 1.95872pt \left [\array{ 1\cr 1 \cr 0\cr 6 } \right ]\right \}\right \rangle = \left \langle \left \{\left [\array{ 1\cr 1 \cr 0\cr 6 } \right ],\kern 1.95872pt \left [\array{ 3\cr 0 \cr −2\cr −9 } \right ],\kern 1.95872pt \left [\array{ 2\cr −1 \cr 3\cr 4 } \right ]\right \}\right \rangle = ℛ\kern -1.95872pt \left (B\right )

Theorem REMRS is at its best when one of the row-equivalent matrices is in reduced row-echelon form. The vectors that correspond to the 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’s 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 {B}^{t}. Then

  1. ℛ\kern -1.95872pt \left (A\right ) = \left \langle S\right \rangle .
  2. S is a linearly independent set.

Proof   From Theorem REMRS we know that ℛ\kern -1.95872pt \left (A\right ) = ℛ\kern -1.95872pt \left (B\right ). If B has any zero rows, these correspond to columns of {B}^{t} 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 ℛ\kern -1.95872pt \left (A\right ) = \left \langle S\right \rangle .

Suppose B has r nonzero rows and let D = \left \{{d}_{1},\kern 1.95872pt {d}_{2},\kern 1.95872pt {d}_{3},\kern 1.95872pt \mathop{\mathop{…}},\kern 1.95872pt {d}_{r}\right \} denote the column indices of B that have a leading one in them. Denote the r column vectors of {B}^{t}, the vectors in S, as {B}_{1},\kern 1.95872pt {B}_{2},\kern 1.95872pt {B}_{3},\kern 1.95872pt \mathop{\mathop{…}},\kern 1.95872pt {B}_{r}. To show that S is linearly independent, start with a relation of linear dependence

{α}_{1}{B}_{1} + {α}_{2}{B}_{2} + {α}_{3}{B}_{3} + \mathrel{⋯} + {α}_{r}{B}_{r} = 0

Now consider this vector equality in location {d}_{i}. 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. Thus, in {B}^{t}, row {d}_{i} is all zeros, excepting a 1 in column i. So, for 1 ≤ i ≤ r,

\eqalignno{ 0 & ={ \left [0\right ]}_{{d}_{i}} & &\text{@(a href="fcla-jsmath-2.22li18.html#definition.ZCV")Definition ZCV@(/a)} & & & & \cr & ={ \left [{α}_{1}{B}_{1} + {α}_{2}{B}_{2} + {α}_{3}{B}_{3} + \mathrel{⋯} + {α}_{r}{B}_{r}\right ]}_{{d}_{i}} & &\text{@(a href="fcla-jsmath-2.22li26.html#definition.RLDCV")Definition RLDCV@(/a)} & & & & \cr & ={ \left [{α}_{1}{B}_{1}\right ]}_{{d}_{i}} +{ \left [{α}_{2}{B}_{2}\right ]}_{{d}_{i}} +{ \left [{α}_{3}{B}_{3}\right ]}_{{d}_{i}} + \mathrel{⋯} +{ \left [{α}_{r}{B}_{r}\right ]}_{{d}_{i}}+ & &\text{@(a href="fcla-jsmath-2.22li30.html#definition.MA")Definition MA@(/a)} & & & & \cr & = {α}_{1}{\left [{B}_{1}\right ]}_{{d}_{i}} + {α}_{2}{\left [{B}_{2}\right ]}_{{d}_{i}} + {α}_{3}{\left [{B}_{3}\right ]}_{{d}_{i}} + \mathrel{⋯} + {α}_{r}{\left [{B}_{r}\right ]}_{{d}_{i}}+ & &\text{@(a href="fcla-jsmath-2.22li30.html#definition.MSM")Definition MSM@(/a)} & & & & \cr & = {α}_{1}(0) + {α}_{2}(0) + {α}_{3}(0) + \mathrel{⋯} + {α}_{i}(1) + \mathrel{⋯} + {α}_{r}(0) & &\text{@(a href="fcla-jsmath-2.22li18.html#definition.RREF")Definition RREF@(/a)} & & & & \cr & = {α}_{i} & & & & }

So we conclude that {α}_{i} = 0 for all 1 ≤ i ≤ r, 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

X = \left \langle \left \{\left [\array{ 1\cr 2 \cr 1\cr 6 \cr 6 } \right ],\kern 1.95872pt \left [\array{ 3\cr −1 \cr 2\cr −1 \cr 6 } \right ],\kern 1.95872pt \left [\array{ 1\cr −1 \cr 0\cr −1 \cr −2 } \right ],\kern 1.95872pt \left [\array{ −3\cr 2 \cr −3\cr 6 \cr −10 } \right ]\right \}\right \rangle

Let A be the matrix whose rows are the vectors in X, so by design X = ℛ\kern -1.95872pt \left (A\right ),

A = \left [\array{ 1 & 2 & 1 & 6 & 6\cr 3 &−1 & 2 &−1 & 6 \cr 1 &−1& 0 &−1& −2\cr −3 & 2 &−3 & 6 &−10 } \right ]

Row-reduce A to form a row-equivalent matrix in reduced row-echelon form,

B = \left [\array{ \text{1}&0&0& 2 &−1\cr 0&\text{1 } &0 & 3 & 1 \cr 0&0&\text{1}&−2& 5\cr 0&0 &0 & 0 & 0 } \right ]

Then Theorem BRS says we can grab the nonzero columns of {B}^{t} and write

X = ℛ\kern -1.95872pt \left (A\right ) = ℛ\kern -1.95872pt \left (B\right ) = \left \langle \left \{\left [\array{ 1\cr 0 \cr 0\cr 2 \cr −1 } \right ],\kern 1.95872pt \left [\array{ 0\cr 1 \cr 0\cr 3 \cr 1 } \right ],\kern 1.95872pt \left [\array{ 0\cr 0 \cr 1\cr −2 \cr 5 } \right ]\right \}\right \rangle

These three vectors provide a much-improved description of X. There are fewer vectors, and the pattern of zeros and ones in the first three entries makes it easier to determine membership in X. And all we had to do was row-reduce the right matrix and toss out a zero row. Next to row operations themselves, this is probably the most powerful computational technique at your disposal as it quickly provides a much improved description of a span, any span.

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 C\kern -1.95872pt \left (A\right ) = ℛ\kern -1.95872pt \left ({A}^{t}\right ).

Proof  

\eqalignno{ C\kern -1.95872pt \left (A\right ) & = C\kern -1.95872pt \left ({\left ({A}^{t}\right )}^{t}\right ) & &\text{@(a href="fcla-jsmath-2.22li30.html#theorem.TT")Theorem TT@(/a)} & & & & \cr & = ℛ\kern -1.95872pt \left ({A}^{t}\right ) & &\text{@(a href="#definition.RSM")Definition RSM@(/a)} & & & & }

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’ll 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

I = \left [\array{ 1 & 4 & 0 &−1& 0 & 7 &−9\cr 2 & 8 &−1 & 3 & 9 &−13 & 7 \cr 0 & 0 & 2 &−3&−4& 12 &−8\cr −1 &−4 & 2 & 4 & 8 &−31 & 37 } \right ].

The transpose is

\left [\array{ 1 & 2 & 0 & −1\cr 4 & 8 & 0 & −4 \cr 0 & −1 & 2 & 2\cr −1 & 3 &−3 & 4 \cr 0 & 9 &−4& 8\cr 7 &−13 & 12 &−31 \cr −9& 7 &−8& 37 } \right ].

Row-reduced this becomes,

\left [\array{ \text{1}&0&0&−{31\over 7} \cr 0&\text{1}&0& {12\over 7} \cr 0&0&\text{1}& {13\over 7} \cr 0&0&0& 0\cr 0&0 &0 & 0 \cr 0&0&0& 0\cr 0&0 &0 & 0 } \right ].

Now, using Theorem CSRST and Theorem BRS

C\kern -1.95872pt \left (I\right ) = ℛ\kern -1.95872pt \left ({I}^{t}\right ) = \left \langle \left \{\left [\array{ 1\cr 0 \cr 0 \cr −{31\over 7}} \right ],\kern 1.95872pt \left [\array{ 0\cr 1 \cr 0 \cr {12\over 7} } \right ],\kern 1.95872pt \left [\array{ 0\cr 0 \cr 1 \cr {13\over 7} } \right ]\right \}\right \rangle .

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

b = \left [\array{ 3\cr 9 \cr 1\cr 4 } \right ].

Since ℒS\kern -1.95872pt \left (I,\kern 1.95872pt b\right ) is consistent, Theorem CSCS tells us that b ∈C\kern -1.95872pt \left (I\right ). 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 b.

b = \left [\array{ 3\cr 9 \cr 1\cr 4 } \right ] = 3\left [\array{ 1\cr 0 \cr 0 \cr −{31\over 7}} \right ]+9\left [\array{ 0\cr 1 \cr 0 \cr {12\over 7} } \right ]+1\left [\array{ 0\cr 0 \cr 1 \cr {13\over 7} } \right ]

Can you now rapidly construct several vectors, b, so that ℒS\kern -1.95872pt \left (I,\kern 1.95872pt b\right ) is consistent, and several more so that the system is inconsistent?

Subsection READ: 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.
    \left [\array{ 1 &3&1&3\cr 2 &0 &1 &1 \cr −1&2&1&0} \right ]
  2. Suppose that A is an n × n nonsingular matrix. What can you say about its column space?
  3. Is the vector \left [\array{ 0\cr 5 \cr 2\cr 3 } \right ] in the row space of the following matrix? Why or why not?
    \left [\array{ 1 &3&1&3\cr 2 &0 &1 &1 \cr −1&2&1&0} \right ]

Subsection EXC: Exercises

C20 For parts (a), (b) and c, find a set of linearly independent vectors X so that C\kern -1.95872pt \left (A\right ) = \left \langle X\right \rangle , and a set of linearly independent vectors Y so that ℛ\kern -1.95872pt \left (A\right ) = \left \langle Y \right \rangle .

  1. A = \left [\array{ 1& 2 &3& 1\cr 0& 1 &1 & 2 \cr 1&−1&2& 3\cr 1& 1 &2 &−1 } \right ]
  2. A = \left [\array{ 1&2& 1 &1&1\cr 3&2 &−1 &4 &5 \cr 0&1& 1 &1&2} \right ]
  3. A = \left [\array{ 2&1& 0\cr 3&0 & 3 \cr 1&2&−3\cr 1&1 &−1 \cr 1&1&−1} \right ]
  4. From your results in parts (a) - (c), can you formulate a conjecture about the sets X and Y ?

 
Contributed by Chris Black

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. In Example CSMCS we determined that the vector

c = \left [\array{ 2\cr 3 \cr 2 } \right ]

was not in the column space of A and that the vector

b = \left [\array{ 8\cr −12 \cr 4 } \right ]

was in the column space of A. Attempt to write c and b as linear combinations of the two vectors in the span construction for the column space in Example CSOCD and record your observations.  
Contributed by Robert Beezer Solution [771]

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, that is, \left \langle T\right \rangle = C\kern -1.95872pt \left (A\right ), (2) T is linearly independent, and (3) the elements of T are columns of A.

A = \left [\array{ 2 & 1 & 4 &−1&2\cr 1 &−1 & 5 & 1 &1 \cr −1& 2 &−7& 0 &1\cr 2 &−1 & 8 &−1 &2 } \right ]

 
Contributed by Robert Beezer Solution [771]

C32 In Example CSAA, verify that the vector b is not in the column space of the coefficient matrix.  
Contributed by Robert Beezer

C33 Find a linearly independent set S so that the span of S, \left \langle S\right \rangle , is row space of the matrix B, and S is linearly independent.

B = \left [\array{ 2 &3&1& 1\cr 1 &1 &0 & 1 \cr −1&2&3&−4 } \right ]

 
Contributed by Robert Beezer Solution [772]

C34 For the 3 × 4 matrix A and the column vector y ∈ {ℂ}^{4} given below, determine if y is in the row space of A. In other words, answer the question: y ∈ℛ\kern -1.95872pt \left (A\right )?

\eqalignno{ A & = \left [\array{ −2& 6 &7&−1\cr 7 &−3 &0 &−3 \cr 8 & 0 &7& 6 } \right ] &y & = \left [\array{ 2\cr 1 \cr 3\cr −2 } \right ] & & & & }

 
Contributed by Robert Beezer Solution [773]

C35 For the matrix A below, find two different linearly independent sets whose spans equal the column space of A, C\kern -1.95872pt \left (A\right ), such that
(a) the elements are each columns of A.
(b) the set is obtained by a procedure that is substantially different from the procedure you use in part (a).

\eqalignno{ A & = \left [\array{ 3 & 5 &1&−2\cr 1 & 2 &3 & 3 \cr −3&−4&7&13 } \right ] & & }

 
Contributed by Robert Beezer Solution [774]

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

 
Contributed by Robert Beezer

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

 
Contributed by Robert Beezer

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

 
Contributed by Robert Beezer

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

 
Contributed by Robert Beezer

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

 
Contributed by Robert Beezer

M10 For the matrix E below, find vectors b and c so that the system ℒS\kern -1.95872pt \left (E,\kern 1.95872pt b\right ) is consistent and ℒS\kern -1.95872pt \left (E,\kern 1.95872pt c\right ) is inconsistent.

E = \left [\array{ −2& 1 &1&0\cr 3 &−1 &0 &2 \cr 4 & 1 &1&6 } \right ]

 
Contributed by Robert Beezer Solution [776]

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.  
Contributed by Robert Beezer Solution [777]

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 × n matrix A and row-reduce to a matrix B with columns {B}_{1},\kern 1.95872pt {B}_{2},\kern 1.95872pt {B}_{3},\kern 1.95872pt \mathop{\mathop{…}},\kern 1.95872pt {B}_{n}. Then form the column space of A as

C\kern -1.95872pt \left (A\right ) = \left \langle \left \{{B}_{1},\kern 1.95872pt {B}_{2},\kern 1.95872pt {B}_{3},\kern 1.95872pt \mathop{\mathop{…}},\kern 1.95872pt {B}_{n}\right \}\right \rangle = C\kern -1.95872pt \left (B\right )

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.  
Contributed by Robert Beezer Solution [777]

T40 Suppose that A is an m × n matrix and B is an n × p matrix. Prove that the column space of AB is a subset of the column space of A, that is C\kern -1.95872pt \left (AB\right ) ⊆C\kern -1.95872pt \left (A\right ). Provide an example where the opposite is false, in other words give an example where C\kern -1.95872pt \left (A\right )⊈C\kern -1.95872pt \left (AB\right ). (Compare with Exercise MM.T40.)  
Contributed by Robert Beezer Solution [777]

T41 Suppose that A is an m × n matrix and B is an n × n nonsingular matrix. Prove that the column space of A is equal to the column space of AB, that is C\kern -1.95872pt \left (A\right ) = C\kern -1.95872pt \left (AB\right ). (Compare with Exercise MM.T41 and Exercise CRS.T40.)  
Contributed by Robert Beezer Solution [778]

T45 Suppose that A is an m × n matrix and B is an n × m matrix where AB is a nonsingular matrix. Prove that
(1) N\kern -1.95872pt \left (B\right ) = \left \{0\right \}
(2) C\kern -1.95872pt \left (B\right ) ∩N\kern -1.95872pt \left (A\right ) = \left \{0\right \}
Discuss the case when m = n in connection with Theorem NPNT.  
Contributed by Robert Beezer Solution [779]

Subsection SOL: Solutions

C30 Contributed by Robert Beezer Statement [761]
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 c, the corresponding system has no solution, as we would expect.

For 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 b as a linear combination of all four columns of A, then there would be infinitely many ways to do this.

C31 Contributed by Robert Beezer Statement [762]
Theorem BCS is the right tool for this problem. Row-reduce this matrix, identify the pivot columns and then grab the corresponding columns of A for the set T. The matrix A row-reduces to

\left [\array{ \text{1}&0& 3 &0&0\cr 0&\text{1 } &−2 &0 &0 \cr 0&0& 0 &\text{1}&0\cr 0&0 & 0 &0 &\text{1} } \right ]

So D = \left \{1,\kern 1.95872pt 2,\kern 1.95872pt 4,\kern 1.95872pt 5\right \} and then

T = \left \{{A}_{1},\kern 1.95872pt {A}_{2},\kern 1.95872pt {A}_{4},\kern 1.95872pt {A}_{5}\right \} = \left \{\left [\array{ 2\cr 1 \cr −1\cr 2 } \right ],\kern 1.95872pt \left [\array{ 1\cr −1 \cr 2\cr −1 } \right ],\kern 1.95872pt \left [\array{ −1\cr 1 \cr 0\cr −1 } \right ],\kern 1.95872pt \left [\array{ 2\cr 1 \cr 1\cr 2 } \right ]\right \}

has the requested properties.

C33 Contributed by Robert Beezer Statement [763]
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’ll do the former,

B\mathop{\longrightarrow}\limits_{}^{\text{RREF}}\left [\array{ \text{1}&0&−1& 2\cr 0&\text{1 } & 1 &−1 \cr 0&0& 0 & 0 } \right ]

So the set S is

S = \left \{\left [\array{ 1\cr 0 \cr −1\cr 2 } \right ],\kern 1.95872pt \left [\array{ 0\cr 1 \cr 1\cr −1 } \right ]\right \}

C34 Contributed by Robert Beezer Statement [764]

\eqalignno{ y ∈ℛ\kern -1.95872pt \left (A\right ) &\kern 3.26288pt \mathrel{⇔}\kern 3.26288pt y ∈C\kern -1.95872pt \left ({A}^{t}\right ) & &\text{@(a href="#definition.RSM")Definition RSM@(/a)} & & & & \cr &\kern 3.26288pt \mathrel{⇔}\kern 3.26288pt ℒS\kern -1.95872pt \left ({A}^{t},\kern 1.95872pt y\right )\text{ is consistent} & &\text{@(a href="#theorem.CSCS")Theorem CSCS@(/a)} & & & & }

The augmented matrix \left [\left .{A}^{t}\kern 1.95872pt \right \vert \kern 1.95872pt y\right ] row reduces to

\eqalignno{ \left [\array{ \text{1}&0&0&0\cr 0&\text{1 } &0 &0 \cr 0&0&\text{1}&0\cr 0&0 &0 &\text{1} } \right ] & & }

and with a leading 1 in the final column Theorem RCLS tells us the linear system is inconsistent and so y∉ℛ\kern -1.95872pt \left (A\right ).

C35 Contributed by Robert Beezer Statement [764]
(a) By Theorem BCS we can row-reduce A, identify pivot columns with the set D, and “keep” those columns of A and we will have a set with the desired properties.

\eqalignno{ A\mathop{\longrightarrow}\limits_{}^{\text{RREF}}\left [\array{ \text{1}&0&−13&−19\cr 0&\text{1 } & 8 & 11 \cr 0&0& 0 & 0 } \right ] & & }

So we have the set of pivot columns D = \left \{1,\kern 1.95872pt 2\right \} and we “keep” the first two columns of A,

\eqalignno{ \left \{\left [\array{ 3\cr 1 \cr −3 } \right ],\kern 1.95872pt \left [\array{ 5\cr 2 \cr −4 } \right ]\right \} & & }

(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.

\eqalignno{ {A}^{t}\mathop{\longrightarrow}\limits_{}^{\text{RREF}}\left [\array{ \text{1}&0&−2\cr 0&\text{1 } & 3 \cr 0&0& 0\cr 0&0 & 0 } \right ] & & }

Taking the nonzero rows and tilting them up as columns gives us

\eqalignno{ \left \{\left [\array{ 1\cr 0 \cr −2 } \right ],\kern 1.95872pt \left [\array{ 0\cr 1 \cr 3 } \right ]\right \} & & }

An approach based on the matrix L from extended echelon form (Definition EEF) and Theorem FS will work as well as an alternative approach.

M10 Contributed by Robert Beezer Statement [767]
Any vector from {ℂ}^{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,

E\mathop{\longrightarrow}\limits_{}^{\text{RREF}}\left [\array{ \text{1}&0&0&1\cr 0&\text{1 } &0 &1 \cr 0&0&\text{1}&1 } \right ]

If we augment E with any vector of constants, and row-reduce the augmented matrix, we will never find a leading 1 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 {ℂ}^{3}, C\kern -1.95872pt \left (E\right ) = {ℂ}^{3}. So by Theorem CSCS any vector of constants will create a consistent system (and none will create an inconsistent system).

M20 Contributed by Robert Beezer Statement [768]
The 2 × 2 matrix

\left [\array{ 1 & 1\cr −1 &−1 } \right ]

has C\kern -1.95872pt \left (A\right ) = N\kern -1.95872pt \left (A\right ) = \left \langle \left \{\left [\array{ 1\cr −1 } \right ]\right \}\right \rangle .

M21 Contributed by Robert Beezer Statement [768]
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).

C\kern -1.95872pt \left (A\right ) will contain some vectors whose final slot (entry m) is non-zero, however, every column vector from the matrix B will have a zero in slot m and so every vector in C\kern -1.95872pt \left (B\right ) will also contain a zero in the final slot. This means that C\kern -1.95872pt \left (A\right )\mathrel{≠}C\kern -1.95872pt \left (B\right ), since we have vectors in C\kern -1.95872pt \left (A\right ) that cannot be elements of C\kern -1.95872pt \left (B\right ).

T40 Contributed by Robert Beezer Statement [769]
Choose x ∈C\kern -1.95872pt \left (AB\right ). Then by Theorem CSCS there is a vector w that is a solution to ℒS\kern -1.95872pt \left (AB,\kern 1.95872pt x\right ). Define the vector y by y = Bw. We’re set,

\eqalignno{ Ay & = A\left (Bw\right ) & &\text{Definition of $y$} & & & & \cr & = \left (AB\right )w & &\text{@(a href="fcla-jsmath-2.22li31.html#theorem.MMA")Theorem MMA@(/a)} & & & & \cr & = x & &\text{$w$ solution to $ℒS\kern -1.95872pt \left (AB,\kern 1.95872pt x\right )$} & & & & \cr & & & & }

This says that ℒS\kern -1.95872pt \left (A,\kern 1.95872pt x\right ) is a consistent system, and by Theorem CSCS, we see that x ∈C\kern -1.95872pt \left (A\right ) and therefore C\kern -1.95872pt \left (AB\right ) ⊆C\kern -1.95872pt \left (A\right ).

For an example where C\kern -1.95872pt \left (A\right )⊈C\kern -1.95872pt \left (AB\right ) choose A to be any nonzero matrix and choose B to be a zero matrix. Then C\kern -1.95872pt \left (A\right )\mathrel{≠}\left \{0\right \} and C\kern -1.95872pt \left (AB\right ) = C\kern -1.95872pt \left (O\right ) = \left \{0\right \}.

T41 Contributed by Robert Beezer Statement [769]
From the solution to Exercise CRS.T40 we know that C\kern -1.95872pt \left (AB\right ) ⊆C\kern -1.95872pt \left (A\right ). So to establish the set equality (Definition SE) we need to show that C\kern -1.95872pt \left (A\right ) ⊆C\kern -1.95872pt \left (AB\right ).

Choose x ∈C\kern -1.95872pt \left (A\right ). By Theorem CSCS the linear system ℒS\kern -1.95872pt \left (A,\kern 1.95872pt x\right ) is consistent, so let 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 w be the unique solution to the linear system ℒS\kern -1.95872pt \left (B,\kern 1.95872pt y\right ). All set, here we go,

\eqalignno{ \left (AB\right )w & = A\left (Bw\right ) & &\text{@(a href="fcla-jsmath-2.22li31.html#theorem.MMA")Theorem MMA@(/a)} & & & & \cr & = Ay & &\text{$w$ solution to $ℒS\kern -1.95872pt \left (B,\kern 1.95872pt y\right )$} & & & & \cr & = x & &\text{$y$ solution to $ℒS\kern -1.95872pt \left (A,\kern 1.95872pt x\right )$} & & & & \cr & & & & }

This says that the linear system ℒS\kern -1.95872pt \left (AB,\kern 1.95872pt x\right ) is consistent, so by Theorem CSCS, x ∈C\kern -1.95872pt \left (AB\right ). So C\kern -1.95872pt \left (A\right ) ⊆C\kern -1.95872pt \left (AB\right ).

T45 Contributed by Robert Beezer Statement [769]
First, 0 ∈N\kern -1.95872pt \left (B\right ) trivially. Now suppose that x ∈N\kern -1.95872pt \left (B\right ). Then

\eqalignno{ ABx & = A(Bx) & &\text{@(a href="fcla-jsmath-2.22li31.html#theorem.MMA")Theorem MMA@(/a)} & & & & \cr & = A0 & &x ∈N\kern -1.95872pt \left (B\right ) & & & & \cr & = 0 & &\text{@(a href="fcla-jsmath-2.22li31.html#theorem.MMZM")Theorem MMZM@(/a)} & & & & }

Since we have assumed AB is nonsingular, Definition NM implies that x = 0.

Second, 0 ∈C\kern -1.95872pt \left (B\right ) and 0 ∈N\kern -1.95872pt \left (A\right ) trivially, and so the zero vector is in the intersection as well (Definition SI). Now suppose that y ∈C\kern -1.95872pt \left (B\right ) ∩N\kern -1.95872pt \left (A\right ). Because y ∈C\kern -1.95872pt \left (B\right ), Theorem CSCS says the system ℒS\kern -1.95872pt \left (B,\kern 1.95872pt y\right ) is consistent. Let x ∈ {ℂ}^{n} be one solution to this system. Then

\eqalignno{ ABx & = A(Bx) & &\text{@(a href="fcla-jsmath-2.22li31.html#theorem.MMA")Theorem MMA@(/a)} & & & & \cr & = Ay & &\text{$x$ solution to $ℒS\kern -1.95872pt \left (B,\kern 1.95872pt y\right )$} & & & & \cr & = 0 & &y ∈N\kern -1.95872pt \left (A\right ) & & & & }

Since we have assumed AB is nonsingular, Definition NM implies that x = 0. Then y = Bx = B0 = 0.

When AB is nonsingular and m = n we know that the first condition, N\kern -1.95872pt \left (B\right ) = \left \{0\right \}, means that B is nonsingular (Theorem NMTNS). Because B is nonsingular Theorem CSNM implies that C\kern -1.95872pt \left (B\right ) = {ℂ}^{m}. In order to have the second condition fulfilled, C\kern -1.95872pt \left (B\right ) ∩N\kern -1.95872pt \left (A\right ) = \left \{0\right \}, we must realize that N\kern -1.95872pt \left (A\right ) = \left \{0\right \}. However, a second application of Theorem NMTNS shows that A must be nonsingular. This reproduces Theorem NPNT.