3
$\begingroup$

Imagine a 2-dimensional vector space in $\mathbb{Z} /2 \mathbb{Z}$. The only possible basis' are $ \left(\begin{array}{c} 1\\ 0 \end{array}\right), \left(\begin{array}{c} 0\\ 1 \end{array}\right); \left(\begin{array}{c} 1\\ 1 \end{array}\right), \left(\begin{array}{c} 0\\ 1 \end{array}\right);\left(\begin{array}{c} 1\\ 0 \end{array}\right), \left(\begin{array}{c} 1\\ 1 \end{array}\right)$

This means for n = 2 would 3 be the correct answer. For n = 1 the answer is 1.

What is the correct answer for a variable n?

  • 0
    I think this is related to http://en.wikipedia.org/wiki/Gaussian_binomial_coefficient2011-09-30

1 Answers 1

6

We can do the more general case for $F = \mathbb{F}_q$ for $q$ a power of a prime. The first vector can be chosen from $q^n - 1$ possible choices. The subspace generated by it has $q$ points, since each vector is determined by $q$ possible coefficients. Continuing we get the formula $(q^n - 1)(q^n - q)\cdots (q^n - q^{n-1})$. This is the number of ordered bases though, but we can just divide by $n!$ to get the number of unordered bases.

For instance in your case $q = 2^1 = 2$ and $n = 2$, so we get $(2^2-1)(2^2-2) = 3\times 2 = 6$ possibilities. To get your $3$ we just divide by $2!$. You could write the general formula to be

$(q^n - 1)(q^n - q)\cdots (q^n - q^{n-1})/n!$

  • 0
    It seems that the expression as a product of terms of the form (q^n-q^i) is already pretty elegant and simple, especially as it only involves the basic operations of arithmetic.2011-10-13