Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-106 | 28th October 2009 09:17

Using Elimination Theory to construct Rigid Matrices


Authors: Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, Jayalal Sarma
Publication: 28th October 2009 09:21
Downloads: 3830


The rigidity of a matrix A for target rank r is the minimum number of entries
of A that must be changed to ensure that the rank of the altered matrix is at
most r. Since its introduction by Valiant (1977), rigidity and similar
rank-robustness functions of matrices have found numerous applications in
circuit complexity, communication complexity, and learning complexity. Almost
all nxn matrices over an infinite field have a rigidity of (n-r)^2. It is a
long-standing open question to construct infinite families of explicit matrices
even with superlinear rigidity when r=Omega(n).
In this paper, we construct an infinite family of complex matrices with the
largest possible, i.e., (n-r)^2, rigidity. The entries of an nxn matrix in this
family are distinct primitive roots of unity of orders roughly exp(n^4 log n).
To the best of our knowledge, this is the first family of concrete (but not
entirely explicit) matrices having maximal rigidity and a succinct algebraic
Our construction is based on elimination theory of polynomial ideals. In
particular, we use results on the existence of polynomials in elimination
ideals with effective degree upper bounds (effective Nullstellensatz). Using
elementary algebraic geometry, we prove that the dimension of the affine
variety of matrices of rigidity at most k is exactly n^2-(n-r)^2+k$. Finally,
we use elimination theory to examine whether the rigidity function is

ISSN 1433-8092 | Imprint