MATHEMATICAL ENGINEERINGTECHNICAL REPORTS

Computing the Inertia from Sign Patterns

Naonori KAKIMURA and Satoru IWATA

METR 2004–42

October 2004

DEPARTMENT OF MATHEMATICAL INFORMATICSGRADUATE SCHOOL OF INFORMATION SCIENCE AND TECHNOLOGYTHE UNIVERSITY OF TOKYOBUNKYO-KU, TOKYO 113-8656, JAPANWWW page: http://www.i.u-tokyo.ac.jp/mi/mi-e.htm

The METR technical reports are published as a means to ensure timely dissemination ofscholarly and technical work on a non-commercial basis. Copyright and all rights therein
are maintained by the authors or by other copyright holders, notwithstanding that they
have offered their works here electronically. It is understood that all persons copying thisinformation will adhere to the terms and constraints invoked by each author’s copyright.
These works may not be reposted without the explicit permission of the copyright holder.

Computing the Inertia from Sign Patterns
Naonori KAKIMURA∗†

Satoru IWATA∗‡

October, 2004

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 (2001) showed that the inertia of a signnonsingular symmetric matrix is determined uniquely by its sign pattern. The purpose of thispaper is to present an efficient algorithm for computing the inertia of such matrices. The algorithm
runs in O(nm) time for a symmetric matrix of order n with m nonzero entries. The correctness of
the algorithm provides an alternative proof of the result by Hall et al. In addition, for a symmetricmatrix in general, it is shown to be NP-complete to decide whether the inertia of the matrix is notdetermined by the sign pattern.

1

Introduction

The inertia of a symmetric matrix indicates the number of the positive/negative eigenvalues. This is
an important quantity invariant under the congruence transformation. Quadratic forms are classified
by the inertia of the coefficient matrices. In this paper, we discuss computing the inertia of a given
symmetric matrix from the sign pattern of its entries without numerical information.
Matrix analysis with sign pattern has been studied by many researchers (see [2]). The analysis iscalled qualitative matrix theory. It is useful because the sign pattern of a matrix can be easily inferredin a variety of situations, rather than the exact value of the matrix entries. For a matrix A, we denoteby Q(A) the set of all matrices having the same sign pattern as A, which is called the sign patternclass of A. Klee, Ladner and Manber[5] proved that for a rectangular matrix A, it is NP-complete todiscern whether there exists Ã ∈ Q(A) which is not row full-rank. However, Robertson, Seymour andThomas[8] devised a polynomial time algorithm to discern whether Ã is nonsingular for any squarematrix Ã ∈ Q(A).
This paper deals with the sign pattern class of symmetric matrices, which is denoted by Q∗ (A) :={Ã | Ã ∈ Q(A), Ã> = Ã}. A symmetric matrix A is said to be sign-nonsingular if Ã is nonsingular
for any symmetric matrix Ã ∈ Q∗ (A). We first discuss computing the inertia of a sign-nonsingularsymmetric matrix from the sign pattern. Hall, Li and Wang[3] gave several characterizations of thesymmetric sign patterns that require unique inertia in 2001. Their result implies that the inertia
of a sign-nonsingular symmetric matrix is determined uniquely by the sign pattern. We prove theuniqueness of the inertia of a sign-nonsingular symmetric matrix in a different way from Hall et al.,that is, we find a nested sequence {Ak }nk=1 of the principal submatrices of order k such that at least
one of Ak−1 and Ak is sign-nonsingular for any k = 2, . . . , n. Our proof is based on a characterizationof the structure of a symmetric bipartite graph. Furthermore, our proof naturally provides an O(nm)time algorithm for computing the inertia of a sign-nonsingular symmetric matrix of order n with mnonzero entries.
∗

Department of Mathematical Informatics, Graduate School of Information Science and Technology, University ofTokyo, Tokyo 113-8656, Japan.
†
naonori kakimura@mist.i.u-tokyo.ac.jp‡
iwata@mist.i.u-tokyo.ac.jp

1

