Computing the inertia from sign patterns

DOI10.1007/S10107-006-0056-6MaRDI QIDQ877192zbMATH OpenOpenAlexFDO

Authors Naonori Kakimura, Satoru Iwata

Publication date 19 April 2007

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10107-006-0056-6

zbMATH Keywords

inertiasign patternssign-nonsingular symmetric matrices

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15)

Review text

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.

Recommendations

• Computing the Inertia from Sign Patterns
• scientific article; zbMATH DE number 1735431
• Inertia sets of two classes of symmetric sign patterns
• Computing of signs of eigenvalues for diagonally dominant matrix for inertia problem
• The complexity of the inertia

Cites work

• An identity for bipartite matching and symmetric determinant
• Faster Scaling Algorithms for Network Problems
• scientific article; zbMATH DE number 825098 (Why is no real title available?)
• scientific article; zbMATH DE number 3048439 (Why is no real title available?)
• Matching theory
• Matrix Analysis
• Permanents, Pfaffian orientations, and even directed circuits
• Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
• Pólya's permanent problem
• Signsolvability revisited
• Symmetric sign pattern matrices that require unique inertia

Cited in

(11)

• Allow problems concerning spectral properties of sign pattern matrices: a survey
• Two classes of symmetric sign patterns that require unique inertia.
• Sign patterns requiring a unique inertia
• Exact computations of the inertia symmetric integer matrices
• Computing the Inertia from Sign Patterns
• Computing of signs of eigenvalues for diagonally dominant matrix for inertia problem
• Computing inertia sets using atoms
• scientific article; zbMATH DE number 1954385 (Why is no real title available?)
• New numerical method for determining inertia and stability of nonsymmetric large sparse matrix
• Matching structure of symmetric bipartite graphs and a generalization of Pólya's problem
• Spectral aspects of symmetric matrix signings

This page was built for publication: Computing the inertia from sign patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q877192)