Thanh Minh Hoang and Thomas Thierauf

**Abstract: **

The *inertia* of a 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.
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)