We also discuss the problem of deciding whether a symmetric matrix is sign-nonsingular or not. We
prove that the decision problem whether a given matrix is not a sign-nonsingular symmetric matrix is
NP-complete by the result of Klee et al. Hence, for a symmetric matrix A in general, it is NP-complete
to discern whether the inertia of Ã is not the same for all Ã ∈ Q∗ (A).
The present paper is organized as follows. Section 2 contains some notations and preliminaries
about matrices and bipartite graphs. In Section 3, we recapitulate the inertia of a symmetric matrix
in terms of linear algebra. From Section 4 to 6, we discuss the inertia of a sign-nonsingular symmetricmatrix. In Section 4, we give the structure of a symmetric bipartite graph with perfect matchings. In
Section 5, we show that the inertia of a sign-nonsingular symmetric matrix A is determined uniquely
be the sign pattern. In Section 6, we design an efficient algorithm for computing the inertia of a signnonsingular symmetric matrix. In Section 7, we describe NP-completeness of the decision problem
whether any Ã ∈ Q∗ (A) does not have the same inertia for a symmetric matrix A in general.

2

Matrices and Bipartite Graphs

For a matrix A, the row index set and the column index set are denoted by Row(A) and Col(A),i.e., A = (aij | i ∈ Row(A), j ∈ Col(A)), where aij is the (i, j)-entry of A. For I ⊆ Row(A) andJ ⊆ Col(A), A[I, J] = (aij | i ∈ I, j ∈ J) means the submatrix of A with row set I and column set J.
For a square matrix A of order n, the determinant of A is defined bydet A :=

X

sgnπ

n
Y

aiπ(i) ,

(2.1)

i=1

π∈Sn

where Sn denotes the set of all the permutations of order n, and sgnπ ∈ {1, −1} is the signature of
the permutation π ∈ Sn . A square matrix is said to be nonsingular if its determinant is distinct fromzero.
As a combinatorial counterpart of nonsingularity, we say that a matrix A is term-nonsingular if
the expansion in (2.1) contains at least one nonvanishing term, that is, if aiπ(i) 6= 0 (∀i ∈ Row(A)) forsome permutation π ∈ Sn . Obviously, nonsingularity implies term-nonsingularity, since the right-handside of (2.1) is distinct from zero only if the summation contains a nonzero term. The term-rank of
A is the maximum size of a term-nonsingular submatrix of A. We denote term-rank of A by t-rankA.
Hence we have t-rankA ≥ rankA.
Let G = (U, V ; E) be a bipartite graph with vertex sets U, V and an edge set E ⊆ U × V . A
path P ⊆ E is a sequence of consecutive edges in a graph. A circuit C ⊆ E is a path which ends atthe vertex it begins. For F ⊆ E, we denote by ∂F the set of all the end-vertices of edges in F , i.e.,∂F := {ui , vj | (ui , vj ) ∈ F }. An edge subset M in G is called a matching if 2|M | = |∂M |, and amatching M is said to be a perfect matching if ∂M = U ∪ V .
With a matrix A, we associate a bipartite graph G(A) = (U, V ; E) with vertex sets U := {ui |i ∈ Row(A)} and V := {vj | j ∈ Col(A)}. The edge set E is given by E := {(ui , vj ) | aij =6 0, ui ∈U, vj ∈ V }, that is, an edge of G(A) represents a nonvanishing entry of A. A perfect matching in
G(A) corresponds to one nonvanishing term of det A. Therefore, A is term-nonsingular if and only
if G(A) has a perfect matching. Furthermore, the term-rank of A is equal to the maximum size of amatching in G(A).
For a square matrix A, we say that A has an equisignum determinant if every nonvanishing term of
the determinant of A has the same sign. If a square matrix has an equisignum determinant, the matrix
is obviously nonsingular. It is known that Ã is nonsingular for any Ã ∈ Q(A) if and only if A has anequisignum determinant[5]. Hence this is a sufficient condition for a matrix to be a sign-nonsingularsymmetric matrix.
Consider a directed bipartite graph D = (U, V ; E). An edge subset F is said to be central if thesubgraph obtained from D by deleting the vertices ∂F has a perfect matching. A circuit is said to be2

oddly oriented in D if the circuit contains an odd number of edges that are directed in the directionof each orientation of the circuit. We say that a directed graph D is Pfaffian if every central circuitin D is oddly oriented.
Let D(A) be a directed bipartite graph associated with a matrix A defined as follows. A vertex set of
D(A) is the same as that of G(A), and an edge e = (ui , vj ) is oriented from ui to vj if aij > 0, and fromvj to ui if aij < 0. It is known that A has an equisignum determinant if and only if D(A) is Pfaffian[6].
The complexity status of the decision problem whether a given matrix has an equisignum determinant
or not had been an open problem for a long time. This problem is polynomial time equivalent to thedecision problem whether a given undirected bipartite graph has a Pfaffian orientation[9]. In 1999,
Robertson, Seymour and Thomas[8] gave a polynomial time algorithm to discern if a given bipartite
graph has a Pfaffian orientation. This algorithm can be easily applied to discern if a given directedbipartite graph is Pfaffian or not. Thus it can be tested in polynomial time whether Ã is nonsingular
for any Ã ∈ Q(A) for a given matrix A.

