Using elimination theory to construct rigid matrices

DOI10.1007/S00037-013-0061-0zbMATH Open1366.68076arXiv0910.5301OpenAlexW2053068069MaRDI QIDQ475335FDOQ475335

Authors: Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, Jayalal Sarma M. N. 

Publication date: 26 November 2014

Published in: Computational Complexity (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/0910.5301

Recommendations

• Using elimination theory to construct rigid matrices
• Theory and Applications of Models of Computation
• On the rigidity of Vandermonde matrices
• scientific article; zbMATH DE number 37868
• A remark on matrix rigidity

zbMATH Keywords

lower boundsmatrix rigidityelimination theory

Mathematics Subject Classification ID

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)

Cites Work

• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The membership problem for unmixed polynomial ideals is solvable in single exponential time
• Determinantal rings
• A remark on matrix rigidity
• A note on matrix rigidity
• On the rigidity of Vandermonde matrices
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
• A linear lower bound on the unbounded error probabilistic communication complexity.
• Matrix rigidity
• Complexity Lower Bounds using Linear Algebra
• The Geometry of Schemes
• Sharp Effective Nullstellensatz
• Theory and Applications of Models of Computation
• Definability and fast quantifier elimination in algebraically closed fields
• Cohen-Macaulay Rings, Invariant Theory, and the Generic Perfection of Determinantal Loci
• Learning complexity vs communication complexity
• Title not available (Why is that?)
• Bounds for the degrees in the Nullstellensatz
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (10)

• Fourier and circulant matrices are not rigid
• Fourier and circulant matrices are not rigid
• A note on matrix rigidity
• Using elimination theory to construct rigid matrices
• Theory and Applications of Models of Computation
• Matrix rigidity and the ill-posedness of robust PCA and matrix completion
• On the rigidity of Vandermonde matrices
• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• Degrees of projections of rank loci
• New applications of the polynomial method: the cap set conjecture and beyond

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)