Align basis of vector space with that of subspace Suppose I have two real vector spaces $V,S\subset\mathbb{R}^n$ and $S\subset V$. Say the dimension of $V$ is $l$ and that of $S$ equals $m<l$. They are given in terms of their basis vectors $v_i, i=1,\ldots,l$ and $s_i,i=1,\ldots,m$ (as results of the computation of the nullspace of two related homogeneous systems). I want to find a new basis of $V$ such that it reads $\{s_i\mid i=1,\ldots,m\}\cup \{w_i\mid i=m+1,\ldots,l\}$. In other words: how can I systematically compute $w_i,i=m+1,\ldots,l$, which are linearly independent of the basis of $S$. Naively, I would simply solve the linear system $v_i=a_1 s_1 + \cdots + a_m s_m$ for each $v_i$ and discard it (as a basis vector of $V$) if this homogeneous system has a non-trivial solution (to see if it is linearly independent). The set of discarded vectors would then be replaced by the basis of $S$. But, since the algorithm is to be implemented in a computer code, I wonder if this is the most clever solution and if there are flaws. Note that numerical stability is not an issue here. The basis vectors shall all have integer elements.
 A: You should not solve that linear system involving only the vectors $s_i$. Instead you should check that each candidate vector for $w_k$ is linearly independent of $s_1,\ldots,s_m$ and $w_1,\ldots,w_{k-1}$. Only then is it ensured that the vectors retained form a basis. Given this modification the method is sound.
From a practical point of view, you might want to replace the vectors $s_1,\ldots,s_m,w_1,\ldots,w_{k-1}$, maybe only for use in the test, by another sequence of vectors that span the same subspace, but are in echelon form: for each vector there is a coordinate position (its pivot position) where it is the last in the sequence to have a nonzero entry. Then for any candidate vector $v_i$, you first clear, from left to right for the vectors already in the sequence, the coordinate of $v_i$ that is in its pivot position (by adding a multiple of that vector). After all these coordinates have been cleared the new vector, as well as the original $v_i$, is linearly independent of the retained vectors if (and only if) the new vector is nonzero. If this is the case $v_i$ can be retained, and the new vector is ready to join the vectors in echelon form, with the position of any chosen non-zero entry (for instance the first one) as its pivot position.
A: Use the Gram-Schmidt algorithm, with the basis vectors of $S$ as your first $m$ inputs.  You will end up with $l-m$ zero vectors, but just discard them.
