15
$\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$
9
$\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.

| cite | improve this answer | |
$\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
3
$\begingroup$

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.

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

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.