ECCC-Report TR06-100https://eccc.weizmann.ac.il/report/2006/100Comments and Revisions published for TR06-100en-usFri, 18 Aug 2006 23:30:37 +0300
Paper TR06-100
| On the Complexity of Rank and Rigidity |
Meena Mahajan,
Jayalal Sarma
https://eccc.weizmann.ac.il/report/2006/100Given 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.
Fri, 18 Aug 2006 23:30:37 +0300https://eccc.weizmann.ac.il/report/2006/100