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.


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.