Algorithm to extend a linearly independent set with unit vectors

Question

Consider a set $S$ of linearly independent vectors in $\mathbb{R}^n$. I want to show that not only I can extend $S$ into a basis of $\mathbb{R}^n$, but I can always do so by adding unit vectors of the form $(0,\ldots,0,1,0,\ldots,0)$.

Intuitively, this property seems clear in two or three dimensions. But how can I prove it in general?

Answer 1

Something more general is true: Let $S$ be an linearly independent subset of a vector space $V$ (of say finite dimension over a field $k$), and $B$ is a basis of $V$, then there exists a subset $A\subset B$ such that $S\cup A$ is a basis of $V$.

We do induction on $\dim V-|S|$. When this is $0$, $S$ is already a basis, hence we may choose $A=\emptyset$.

As for the inductive step, since $\dim V-|S|>0$, the linear span of $S$ is not the entire space $V$, in particular there exists $e\in B$ such that $e$ is not a linear combination of vectors from $S$, therefore $B\cup\{e\}$ is linearly independent. Now by induction hypothesis, we can choose $A'\subset B$ such that $B\cup\{e\}\cup A'$ is a basis of $V$, hence we may let $A:=A'\cup\{e\}$ to finish the business.

With the help of Zorn's lemma, we can actually elimiate the finiteness of dimension in the proposition, but the proof becomes less constructive and instructive.

This also produces an algorithm: Given $S$ and $B=\{e_1, \cdots, e_n\}$, for each $e_i$, test whether it is in the linear span of $S$, if so continue, otherwise update $S:=S\cup\{e_i\}$, and eventually you'll get $S$ to be a basis of $V$.

Answer 2

If $S$ already has $n$ vectors, then it's already a basis and you can't extend it. Consider the standard basis of unit vectors $(\epsilon_1,\ldots,\epsilon_n)$. If $|S|<n$, then there exists at least one $\epsilon_i$ such that it's not in the span of $S$. If all $\epsilon$'s were spanned by $S$, then $S$ would also span $\mathbb{R}^n$, i.e. $S$ would be a basis - contradiction.

So now you get $S\cup\epsilon_i$ which is again a set of independent vectors. If $|S\cup\epsilon_i|=n$, you're done. If not, repeat the process till you get the union (whose cardinality is $n$) of $S$ and a bunch of $\epsilon$'s.

Answer 3

You can use the fact that elementary row operations on a matrix do not change column dependencies. Suppose $S$ has $k$ vectors in it. Put the vectors of $S$ into the first $k$ columns of a matrix, $M$; and then put in the standard basis vectors of $\mathbb{R}^n$ as the next $n$ columns of the matrix (so the matrix will have dimensions $n\times(n+k))$.

Here is what the starting matrix looks like

$$M= \left[\begin{array}{cccc|cccc} \mid & \mid &...& \mid& \mid & \mid &...& \mid \\ \vec{s_1} & \vec{s_2} &...&\vec{s_k}& \vec{e_1}& \vec{e_2} & ... &\vec{e_n} \\ \mid & \mid &...& \mid& \mid & \mid &...& \mid \\ \end{array}\right] $$

Now use elementary row operations to bring this matrix to reduced row-echelon form. The columns with leading $1$s will correspond to columns of the desired basis, but with the basis vectors being columns from the original matrix. Columns that are dependent on previous columns will not have leading $1$s in them.