Finding basis for column space of matrix

To find a basis for the column space of a matrix one finds the RREF of the matrix. The columns in the RREF are not a basis for the column space, but the same columns in the original matrix are a basis.

I get that the rox space doesn't change under elementary row operations, and I can see (from examples) how the column space does change.

But I can't understand why one can just pick the columns in the original matrix when finding a basis for the column space. Is there a proof of this?

• Row reduction doesn't change the order of the columns. And the columns with the pivots in them are guaranteed to be linearly independent. To see this, get any matrix into RREF, then circle the pivots and start doing elementary column operations (keeping those same pivots circled) and you'll eventually get the matrix $$\pmatrix{I_{r\times r} & 0_{r\times(n-r)} \\ 0_{(n-r)\times r} & 0_{(n-r)\times(n-r)}}$$ At which point you'll notice the only nonzero numbers left are the pivots that you circled. See if you can construct a proof based on this observation. – user137731 May 18 '16 at 21:00

The column space is defined as the vector space generated by the columns, so surely the columns span this space. They need not be a basis of the column space, but you can always reduce to a basis by removing those columns that are linearly dependent on others.

• So how do I know that the linear independent columns in the RREF of the matrix give linearly independent columns in the original matrix? – John Doe May 5 '16 at 19:09
• The column space of the RREF is not the same as the column space of the original matrix, the dimension is however. This follows from the fact the one has that the row rang is the same as the column rang of a matrix. Notice that the row space remains the same during the Gauss algorithm. – Mathematician 42 May 5 '16 at 21:23