Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-100 | 17th July 2006 00:00

On the Complexity of Rank and Rigidity


Authors: Meena Mahajan, Jayalal Sarma
Publication: 18th August 2006 23:30
Downloads: 2857


Given a matrix $M$ over a ring \Ringk, a target rank $r$ and a bound
$k$, we want to decide whether the rank of $M$ can be brought down to
below $r$ by changing at most $k$ entries of $M$. This is a decision
version of the well-studied notion of matrix rigidity. We examine the
complexity of the following related problems and obtain completeness
results for small (counting logspace or smaller) classes:
(a)~computing the determinant, testing singularity, and computing the
rank for matrices with special structure, (b)~determining whether $k
\in O(1)$ changes to a matrix suffice to bring its rank below a
specified value, and (c)~constructing a singular matrix {\em closest}
(in a restricted sense) to the given matrix. We then consider bounded
rigidity, where the magnitude of individual changes is bounded by a
pre-specified value, and show \NP\ hardness in general, and tighter
bounds in special cases. We also extend the rigidity lower and upper
bounds for the full-1s lower triangular matrices to full-1s extended
lower triangular matrices, with a small gap between the two.

ISSN 1433-8092 | Imprint