Let be an -dimensional vector space over a field having basis and let be vectors in . Let be the matrix whose th column is the coordinates of expressed in terms of the ordered basis . Let be the reduced row echelon form of .

- Let be any matrix that is row equivalent to , and let be the elements of whose coordinates (in terms of the ordered basis ) are the columns of . Prove that if , then .
- Prove that the vectors whose -coordinates are the pivotal columns of are linearly independent, and that the vectors whose -coordinates are given by the nonpivotal columns of are linearly dependent on these.
- Prove that the vectors are linearly independent if and only if has nonzero rows.
- By part (3), the vectors are linearly dependent if and only if has nonpivotal columns. In this case, compute all of the linear dependencies among the .
- Prove that the dimension of the subspace spanned by is the row rank of . Prove also that the columns of corresponding to the pivotal columns of form a basis for .

- Say and are row equivalent via the invertible matrix – that is, . Now , so that for each . Now if , then , so that , and thus .
- Note that the pivotal columns of are a subset of , and thus are linearly independent. Moreover, any nonpivotal column has nonzero entries only in those rows containing a pivot; hence each of the nonpivotal columns of is linearly dependent on the pivot columns.
- Suppose the are linearly independent. Then by part (1) the columns of are linearly independent. By part (2), all columns of are pivot columns, and so the column rank (hence row rank) of is . Using this previous exercise, has nonzero rows.
Conversely, suppose has nonzero rows. Then the row rank (hence column rank) of is , so that the columns of are linearly independent. By part (1), the columns of are linearly independent.

- Using part (1), it suffices to find the linear dependencies among the columns of . To that end, let be the columns of (in order) and suppose . Letting , we have . We computed the solutions of this matrix equation here; in particular, we may choose the corresponding to nonpivotal columns of arbitrarily, and the corresponding to pivotal columns are then determined uniquely. Every such solution then gives a linear dependence among the columns of .
- Because the matrix carrying to is invertible, the span of the is the preimage of the span of the , and the preimage of a basis is a basis. In (2) we saw that the pivotal columns of are a maximal linearly independent set of columns of , and thus form a basis of the column space of . Hence the columns of corresponding to pivotal columns of form a basis of the column space of . In particular, the dimension of this subspace is the row rank (i.e. number of nonzero rows) of .

## Comments

“Moreover, any nonpivotal column has nonzero entries only in those rows not containing a pivot; hence each of the nonpivotal columns of A^\prime is linearly dependent on the pivot columns.”

Shouldn’t it be in those rows that do contain a pivot?

Indeed. Thanks!