2
$\begingroup$

I have studied linear algebra for 2 months now and i cannot understand a task that i am currently trying to solve. Basically i am trying to find the amount of bases for n-dimensional vector space over a field with q elements. Let's call our Vector base V. Because it is field with q elements, i know that 0 is in V.

Now i think that if we make a vector out of all basis vectors and because they are linearly independent , from this i gather that every row should have atleast 1 element that is nonzero. Also it should be able to do simple matrix operations so that nonzero elements appear only on main diagonal. From this i should have a matrix that looks like this: \begin{pmatrix} a_1 & 0 & 0 & \cdots & 0 \\ 0 & a_2 & 0 & \cdots & 0 \\ 0 & 0 & a_3 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & a_n \end{pmatrix} So for choosing $a_1$ i have $q^n-1$ choices, because i swap nonzeros with random elements from V, for $a_2$ i have $q^n-q$ choices, and so on until for $a_n$ where i don't have any choices, this gives me $(q^n-1)(q^n-q)(q^n-q^2)*...*(q^n-q^(n-1))$ choices. ( extra question are $a_i$ = 1 or are they just some numbers , i wasn't sure about that.

But from what i researched from here and the web i found this place http://cameroncounts.wordpress.com/2011/07/20/the-field-with-one-element/ , this is wrong, and i should be getting Gaussian coefficent $Gauss(n,k)_q$ ,but i just cannot understand where the denominator part comes from ... Also what is k in this equation ???

For n = 2 and q = {0,1} i tried manually and i got 3 different bases 1) {0,1} and {1,0} 2) {1,1} and {1,0} 3) {1,1} and {0,1} , but my equation gives me answer 6, but it should be 3, i found somewhere also that the denominator should be $n!$, that seems to work for n = 2 and q = 2.

If you answer, try to use beginner like language sinse i've only studied Algebra 2 months( vector bases 1 week ) and never used Gaussian coefficent.

$\endgroup$
2
$\begingroup$

We will find the number $N$ of ordered bases, that is, of sequences $v_1,v_2,\dots,v_n$ of vectors such that $\{v_1,v_2,\dots,v_n\}$ is linearly independent. Then the number of ordinary (unordered) bases is $\frac{N}{n!}$.

We can assume that our vector space is the space $F^n$ of all $n$-tuples with elements in our field $F$, since any $n$-dimensional space over $F$ is isomorphic to $F^n$.

The first vector $v_1$ can be any of the $q^n-1$ non-zero vectors.

The second vector $v_2$ can be any of the $q^n$ non-zero vectors, except for the multiples of $v_1$. There are $q$ multiples of $v_1$, so for each choice of first vector, there are $q^n-q$ choices of second vector. Thus if we our constructing our basis sequentially, there are $(q^n-1)(q^n-q^2)$ ways to choose the first two vectors.

For every choice of $v_1$ and $v_2$, the third vector $v_3$ can be any vector except for the linear combinations of $v_1$ and $v_2$. Since $v_1$ and $v_2$ are linearly independent, there are $q^2$ such linear combinations. So for each choice of $v_1$ and $v_2$, there are $q^n-q^2$ choices for $v_3$.

Continue. At the end, we find that for every choice of $v_1,v_2,\dots, v_{n-1}$ there are $q^n-q^{n-1}$ choices for $v_n$, and therefore $$N=(q^n-1)(q^n-q)(q^n-q^2)\cdots(q^n-q^{n-1}).$$ We conclude that the number of (unordered) bases is $$\frac{(q^n-1)(q^n-q)(q^n-q^2)\cdots(q^n-q^{n-1})}{n!}.$$

$\endgroup$
  • $\begingroup$ Thanks , very good and clean answer. $\endgroup$ – La'tel Apr 10 '14 at 6:18
  • $\begingroup$ You are welcome. $\endgroup$ – André Nicolas Apr 10 '14 at 6:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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