> [!NOTE] Lemma (Can choose basis from spanning set of FDVS) > Let $V$ be a [[Finite Dimensional Real Vector Space|finite dimensional, real vector space]] such that $V \neq \{ 0_{V} \}.$ Suppose $S=\{ v_{1},\dots,v_{s} \}$ is a [[Spanning Set of Real Vector Space|spanning set]]. Then there is a subset $\mathcal{B} \subset S$ that is a [[Basis of a Real Vector Space|basis]] of $V.$ Moreover, if $\mathcal{L}\subset S$ is a [[Linearly Independent Subset of Real Vector Space|linearly independent subset]], then we may choose $\mathcal{B}$ to contain $\mathcal{L}.$ **Proof**: Let $B \subset S$ be a maximal linearly independent subset of $S$ that contains $L$. It certainly exists, since $L$ is linearly independent. Suppose $B$ does not span $S$. Then there must be some $v_{j}$ that is not in $\langle B \rangle$. The set $B \cup \{ v_{j} \}$ is linearly independent by [[Linear Independence#^c97b84|span of linearly independent set lemma]], which contradicts the maximality of $B$. **Proof (by Algorithm)**: WLOG suppose $L=\{ v_{1},\dots,v_{r} \}$ for some $r\geq 0$. Set $B=L$. Consider $v_{j}$ for $r+1\leq j\leq s$. If $v_{j}$ lies in the span of $B$ discard it, else if $v_{j}\not\in \langle B \rangle$, set $B:=B \cup \{ v_{j} \}$ which is linearly independent by [[Span of Linearly Independent Subset of Real Vector Space is Strongly Minimal]]. If $j<s$, continue with $v_{j+1}$. This process stops when $j=s$. The resulting $B$ is linearly independent by construction, and it spans trivially: each $v_{j}$ that we discarded was a linear combination of other $v_{i}\in B$.