1
$\begingroup$

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!

  • 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.2012-04-06
  • 0
    @AndréNicolas: is there a fast way to determine whether a set is linearly independent?2012-04-06
  • 1
    For small collections, eyeballing usually works. For larger ones, use row reduction. The answer by Quimey says this.2012-04-06
  • 0
    @AndréNicolas: Okay, thanks :)2012-04-06
  • 0
    Please excuse my ignorance, but what is $\Bbb F^n_q$?2012-04-06
  • 0
    @DavidMitra The set of vectors of length $n$ with elements in the field $\mathbb{F}_q$2012-04-06

1 Answers 1

4

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

  • 0
    Awesome! Thanks <32012-04-06
  • 2
    +1 @badatmath, do observe that the same algorithm works with any field (e.g. the reals) in place of $\mathbb{F}_q$.2012-04-06
  • 0
    @JyrkiLahtonen Cool observation,2012-04-06