## The Geometry of Matrix Rigidity

##### View/Open

##### Date

2003##### Author

Landsberg, J. M.

Taylor, Jacob

Vishnoi, Nisheeth Kumar

##### Metadata

Show full item record##### Abstract

Consider the following problem: Given an n×n matrix A and an input x, compute Ax. This problem
has a simple algorithm which runs in time O(n²). The question thus is: Is this is the best possible ?
Valiant showed ([12]) that if an n × n matrix A is rigid, then the smallest straight line program
computing Ax is either super-linear size, or has super logarithmic depth. Roughly a matrix of rank n is
said to be rigid, if to bring its rank down to n/2, one has to change at least n[superscript1+є] of its entries, for some
є > 0. After considerable effort by many researchers, the problem of finding an explicit rigid matrix
(hence proving circuit lower bounds) remains elusive.
This paper casts the problem of matrix rigidity in the language of algebraic geometry. As a first step,
we provide the basic setup and prove some elementary results about this problem. This setting facilitates
our understanding of the difficulty of determining the rigidity of an explicit matrix (like Hadamard). On
the brighter side, we hope that tools from algebraic geometry might eventually help establish rigidity of
explicit matrices.