Why is the basis for the column space of a matrix $A$ merely the columns that which have pivots in $\operatorname{rref}(A)$?

Question

From my knowledge, the column space of a matrix is the vector space that is spanned by the column vectors of that matrix. From my lectures, I've been told to find a basis of the column space of a matrix (unless I've forgotten) by analog to finding a basis for the row space of a matrix, which would be to reduce the matrix $A^\sf T$ to row echelon form and note which rows have non-zero entries, just as similarly you would do for a basis of the row space—convert $A$ to row echelon form and take the rows that are non-zero.

But apparently, and which I find easier, a column space basis can be found by merely noting which columns in $\operatorname{rref}(A)$ have a pivot, and then taking the original columns of $A$ as the basis for the column space. This doesn't make much intuitive sense to me. Why is this the case?

Answer 1

[I’m sure that this must have been answered before, but a quick scan of the related questions at right didn’t turn up anything that addressed this particular point.]

Elementary row operations correspond to left-multiplication by particular invertible square matrices called elementary matrices. Thus, if $R$ is the rref of $A$, then $R=E_k\cdots E_2E_1A=SA$ for some invertible square matrix $S$. The column space of $R$ is obviously spanned by its pivot columns, which consist of a $1$ in some slot and zeros everywhere else. To find a basis for the column space of $A$, we need to let $S^{-1}$ act on the column space of $R$, but since each column of $R$ is the image under $S$ of the corresponding column of $A$, the images of $R$’s pivot columns under $S^{-1}$ are the corresponding columns of $A$. $S$ has full rank, so these columns are linearly independent and the rank-nullity theorem tells us that they form a basis for $C(A)$.

I’ll add here that finding a basis for the column space of $A$ by computing the rref of $A^T$ (eqv. column-reducing $A$) usually results in a “nicer” basis than the one you get by picking out a set of linearly-independent columns of $A$.