Let $p$ be prime (of size roughly $100$, say). Suppose that $M$ is a matrix with coefficients in $\mathbf{F}_p$ with roughly $An$ rows and $n$ columns, where $A>1$ is some fixed small constant. Suppose, moreover, that
- Every row of $M$ has at most $B$ non-zero entries, which are all $\pm 1$, for some small $B$.
- The rank of this matrix is small, say, of order $O(\sqrt{n})$ (this may or may not be relevant.)
I am interested in computing the rank of $M$. Does the fact that $M$ is sparse imply that there are relatively efficient ways of computing this rank? How large should I expect to be able to take $n$ and still be able to compute the rank? The current program I am running (which was kindly written [very quickly without a view to optimization] for me by someone else) chokes up with $n \sim 5000$ or so, and for $n \sim 4000$ seems to take around $20$ minutes.