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

[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$.