Computing a lower bound on matrix rank

Suppose you want to know the rank of an n × n matrix A, the number of linearly independent rows of A, or equivalently the number of linearly independent columns. There are at least three difficulties. Difficulties in computing rank First of all, rank is not a continuous function of a matrix. Since rank is an integer, an arbitrarily small change in the matrix could cause a discrete change in the rank [1]. A small error in computing A could produce a matrix with a different rank. Second, finding the rank takes O(n³) operations, which may or may not be an issue depending on context. Third, you may not have the matrix A in an explicit form. Maybe you’re able to compute products Av for vectors v but it’s not practical to form the entire matrix A. Rank-trace inequality If you don’t need to know the rank of A per se, but only need to know whether it is above a certain size, a lower bound on the rank may enough. Suppose A is a Hermitian matrix. If A is real, this means A is symmetric. If A is…