The Complexity of the Inertia

Thanh Minh Hoang and Thomas Thierauf

Abstract:
The inertia of a square matrix A is defined as the triple (i+(A), i-(A), i0(A)), where i+(A), i-(A), and i0(A) are the number of eigenvalues of A, counting multiplicities, with positive, negative, and zero real part, respectively.

A hard problem in Linear Algebra is to compute the inertia. No method is known to get the inertia of a matrix exactly in general. In this paper we show that the inertia is hard for PL ( probabilistic logspace) and in some cases the inertia can be computed in PL. We extend our result to some problems related to the inertia. Namely, we show that matrix stability is complete for PL and the inertia of symmetric matrices can be computed in PL.