3

The Inertia of Symmetric Matrices

In this section, we recapitulate the inertia of a symmetric matrix in terms of linear algebra. We
consider a symmetric matrix A of order n, where Row(A) and Col(A) are both identical with a finite
set N of cardinality n.
Let p(A) be the number of positive eigenvalues of A, q(A) the number of negative eigenvalues,and z(A) the number of zero eigenvalues, all counting multiplicity. The ordered triple In(A) :=(p(A), q(A), z(A)) is called the inertia of A. By the definition of the inertia, we have
rankA = p(A) + q(A),(3.1)

z(A) = n − rankA.

(3.2)

Consider transforming A to S > AS by a nonsingular matrix S. This transformation is called acongruence transformation. It is known that the inertia of a symmetric matrix is invariant undercongruence transformations (Sylvester’s law of inertia[4]). Hence, a symmetric matrix A is congruent
to a diagonal matrix as follows:
S > AS = diag(1, . . . , 1, −1, . . . , −1, 0, . . . , 0),(3.3)

where the indicated matrix has exactly p(A) “1”, q(A) “−1”, and z(A) “0” in its diagonal entries.
Let us consider the determinant of S > AS. If A is nonsingular, it follows from (3.3) thatdet(S > AS) = (det S)2 det A = (−1)q(A) .

(3.4)

The sign of det A is thus determined by the parity of q(A).
Let Ak be a principal submatrix of order k for 1 ≤ k ≤ n. Then there exists a nonsingular matrix
S such that
Ip(Ak )OO
−Iq(Ak ) O  ,S > AS =  O
(3.5)
O
O
H
where H is a symmetric matrix. This impliesp(Ak ) ≤ p(A), q(Ak ) ≤ q(A).
Let {Ak }nk=1 be a nested sequence of principal submatrices of order k (An := A). In a similar way, wehavep(Ak ) ≤ p(Al ), q(Ak ) ≤ q(Al ),(3.6)
3

for each 1 ≤ k ≤ l ≤ n.
A nonsingular symmetric matrix A has a nested sequence {Ak }nk=1 of principal submatrices suchthat no two consecutive submatrices are singular. We call such a sequence admissible. If we find an
admissible nested sequence {Ak }nk=1 of principal submatrices, then the inertia of A can be obtainedby comparing the signs of det Ak as follows.
If both Ak and Ak−1 are nonsingular (k ≥ 2), then (3.4) implies that the signs of the principal minors det Ak and det Ak−1 are equal to (−1)q(Ak ) and (−1)q(Ak−1 ) , respectively. Moreover, the difference
between q(Ak ) and q(Ak−1 ) is at most one by (3.1) and (3.6). Therefore, we have½
In(Ak−1 ) + (1, 0, 0)(if sgn det Ak = sgn det Ak−1 )In(Ak ) =(3.7)
In(Ak−1 ) + (0, 1, 0)(if sgn det Ak 6= sgn det Ak−1 ).
In an admissible sequence {Ak }nk=1 , if Ak is nonsingular and Ak−1 is singular (k ≥ 3), then Ak−2
is nonsingular. Consider transforming Ak by a nonsingular matrix S to diagonalize Ak−2 as (3.5).
Since Ak−1 is singular and Ak is nonsingular, this implies the determinant of the submatrix H in theright-hand side of (3.5) is nonpositive. Hence sgn det Ak 6= sgn det Ak−2 . Then, by (3.4), the paritiesof q(Ak ) and q(Ak−2 ) are different. Moreover, the difference between q(Ak ) and q(Ak−2 ) is at most
two by (3.1) and (3.6). Therefore, we have
In(Ak ) = In(Ak−2 ) + (1, 1, 0).

4

(3.8)

Symmetric Bipartite Graphs

