14
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Ho Yee Cheung Mar 30 '11 at 18:11
  • $\begingroup$ Is there a lower bound for this? As in does the rank have any computational strength? $\endgroup$ – Thomas Ahle Feb 26 '14 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.