7
$\begingroup$

If I have an n-dimensional vector space over a field with q elements, how can I find the number of bases of this vector space?

$\endgroup$

1 Answer 1

20
$\begingroup$

There are $q^n-1$ ways of choosing the first element, since we can't choose zero. The subspace generated by this element has $q$ elements, so there are $q^n-q$ ways of choosing the second element. Repeating this process, we have $$(q^n-1)(q^n-q)\cdots(q^n-q^{n-1})$$ for the number of ordered bases. If you want unordered bases, divide this by $n!$.

$\endgroup$
3
  • 2
    $\begingroup$ I was wondering if this problem can be solved using matrices. As I see it, the number of bases in an n-dimensional vector space over the field q is equal to the number of non-singular nxn matrices over the same field. Is this correct? And if so then how can I get an equivalent formula using matrices? $\endgroup$ Apr 15, 2013 at 12:31
  • 1
    $\begingroup$ @Faz3r: Your observation is correct, but then to compute the number of non-singular matrices, the easiest thing to do is to compute the number of possible first columns, $q^n - 1$, and then given a choice for the first column to compute the number of possible second columns, $q^n - q$, and so on. Since the matrix is invertible, the first $k$ columns must have rank $k$ which is equivalent to saying that the $k$th column must not be in the span of the first $k-1$ columns. $\endgroup$ Apr 15, 2013 at 12:48
  • $\begingroup$ Okay, I think i get it now. Thanks! $\endgroup$ Apr 15, 2013 at 13:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .