Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
2  
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
1  
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

1 Answer

up vote 4 down vote accepted

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$.

share|improve this answer
    
Awesome! Thanks <3 –  badatmath Apr 6 '12 at 17:50
2  
+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
    
@JyrkiLahtonen Cool observation, –  badatmath Apr 6 '12 at 21:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.