Let G = (U, V ; E) be a bipartite graph with vertex sets U := {u1 , . . . , un } and V := {v1 , . . . , vn }.
Both of the vertex sets are identified with N := {1, . . . , n}. A bipartite graph G = (U, V ; E) is said
to be symmetric if e = (ui , vj ) ∈ E implies (uj , vi ) ∈ E for all e ∈ E. The bipartite graph G(A)associated with a symmetric matrix A is symmetric.
Let G = (U, V ; E) be a symmetric bipartite graph with perfect matchings. An edge (ui , vi ) ∈ E iscalled a diagonal edge for i ∈ N . For an edge subset F of G, we call F > := {(uj , vi ) | (ui , vj ) ∈ F }the transpose of F . If F > coincides with F , it is called symmetric, otherwise asymmetric. For edge
subsets F1 and F2 of G, we denote by F1 4F2 the symmetric difference between F1 and F2 .
Let M be a perfect matching in G. We denote by π a permutation corresponding to M . Since G
is symmetric, M > is also a perfect matching in G. Then M > corresponds to the inverse permutation
π −1 .QA permutation π is expressed uniquely as a product of some cyclic permutations. We suppose
π = hk=1 σk , where h is a positive integer and σk is a cyclic permutation. Let Mk ⊆ M be a matchingS
in G corresponding to σk . Then M is the disjoint union of Mk , that is, M = hk=1 Mk .
Let C be a circuit in G. Since G is symmetric, the transpose C > is also a circuit in G. A chord ofa circuit is an edge in E \ C having both ends on the circuit. We say that a circuit C is chordless if
C has no chord.
Theorem 4.1 Let G be a symmetric bipartite graph with perfect matchings. Then G satisfies thefollowing (a), (b) or (c).
(a) There exists a perfect matching M in G such that (ui , vi ) ∈ M for some i ∈ N .
(b) There exists a perfect matching M in G such that (ui , vj ) ∈ M and (uj , vi ) ∈ M for some distincti, j ∈ N .
(c) The symmetric bipartite graph G is a disjoint union of some chordless symmetric circuits.
Proof. By the assumption, the symmetric bipartite graph G has a perfect matching M and its
transposed perfect matching M > . Furthermore, M is the disjoint union of matchings Mk for k =1, . . . , h corresponding to cyclic permutations.
4We will show that if G does not satisfy the condition (a) or (c), then G satisfies the condition (b).
First, we claim that M ∪ M > consists of Ck ∪ Ck> for k = 1, . . . , h, where Ck is a circuit (Ck may
coincide with Ck> ). Indeed, M ∪ M > is the disjoint union of Mk ∪ Mk> for k = 1, . . . , h. Since M
does not have either (ui , vj ) or (uj , vi ) for some i, j ∈ N (otherwise, G satisfies (a) or (b)), Mk ∪ Mk>
consists of circuits. If |Mk |(≥ 3) is odd, then Mk ∪ Mk> is a symmetric circuit of length 2|Mk | (seeFig.1 for the case of |Mk | = 5). If |Mk |(≥ 4) is even, then Mk ∪ Mk> consists of an asymmetric circuitof length |Mk | and its transpose (see Fig.2 for the case of |Mk | = 4).

u
P
³u
S PP
³³ ¶
P
³
P
u
¶Pu
³S³
P
PSP³¶³³P³u³³ S¶ PP
P
³u
PP
S
³³
¶P
³
PPu
S
u
³³
¶
P
³³
³
¶PP
³PPS
³
P
u
³
Su
¶

u
u
P
³³
@P³
P³
¡
P
P
@
u³
¡Pu
³
P
P@
³³
P
³
¡
P
³
u ³¡@P³
Pu
³
P
P
³
P³
@
¡³
P
P@
u
³³
Pu
¡

Figure 1: The union Mk ∪ Mk> (|Mk | = 5).

Figure 2: The union Mk ∪ Mk> (|Mk | = 4).

