# Extending a subset of $\mathbb{F}_q^n$ to a basis

So I have a linearly independent subset of $\mathbb{F}_q^n$ and I'm trying to extend it to a basis. I heard this can be done, but I can't find an algorithm for actually doing it. Can you help me?

Also, what if it wasn't a subset of $\mathbb{F}_q^n$, but rather an arbitrary vector space $V$?

Thanks!

-
Let $v_i$ be the vector all of whose coordinates are $0$ except the $i$-th coordinate, which is $1$. Take your linearly independent subset $S_0$. Test whether $S_0\cup\{v_1\}$ is a linearly independent set or not. If linearly independent, add $v_1$ to $S_0$, to get $S_1$. If not linearly independent, discard $v_1$. Continue to $v_2$. It may save time to do the requisite row reductions simultaneously. –  André Nicolas Apr 6 '12 at 17:44
@AndréNicolas: is there a fast way to determine whether a set is linearly independent? –  badatmath Apr 6 '12 at 17:48
For small collections, eyeballing usually works. For larger ones, use row reduction. The answer by Quimey says this. –  André Nicolas Apr 6 '12 at 17:50
@AndréNicolas: Okay, thanks :) –  badatmath Apr 6 '12 at 17:51
Please excuse my ignorance, but what is $\Bbb F^n_q$? –  David Mitra Apr 6 '12 at 18:13
show 1 more comment

The gaussian elimination algorithm might be useful. Take a look at here. If you put your vectors as rows of a matrix and you compute the echelon form you should add the vector $e_i$ if there is no row starting (with $1$) at column $i$.
+1 @badatmath, do observe that the same algorithm works with any field (e.g. the reals) in place of $\mathbb{F}_q$. –  Jyrki Lahtonen Apr 6 '12 at 17:56