The Complexity of the Inertia
The inertia of an n x n matrix A is defined as the triple (i(+)(A), i(-)(A), i(0)(A)), where i(+)(A), i(-)(A), and i(0)(A) are the number of eigenvalues of A, counting multiplicities, with positive, negative, and zero real part. We show in this paper that the problem to compute the inertia of an integer matrix is complete for the complexity class PL (Probabilistic Logspace). Furthermore, we extend this result to the problem of testing the stability of integer matrices.
inertia matrix stability logspace complexity