Welcome to our community

Be a part of something great, join today!

Problem of the Week #63 - August 12th, 2013

Status
Not open for further replies.
  • Thread starter
  • Moderator
  • #1

Chris L T521

Well-known member
Staff member
Jan 26, 2012
995
Here's this week's problem.

-----

Problem: Let $V$ be a finite-dimensional vector space over a finite field $\mathbb{F}_q$ of cardinality $q$. Let $\mathscr{B}$ be the set of ordered bases of $V$. Compute the cardinality of $\mathscr{B}$, as a formula involving $q$ and $\mathrm{dim}(V)$.

-----

Remember to read the POTW submission guidelines to find out how to submit your answers!
 
  • Thread starter
  • Moderator
  • #2

Chris L T521

Well-known member
Staff member
Jan 26, 2012
995
No one answered this week's question. You can find my solution below.

Let $B$ be any basis of $V$ and $d:=\dim V$. First choose a non-zero vector in $V$. Since every vector in $V$ can be written as a linear combination of elements in $B$ with coefficients in $\mathbb{F}_q$, there are $q^d-1$ nonzero vectors in $V$. Now assume we have chosen linearly independent vectors $v_1,v_2,\dots, v_n$ for $n<d$. Then $\#\mathrm{Span}\{v_1,\dots,v_n\}=q^n$, and there are $q^d-q^n$ choices for vectors not in the span of $v_1,\dots, v_n$. This process must continue until we have $\dim (V)=d$ linearly independent vectors. Therefore
\[\#\mathscr{B}=\prod_{i=0}^{d-1}(q^d-q^i).\]
 
Status
Not open for further replies.