# What is the fastest algorithm to compute rank of a rectangular matrix?

Given an $m \times n$ matrix (assuming $m \ge n$), what is the fastest algorithm to compute its rank and basis of the columns?

I am aware it can be solved through linear matroid intersection, which implies an $O(mn^{1.62})$ time deterministic algorithm and an $O(mn^{\omega-1})$ time randomized algorithm. Is there an $O(mn^{\omega-1})$ time deterministic algorithm that more directly reduce the problem (or Gaussian elimination) to matrix multiplication?

You can bring a $2n \times n$-matrix into echelon form in time $O(n^{\omega + \epsilon})$ for any $\epsilon > 0$. See the book "Algebraic Complexity Theory" by Bürgisser, Clausen, Shokrollahi, Section 16.5.

Now you apply this procedure $m/n$ times to your $m \times n$-matrix. This gives an algorithm with $O(mn^{\omega-1})$ arithmetic operations.

If you bring an $2n \times n$-matrix into echelon form, then it contains a zero matrix of size $n \times n$ afterwards. You take the remaining $n \times n$-matrix, add a new $n \times n$-block of your input matrix and bring this to echelon form and so on.

• Do you mean splitting the $m$ rows into $m/n$ groups? How do you combine the $m/n$ results to give the rank? Consider two rows in echelon form from different groups that both have 1 in the first column, they may have rank 2 right? – Ho Yee Cheung Mar 30 '11 at 18:11
• Is there a lower bound for this? As in does the rank have any computational strength? – Thomas Ahle Feb 26 '14 at 16:09

We can compute the rank of a $$m \times n$$ matrix A in $$\tilde{O}(\textrm{nnz}(A) + r^{\omega})$$ time, where $$\textrm{nnz}(A)$$ is the number of non-zero entries in $$A$$ and $$r$$ is the rank of $$A$$. This follows from Theorem 1.1 in Cheung et. al. [CKL'13] and binary searching over $$r$$. This is faster than the $$O(mn^{\omega-1})$$ algorithm mentioned above.

• I guess you mean "faster than the $O(mn^{\omega-1})$ algorithm" (I cannot edit the answer myself as the edit is too small) – smapers Feb 5 '20 at 11:23
• Thanks for pointing that out. The citation above is a paper by the OP so my answer is mostly for completeness. – Ainesh Bakshi Feb 6 '20 at 1:13