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 &gt; 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.