Let $V$ be a $n$-dimensional vector space over $\mathbb{F}_p$ and let $W$ be a $k$-dimensional subspace. What's the most efficient way to algorithmically write down a basis for each distinct subspace $W_1$ such that $V = W \oplus W_1$ ?
Using the same idea behind $q$-binomials, I think I have the number of such subspaces:
$$ \frac{(p^n - p^k)(p^n-p^{p^k+1})\ldots(p^n - p^{n-1})}{(p^{n-k} - 1)(p^{n-k}-p)\ldots(p^{n-k}-p^{n-k-1})}$$
That same idea gives a pretty clear idea about how to pick a basis. Except that I can't tell without computing the span of a basis (Which is expensive, computationally) whether I've already seen this subspace before. So I'm searching through $(p^n - p^k)(p^n-p^{p^k+1})\ldots(p^n - p^{n-1})$ elements. Even for $p=2$, $n=8$ and $k=4$, this is a really, really big number.
Is there a better way to list all such subspaces?
I would do this as follows (if I understood the problem correctly). I will use the fact that the group $GL_n(\Bbb{F}_p)$ acts transitively on the set of $k$-dimensional subspaces.
So assume first that $W=W_0=$ the span of $e_{n-k+1},e_{n-k+2},\ldots,e_n$, where $e_i$ is the vector in $\Bbb{F}_p^n$ with $1$ in position $i$ and zeros elsewhere. Consider then a complementary subspace $W_1$. Let $A$ be a $(n-k)\times n$ matrix such that $W_1$ is its row space. So we require that $A$ has full rank, and that $W_1$ intersects with $W_0$ trivially. Next we use the fact that replacing $A$ with a row equivalent matrix does not change its row space, so w.l.o.g. we can assume that $A$ is in reduced row echelon form. But the row space of $A$ must not contain any vectors with $n-k$ leading zeros, because then $W_1\cap W_0$ would be non-trivial. This forces $A$ to have its leading $1$s in columns $1$ thru $n-k$. In other words $A$ looks like $$ A=(I_{n-k}\ |\ *), $$ where $*$ denotes an arbitrary $k\times(n-k)$ block.
But a different choice of the $*$-block gives rise to a different subspace $W_1$. This means that we have solved the problem in the case $W=W_0$:
Now we move on to the general case of $W$ being an arbitrary $k$-dimensional subspace. Let $v_{n-k+1},v_{n-k+2},\ldots,v_n$ be a basis of $W$ (any will do, just pick one). Complete that to a basis $v_1,v_2,\ldots,v_{n-k+1},v_{n-k+2},\ldots,v_n$ of all of $\Bbb{F}_p^n$. Form the matrix $M$ that has the vectors $v_1,v_2,\ldots,v_n$ as its rows. Let $A_1,A_2,\ldots, A_\ell$ be the $\ell=p^{k(n-k)}$ matrices we generated above. Form the $(n-k)\times n$ matrices $$ B_i=A_iM, i=1,2,\ldots,\ell. $$ A desired set of bases, one for each complementary subspace $W_1$, is then formed by the rows of the matrices $B_i$. In other words, the task is completed.
What happened in the end? Multiplication by $M$ (from right) is an invertible linear mapping $f:\Bbb{F}_p^n\to\Bbb{F}_p^n$. It has the key property that $f(W_0)=W$. Because $f$ is bijective, any complement $W'$ of $W_0$ has the property that $f(W')$ is a complement of $f(W_0)=W$. Conversely all the complements of $W$ are of this form, again because $f$ is invertible.