Suppose one has an matrix $A$ with $c$ columns and $r$ rows with entries in the binary field $GF(2)$. One wants to determine
- its rank, and
- a basis for its null-space.
These can be computed easily in time $O(r^2 c)$ by Gauss elimination, but that is a very sequential algorithm.
Are there deterministic parallel (NC, polylogarithmic time, polynomial space) algorithms to compute these?
One may be able to assume that either $r$ or $c$ is small (maybe polylogarithmic) if it helps.