Every Spanning List Contains a Basis

A spanning list in a vector space may not be a basis because it is not linearly independent. Our next result says that given any spanning list, some (possibly none) vectors in it can be discarded so that the remaining list is linearly independent and still spans the vector space.

Every spanning list contains a basis.

Every spanning list in a vector space can be reduced to a basis of the vector space.

Proof. Suppose $v_1,\dots ,v_n$ spans $V$. We want to remove some of the vectors from $v_1,\dots ,v_n$ so that the remaining vectors form a basis of $V$. We do this through the process described below.

Start with $B$ equal to the list $v_1,\dots ,v_m$.

Step 1: If $v_1=0$, then delete $v_1$ from $B$. If $v_1\ne 0$, then leave $B$ unchanged.

Step k: If $v_k$ is in $\text{span}(v_1,\dots ,v_{k-1})$, then delete $v_k$ from the list $B$. If $v_k$ is not in $\text{span}(v_1,\dots ,v_{k-1})$, then leave $B$ unchanged.

Stop the process after step $n$, getting a list $B$. This list $B$ spans $V$ because our original list spanned $V$ and we have discarded only vectors that were in the span of the previous vectors. The process ensures that no vector in $B$ is in the span of the previous ones. Thus $B$ is linearly independent, by the linear dependence lemma. Hence $B$ is a basis of $V$. $■$