Computing the inertia from sign patterns |
| |
Authors: | Naonori Kakimura Satoru Iwata |
| |
Institution: | (1) Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo 113-8656, Japan;(2) Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan |
| |
Abstract: | 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 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. |
| |
Keywords: | Inertia Sign patterns Sign-nonsingular symmetric matrices |
本文献已被 SpringerLink 等数据库收录! |
|