Skip to main content

Section 20.5 Theory

Subsection 20.5.1 Column space

First we’ll record two facts concerning how multiplying each in a set of column vectors in \(\R^n \) by a common matrix affects linear dependence and independence, leading to our conclusion about how to determine a basis for the column space of a matrix from examining its RREF.

Proof of Statement 1.
Let’s apply the Test for Linear Dependence/Independence (Proposition 17.5.1) to the vectors \(\uvec{v}_1, \uvec{v}_2, \dotsc, \uvec{v}_\ell \text{:}\) suppose that \(k_1, k_2, \dotsc, k_\ell \) are scalars so that
\begin{equation} k_1\uvec{v}_1 + k_2\uvec{v}_2 + \dotsc + k_\ell\uvec{v}_\ell = \zerovec\text{.}\tag{✶} \end{equation}
Multiplying both sides of this equation by the matrix \(E \text{,}\) and using some matrix algebra, we get
\begin{equation*} k_1 E \uvec{v}_1 + k_2 E \uvec{v}_2 + \dotsc + k_\ell E \uvec{v}_\ell = E \zerovec = \zerovec \text{.} \end{equation*}
But we have assumed that the vectors \(E \uvec{v}_1, E \uvec{v}_2, \dotsc, E \uvec{v}_\ell \) are linearly independent, so the only way this linear combination could equal the zero vector is if all the scalars \(k_1, k_2, \dotsc, k_\ell \) are zero. Thus, the linear combination in (✶) must be the trivial one, and so the vectors \(\uvec{v}_1,\uvec{v}_2,\dotsc,\uvec{v}_\ell \) are linearly independent.

Proof of Statement 2.
We assume \(\uvec{v}_1, \uvec{v}_2, \dotsc, \uvec{v}_\ell \) are linearly independent. Since we also assume \(E \) to be invertible, we can restate this as saying that vectors
\begin{equation*} \inv{E} (E \uvec{v}_1), \inv{E} (E \uvec{v}_2), \dotsc, \inv{E} (E \uvec{v}_\ell) \end{equation*}
are linearly independent. Now we can apply Statement 1 with \(E \) replaced by \(\inv{E} \) and \(\uvec{v}_1, \uvec{v}_2, \dotsc, \uvec{v}_\ell \) replaced by \(E \uvec{v}_1, E \uvec{v}_2, \dotsc, E \uvec{v}_\ell \text{.}\)

Proof of Statement 3.
Simply apply the inverse \(\inv{E} \) to both sides of
\begin{equation*} E\uvec{w} = k_1 E \uvec{v}_1 + k_2 E \uvec{v}_2 + \dotsb + k_\ell E \uvec{v}_\ell \end{equation*}
to obtain
\begin{equation*} \uvec{w} = k_1 \uvec{v}_1 + k_2 \uvec{v}_2 + \dotsb + k_\ell \uvec{v}_\ell \text{.} \end{equation*}

Proof of Statement 1.
By definition, the columns of \(A \) are a spanning set for the column space of \(A \text{.}\) By Proposition 18.5.1, this spanning set can be reduced to a basis; it’s a matter of determining the largest possible linearly independent set of these spanning column vectors.
Let \(E = E_t E_{t-1} \dotsm E_1 \) be the product of elementary matrices corresponding to some sequence of row operations that reduces \(A \) to its RREF. Because of the nature of RREF, each column of \(\RREF(A) \) that contains a leading one will be a standard basis vector in \(\R^m \text{,}\) no two such leading-one columns will be the same standard basis vector, and each column that does not contain a leading one will be a linear combination of those leading-one columns that appear to its left. Therefore, the leading-one columns represent the largest set of linearly independent vectors that can be formed from the columns of \(\RREF(A) \text{.}\) Since \(E \) is invertible, the two statements of Proposition 20.5.1 tell us that the columns of \(A \) will have the same relationships: those columns in \(A \) that are in positions where the leading ones occur in \(\RREF(A) \) will be linearly independent, and that will be the largest possible collection of linearly independent columns of \(A \text{,}\) because each of the other columns will be linearly dependent with the leading-one-position columns of \(A \) to its left.
Thus, we can reduce the spanning set made up of all columns of \(A \) to a basis for its column space by discarding the linearly dependent columns and keeping only those columns in positions corresponding to the locations of the leading ones occur in \(\RREF(A) \text{.}\)

