Computing the inertia from sign patterns

Naonori Kakimura, Satoru Iwata

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


A symmetric matrix A is said to be sign-nonsingular if every symmetric matrix with the same sign pattern as A is nonsingular. Hall, Li and Wang showed that the inertia of a sign-nonsingular symmetric matrix is determined uniquely by its sign pattern. The purpose of this paper is to present an efficient algorithm for computing the inertia of such symmetric matrices. The algorithm runs in O(√nm log n) time for a symmetric matrix of order n with m nonzero entries. In addition, it is shown to be NP-complete to decide whether the inertia of a given symmetric matrix is not determined by its sign pattern.

Original languageEnglish
Pages (from-to)229-244
Number of pages16
JournalMathematical Programming
Issue number1
Publication statusPublished - 2007 Jun 1
Externally publishedYes


  • Inertia
  • Sign patterns
  • Sign-nonsingular symmetric matrices

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Computing the inertia from sign patterns'. Together they form a unique fingerprint.

Cite this