The individual equations of the homogeneous linear system $\mathbf{\text{Ax}}=\mathbf{0}$ correspond to the “row matrices”

of the $m\times n$ matrix $\mathbf{\text{A}}=\left[a_{ij}\right].$ The row vectors of A are the m vectors

in ${\mathbf{\text{R}}}^n$. Recalling from Section 3.4 the convection that n-tuples denote column-vector elements of ${\mathbf{\text{R}}}^n$, we see that the row vectors of A are the transposes of its row matrices; that is,

for $i=1,2,\dots ,m$, and thus actually are column vectors (despite being called “row vectors”). The subspace of ${\mathbf{\text{R}}}^n$ spanned by the m row vectors ${\mathbf{r}}_1,{\mathbf{r}}_2,\dots ,{\mathbf{r}}_{\mathbf{m}}$ is called the row space Row(A) of the matrix A. The dimension of the row space Row(A) is called the row rank of the matrix A.

It should be apparent that the method used in Example 1 applies to any echelon matrix $\mathbf{E}=[e_{ij}]$. If the first column of E isnot all zero, then its nonzero row vectors ${\mathbf{r}}_1,{\mathbf{r}}_2$, $\dots ,{\mathbf{r}}_k$ have the forms

and so forth (where $e_{11},e_{2p}$, and $e_{3q}$ denote nonzero leading entries). Then the equation

implies that

and so forth. We can therefore conclude in turn that $c_1=0$, $c_2=0,\dots ,c_k=0$. Thus the row vectors ${\mathbf{r}}_1,{\mathbf{r}}_2,\dots ,{\mathbf{r}}_k$ are linearly independent, and hence we have the following result.

We investigate the row space of an arbitrary matrix A by reducing A to an echelon matrix E. The following theorem then guarantees that A and E have the same row space. Recall that two matrices are (row) equivalent provided that each can be transformed to the other by elementary row operations.

Theorems 1 and 2 together provide a routine procedure for finding a basis for the row space of a given matrix, thereby determining its row rank.

In Example 2, note that Algorithm 1 does not tell us that the first three row vectors of the matrix A itself are linearly independent. We know that some three row vectors of A span Row(A), but without further investigation we do not know which three.

Now we turn our attention from row vectors to column vectors. Given an $m\times n$ matrix $\mathbf{\text{A}}=[a_{ij}]$, the column vectors of A are the n vectors

in ${\mathbf{\text{R}}}^m$. The subspace of ${\mathbf{\text{R}}}^m$ spanned by the n column vectors ${\mathbf{c}}_1,{\mathbf{c}}_2,\dots ,{\mathbf{c}}_n$ is called the column space Col(A) of the matrix A. The dimension of the space Col(A) is called the column rank of the matrix A.

To find the column rank of an arbitrary $m\times n$ matrix A, we begin in the same way as when finding the row rank. First we use elementary row operations to reduce A to an echelon matrix E. But the relationship between the column spaces of A and E is far more subtle than between their row spaces; the reason is that elementary row operations generally do not preserve column spaces. (See Problem 36.)

To analyze this situation, let us denote by ${\mathbf{c}}_1,{\mathbf{c}}_2,\dots ,{\mathbf{c}}_n$ the column vectors of the original matrix A, and by ${\mathbf{c}}_1^{\ast },{\mathbf{c}}_2^{\ast },\dots ,{\mathbf{c}}_n^{\ast }$ the column vectors of the echelon matrix to which we have reduced A. Suppose that E has k nonzero rows. Then each column vector of E has the form ${\mathbf{c}}_j^{\ast }=(\ast ,\dots ,\ast ,0,\dots ,0)$ with $m-k$ final zeros. Hence the column space Col(E) is contained in ${\mathbf{\text{R}}}^k$ (considered as the subspace of ${\mathbf{\text{R}}}^m$ for which $x_{k+1}=\cdots =x_m=0$).

We are particularly interested in those columns of E that contain the nonzero leading entries in the nonzero rows of E. These k columns are called the pivot columns of E. The echelon matrix E has the general form

where $d_1,d_2,\dots ,d_k$ are the nonzero leading entries. Hence the k pivot column vectors of E look like

Because of the upper triangular pattern visible here, it should be apparent that the argument in Example 3 can be used to show that these k pivot vectors form a basis for Col(E). Thus the column rank of the echelon matrix E is equal to the number k of its nonzero rows, and hence is equal to its row rank.

Now comes the subtle part. We want to show that the column rank of the original matrix A also is k. Note first that the homogeneous linear systems

have the same solution set because the matrices A and E are equivalent. If $\mathbf{x}=(x_1,x_2,\dots ,x_n)$, then the left-hand sides in (9) are linear combinations of column vectors:

Because x satisfies either both or neither of the systems in (9), it follows that

if and only if

