1
$\begingroup$

Suppose I want to find the rank of an $m \times n$ matrix $A$ over $GF(2)$, where $m \ll n$. The algorithms for rank in the literature seem to be focused on the case when $m = n$, giving a time complexity of $O(log^2 n)$ and $n^{4.5}$ processors. Are there better algorithms known when $m$ and $n$ are very different? I am thinking that $m \approx \text{polylog}(n)$.

In the case when $m = c \log n$, then one can simply exhaust over all $2^m$ subsets of the rows of $A$, and this is actually more efficient than Gauss elimination.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.