<p>We can compute the rank of a <span class="math-container">$m \times n$</span> matrix A in <span class="math-container">$\tilde{O}(\textrm{nnz}(A) + r^{\omega})$</span> time, where <span class="math-container">$\textrm{nnz}(A)$</span> is the number of non-zero entries in <span class="math-container">$A$</span> and <span class="math-container">$r$</span> is the rank of <span class="math-container">$A$</span>. This follows from Theorem 1.1 in Cheung et. al. <a href="https://dl.acm.org/doi/pdf/10.1145/2528404" rel="nofollow noreferrer">[CKL'13]</a> and binary searching over <span class="math-container">$r$</span>. This is faster than the <span class="math-container">$O(mn^{\omega-1})$</span> algorithm mentioned above. </p>

CC BY-SA 4.0
2020-02-05T11:23:15.557Z
I guess you mean "faster than the $O(mn^{\omega-1})$ algorithm" (I cannot edit the answer myself as the edit is too small)
smapers
CC BY-SA 4.0
2020-02-06T01:13:44.453Z
Thanks for pointing that out. The citation above is a paper by the OP so my answer is mostly for completeness.
Ainesh Bakshi
CC BY-SA 4.0
2020-02-03T23:51:35.237Z
2020-02-06T01:12:26.273Z
2020-02-06T01:12:26.273Z
Ainesh Bakshi
<p>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.</p>

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

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

CC BY-SA 2.5
2011-03-30T18:11:48.373Z
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
CC BY-SA 3.0
2014-02-26T16:09:55.073Z
Is there a lower bound for this? As in does the rank have any computational strength?
Thomas Ahle
CC BY-SA 2.5
2011-03-30T12:49:15.847Z
2011-03-30T21:00:07.433Z
2011-03-30T21:00:07.433Z
5501
<p>Given an $m \times n$ matrix (assuming $m \ge n$), what is the fastest algorithm to compute its rank and basis of the columns? </p>

<p>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?</p>

<ds.algorithms><reference-request><time-complexity><linear-algebra><matrices>
What is the fastest algorithm to compute rank of a rectangular matrix?
Ho Yee Cheung
# What is the fastest algorithm to compute rank of a rectangular matrix?

(Asked by: username_0 on 2011-03-30)

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?

**Tags:** ds.algorithms, reference-request, time-complexity, linear-algebra, matrices

---

## 2 answers

### Answer by username_3 on 2011-03-30. Score: 9 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_4**: Is there a lower bound for this? As in does the rank have any computational strength?  

---

### Answer by username_1 on 2020-02-03. Score: 3

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]](https://dl.acm.org/doi/pdf/10.1145/2528404) and binary searching over $r$. This is faster than the $O(mn^{\omega-1})$ algorithm mentioned above.

> **Comments:**
> **username_2**: I guess you mean "faster than the $O(mn^{\omega-1})$ algorithm" (I cannot edit the answer myself as the edit is too small)  
> **username_1**: Thanks for pointing that out. The citation above is a paper by the OP so my answer is mostly for completeness.  

---

