Most efficient way to find distinct complementary subspaces over a finite field 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?
 A: 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$:


*

*Write down all the $p^{k(n-k)}$ matrices $*$

*Augment each and every one of those with the $I_{n-k}$-block to form a matrix $A$

*The rows of any such matrix $A$ form a basis of one possible complementary subspace $W_1$. Different choices of the $*$-block correspond to different choices of $W_1$.


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.
