Let be given positive integers $m,n,r$, with $r \leq \min(m, n)$, and a finite field of $q$ elements $\mathbb{F}_q$.
I'm looking for an efficient algorithm to enumerate (i.e., generate one by one) all the $m \times n$ matrices over $\mathbb{F}_q$ that have rank equal to $r$.
One obvious solution is to enumerate the matrices over $\mathbb{F}_q$ and to test if each of them has rank equal to $r$, so the complexity of each enumeration step is $O(mn^{\omega-1})$, where $\omega$ is the exponent of matrix multiplication (i.e., multiplying two $n \times n$ matrices has complexity $O(n^{\omega})$).
However, I think that more efficient algorithm should exist. For example, if the matrices are enumerated using some kind of Gray code, then each matrix $M$ and the next matrix $M^\prime$ differ only by one entry. Therefore, it might be possible to compute the rank of $M^\prime$ in a more efficient way, by somehow using the previous computation of the rank of $M$.
Thanks for any help/reference.