# How many different basis' exist for an n-dimensional vector space in mod 2?

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?

-
I think this is related to en.wikipedia.org/wiki/Gaussian_binomial_coefficient – Srivatsan Sep 30 '11 at 21:21

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!$
So your answer is $f(n,q) = \frac{1}{n!} \cdot \prod_{i=0}^{n-1} (q^n - q^i)$. Thanks. – Martin Thoma Oct 5 '11 at 8:15
Is this equal to $g(n,q) = \frac{1}{2} \cdot \binom {n^q}{n}$? – Martin Thoma Oct 5 '11 at 8:57
No. It just happens to work for $n=2,q=2$. Try $n=3,q=8$, and then $g(n,q)$ is much larger. You can see that these expressions don't have much hope of being equal because the second expression has a $n^q$ in it. – Jason Polak Oct 6 '11 at 18:11
guess there is no simpler way to write f(n,q) ... Wolfram|Alpha gave me some alternate forms, but they are by far more complex: wolframalpha.com/input/?i=1%2Fn%21+%28product_%28i%3D0%29^%28n-1%29+%282^‌​n+-+2^i%29%29 e.g. $$f(n,2) = \frac{2^{n^2} e^{2 i n π \lfloor \frac{1}{2}-\frac{Im(n) log(2)}{2 π} \rfloor} (2^{-n}, 2)_n}{n!}$$ – Martin Thoma Oct 8 '11 at 3:58