# 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