Suppose that there exists an asymmetric circuit Ck and its transposed circuit Ck> (6= Ck ) in M ∪M > .
Then M 0 := M 4Ck> is also a perfect matching in G, and M 0 has both (uj , vi ) and (ui , vj ) for each(ui , vj ) ∈ Ck ∩ M . This implies G satisfies the condition (b).
Hence we may suppose there exist only symmetric circuits in M ∪ M > . Since G is not a disjoint
union of some chordless circuits, (i) there exists (ui , vj ) ∈ E \ (M ∪ M > ), ui ∈ ∂Ck , vj ∈ ∂Cl forsome distinct 1 ≤ k, l ≤ h, or (ii) there exists (ui , vj ) ∈ E \ (M ∪ M > ), ui ∈ ∂Ck , vj ∈ ∂Ck for some1 ≤ k ≤ h.
Suppose G satisfies (i). Then there also exists (uj , vi ) ∈ E \ (M ∪ M > ), uj ∈ ∂Cl , vi ∈ ∂Ck ,because of symmetry of G(A). Let Pk ⊆ Ck be a path from ui ∈ U ∩ ∂Ck to vi ∈ V ∩ ∂Ck suchthat both end-vertices of Pk are incident with an edge of M ∩ Pk . Let Pl ⊆ Cl be a path in a similar
way. Then C 0 := (Pk ∪ Pl ) ∪ {(ui , vj ), (uj , vi )} is a circuit in G. Furthermore, M 0 := M 4C 0 is alsoa perfect matching in G, and M 0 has both (ui , vj ) and (uj , vi ). Moreover, it shows that there exists(uj 0 , vi0 ) ∈ (Pk> ∪ Pl> ) ∩ M 0 for each (ui0 , vj 0 ) ∈ (Pk ∪ Pl ) ∩ M 0 because Ck and Cl are symmetric. Thus
G satisfies the condition (b).
Suppose G satisfies (ii). Then let Pk ⊆ Ck be a path from ui ∈ U ∩ ∂Ck to vj ∈ V ∩ ∂Ck such thatboth end-vertices of Pk are incident with an edge of M ∩ Pk . Then C 0 := Pk ∪ {(ui , vj )} is a circuit in
G. Furthermore, M 0 := M 4C 0 is also a perfect matching in G, and there exists (uj 0 , vi0 ) ∈ Ck ∩ M 0
for each (ui0 , vj 0 ) ∈ (Pk 4Pk> ) ∩ M 0 . Thus G satisfies the condition (b).
Consequently, if G does not satisfy the condition (a) or (c), G satisfies the condition (b).

5Uniqueness of the Inertia

In this section, we discuss the uniqueness of the inertia of a sign-nonsingular symmetric matrix A. For
convenience, we denote by A[J] the principal submatrix A[J, J] for J ⊆ N . Since sign-nonsingularity
implies nonsingularity, it is clear that z(A) = 0.
A nested sequence {Ak }nk=1 of principal submatrices is called sign-admissible if at least one of
Ak−1 and Ak is sign-nonsingular for any k = 2, . . . , n. It follows from (3.7) and (3.8) that if A has asign-admissible sequence, the inertia of A is determined uniquely by the sign pattern.
However, it is not easy to find such a sequence. Even if a symmetric matrix A has an equisignum

5determinant, a principal submatrix of A may not be sign-nonsingular. For example,
+1 +1 +1 −1
 +1 +1 +1 +1 A=
 +1 +1 −1 0 −1 +1 00
has an equisignum determinant, and hence A is sign-nonsingular, while a nested sequence of the leading principal submatrices is not sign-admissible (A[{1, 2}] and A[{1, 2, 3}] are not sign-nonsingular).
However, the inertia is determined independently of the magnitude of the entries, In(A) = (2, 1, 0).
This is because each of A[{2}], A[{2, 3}] and A[{1, 2, 3, 4}] has an equisignum determinant.
Thus, it is sufficient to find one sign-admissible nested sequence of principal submatrices for determining the inertia uniquely from the sign pattern. To find a sign-admissible nested sequence ofprincipal submatrices, we will use the characterization of a symmetric bipartite graph described in
Section 4.
The main result in this section is the following theorem.
Theorem 5.1 Let A be a sign-nonsingular symmetric matrix. Then there exists a sign-admissible
nested sequence of principal submatrices. Hence Ã has the same inertia for any Ã ∈ Q∗ (A).
We first provide the following three lemmas to prove Theorem 5.1.
Lemma 5.2 Let A be a sign-nonsingular symmetric matrix such that G(A) satisfies the condition (a)of Theorem 4.1, that is, there exists a perfect matching M in G(A) containing (ui , vi ) for some i ∈ N .
Then the principal submatrix A0 := A[N \ {i}] is a sign-nonsingular symmetric matrix, and the inertiaof A is obtained by½
In(A0 ) + (1, 0, 0)(if aii > 0)
In(A) =
(5.1)
0
In(A ) + (0, 1, 0)(if aii < 0).
Proof. The determinant of A is expanded as
X(−1)i+j aij det A[N \ {i}, N \ {j}].
det A = aii det A0 +j6=iSince G(A0 ) has a perfect matching M \ {(ui , vi )}, A0 is term-nonsingular. It then follows from thesign-nonsingularity of A that A0 is a sign-nonsingular symmetric matrix (otherwise, the sign of thedeterminant of A can change by the magnitude of aii ). Therefore, by (3.4), we have0

sgn det A = (−1)q(A) = sgn(aii )(−1)q(A ) ,which implies that the parity of q(A) depends on that of q(A0 ) and the sign of aii . Therefore, by (3.7),
we have½(p(A0 ) + 1, q(A0 ))(if aii > 0)(p(A), q(A)) =00(p(A ), q(A ) + 1)
(if aii < 0).

