On the Complexity of Matrix Rank and Rigidity

Abstract

We revisit a well studied linear algebraic problem, computing the rank and determinant of matrices, in order to obtain completeness results for small complexity classes. In particular, we prove that computing the rank of a class of diagonally dominant matrices is complete for L. We show that computing the permanent and determinant of tridiagonal matrices over ℤ is in GapNC 1 and is hard for NC 1. We also initiate the study of computing the rigidity of a matrix: the number of entries that needs to be changed in order to bring the rank of a matrix below a given value. It is NP-hard over F2 and we prove that some restricted versions characterize small complexity classes. We also look at a variant of rigidity where there is a bound on the amount of change allowed. Using ideas from the linear interval equations literature, we show that this problem is NP-hard over ℚ and that a certain restricted version is NP-complete. Restricting the problem further, we obtain variations which can be computed in PL and are hard for C = L.