0
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks for this suggestion. However, a couple things are not clear to me: What is the complexity of each enumeration step of this algorithm? Does this algorithm prevent repetitions of the same matrix? $\endgroup$
    – Kleo
    Aug 9, 2022 at 7:47
  • $\begingroup$ 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. $\endgroup$ Aug 9, 2022 at 8:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.