Lemma 5.3 Let A be a sign-nonsingular symmetric matrix such that G(A) does not satisfy the condition (a) of Theorem 4.1. Suppose G(A) satisfies the condition (b), that is, there exists a perfectmatching M in G(A) such that (ui , vj ) ∈ M and (uj , vi ) ∈ M for some distinct i, j ∈ N . Then theprincipal submatrix A0 = A[N \ {i, j}] is a sign-nonsingular symmetric matrix, and the inertia of A is
obtained by
In(A) = In(A0 ) + (1, 1, 0).
(5.2)

6

Proof. In the same way as Lemma 5.2, the determinant of A is expanded asX
det A = −(aij )2 det A0 +± det A[{k, l}, {i, j}] det A[N \ {k, l}, N \ {i, j}].
(k,l)6=(i,j),k6=lNotice that det A[{i, j}] = −(aij )2 , because G(A) has no perfect matching containing any diagonaledge by the assumption. Since A is a sign-nonsingular symmetric matrix and G(A0 ) has a perfectmatching M \ {(ui , vj ), (uj , vi )}, the principal submatrix A0 is sign-nonsingular. Then, by (3.4), we
have
0
sgn det A = (−1)q(A) = (−1)q(A )+1 ,which implies that the parity of q(A) is different from that of q(A0 ). Therefore, by (3.8), we have(p(A), q(A)) = (p(A0 ) + 1, q(A0 ) + 1).
Notice that it is not necessary that the principal submatrix A[N \ {i}] or A[N \ {j}] is signnonsingular.
Lemma 5.4 Let A be a sign-nonsingular symmetric matrix of order n = 2s + 1 such that G(A) is achordless symmetric circuit. Let 2t be the number of the negative entries of A. Then the inertia of A
is obtained by½(s + 1, s, 0) (if t ≡ s mod 2)
In(A) =
(5.3)
(s, s + 1, 0) (if t 6≡ s mod 2).
Proof. Since G(A) is a chordless symmetric circuit, the matrix size n is odd. Since det A has only twononvanishing terms, we havesgn det A = (−1)t .
(5.4)
Let A0 be the principal submatrix obtained by deleting the ith row and the ith column from A for
any i ∈ N . Then G(A0 ) consists of two paths. Since G(A0 ) has only one perfect matching, A0 has anequisignum determinant. Hence A0 is a sign-nonsingular symmetric matrix. Then, by (3.4), we have0

sgn det A0 = (−1)q(A ) .

(5.5)

Since G(A0 ) consists of two paths and G(A0 ) has no diagonal edge, G(A0 ) satisfies the condition (b)of Theorem 4.1. By applying (5.2) repeatedly, we have p(A0 ) = q(A0 ) = s. Hence, by (3.7), we have½
(s + 1, s)(if sign det A = sign det A0 )(p(A), q(A)) =(s, s + 1)
(if sign det A 6= sign det A0 ),which together with (5.4) and (5.5) implies (5.3).
A sign-nonsingular symmetric matrix A such that G(A) is a chordless circuit has a sign-admissible
sequence. Indeed, by row and column permutations, A is represented as
0 ∗0 ··· 0 ∗


..
 ∗ 0
.
∗
0 



. 
 0 ∗ . . . . . . . . . .. ,A=
 .. . . . .
..
 .
.
.
. ∗ 0 




..
 0
. ∗
0 ∗ 
∗

0

···

7

0

∗

0

where ∗ designates a nonzero entry of A. Hence any nested sequence of principal submatrices in A issign-admissible.
We are now ready to prove Theorem 5.1.
Proof of Theorem 5.1. By Lemmas 5.2–5.4 and Theorem 4.1, if A is a sign-nonsingular symmetricmatrix, then there is a sign-admissible nested sequence of principal submatrices in A. Therefore, theinertia of A is uniquely determined by the sign pattern.

6

Algorithm for Sign-Nonsingular Symmetric Matrices

