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.