2

Let $\mathbb{K}$ be a finite field with $q$ elements and $V$ a $n$-dimensional $\mathbb{K}$-vectorspace.

  1. How many elements are in $V$?
  2. How many subsets of $V$ are a basis of $V$?

For the first question I reasoned that I have $n$ dimensions that I can fill up with $q$ different elements. So from a combinatorics standpoint $V$ should have a length of $q^n$.

For the second question I'm almost certain I'm wrong:

Let $\{a_1, a_2, \cdots a_n\}$ be a basis of $V$

I can multiply each of my basis vectors by $q-1$ different elements in $\mathbb{K}/\{0\}$ (excluding $0$ because multiplying a basisvector by zero nolonger makes it a basisvector) that alone yields $(q-1)^n$ different possibilities now for each one of these options I can take any of the $n$ vectors and add them to any of the other $(n-1)$ remaining vectors.

So in total there are $n(n-1)(q-1)^n$ subsets in $V$ that form a basis of $V$

I haven't done lots of combinatorics yet, so I would appreciate it if someone could help me out.

haifisch123
  • 325
  • Hmmm.. I think you have under-estimated the number of bases a bit. Do you agree that you would still need to prove "every basis can be obtained in this way from ${a_1, \dotsc, a_n}$" for this answer to be complete? A small hint is to try counting the number of "ordered bases", using a product argument, first. There are more details here. – Izaak van Dongen Mar 06 '24 at 17:33
  • Did you try with $\mathbb K:=\mathbb Z/3\mathbb Z(q=3)$ and $n=2$? – Stéphane Jaouen Mar 06 '24 at 17:34

1 Answers1

1

Let's first count ordered basis.

You can pick the first vector in the basis any way you want, as long as it's not the zero vector. That gives you $q^n-1$ possibilities.

The second vector should not be any of the $q$ multiples of the first vector. So that gives you $q^n-q$ possibilities.

The third vector should not be any of the $q^2$ linear combinations of the first two vectors ($q$ choices of scalars for each), so that gives you $q^n-q^2$ possibilities. And so on.

So that's the number of ordered bases. What about if we ignore order? How many times have we counted each un-ordered basis?

Arturo Magidin
  • 398,050