Proof of Statement 2.
Since we obtain a basis for column space by taking those columns in the matrix in positions corresponding to the leading ones in a reduced form for the matrix, the number of basis vectors is equal to the number of leading ones.

Proof of Statement 3.
Let \(\{ \uvec{a}_1, \uvec{a}_2, \dotsc, \uvec{a}_n \} \) represent the columns of \(A \text{,}\) and let \(\basisfont{B} = \{ \uvec{b}_1, \uvec{b}_2, \dotsc, \uvec{b}_r \} \) represent the basis for the column space of \(A \) posited in Statement 1 (where \(r = \rank A \)). These column space basis vectors are chosen from the columns of \(A \) in correspondence with the positions of the leading ones in \(\RREF(A) \) (which occur in the same positions in \(R \)), so we have \(\uvec{b}_i = \uvec{a}_j \) when there is a leading one in the \(\nth[(i,j)] \) entry of \(\RREF(A) \) (and also in \(R \)).
Leading ones in an RREF matrix might skip columns, but they never skip rows. So the leading-one columns of \(\RREF(A) \) are precisely the first \(r \) standard basis vectors in \(\R^m \text{.}\) These correspond, in order, to our column space basis vectors: through the row reduction process, \(\uvec{b}_1 \) becomes \(\uvec{e}_1 \text{,}\) \(\uvec{b}_2 \) becomes \(\uvec{e}_2 \text{,}\) and so on.
Fix a column index \(j \text{.}\) As above, the \(\nth[j] \) column of \(A \) is \(\uvec{a}_j \text{.}\) Let \(\uvec{c}_j \) represent the corresponding \(\nth[j] \) column of \(R \text{,}\) and let \(\uvec{d}_j \) represent the corresponding \(\nth[j] \) column of \(\RREF(A) \text{.}\) Keep in mind that \(\uvec{a}_j \) and \(\uvec{d}_j \) are \(m \)-dimensional vectors while \(\uvec{c}_j \) is an \(r \)-dimensional vector. Let \(c_1, c_2, \dotsc, c_r \) represent the components of \(\uvec{c}_j \text{.}\) The only potential difference between \(\uvec{c}_j \) and \(\uvec{d}_j \) is that the “extra” components in \(\uvec{d}_j \) are all zero in the case that \(r \lt m \text{:}\)
\begin{equation*} \uvec{c}_j = \begin{bmatrix} c_1 \\ c_2 \\ \vdots \\ c_r \end{bmatrix} \qquad \implies \qquad \uvec{d}_j = \begin{bmatrix} c_1 \\ c_2 \\ \vdots \\ c_r \\ 0 \\ \vdots \\ 0 \end{bmatrix}\text{.} \end{equation*}
As with all vectors in \(\R^m \text{,}\) we can express \(\uvec{d}_j \) as a linear combination of standard basis vectors via its components:
\begin{equation*} \uvec{d}_j = c_1 \uvec{e}_1 + c_2 \uvec{e}_2 + \dotsb + c_r \uvec{e}_r + 0 \uvec{e}_{r + 1} + \dotsb + 0 \uvec{e}_m \text{.} \end{equation*}
Because of those “trailing” zero components, we can shorten this to simply
\begin{equation} \uvec{d}_j = c_1 \uvec{e}_1 + c_2 \uvec{e}_2 + \dotsb + c_r \uvec{e}_r\text{.}\tag{✶✶} \end{equation}
Let \(E \) represent a product of elementary matrices so that \(E A = \RREF(A) \text{.}\) Then \(E \uvec{a}_j = \uvec{d}_j \text{,}\) and, as described above, \(E \uvec{b}_1 = \uvec{e}_1 \text{,}\) \(E \uvec{b}_2 = \uvec{e}_2 \text{,}\) and so on. Using these substitutions, (✶✶) becomes
\begin{equation*} E \uvec{a}_j = c_1 E \uvec{b}_1 + c_2 E \uvec{b}_2 + \dotsb + c_r E \uvec{b}_r \text{.} \end{equation*}
As \(E \) is a product of invertible matrices, it itself is also invertible (Statement 4 of Proposition 5.5.5), and so Statement 3 of Proposition 20.5.1 can be applied to conclude that
\begin{equation*} \uvec{a}_j = c_1 \uvec{b}_1 + c_2 \uvec{b}_2 + \dotsb + c_r \uvec{b}_r \text{.} \end{equation*}
Collecting these coefficients into a coordinate vector, we have
\begin{equation*} \rmatrixOf{\uvec{a}_j}{B} = (c_1, c_2, \dotsc, c_r) = \uvec{c}_j \text{,} \end{equation*}
as desired.

