The inertia of a matrix A is defined as the triple (i_+(A), i_-(A), i_0(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. It is known that the inertia of a large class of matrices can be determined in PL (probabilistic logspace). However, the general problem, whether the inertia of an arbitrary integer matrix is computable in PL, was an open question. In this paper we give a positive answer to this question and show that the problem is complete for PL.
As consequences of this result
we show necessary and sufficient conditions that
certain algebraic functions like the rank or the inertia
of an integer matrix can be computed in GapL.
(pdf-version)