Hence every linear dependence between column vectors of E is mirrored in a linear dependence with the same coefficients between the corresponding column vectors of A. In particular, because the k pivot column vectors of E are linearly independent, it follows that the corresponding k column vectors of A are linearly independent. And because the k pivot column vectors of E span Col(E), it follows that the corresponding k column vectors of A span Col(A). Thus the latter k vectors form a basis for the column space of A, and the column rank of A is k. Consequently we have established the following method for finding a basis for the column space of a given matrix.

The fact that Algorithm 2 provides a basis for Col(A) consisting of column vectors of A itself (rather than the echelon matrix E) enables us to apply it to the problem of extracting a maximal linearly independent subset from a given set of vectors in ${\mathbf{\text{R}}}^n$.

We have seen that the row rank and the column rank of an echelon matrix E both equal the number of rows of E that are not all zeros. But if A is any matrix that reduces by row operations to the echelon matrix E, then—according to Algorithm 1—the row rank of A is equal to the row rank of E, while Algorithm 2 implies that the column rank of A is equal to the column rank of E. We therefore have the following fundamental result.

For instance, if A is a $5\times 7$ matrix and Row(A) is a 3-dimensional subspace of ${\mathbf{\text{R}}}^7$, then Theorem 3 tells us that Col(A) must be a 3-dimensional subspace of ${\mathbf{\text{R}}}^5$.

To see what an extraordinary theorem this is, think of a random $11\times 17$ matrix A, possibly printed by a computer that uses a random number generator to produce independently the 187 entries in A. If it turns out that precisely 9 (no more) of the 11 row vectors of A are linearly independent, then Theorem 3 implies that precisely 9 (no more) of the 17 column vectors of A are linearly independent.

The common value of the row rank and the column rank of the matrix A is simply called the rank of A and is denoted by rank(A). The rank of A provides a meaning for the number of irredundant equations in the homogeneous linear system

Indeed, the individual scalar equations in (11) correspond to the column vectors of the transpose matrix ${\mathbf{\text{A}}}^T$, whose rank r equals that of A (Problem 25). Then the r columns vectors of ${\mathbf{\text{A}}}^T$ that form a basis for $\text{Col}({\mathbf{\text{A}}}^T)$ correspond to the r equations in (11) that are irredundant; the remaining equations are linear combinations of these irredundant ones and hence are redundant.

The solution space of the homogeneous system $\mathbf{\text{Ax}}=\mathbf{0}$ is sometimes called the null space of A, denoted by Null(A). Note that if A is an $m\times n$ matrix, then Null(A) and Row(A) are subspaces of ${\mathbf{\text{R}}}^n$, whereas Col(A) is a subspace of ${\mathbf{\text{R}}}^m$. If $r=\text{rank}(\mathbf{\text{A}})$, then the r column vectors of A that form a basis for Col(A) correspond to the r leading variables in a solution of $\mathbf{\text{Ax}}=\mathbf{0}$ by Gaussian elimination. Moreover, we know from the algorithm in Section 4.4 that the dimension of the solution space Null(A) is equal to the number $n-r$ of free variables. We therefore obtain the important identity

for any $m\times n$ matrix A. For instance, if A is the matrix of Example 4 with rank 3 and $n=5$, then the dimension of the null space of A is $5-3=2$.

For another typical application of Equation (12), consider a homogeneous system of five linear equations in seven unknowns. If the $5\times 7$ coefficient matrix of the system has rank 3, so only 3 of the 5 equations are irredundant, then (because $n=7$) the system has $7-3=4$ linearly independent solutions.

If A is an $m\times n$ matrix with rank m, then Equation (12) implies that the system $\mathbf{\text{Ax}}=\mathbf{0}$ has $n-m$ linearly independent solutions. Thus $\text{rank}(\mathbf{\text{A}})=m$ is the condition under which the “conventional wisdom” about the relation between the numbers of equations, unknowns, and solutions is valid.

It follows immediately from Equation (10) and the definition of Col(A) that the nonhomogeneous linear system $\mathbf{\text{Ax}}=\mathbf{b}$ is consistent if and only if the vector b is in the column space of A. In the problems below we outline some of the applications to nonhomogeneous systems of the results in this section.

If we can find a single particular solution ${\mathbf{x}}_0$ of the nonhomogeneous system

then the determination of its solution set reduces to solving the associated homogeneous system

For then Problem 29 in Section 4.2 implies that the solution set of (13) is the set of all vectors x of the form

where ${\mathbf{x}}_h$ is a solution of (14). Hence if ${\mathbf{x}}_1,{\mathbf{x}}_2,\dots ,{\mathbf{x}}_r$ is a basis for the solution space of (14), then the solution set of the nonhomogeneous system is the set of all vectors of the form

We may describe this solution set as the translate by the vector ${\mathbf{x}}_0$ of the r-dimensional solution space of the corresponding homogeneous system.