Fast Matrix Rank Algorithms and Applications

Understand

We consider the problem of computing the rank of an m x n matrix A over a field.

• We present a randomized algorithm to find a set of r = rank(A) linearly independent columns in \~O(|A| + r^\omega) field operations, where |A| denotes the number of nonzero entries in A and \omega < 2.38 is the matrix multiplication exponent.
• Previously the best known algorithm to find a set of r linearly independent columns is by Gaussian elimination, with running time O(mnr^{\omega-2}).
• Our algorithm is faster when r < max(m,n), for instance when the matrix is rectangular.