In this section, we present a polynomial time algorithm for computing the inertia of a given signnonsingular symmetric matrix.
Let A be a sign-nonsingular symmetric matrix of order n. Then z(A) = 0. It is easy to see from
Lemmas 5.2–5.4 that the inertia is obtained by computing the inertia of a sign-nonsingular symmetricmatrix smaller than A, if we find a perfect matching M in G(A) which satisfies the condition (a) or (b)of Theorem 4.1. Thus we can compute the inertia of A recursively. However, we present a practicallymore efficient algorithm that computes the inertia by finding circuits in M ∪ M > in the same way as
the proof of Theorem 4.1.
The algorithm starts with finding a perfect matching Md in G(A) with maximum number of
diagonal edges. The index set N of the row and column set is partitioned into J+ := {j | (uj , vj ) ∈Md , ajj > 0}, J− := {j | (uj , vj ) ∈ Md , ajj < 0} and J∗ := {j | (uj , vj ) 6∈ Md }. We can find Md
efficiently by the maximum weight perfect matching algorithm. Indeed, define the weight function
w : E → {0, 1} on the bipartite graph G(A) by we = 1 for each diagonal edge e and we = 0 for theother edges. Then a maximum weight perfect matching with respect to w corresponds to Md . The
maximum weight perfect matching algorithm runs in O(n(m + nW )) time with Dial’s implementationof Dijkstra’s shortest path algorithm[1], where W is the largest weight in the graph and m is thenumber of edges. In this case, W is equal to 1. Hence it requires O(nm) time.
Let C be the set of all symmetric circuits in Md ∪ Md> . If there exist a pair of symmetric circuits
C, C 0 ∈ C connected by an edge in E \ (Md ∪ Md> ), then delete C and C 0 from C. We repeat this until
there are no such pair of symmetric circuits.
We denote by C1 , . . . , Ch the remaining symmetric circuits in C. Let Jk be the indices corresponding
to Ck for each k = 1, . . . , h, that is, Jk := {i | (ui , vj ) ∈ Ck }. Let J0 be the remaining indices, that is,S
J0 := J∗ \ hk=1 Jk . Then it follows from Lemmas 5.2 and 5.3 that the inertia of A is obtained byhX
1p(A[Jk ]),p(A) = |J+ | + |J0 | +
2
k=1
h

X
1
q(A) = |J− | + |J0 | +q(A[Jk ]).
2

(6.1)

k=1

The first term in the right-hand side of (6.1) is obtained by applying (5.1) repeatedly to each i ∈J+ ∪ J− , and the second term by applying (5.2) repeatedly to each i, j ∈ J0 .
The inertia of A[Jk ] for k = 1, . . . , h is obtained by Lemmas 5.3 and 5.4. Indeed, if Ck has achord, then find a chordless symmetric circuit Ck0 in G(A[Jk ]) (otherwise Ck0 := Ck ). Let Jk0 be theindices corresponding to Ck0 . Let 2t0k be the number of the negative entries of A[Jk0 ]. Comparings0k = (|Jk0 | − 1)/2 with t0k , we have, by (5.2) and (5.3), that½
(sk + 1, sk ) (if t0k ≡ s0k mod 2)(6.2)(p(A[Jk ]), q(A[Jk ])) =(sk , sk + 1) (if t0k 6≡ s0k mod 2),
where sk := (|Jk | − 1)/2. Thus the inertia of A can be computed from (6.1) and (6.2).
8

¶

³

1. Find a perfect matching Md in G(A) with maximum number of diagonal edges.
2. Find the set of all symmetric circuits C in Md ∪ Md> .
3. Repeat the following.
• If there exists a pair of symmetric circuits C and C 0 in C connected by an edge in
E \ (Md ∪ Md> ), then delete C and C 0 from C.
4. Denote the remaining symmetric circuits in C by C1 , . . . , Ch . Let Jk be the indices corresponding to Ck . For each connected component G(A[Jk ]) for k = 1, . . . , h, do the following.
• If Ck has a chord, then find a chordless symmetric circuit Ck0 in G(A[Jk ]).
• Compute the inertia of A[Jk ] by (6.2).
5. Return the inertia of A obtained by (6.1).
µ´

Figure 3: Algorithm for computing the inertia of a sign-nonsingular symmetric matrix
The algorithm is now summarized in Fig. 3.
The algorithm requires O(mn) time in total. Indeed, it requires O(nm) time to find a perfectmatching Md . In addition, it requires O(m) time to find symmetric circuits C1 , . . . , Ch in Md ∪ Md> ,and O(m) time to find a chordless symmetric circuit in G(A[Jk ]) for k = 1, . . . , h.
Theorem 6.1 For a sign-nonsingular symmetric matrix A of order n, the inertia of A can be computed in O(nm) time, where m is the number of nonzero entries of A.

7

Complexity of Testing Sign-Nonsingularity

