What is a basis?
A basis is the smallest set of vectors that spans a space. I like to think of it as the axes of a space, and we'll get to that in another post. So, for 3-space, the x-axis is the vector [1,0,0], the y-axis is the vector [0,1,0], and the z-axis is the vector [0,0,1].
Formal Definition
(i) $\mathcal{B}$ is a linearly indepedent set, and
(ii) the subspace spanned by $\mathcal{B}$ = H
Spanning Set Theorem
Now, imagine you have a set of vectors that you want to be a basis, but the set is linearly dependent. That is to say, one vector can be expressed as a linear combination of the others. That means that that vector is redundant; we don't need it, so we can remove it. The spanning set theorem says exactly this:
If one of the vectors is a linear combination of the remaining vectors in S, the set formed from S by removing that vector still spans H.
If H $\neq$ {0}, some subset of S is a basis for H. That pretty much just says that eventually, if you keep removing unnecessary vectors, you'll be left with your basis.
Bases for Nul(A) and Col(A)
Recall that Nul(A) is the null space of A, and Col(A) is the column space, or span of the columns of A. (see the previous post)
We previously calculated the basis of a null space, so look back to that. The number of vectors in that set equals the number of free variables.
Important Fact
Elementary row operations don't affect the linear independence of the columns of the matrix.
Theorem
The pivot columns of matrix A form a basis for Col(A).
Proof (more like a justification)
This isn't a full-on proof, but recalling our fact, if we look at a reduced matrix, if there are n pivots, n rows have pivots, and n columns have pivots. By the original TFAE, if there are n pivots, the space spans R^n. So, we need n vectors. The n pivot columns must be linearly independent, because they aren't linear combinations of what come before them.