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.



Enumerating (i.e. generating one by one) matrices of given rank over a finite field
You may fix an ordering of $\mathbb{F}\_q^n$ (like lexicographic or which you prefer), then start the following: choose the first row, then choose the second etc. Denote by $r(i)$ the dimension of the span of the first chosen $i$ rows; also let $B(i)$ be (some) set of linearly independent rows between the first $i$ rows. If $r(i)<r$, choose the next row arbitrarily and modify $r(i)$, $B(i)$ accordingly.


If $r(i)=r$ for the first time, proceed with linear combinations of the rows from $B(i)$ (they are in the natural bijection with $\mathbb{F}\_q^r$, so you have some order pre-chosen there).


This enumerates all matrices of rank at most $r$. If you need rank exactly $r$, you must also assure that $r(i)+n-i\geqslant r$ on all steps.


