TR06-100 Authors: Meena Mahajan, Jayalal Sarma

Publication: 18th August 2006 23:30

Downloads: 1871

Keywords:

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.