#### Theory Seminar

# 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.