Remark 20.5.3.

In the case that \(A = \zerovec \text{,}\) the column space of \(A \) is the trivial space \(\{ \zerovec \} \) of dimension \(0 \text{,}\) so it is still true that the dimension of the column space is equal to the rank.

Subsection 20.5.2 Row space

Next we’ll record our observations concerning how the row operations affect the row space of a matrix, leading to our conclusion about how to obtain a basis for the row space of a matrix from its RREF.

Proof.
Consider an \(m \times n \) matrix \(A \) as a collection of row vectors in \(\R^n \text{:}\)
\begin{equation*} A = \begin{bmatrix} \leftrightlinesubstitute \amp \uvec{a}_1 \amp \leftrightlinesubstitute\\ \leftrightlinesubstitute \amp \uvec{a}_2 \amp \leftrightlinesubstitute\\ \amp\vdots\\ \leftrightlinesubstitute \amp \uvec{a}_m \amp \leftrightlinesubstitute\\ \end{bmatrix}\text{.} \end{equation*}
Then the row space of \(A \) is, by definition, the subspace \(\Span \{ \uvec{a}_1, \uvec{a}_2, \dotsc, \uvec{a}_m \} \) of \(\R^m \text{.}\)
As we did in Discovery 20.5, we will make repeated use of Statement 2 of Proposition 16.5.6, which tells us how to determine when two spanning sets generate the same subspace.
Let’s consider each type of elementary row operation in turn.
  1. Suppose we swap two rows in \(A \text{:}\)
    \begin{equation*} A = \begin{bmatrix} \leftrightlinesubstitute \amp \uvec{a}_1 \amp \leftrightlinesubstitute\\ \amp\vdots\\ \leftrightlinesubstitute \amp \uvec{a}_i \amp \leftrightlinesubstitute\\ \amp\vdots\\ \leftrightlinesubstitute \amp \uvec{a}_j \amp \leftrightlinesubstitute\\ \amp\vdots\\ \leftrightlinesubstitute \amp \uvec{a}_m \amp \leftrightlinesubstitute\\ \end{bmatrix} \quad \longrightarrow \quad A' = \begin{bmatrix} \leftrightlinesubstitute \amp \uvec{a}_1 \amp \leftrightlinesubstitute\\ \amp\vdots\\ \leftrightlinesubstitute \amp \uvec{a}_j \amp \leftrightlinesubstitute\\ \amp\vdots\\ \leftrightlinesubstitute \amp \uvec{a}_i \amp \leftrightlinesubstitute\\ \amp\vdots\\ \leftrightlinesubstitute \amp \uvec{a}_m \amp \leftrightlinesubstitute\\ \end{bmatrix}\text{.} \end{equation*}
    The row space of the new matrix, \(A' \text{,}\) is the span of its row vectors. But every row vector in \(A' \) is equal to one of the row vectors in \(A \text{,}\) and vice versa. So clearly the conditions of the above-referenced Statement 2 are satisfied, and the rowspaces of the two matrices are the same space.
  2. Suppose we multiply one of the rows in \(A \) by a nonzero constant \(k \text{:}\)
    \begin{equation*} A = \begin{bmatrix} \leftrightlinesubstitute \amp \uvec{a}_1 \amp \leftrightlinesubstitute\\ \amp\vdots\\ \leftrightlinesubstitute \amp \uvec{a}_i \amp \leftrightlinesubstitute\\ \amp\vdots\\ \leftrightlinesubstitute \amp \uvec{a}_m \amp \leftrightlinesubstitute\\ \end{bmatrix} \quad \longrightarrow \quad A'' = \begin{bmatrix} \leftrightlinesubstitute \amp \uvec{a}_1 \amp \leftrightlinesubstitute\\ \amp\vdots\\ \leftrightlinesubstitute \amp k\uvec{a}_i \amp \leftrightlinesubstitute\\ \amp\vdots\\ \leftrightlinesubstitute \amp \uvec{a}_m \amp \leftrightlinesubstitute\\ \end{bmatrix}\text{.} \end{equation*}
    Again, most of the row vectors in the new matrix \(A'' \) are equal to one of the row vectors in \(A \text{,}\) and vice versa. So to fully satisfy the conditions of the above-referenced Statement 2, we need to verify that \(k \uvec{a}_i \) is somehow a linear combination of row vectors from \(A \) and that \(\uvec{a}_i \) is somehow a linear combination of row vectors from \(A'' \text{.}\) But \(k \uvec{a}_i \) is already expressed as a scalar multiple of a row vector from \(A \text{,}\) and since \(k \) is nonzero we can also write
    \begin{equation*} \uvec{a}_i = \frac{1}{k} \cdot (k\uvec{a}_i) \text{,} \end{equation*}
    so that \(\uvec{a}_i \) is also a scalar multiple of a row vector from \(A'' \text{.}\)
    With the conditions of the above-referenced Statement 2 now fully satisfied, we can conclude that the rowspaces of the two matrices are the same space.
  3. Suppose we replace one row vector in \(A \) by the sum of that row and a scalar multiple of another:
    \begin{equation*} A = \begin{bmatrix} \leftrightlinesubstitute \amp \uvec{a}_1 \amp \leftrightlinesubstitute\\ \amp\vdots\\ \leftrightlinesubstitute \amp \uvec{a}_i \amp \leftrightlinesubstitute\\ \amp\vdots\\ \leftrightlinesubstitute \amp \uvec{a}_m \amp \leftrightlinesubstitute\\ \end{bmatrix} \quad \longrightarrow \quad A''' = \begin{bmatrix} \leftrightlinesubstitute \amp \uvec{a}_1 \amp \leftrightlinesubstitute\\ \amp\vdots\\ \leftrightlinesubstitute \amp \uvec{a}_i + k\uvec{a}_j \amp \leftrightlinesubstitute\\ \amp\vdots\\ \leftrightlinesubstitute \amp \uvec{a}_m \amp \leftrightlinesubstitute\\ \end{bmatrix}\text{.} \end{equation*}
    Once again, most of the row vectors in the new matrix \(A''' \) are equal to one of the row vectors in \(A \text{,}\) and vice versa. So to fully satisfy the conditions of the above-referenced Statement 2, we need to verify that \(\uvec{a}_i + k \uvec{a}_j \) is somehow a linear combination of row vectors from \(A \) and that \(\uvec{a}_i \) is somehow a linear combination of row vectors from \(A''' \text{.}\) But \(\uvec{a}_i + k\uvec{a}_j \) is already expressed as a linear combination of row vectors from \(A''' \text{,}\) and for \(\uvec{a}_i \) we can write
    \begin{equation*} \uvec{a}_i = 1 ( \uvec{a}_i + k \uvec{a}_j ) + (-k) \uvec{a}_j \text{,} \end{equation*}
    a linear combination of row vectors from \(A''' \text{.}\)

    Aside: Note.

    With the conditions of the above-referenced Statement 2 now fully satisfied, we can conclude that the rowspaces of the two matrices are the same space.

Proof of Statement 1.
Since \(E \) is invertible, it can be expressed as a product of elementary matrices (Theorem 6.5.2), and the product \(E A \) has the same result as applying to \(A \) the sequence of row operations represented by those elementary matrices. But Proposition 20.5.4 tells us that applying those operations does not change the row space.

Proof of Statement 2.
Suppose that \(B \) is row equivalent to \(A \text{.}\) By definition, this means that we can obtain \(B \) through a sequence of elementary row operations applied to \(A \text{.}\) Let \(E_1, E_2, \dotsc, E_\ell \) be elementary matrices corresponding to some sequence of row operations that transforms \(A \) into \(B \text{.}\) Set \(E = E_\ell \dotsm E_2 E_1 \text{.}\) Then \(E \) is an invertible matrix and \(B = E A \text{.}\) Therefore, \(B \) has the same row space as \(A \) by Statement 1 of this corollary.

Proof of Statement 1.
Let \(F \) be an REF for \(A \text{.}\) By Statement 2 of this corollary, the rows of \(F \) are a spanning set for the row space of \(A \text{.}\) Clearly we can discard any zero rows from this spanning set, so it just remains to verify that the nonzero rows of \(F \) are linearly independent. For this, we will use Proposition 17.5.6, building up our linearly independent spanning set one vector at a time. Let \(\uvec{v}_1, \uvec{v}_2, \dotsc, \uvec{v}_\ell \) represent the nonzero rows of \(F \text{,}\) from top to bottom. Start with \(\uvec{v}_\ell \text{;}\) all by itself, this one nonzero vector is linearly independent. Now, \(\uvec{v}_{\ell-1} \) cannot be in \(\Span \{ \uvec{v}_\ell \} \text{,}\) because the leading one in \(\uvec{v}_{\ell-1} \) appears to the left of the leading one in \(\uvec{v}_\ell \text{,}\) and so no scalar multiple of \(\uvec{v}_\ell \) will have a nonzero entry in the component where \(\uvec{v}_{\ell-1} \) has its leading one. From this, Proposition 17.5.6 tells us that \(\{ \uvec{v}_{\ell-1}, \uvec{v}_\ell \} \) is linearly independent. Moving on, \(\uvec{v}_{\ell-2} \) cannot be in \(\Span \{ \uvec{v}_{\ell-1}, \uvec{v}_\ell \} \text{,}\) because the leading one in \(\uvec{v}_{\ell-2} \) appears to the left of both the leading one in \(\uvec{v}_{\ell-1} \) and in \(\uvec{v}_{\ell} \text{,}\) and so no linear combination of those two vectors will have a nonzero entry in the component where \(\uvec{v}_{\ell-2} \) has its leading one. From this, Proposition 17.5.6 tells us that \(\{ \uvec{v}_{\ell-2}, \uvec{v}_{\ell-1}, \uvec{v}_\ell \} \) is linearly independent. Repeating this argument as we move up the rows of \(F \text{,}\) we see that the nonzero rows of \(F \) are linearly independent when taken altogether.

Proof of Statement 2.
Applying Statement 1 of this corollary to the RREF for \(A \text{,}\) the nonzero rows of \(\RREF(A) \) form a basis for the row space of \(A \text{.}\) But the nonzero rows of \(\RREF(A) \) must all contain leading ones, so the number of vectors in a basis for the row space of \(A \) is equal to the number of leading ones in \(\RREF(A) \text{,}\) as desired.

Proof of Statement 1.
Matrices that have the same RREF are row equivalent, and we have already verified that row equivalent matrices have the same row space (Statement 2 of Corollary 20.5.5). It only remains to verify that having the same row space implies having the same RREF.
Suppose \(A \) and \(B \) are matrices of the same size that have the same row space. If one the two matrices is the zero matrix, then the row space of that matrix is the trivial space \(\{ \zerovec \} \text{.}\) But then the other cannot be nonzero, since a nonzero matrix would have a nontrivial row space. And if both matrices are the zero matrix, then they are both already in RREF, and so have the same RREF.
So assume both matrices are nonzero. Then their RREFs are both nonzero has well. Let \(\uvec{a}_1, \uvec{a}_2, \dotsc, \uvec{a}_m \) represent the non-zero rows of \(\RREF(A) \) and let \(\uvec{b}_1, \uvec{b}_2, \dotsc, \uvec{b}_m \) represent the non-zero rows of \(\RREF(B) \text{.}\) By Statement 1 of Statement 20.5.6, each of these collections is a basis for the same space: the shared row space of \(A \) and \(B \text{.}\) Because of this, each \(\uvec{a}_i \) is somehow a linear combination of the \(\uvec{b}_j \) vectors, and vice versa.
Now, each of \(\uvec{a}_1 \) and \(\uvec{b}_1 \) has a leading one as the first nonzero component. It is not possible for the leading one in \(\uvec{a}_1 \) to be “earlier” than the leading one in \(\uvec{b}_1 \text{,}\) since if it were then it would also be “earlier” than all of the leading ones in \(\RREF(B) \text{,}\) and then it would be impossible for \(\uvec{a}_1 \) to be a linear combination of the \(\uvec{b}_j \) vectors. By the same argument, the leading one in \(\uvec{b}_1 \) cannot be “earlier” than the leading one in \(\uvec{a}_1 \text{,}\) and so both \(\uvec{a}_1 \) and \(\uvec{b}_1 \) have their leading ones in the same position.
From this we can conclude that expressing \(\uvec{a}_2 \) as a linear combination of the \(\uvec{b}_j \) vectors cannot involve \(\uvec{b}_1 \text{,}\) since that would create a nonzero entry in \(\uvec{a}_2 \) at the same position as the leading one in \(\uvec{a}_1 \text{,}\) which cannot happen in RREF. And similarly expressing \(\uvec{b}_2 \) as a linear combination of the \(\uvec{a}_j \) vectors cannot involve \(\uvec{a}_1 \text{.}\) But then essentially the same argument as above for \(\uvec{a}_1 \) and \(\uvec{b}_1 \) can be applied to conclude that the leading ones in \(\uvec{a}_2 \) and \(\uvec{b}_2 \) must occur at the same position. And so on, so that each pair \(\uvec{a}_i, \uvec{b}_i \) must have their leading ones in the same component. This also means that wherever a particular \(\uvec{a}_i \) vector has a leading one, all of the \(\uvec{b}_j \) vectors have a zero in that same position, except \(\uvec{b}_i \text{.}\) (And vice versa for each \(\uvec{b}_i \) compared to the \(\uvec{a}_j \) vectors.)
For each expresion
\begin{equation*} \uvec{a}_i = k_1 \uvec{b}_1 + k_2 \uvec{b}_2 + \dotsb + k_m \uvec{b}_m \end{equation*}
we can now make the following determinations:
  1. Each of \(k_1, k_2, \dotsc, k_{i - 1} \) must be zero, since otherwise the coefficient \(k_j \) times the leading one in the corresponding \(\uvec{b}_j \) vector would create a nonzero entry in \(\uvec{a}_i \) that is “earlier” than the leading one in \(\uvec{a}_i \text{,}\) which cannot happen.
  2. The coefficient \(k_i \) must be \(1 \text{,}\) so that when multiplied against the leading one in the corresponding \(\uvec{b}_i \) vector it creates the leading one in \(\uvec{a}_i \text{.}\)
  3. Each of \(k_{i + 1}, k_{i + 2}, \dotsc, k_m \) must be zero, since otherwise the coefficient \(k_j \) times the leading one in the corresponding \(\uvec{b}_j \) vector would create a nonzero entry in \(\uvec{a}_i \) at the same position as a leading one in \(\uvec{a}_j \text{,}\) which cannot happen.
Simplifying using these determinations, we conclude that \(\uvec{a}_i = \uvec{b}_i \) in each case, and therefore \(\RREF(A) = \RREF(B) \text{.}\)

Proof of Statement 2.
This now follows immediately from Statement 1 of this corollary, as matrices of the same size are row equivalent precisely when they have the same RREF.

Subsection 20.5.3 Column and row spaces versus rank and invertibility

As discovered in Discovery 20.4, we can use our observations recorded in Proposition 20.5.1 to connect column space to invertibility. We can similarly use Corollary 20.5.5 to also connect row space to invertibility.
First, we will extend the list of properties that are equivalent to invertibility of a square matrix, first started in Theorem 6.5.2, and then continued in Theorem 10.5.3.

Proof.
We have previously encountered the equivalence of many of these statements, most recently in Theorem 10.5.3. So currently we only need to concern ourselves with the new statements. For each of these, if we can establish equivalence of the new statement to one of the old, then the new statement must be equivalent to all of the old, by the transitivity of logical equivalence.
Finally, we’ll record an observation from Discovery 20.9, which is just a reframing of Proposition 2.5.8.

Proof.
The dimension of the column space of \(A \) is equal to the number of leading ones in its RREF, while the dimension of the null space of \(A \) is equal to the number of free variables, which is equal to the number of columns in the RREF that do not have a leading one. These two numbers must add up to the total number of columns in \(A \text{.}\)
PrevTopNext