Quadratic Lower Bounds on Matrix Rigidity

p> 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 \times 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 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.