Extracting a Basis from a Spanning Set

The theorem of existence of bases tells us that any set that spans a Vector Space has some subset that forms the Basis of that vector space.

We can extract that basis by representing the vectors using matrices.

Let $V_{\mathbb{F}}^n$ be a vector space, and let $S_k=\{{\vec{v}}_1,{\vec{v}}_2,\dots {\vec{v}}_k\}|{\vec{v}}_{1\dots k}\in V^n$ be the spanning set of $V_{\mathbb{F}}^n$. I.e.

$$V_{\mathbb{F}}^n=\text{span}(S_k)$$

Method 1: Vectors as Columns §

1. Create a matrix, $\mathbf{A}$ of size $n\times k$, using ${\vec{v}}_{1\dots k}$ as column matrices:

$$\mathbf{A}=[{\mathbf{v}}_1,{\mathbf{v}}_2,\dots {\mathbf{v}}_{\mathbf{k}}]$$

$$\mathbf{A}=\left[\begin{array}{cccc}{{\mathbf{v}}_1}_1& {{\mathbf{v}}_2}_1& \dots & {{\mathbf{v}}_k}_1\\ {{\mathbf{v}}_1}_2& {{\mathbf{v}}_2}_2& \dots & {{\mathbf{v}}_k}_2\\ \dots & \dots & \dots & \dots \\ {{\mathbf{v}}_1}_n& {{\mathbf{v}}_2}_n& \dots & {{\mathbf{v}}_k}_n\end{array}\right]$$

2. Use Gaussian Elimination to reduce $\mathbf{A}$ to Row Echelon Form, denoted by ${\mathbf{A}}_{REF}$

$$\mathbf{A}\sim {\mathbf{A}}_{REF}$$

3. The columns with leading entries in ${\mathbf{A}}_{REF}$ are the same column vectors in the original matrix $\mathbf{A}$. These column vectors form the basis of $V_{\mathbb{F}}^n$

This method returns a subset of the original spanning set, $S_k$

Method 2: Vectors as Rows §

1. Create a matrix, A of size k × n using the vectors as row matrices
2. Again, use gaussian elimination to row-reduce A to ${\mathbf{A}}_{REF}$

$$\mathbf{A}\sim {\mathbf{A}}_{\mathbf{REF}}$$

3. The non-zero rows of ${\mathbf{A}}_{REF}$ return the vectors in the basis of $V_{\mathbb{F}}^n$

This method gives a basis that will usually not be a subset of the original set of vectors. It works because elementary row operations do not change the subspace spanned by the rows, and in the row echelon form the non-zero rows are linearly independent.