Computing the inertia from sign patterns (Q877192)

The purpose of the paper is to present an efficient algorithm for computing the inertia of a sign-nonsingular symmetric matrix. The first section is an introduction in nature. The second section provides some notations and preliminaries about matrices and bipartite graphs. In the third section one recapitulates the inertia of a symmetric matrix in terms of linear algebra. The fourth section focuses on the inertia of sign-nonsingular symmetric matrices, giving a characterization of a symmetric bipartite graph with perfect matchings. Section five is devoted to fundamental properties of a nested sequence of principal submatrices in a sign-nonsingular symmetric matrix. In the sixth section the authors design an efficient algorithm for computing the inertia of a sign-nonsingular symmetric matrix. The seventh section discusses the complexity status of the problem of deciding whether the sign pattern of a given symmetric matrix determines the inertia uniquely or not.