How to complete a set of independent vectors to a basis of a subspace?

$\newcommand{\Span}{\operatorname{Span}}$Let $V$ be a vector such that $\dim V = n$, and let $v_1,\ldots,v_k \in V$ be independent vectors such that $1<k\leq n$. Now Let $w_1,\ldots,w_r\in$ $\Span\left\{ v_1,\ldots,v_k \right\}$ be independent vectors such that $1\leq r <k$.

My question is this: How do I find the missing vectors $w_{r+1},\ldots,w_k\in \Span\left\{ v_1,\ldots,v_k \right\}$ so that $\Span\left\{w_1,\ldots,w_r,w_{r+1},\ldots,w_k\right\} = \Span\left\{ v_1,\ldots,v_k \right\}$ ?

Now I know they exist, I just don't know how I actually find them.

For example: Lets look at $\mathbb{R}^5$ and $$U=\Span\left\{ \begin{pmatrix} 5\\2\\3\\7\\3 \end{pmatrix},\begin{pmatrix} 2\\4\\4\\8\\1 \end{pmatrix} ,\begin{pmatrix} 3\\4\\7\\6\\1 \end{pmatrix},\begin{pmatrix} 5\\8\\6\\4\\8 \end{pmatrix} \right\}$$

Those are all independent vectors. Now lets take $2$ independent vectors that are linear combination of those. lets say, $$w_1 = \begin{pmatrix} 6\\2\\11\\15\\-3 \end{pmatrix} \; w_2=\begin{pmatrix} 0\\4\\-2\\12\\1 \end{pmatrix}$$ How can we complete those two vectors to form a basis of $U$ ?

I would really like to understand the general idea of this. This is actually a general question of something I need it for, which is the process of finding a Jordan basis for matrices\transformations.

Thanks for any help

Here's one method for the case of $V = \Bbb R^n$: row-reduce the matrix $$\pmatrix{w_1 & \cdots & w_r & v_1 & \cdots & v_k}$$ The columns of this matrix that eventually become pivot columns are precisely those which are linearly independent to the preceding columns. It suffices, then, to take these columns to form your basis.

• Hey thanks for your answer. I don't think I quite understand what you meant here, but here is the the row-reduced matrix of $\begin{pmatrix}w_{1} & w_{2} & v_{1} & v_{2} & v_{3} & v_{4}\end{pmatrix}$ as in the example: $$\begin{pmatrix}1 & & & & 0 & -1\\ & 1 & & & -\frac{1}{2} & -1\\ & & 1 & & 0 & 1\\ & & & 1 & \frac{3}{2} & 3\\ 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$$How should I go on ? – Jon Dec 26 '16 at 20:03
• @Jon in the row-reduced matrix, the 1st, 2nd, 3rd, and 4th columns have pivots (leading $1$s). Correspondingly, we take the 1st, 2nd, 3rd, and 4th columns of the original matrix to make our basis. That is, the set $\{w_1,w_2,v_1,v_2\}$ is a basis of $V$. – Omnomnomnom Dec 26 '16 at 20:15
• Amazing! Thank you very much =) – Jon Dec 26 '16 at 20:21

Write $w_1,w_2$ as a linear combination of $\mathcal{B} = (v_1,v_2,v_3,v_4)$ and put the coefficients as the first two columns of a $4 \times 4$ matrix:

$$A = \begin{pmatrix} [w_1]_{\mathcal{B}} & [w_2]_{\mathcal{B}} & ? & ? \end{pmatrix}.$$

Fill the third and fourth columns of $A$ in any way you want as long as the resulting matrix will be invertible (you can check it with the determinant or in many other ways - the most comfortable way will depend on the specific form of $A$ you get). Then define $w_3$ as a linear combination of the $v_i$ using the third column and similarly for $w_4$. This guarantess that $(w_1,w_2,w_3,w_4)$ will form a basis of $U = \operatorname{span} \mathcal{B}$ and any basis of $U$ in which the first two elements are $w_1,w_2$ is obtained in this way.

This also generalizes in the obvious way to the case $r < k \leq n$.

• Hey thanks for your answer. Well I guess that returns me to the same question. How would I fill those 3rd and 4th columns in such a way that A would be invertible? – Jon Dec 26 '16 at 19:36
• @Jon: Well, that depends on the first two columns. For example, if the upper-left $2 \times 2$ matrix is invertible, you can put zeros in the upper-right $2 \times 2$ matrix and $I_2$ in the lower-right $2 \times 2$ matrix. Then you'll get a lower-triangular matrix which must be invertible. If not, you'll need to play with it some more. Also, any "random" choice will work (with probability $1$). The point is that in any homework question like this I've ever seen in which the students were expected to solve the problem without using a computer, it was possible to complete the columns by – levap Dec 26 '16 at 19:59
• applying heuristics like the one I described. If you want an algorithm that always works (for example, if you want to write a code that does it), then it is better to take the row/column reduction approach. – levap Dec 26 '16 at 20:00
• Thanks, I see what you mean. Its true that eventually the matrices we get are at most 5x5, but also I wanted to look for an algorithm as you mentioned which could help me with that. How could I use the row/column reduction approach? – Jon Dec 26 '16 at 20:09

If I have correctly understood the question: you choose a vector of $v_i \in Span\{v_1, ..., v_k\}$, check if it is linearly independent from $w_1$ and $w_2$, then solve the system $\alpha w_1 + \beta w_2 + \gamma x = v_i$, where $x = (x_1, ..., x_n)$ is your new vector in $Span\{w_1,...,w_k\}$. Now, repeat.

• Thanks for your answer. I was looking for a more effective way than just choosing random vectors from Span$\left\{ v_1,\ldots,v_k \right\}$ and hoping they would be independent with $w_1,w_2$. – Jon Dec 26 '16 at 19:28
• @Jon you can find what $e_i = (0, ...1_i, ..., 0) \in Span\{v_1,...,v_k\}$, so you can choose with less difficult a vector probably indipendent from $w_1$ and $w_2$, but I don't remember now a way without a random choice. – Luigi Dec 26 '16 at 19:44
• So let me see if I have understood you right. First you suggest that ill check which of $e_1,\ldots,e_n$ belongs to Span$\left\{ v_1,\ldots,v_k \right\}$, and after that I should check which one of them is not dependent on $w_1,\ldots,w_r$ ? – Jon Dec 26 '16 at 19:49
• @Jon Yes, the vectors with more zeros are easier to use, but you still have to choise the best $e_i \in Span\{V\}$ "randomly", without a technique to know if it will be independent on $w_1$ and $w_2$ – Luigi Dec 26 '16 at 20:03