# Algorithm to check a conjectural value for the rank of a large matrix

Feel free to suggest a different title, I'm not sure how to phrase this. I'm in the following somewhat specific situation:

I'm checking a conjecture which at the end of the day boils down to the computation of the rank of a large but very very sparse matrix with integer coefficients. The matrix is rectangular, of size roughly $$n\times 2n$$ for a somewhat scary value of $$n$$. Crucially, I know an upper bound $$r$$ for that rank, and crucially again the conjecture I'm trying to verify state that the rank is, in fact, exactly $$r$$. The bad news is that the conjectural $$r$$ is pretty close to $$n$$ (ie $$n$$ is more than a million, while $$n-r$$ is expected to be 34...)

What is the cleverest algorithm to check this ?

A fairly usual trick is to work modulo some small prime $$p$$ since it can only decreases the rank (so that if I do find exactly $$r$$ I know I'm done). Another idea is that it would be enough to find, maybe randomly, $$r$$ linearly independent rows or columns, and if $$r$$ was much smaller than $$n$$ I think it would indeed be much more efficient than actually computing the rank, but in my situation I'm not entirely sure it would. In particular, I'm wondering if there's a known way to turn the fact that the matrix at hand is almost of maximal rank to an advantage.

• How large an $n$ do you find scary? And how sparse is sparse? – Andrej Bauer Sep 19 '19 at 15:25
• $n$ is roughly 1.3 millions, and density is around 0.05. For the one I did handle by just computing the rank mod 17 using github.com/cbouilla/spasm, $n$ was about 600.000 and it took 40 hours. It seems for the largest one just computing the rank is gonna be tricky. – Adrien Sep 19 '19 at 16:31
• How is it represented? Is each row and column a linked list? How long would it take you to make it into upper triangular form? Is it easy to sort the rows lexicographically? There might be algorithms almost linear in n in time if you have a good representation. Also, how useful is an approximation (e.g. quickly showing n-r less than 100)? Gerhard "Is Not Sparse With Ideas" Paseman, 2019.09.19. – Gerhard Paseman Sep 19 '19 at 19:38
• I'm not sure if it is of any help, but if you managed to find $n-r$ independent vectors in $\ker A^T$, then you would be able to conclude that the rank of $A$ is at most $r$. – Federico Poloni Sep 20 '19 at 15:19
• Reminds me of this paper where they had to use a little bit of strategy to compute a rank of a fairly large matrix: arxiv.org/abs/1510.02029 – Zach Teitler Sep 20 '19 at 17:15