In this section, we discuss the complexity status of the decision problem whether the inertia of agiven symmetric matrix is uniquely determined by the sign pattern of the matrix entries. Hall, Li andWang[3] proved the following theorem.
Theorem 7.1 (Hall, Li and Wang [3]) For a given symmetric matrix A, Ã has the same inertia
for any Ã ∈ Q∗ (A) if and only if
max{rankÃ | Ã ∈ Q∗ (A)} = min{rankÃ | Ã ∈ Q∗ (A)}.
Furthermore, it is known that t-rankA = max{rankÃ | Ã ∈ Q∗ (A)} [7]. Hence the inertia of A is
uniquely determined by the sign pattern if and only if A satisfies
t-rankA = min{rankÃ | Ã ∈ Q∗ (A)}.

(7.1)

However, it is not clear how to discern efficiently if a given matrix satisfies (7.1) or not.
First, we suppose A is a term-nonsingular matrix of order n. Then A satisfies (7.1) if and only
if A is a sign-nonsingular symmetric matrix. As already mentioned in Section 2, it can be donein polynomial time to discern whether a given symmetric matrix has an equisignum determinant.
However, having an equisignum determinant is not a necessary condition for a symmetric matrix to9

be sign-nonsingular. For example,+1 0 +1 +1
 0 +1 +1 +1 A=
 +1 +1 −1 0 +1 +1 0 −1is a sign-nonsingular symmetric matrix, while it does not have an equisignum determinant[3].
We prove the following theorem.
Theorem 7.2 For a symmetric matrix A, the problem of deciding whether A is not a sign-nonsingularsymmetric matrix is NP-complete.
To prove Theorem 7.2, we use the following result by Klee, Ladner and Manber[5].
Theorem 7.3 (Klee, Ladner and Manber [5]) For each positive integer k, the problem of deciding whether an n × (n + bn1/k c) matrix is not row full-rank only by the sign pattern is NP-complete.
Proof of Theorem 7.2. It is clear that the decision problem whether a given matrix A is not a signnonsingular symmetric matrix is in NP, as it suffices to exhibit a singular symmetric matrix with thesame sign pattern as A.
Suppose we can discern in polynomial time whether A is not a sign-nonsingular symmetric matrix.
Consider
µ
¶
O B
A=
,
B> I
where B is a rectangular matrix such that |Col(B)| = |Row(B)| and t-rankB = |Row(B)|, and I is
an identity matrix. Then det A = − det B > B holds. Since B > B is a positive semidefinite matrix,
this implies
det A¶ ≤ 0. By the assumption, we can discern in polynomial time whether there exists
µ
O B̃
Ã =
∈ Q∗ (A) such that det Ã = − det B̃ > B̃ = 0. This implies that we can test inB̃ > I˜
polynomial time whether there exists B̃ ∈ Q(B) which is not row full-rank. Hence it is NP-complete
to discern whether A is not a sign-nonsingular symmetric matrix by Theorem 7.3.
It follows from Theorem 7.2 that the decision problem whether the inertia of A is not determinedby the sign pattern is also NP-complete.
Corollary 7.4 For a symmetric matrix A, the problem of deciding whether the inertia of A is notdetermined by the sign pattern is NP-complete.

References[1] R. K. Ahuja, T. L. Magnanti and J. B. Orlin: Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.
[2] R. A. Brualdi and B. L. Shader: Matrices of Sign-solvable Linear Systems, Cambridge University
Press, Cambridge 1995.
[3] F. J. Hall, Z. Li, and D. Wang: Symmetric sign pattern matrices that require unique inertia,
Linear Algebra and Its Applications, 338, pp.153–169, 2001.
[4] R. A. Horn and C. R. Johnson: Matrix Analysis, Cambridge University Press, 1985.
[5] V. Klee, R. Ladner and R. Manber: Sign-solvability revisited, Linear Algebra and Its Applications,59, pp.131–158, 1984.
10

[6] L. Lovász and M. D. Plummer: Matching Theory, Annals of Discrete Math, 29, North-Holland,
Amsterdam, 1986.
[7] K. Murota: An identity for bipartite matching and symmetric determinant, Linear Algebra and
Its Applications, 222, pp.261–274, 1995.
[8] N. Robertson, P. D. Seymour, and R. Thomas: Permanents, Pfaffian orientations, and even directed circuits, Annals of Mathematics, 150, no. 3, pp.929–975, 1999.
[9] V. V. Vazirani and M. Yannakakis: Pfaffian orientations, 0-1 permanents, and even cycles in
directed graphs, Discrete Applied Mathematics, 25, pp.179–190, 1989.

11