Matrix Rigidity : Matrix Theory from the Viewpoint of Parameterized Complexity

Abstract

The rigidity of a matrix A for a target rank r over a field F is the minimum Hamming distance between A and a matrix of rank at most r. Rigidity is a classical concept in Computational Complexity Theory: constructions of rigid matrices are known to imply lower bounds of significant importance relating to arithmetic circuits. Yet, from the viewpoint of Parameterized Complexity, the study of central properties of matrices in general, and of the rigidity of a matrix in particular, has been neglected. In this paper, we conduct a comprehensive study of different aspects of the computation of the rigidity of general matrices in the framework of Parameterized Complexity. Naturally, given a parameter k, the Matrix Rigidity problem asks whether the rigidity of A is at most k. In the case when F = Q or if the replaced entries must be integers, it is not even known whether the problem is decidable. Surprisingly, we show that in case F = R or F is any finite field, this fundamental problem is fixed-parameter tractable with respect to k + r. To this end, we present a simple yet powerful dimension reduction procedure, which we believe to be a valuable primitive in future studies of problems of this nature. We further employ central tools in Real Algebraic Geometry, which are not well known in Parameterized Complexity, thus establishing their ability to form a bridge between Matrix Theory and Parameterized Complexity. In particular, we view the output of our dimension reduction procedure as an algebraic variety. Our main results are complemented by a W[1]-hardness result and a subexponential-time parameterized algorithm for a special case of Matrix Rigidity, highlighting the different flavors of this problem.