The problem of finding the rank of a matrix is a central problem in linear algebra. It is known that this problem can be reduced to fast matrix multiplication [1]}, [2]}, hence there exist algorithms for the rank-finding algorithm that run in time \(O(n^\omega )\) . There are known faster algorithms for restricted classes of matrices. For sparse matrices we know of \(O(n^2)\)  algorithms [3]} and for low-rank matrices the \(O(n^2+\text{rank}(A)^\omega )\) -time algorithms of [4]}, [5]}, [6]} run in time \(n^{\omega -\Omega (1)}\)  when \(\text{rank}(A) = n^{1-\Omega (1)}\) . No improvement over the \(O(n^\omega )\) -runtime is known for general matrices though. We conjecture that this run time is in fact optimal for general matrices. The rank-finding problem is equivalent to checking whether the determinant of a matrix is 0. We get some evidence towards the truth of our conjecture by considering the computational model of arithmetic circuitsSuch a reduction is unknown in the RealRAM model.: In a seminal work Baur and Strassen [7]} linearly reduced the the problem of matrix multiplication to the problem of computing the determinant, thus showing that the latter problem requires arithmetic circuits of size as large as those required for matrix multiplication. Furthermore, this is a central conjecture because falsifying it (getting faster algorithms for the rank-finding problem) would yield better algorithms for important problems like finding the size of a maximum matching in a graph [8]}, [9]}. This is because maximum matching algorithms has a randomized reduction to the rank-finding problem. For some direct evidence: there has been a line of work by Musco et al [10]} that gives algorithms to approximate the Schatten \(p\) -norms in time better that \(O(n^{\omega })\)  when \(p > 0\) . But at \(p = 0\) , the problem of finding the Schatten \(p\) -norm is the same as finding the rank of the matrix, and their algorithms run in time \(\Omega (n^{\omega })\) . Hence they are not able to beat the runtime of \(O(n^\omega )\)  to approximate the rank of a matrix, let alone determine it exactly.
