# Enumerating (i.e. generating one by one) matrices of given rank over a finite field

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.

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), 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.
• At each step (well, at some steps), you need to check whether a certain rows belongs to a certain subspace. I suggest to support the semi-unitriangular basis of this subset, then this is checked in $O(m)$ time. Yes, all matrices are enumerated once by the construction. Aug 9, 2022 at 8:04