= Gaussian binomial coefficient counts finite-field subspaces
{c}
{title2=$\#\operatorname{Gr}(k,\mathbb F_q^n)=G_{n,k}(q)$}
For a <prime power> $q$ and $0\leq k\leq n$, count ordered lists of $k$ <linearly independent vectors> in $\mathbb F_q^n$. The first has $q^n-1$ choices. After $i$ independent choices, their <linear span> contains $q^i$ <vectors>, so the next has $q^n-q^i$ choices. Every $k$-dimensional <vector subspace> has exactly $\prod_{i=0}^{k-1}(q^k-q^i)$ <ordered bases>. Dividing the list count by this common multiplicity gives
$$
\#\operatorname{Gr}(k,\mathbb F_q^n)=\frac{\prod_{i=0}^{k-1}(q^n-q^i)}{\prod_{i=0}^{k-1}(q^k-q^i)}=G_{n,k}(q).
$$
The notation $\operatorname{Gr}$ refers to the <Grassmannian>, here considered simply as the finite collection of these <vector subspaces>.<Enumerative Combinatorics, Volume 1 (second-edition draft) by Richard Stanley>[§1.7, Proposition 1.7.2, pp. 63–64]{ref}
For $n=4,k=2,q=2$, there are $15\cdot14=210$ ordered independent pairs. Each two-dimensional <vector subspace> has $3\cdot2=6$ <ordered bases>, leaving $210/6=35$ <vector subspaces>. There are only $\binom42=6$ coordinate-selected <vector subspaces>; most of the 35 also contain <vectors> combining coordinates.
A unique <reduced row echelon form> gives another count. Its six possible pivot-column patterns have $4,3,2,2,1,0$ freely chosen entries. Each free entry lies in $\mathbb F_2$, giving $16,8,4,4,2,1$ <vector subspaces>, respectively. The diagram fixes the zero entries required to make each pivot the first nonzero entry in its row and the only nonzero entry in its column. Different choices describe different <row spaces>.
\Image[/gaussian-binomial-finite-field-subspaces.png]
{title=The six <reduced row echelon form> pivot patterns give 35 two-dimensional <vector subspaces> of $\mathbb F_2^4$}
{description=Original exact matrix-pattern enumeration. A star is a freely chosen <finite field> entry, while every displayed zero or one is fixed. Pivot columns are numbered from one in this image.}
Back to article page
