On the rigidity of Vandermonde matrices
The rigidity function R-A(r) of a matrix A is the minimum number of entries of A that must be changed to reduce the rank of A to less than or equal to I. While almost all matrices have rigidity close to (n - r)(2), proving strong lower bounds on the rigidity of explicit matrices is a fundamental open question with several consequences in complexity theory. A natural class of matrices expected to have high rigidity is that of Vandermonde matrices V = (x(i)(j-1))(1 less than or equal to i,j less than or equal to n). However, even when the x(i) are algebraically independent, it was not known if R-V(r) = Omega(n(2)) for nonconstant I. We prove that for any constant c   0 such that if r less than or equal to epsilon root n, then R-V(r)greater than or equal to cn(2), when the x(i) are algebraically independent. Although not explicit, this provides a natural n-dimensional manifold in the space of n x it matrices with Omega(n(2)) rigidity for nonconstant r. Our proof is based on a technique due to Shoup and Smolensky (Comput. Complexity 6(4) (1997) 301-311). For explicit Vandermonde matrices, the best-known lower bound is R-V(r) = Omega(n(2)/r log(n/r)), when log(2) n less than or equal to r less than or equal to n/2, which follows from a result of Shukrollahi ct al. (C) 2000 Elsevier Science B.V. All rights reserved.
matrix rigidity arithmetic circuits vandermonde matrix