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.
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.
