Quadratic lower bounds on matrix rigidity

University of Michigan

Abstract

The rigidity of a matrix A is the minimum number of entries of A that must be changed to reduce its rank to, or below, a given value r. It is a major unsolved problem [Valiant, 1977] to construct "explicit" families of n by n matrices of rigidity at least n^{1+\delta} for rank bound r=\epsilon n, where \epsilon and \delta are positive constants. In fact, no superlinear lower bounds are known for explicit families of matrices for rank bound r=\epsilon n. An important consequence of such a lower bound is a superlinear lower bound on the arithmetic complexity of the linear transformation given by the matrix A.

In a recent joint work with Babai, we prove an \Omega(n^2) lower bound on the rigidity of the matrix P=(\sqrt(p_{ij})), where p_{ij} are distinct primes, with respect to the rank bound r=n/17; this is optimal to within a constant factor. We also show a nearly optimal \Omega(n^2/\log n) lower bound on the arithmetic complexity of the linear transformation given by the matrix P. Our proofs use a certain algebraic dimension due to Shoup and Smolensky.