Using elimination theory to construct rigid matrices
From MaRDI portal
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Determinants, permanents, traces, other special matrix functions (15A15) Computational aspects of algebraic surfaces (14Q10) Vector spaces, linear dependence, rank, lineability (15A03)
Abstract: 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 n x n matrix in this family are distinct primitive roots of unity of orders roughly exp(n^2 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 description. 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 semi-continuous.
Recommendations
Cites work
- scientific article; zbMATH DE number 1703931 (Why is no real title available?)
- scientific article; zbMATH DE number 3572315 (Why is no real title available?)
- scientific article; zbMATH DE number 3597878 (Why is no real title available?)
- scientific article; zbMATH DE number 621807 (Why is no real title available?)
- scientific article; zbMATH DE number 2081103 (Why is no real title available?)
- scientific article; zbMATH DE number 1466163 (Why is no real title available?)
- scientific article; zbMATH DE number 2107000 (Why is no real title available?)
- scientific article; zbMATH DE number 2187726 (Why is no real title available?)
- A linear lower bound on the unbounded error probabilistic communication complexity.
- A note on matrix rigidity
- A remark on matrix rigidity
- Bounds for the degrees in the Nullstellensatz
- Cohen-Macaulay Rings, Invariant Theory, and the Generic Perfection of Determinantal Loci
- Complexity Lower Bounds using Linear Algebra
- Definability and fast quantifier elimination in algebraically closed fields
- Determinantal rings
- Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
- Learning complexity vs communication complexity
- Matrix rigidity
- On the rigidity of Vandermonde matrices
- Sharp Effective Nullstellensatz
- Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
- The Geometry of Schemes
- The membership problem for unmixed polynomial ideals is solvable in single exponential time
- Theory and Applications of Models of Computation
Cited in
(10)- Fourier and circulant matrices are not rigid
- Fourier and circulant matrices are not rigid
- Matrix Rigidity from the Viewpoint of Parameterized Complexity
- Matrix rigidity and the ill-posedness of robust PCA and matrix completion
- On the rigidity of Vandermonde matrices
- Theory and Applications of Models of Computation
- Using elimination theory to construct rigid matrices
- Degrees of projections of rank loci
- New applications of the polynomial method: the cap set conjecture and beyond
- A note on matrix rigidity
This page was built for publication: Using elimination theory to construct rigid matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q475335)
