Algorithm to (effectively) extend basis How do you (effectively) solve these two problems?
1) Extend the set $V=\{v_1,v_2, \ldots. v_m\}$ of $m$ linearly independent vectors to a basis of an $(m+n)$-dimensional space $S,\ \mathrm{dim}(S)<\infty$.
2) Extend the set $W=\{w_1,w_2,...w_m\}$ of $m$ orthonormal vectors to an orthonormal basis of $(m+n)$-dimensional space $S, \ \mathrm{dim}(S)<\infty$.
According to the first point I know only the strategy of picking up a random vector and checking, if that is linearly independent to the others. That means, creating a matrix and determining its' rank with Gauss. Still, if you do not have a standard basis, the procedure can become difficult. 
According to the second point I thought of Gram-Schmidt. But the problem is: applying the algorithm to some chosen vector I cannot guaranty that those produced vectors will be orthonormal to the remaining $m-1$. 
Any ideas?
 A: You already know how to get an orthogonal basis (Gram-Schmidt) from a basis, so I'll only address the first point. Randomness is indeed a good way to do this. If you've already got a set of vectors that you want to extend, a randomly chosen vector (e.g. chosen uniformly in the unit sphere, perhaps) is very unlikely to lie within the hyperplane spanned by your original collection. In fact, this would have probability zero (but on a numerical implementation, vanishingly small non-zero probability).
To see this, think geometrically. If we have one vector in $\mathbb{R}^2$, and you choose a random direction, what's the likelihood that it's parallel to the first vector? Pretty small, I hope you agree.

Another way to do this would be to take a small random perturbation of the vectors in your collection, for the same reasoning. The downside here is that you may end up with numerical instability later on, because vectors are almost aligned.
A: Others have addressed the orthonormal case. Here's how to do the regular.
Start with a known basis and use the basis exchange property. This is more effective than guess and check since that might not halt. For completeness here is a statement of the basis exchange property.
Thereom Let $A$ and $B$ be linearly independent sets. If $|A| < |B|$ Then there is a element $y \in B$ such that $A \cup \{y\}$ is linearly independent.
We start with $A$, the basis you wish to extend and $B$ the standard basis. It is the collection of $e_i$ (a vector which is zero for all entries except for the $i$th which is 1). Let $M_0$ be the matrix of your basis elements (each column is a member of $A$) if there is a $x$ such
that $M_0x = y$, then $y$ is contained in the span of $A$.
So test $M_ix = e_i$ for each $e_i$. If it has no solution then use $e_i$ to extend your basis, and define $M_{i+1}$ as the matrix $M_i$ with the additional column $e_i$.
A: This post is mainly a long comment.
This is about your comment regarding Gram-Schmidt procedure. You mentioned, "applying the algorithm to some chosen vector I cannot guaranty that those produced vectors will be orthonormal to the remaining $m−1$." Consider $\mathbf{x}$ be a randomly-chosen vector from S. If $\mathbf{x}$ is not linearly dependent on $w_1, w_2, \cdots, w_m$ then $$\mathbf{x}=\mathbf{y}+\sum_{i=1}^{m} c_i w_i.$$
Gram-Schmidt computes $\mathbf{y}$ (or $\frac{\mathbf{y}}{|\mathbf{y}|}$) which is orthogonal to $w_1, w_2, \cdots, w_m$. 
A: 1) Consider the span of $V$ as a subspace of $S$. If it is a proper subspace, then there is an element $v_{m+1}$ in $S$ that is not spanned by $V$. In this case, the set $V\cup\{v_{m+1}\}$ will be linearly independent. Continue this process until you have $m+n$ linearly independent vectors.
2) Use the technique from (1) and Gram-Schmidt.
