Extending a set of vectors to a basis by picking from a given basis

Question

I have a linear independent set ${\cal K}=\{v_1,\dots,v_{k-d}\}\subset\mathbb{R}^k$. I'd like to find $\cal W=\{w_1,\dots,w_d\}$ such that $\cal K\cup W$ is a basis for $\mathbb{R}^k$. To do this, put any basis $B=\{B_1,\dots,B_k\}$. Note that $A=[K\quad B]$ has rank $k$, where $K$ and $B$ is the matrix with columns from $K$ and $B$, respectively. I am sure that, by elementary columns operation, we can get a matrix $A^\prime=[K\quad C\quad 0]$ where $C$ has rank $d$. But, how can I prove it mathematically. Thanks in advance

Answer 1

$\DeclareMathOperator\span{span} \newcommand\R{\mathbb R} $Since $\span B=\R^k$ and $\span\mathcal K \nsubseteq \R^k$ there is a $w_1\in B$ such that $w_1\notin\span\mathcal K$. Then $\mathcal K\cup\{w_1\}$ is linearly independent and spans a subspace of dimension $(k-d+1)$. Iterate this procedure $d$ times to obtain a basis of $\mathbb R^k$ of the form $\mathcal K\cup\mathcal W$.

To do this start as you suggested with the matrix $$(\ K\ |\ B\ )$$ and do row operations to obtain $$ \left( \matrix{E_{k-d}\\0} \ \Bigg|\ B'\right). $$

Now you see immediatly which column of $B'$ is not the span of $K'=\pmatrix{E_{k-d}\\0}$, the same column of $B$ (namely $w_1$) is not in the span of $\mathcal K$. Without loss of generality this is the first column of $B'$ (otherwise swap columns) so you can again perform row operations to obtain $$ \left( \matrix{E_{k-d+1}\\0} \ \Bigg|\ B''\right), $$ where you can now find a column of $B''$ not in the span of $K''=\pmatrix{E_{k-d+1}\\0}$. The corresponding column $w_2$ of $B$ is not in the span of $\mathcal K \cup \{w_1\}$. Proceed until you reach $E_k$.

To summarize, reduce $(\ K\ |\ B\ )$ to $(\ E_k\ | *\ )$ by only performing row operations and swapping columns right from $K$, keep track of column numbers to read of your basis in the end.

You can do the same procedure a little faster by just getting to upper triangular matrices instead of $E_i$ in each step, since this is enough to read of what is in the span and what isn't.