MATHEMATICAL ENGINEERINGTECHNICAL REPORTS

Sign-Solvable Linear Complementarity Problems

Naonori KAKIMURA(Communicated by Satoru IWATA)METR 2006–60

November 2006

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 oﬀered 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.

Sign-Solvable Linear Complementarity Problems
Naonori KAKIMURA∗
November 2006 (Revised March 2007)

Abstract
This paper presents a connection between qualitative matrix theory and linear complementarity problems (LCPs). An LCP is said to be sign-solvable if the set of the sign patterns of thesolutions is uniquely determined by the sign patterns of the given coeﬃcients. We provide acharacterization for sign-solvable LCPs such that the coeﬃcient matrix has nonzero diagonals,
which can be tested in polynomial time. This characterization leads to an eﬃcient combinatorial algorithm to ﬁnd the sign pattern of a solution for these LCPs. The algorithm runs in
O(γ) time, where γ is the number of the nonzero coeﬃcients.
Key Words: Linear Complementarity Problems, Combinatorial Matrix Theory

1

Introduction

This paper deals with linear complementarity problems (LCPs) in the following form:
LCP(A, b): ﬁnd (w, z)s.t. w = Az + b,
wT z = 0,
w ≥ 0, z ≥ 0,
where A is a real square matrix, and b is a real vector. The LCP, introduced by Cottle [4], Cottle andDantzig [5], and Lemke [16], is one of the most widely studied mathematical programming problems,
which contains linear programming and convex quadratic programming. Solving LCP(A, b) for an
arbitrary matrix A is NP-complete [3], while there are several classes of matrices A for which theassociated LCPs can be solved eﬃciently. For details of the theory of LCPs, see the books of
Cottle, Pang, and Stone [6] and Murty [20].
The sign pattern of a real matrix A is the {+, 0, −}-matrix obtained from A by replacing eachentry by its sign. When we develop an LCP model in practice, the entries of A and b are subject tomany sources of uncertainty including errors of measurement and absence of information. On theother hand, the sign patterns of A and b are structural properties independent of such uncertainty.
This motivates us to provide a combinatorial method that exploits the sign patterns before using
numerical information.
Sign pattern analysis for matrices and linear systems, called qualitative matrix theory, wasoriginated in economics by Samuelson [24]. Various results about qualitative matrix theory arecompiled in the book of Brualdi and Shader [1]. For a matrix A, we denote by Q(A) the set of∗
Department of Mathematical Informatics, Graduate School of Information Science and Technology, Universityof Tokyo, Tokyo 113-8656, Japan. naonori kakimura@mist.i.u-tokyo.ac.jp

1

all matrices having the same sign pattern as A, called the qualitative class of A. The qualitativeclass of a vector is deﬁned similarly. A square matrix A is said to be sign-nonsingular if Ã is
nonsingular for any Ã ∈ Q(A). The problem of recognizing sign-nonsingular matrices has manyequivalent problems in combinatorics [17, 21, 25, 27], while its time complexity had been open for along time. In 1999, Robertson, Seymour, and Thomas [22] presented a polynomial-time algorithm
for solving this problem (cf. McCuaig [18, 19]).
For linear programming, Iwata and Kakimura [11] proposed sign-solvability in terms of qualitative matrix theory. A linear program max{cx | Ax = b, x ≥ 0}, denoted by LP(A, b, c), is
sign-solvable if the set of the sign patterns of the optimal solutions of LP(Ã, b̃, c̃) is the same asthat of LP(A, b, c) for any Ã ∈ Q(A), b̃ ∈ Q(b), and c̃ ∈ Q(c). They showed that recognizing
sign-solvability of a given LP is NP-hard, and gave a suﬃcient condition for sign-solvable linear
programs, which can be tested in polynomial time. Moreover, they devised a polynomial-timealgorithm to obtain the sign pattern of an optimal solution for linear programs satisfying thissuﬃcient condition.
In this paper, we introduce sign-solvability for linear complementarity problems. We say that
LCP(A, b) is sign-solvable if the set of the sign patterns of the solutions of LCP(Ã, b̃) coincides withthat of LCP(A, b) for any Ã ∈ Q(A) and b̃ ∈ Q(b). An LCP(A, b) such that all diagonal entries
of A are nonzero is said to have nonzero diagonals. The class of LCPs with nonzero diagonals
includes LCPs associated with positive deﬁnite matrices, P-matrices, and nondegenerate matrices,which are all of theoretical importance in the context of LCPs (e.g. [6, Chapter 3]). LCPs with
P-matrices are related to a variety of applications such as circuit equations with piecewise linear
resistances [8] and linear systems of interval linear equations [23]. We present a characterization
for a sign-solvable LCP(A, b) with nonzero diagonals, and describe a polynomial-time algorithm tosolve them from the sign patterns of A and b.
We ﬁrst provide a suﬃcient condition for sign-solvable LCPs with nonzero diagonals. A squarematrix A is term-nonsingular if the determinant of A contains at least one nonvanishing expansion
term. A square matrix A is term-singular if it is not term-nonsingular. A matrix A is term-singular
if and only if Ã is singular for any Ã ∈ Q(A). An m × n matrix with m ≤ n is said to be totally
sign-nonsingular if all submatrices of order m are either sign-nonsingular or term-singular, namely,
if the nonsingularity of each submatrix of order m is determined uniquely by the sign pattern ofthe matrix. Totally sign-nonsingular matrices were investigated in the context of sign-solvability oflinear systems [1, 12, 13, 26] (the terms “matrices with signed mth compound” and “matrices withsigned null space” are used instead). Recognizing totally sign-nonsingular matrices can be donein polynomial time by testing sign-nonsingularity of related square matrices [11]. We show that, if
the matrix M = (A b) is totally sign-nonsingular and A has nonzero diagonals, then LCP(A, b) issign-solvable.
We then present a characterization of sign-solvable LCPs with nonzero diagonals. A row of amatrix is called mixed if it has both positive and negative entries. A matrix is row-mixed if every row
is mixed. For an LCP(A, b) with nonzero diagonals, we introduce the residual row-mixed matrix,
which is the special submatrix of M = (A b) deﬁned in Section 3. Then LCP(A, b) with nonzero
diagonals is sign-solvable if and only if its residual row-mixed matrix M 0 satisﬁes one of followings:
M 0 does not contain the subvector of b, M 0 has no rows, or M 0 is totally sign-nonsingular. The
residual row-mixed matrix can be obtained in polynomial time. Thus the sign-solvability of a given
LCP(A, b) with nonzero diagonals can be recognized in polynomial time.
This characterization leads to an eﬃcient combinatorial algorithm to solve a given LCP(A, b)
with nonzero diagonals from the sign patterns of A and b. The algorithm tests the sign-solvability,and ﬁnds the sign pattern of a solution if it is a sign-solvable LCP with solutions. In this algorithm,
we obtain a solution of LCP(Ã, b̃) for some Ã ∈ Q(A) and b̃ ∈ Q(b). If LCP(A, b) is sign-solvable,2then LCP(A, b) has a solution with the same sign pattern as the obtained one. The time complexity
is O(γ), where γ is the number of nonzero entries in A and b. We note that the obtained signpattern easily derives a solution of the given LCP by Gaussian elimination. Thus a sign-solvable
LCP with nonzero diagonals is a class of LCPs which can be solved in polynomial time.
Before closing this section, we give some notations and deﬁnitions used in the following sections.
For a matrix A, the row and column sets are denoted by U and V . If A is a square matrix,
suppose that U and V are both identical with N . We denote by aij the (i, j)-entry in A. Let
A[I, J] be the submatrix in A with row subset I and column subset J, where the orderings of theelements of I and J are compatible with those of U and V . The submatrix A[J, J] is abbreviatedas A[J]. The support of a row subset I, denoted by Γ(I), is the set of columns having nonzero
entries in the submatrix A[I, V ], that is, Γ(I) = {j ∈ V | ∃i ∈ I, aij 6= 0}. For a vector b, the jthentry of b is denoted by bj . The vector b[J] means the subvector with index subset J. The support
of a vector b is the column index subset {j | bj 6= 0}.
For a square matrix∏ A, let π be a bijection from the row set N to the column set N . We denoteby p(A|π ) = sgnπ i∈N aiπ(i) the expansion term of det A corresponding to π. Then a matrix A
is term-nonsingular if and only if there exists a bijection π : N → N with p(A|π ) 6= 0. A squarematrix A is sign-nonsingular if and only if A is term-nonsingular and every nonvanishing expansion
term of det A has the same sign [1, Theorem 1.2.5]. Thus, if A is sign-nonsingular, the determinantof every matrix in Q(A) has the same sign. It is also shown in [1, Theorem 2.1.1] that, if a squarematrix A is sign-nonsingular, then A is not row-mixed.
This paper is organized as follows. In Section 2, we provide a suﬃcient condition using totally
sign-nonsingular matrices. Section 3 gives a characterization for sign-solvable LCPs with nonzero
diagonals. In Section 4, we describe a polynomial-time algorithm to solve sign-solvable LCPs with
nonzero diagonals from the sign patterns of the given coeﬃcients.

2

Totally Sign-Nonsingular Matrices

In this section, we give a suﬃcient condition for sign-solvable LCPs using totally sign-nonsingularmatrices. For that purpose, we deﬁne sign-nondegenerate matrices. A square matrix A is nondegenerate if every principal minor is nonzero. A matrix A is nondegenerate if and only if LCP(A, b)
has a ﬁnite number of solutions for any vector b [6]. Recognizing nondegenerate matrices is co-NPcomplete [2, 20]. A square matrix A is said to be sign-nondegenerate if Ã is nondegenerate for any
Ã ∈ Q(A). Then the following lemma holds, which implies that sign-nondegeneracy can be tested
in polynomial time.
Lemma 2.1. A square matrix A is sign-nondegenerate if and only if A is a sign-nonsingularmatrix with nonzero diagonals.
Proof. To see the necessity, suppose that A is sign-nondegenerate. Let Ã be a matrix in Q(A).
Since all principal minors in Ã are nonzero, all diagonal entries are nonzero. Moreover, det Ã
is nonzero, which implies that A is sign-nonsingular. Thus A is a sign-nonsingular matrix with
nonzero diagonals.
To see the suﬃciency, suppose that A is a sign-nonsingular matrix with nonzero diagonals.
Let J ⊆ N be an index subset. Since the principal submatrix A[J] has nonzero diagonals, A[J]is term-nonsingular. Let σ1 and σ2 be bijections from J to J such that p(A[J]|σ1 ) 6= 0 andp(A[J]|σ2 ) 6= 0. Deﬁne bijections πk : N → N to be πk (j) = j if j ∈ N \ J and πk (j) = σk (j)if j ∈ J for k = 1, 2.∏Since A has nonzero diagonals, p(A|π1 ) and p(A|π2 ) are both nonzero. Byp(A|πk ) = p(A[J]|σk ) i∈N \J aii for k = 1, 2, it follows from sign-nonsingularity of A that the two3

nonzero terms p(A[J]|σ1 ) and p(A[J]|σ2 ) have the same sign. Thus A[J] is sign-nonsingular, which
implies that A is sign-nondegenerate.
We now obtain the following theorem. For LCP(A, b), let M be the matrix in the form of
M = (A b), where the column set is indexed by N ∪ {g}.
Theorem 2.2. For a linear complementarity problem LCP(A, b) with nonzero diagonals, if thematrix M = (A b) is totally sign-nonsingular, then LCP(A, b) is sign-solvable.
Proof. First) LCP(A, b) has a solution (w, z). Let J be the support of z. Then we( assume thatw[N \ J]+ b = 0, where AJ is the matrix in the form of
have AJ
z[J]
(
)
O
A[J]
AJ =
.
−I A[N \ J, J]
Since A is sign-nondegenerate by Lemma 2.1, each principal submatrix is sign-nonsingular, andhence AJ is also sign-nonsingular by det AJ = ± det A[J]. Then it holds by Cramer’s rule that{−det AjJ /det AJ , if j ∈ J,
zj =
(1)
0,
if j ∈ N \ J,{0,
if j ∈ J,
wj =
(2)
j
−det AJ /det AJ , if j ∈ N \ J,where AjJ is the matrix obtained from AJ by replacing the jth column vector of AJ with b. The
determinant of AjJ is represented by{± det M [J, J − j + g], if j ∈ J,j
det AJ =(3)± det M [J + j, J + g], if j ∈ N \ J,where J − j + g means J \ {j} ∪ {g} with g being put at the position of j in J, the set J + j
coincides with J ∪ {j}, and J + g means J ∪ {g} in which g is put at the same position as that ofj in J + j.
We show that AjJ is either term-singular or sign-nonsingular for any J ⊆ N and j ∈ N . Assume
that there exists j ∈ N such that AjJ is term-nonsingular, but not sign-nonsingular. First supposethat j ∈ J. By (3), the submatrix M [J, J − j + g] is term-nonsingular, but not sign-nonsingular.
Then there exist two bijections σ1 and σ2 from J to J − j + g such that p(M [J, J − j + g]|σ1 )and p(M [J, J − j + g]|σ2 ) are both nonzero, and have the opposite signs. Deﬁne two bijections
πk : N → N − j + g to be πk (i) = i if i ∈ N \∏J and πk (i) = σk (i) if i ∈ J for k = 1, 2. Byp(M [N, N − j + g]|πk ) = p(M [J, J − j + g]|σk ) i∈N \J aii for k = 1, 2, the two nonzero termsp(M [N, N − j + g]|π1 ) and p(M [N, N − j + g]|π2 ) are both nonzero, and have the opposite signs.
This contradicts the total sign-nonsingularity of M . Next suppose that j ∈ N \ J. Then, by (3),M [J + j, J + g] is term-nonsingular, but not sign-nonsingular. Let σ1 and σ2 be bijections fromJ + j to J + g such that p(M [J + j, J + g]|σ1 ) and p(M [J + j, J + g]|σ2 ) are both nonzero, andhave the opposite signs. Deﬁne two bijections πk : N → N − j + g for k = 1, 2 to be πk (i) = i if
i ∈ N \(J ∪{j}) and πk (i) = σk (i) if i ∈ J ∪{j}. Then the two nonzero terms p(M [N, N −j +g]|π1 )and p(M [N, N − j + g]|π2 ) have the opposite signs, which contradicts the total sign-nonsingularityof M .
Thus AjJ is either term-singular or sign-nonsingular for any index j. The matrix AJ is signnonsingular. Therefore, it follows from (1) that the sign pattern of (w, z) is independent of the4magnitudes of A and b. Hence LCP(Ã, b̃) has a solution with the same sign pattern as that of(w, z) for any Ã ∈ Q(A) and b̃ ∈ Q(b). Thus LCP(A, b) is sign-solvable.
Next assume that LCP(A, b) has no solutions. Note that LCP(A, b) has no solutions if andonly if AJ x + b = 0 has no nonnegative solutions for any J ⊆ N , that is, there exists j ∈ N−1such that (A−1
J b)j < 0 for any J ⊆ N . It follows from Cramer’s rule that we have (AJ b)j =jjj−det AJ /det AJ < 0. Since det AJ 6= 0, the matrix AJ is sign-nonsingular. Hence it holds that−det ÃjJ /det ÃJ < 0 for any Ã ∈ Q(A) and b̃ ∈ Q(b). Thus LCP(Ã, b̃) has no solutions for any
Ã ∈ Q(A) and b̃ ∈ Q(b), which means that LCP(A, b) is sign-solvable.
Sign-solvable LCPs do not necessarily satisfy this suﬃcient condition. Indeed, consider LCP(A, b),
where A and b are deﬁned to be()()−p1 −p2
0A=and b =
+p3 +p4+p5
for positive constants p1 , . . . , p5 > 0. Then LCP(A, b) has a unique solution w = (0 p5 )T and z = 0,
and hence LCP(A, b) is sign-solvable. However, this does not satisfy the condition of Theorem 2.2,
as A is not sign-nonsingular.
We conclude this section with sign-solvability of LCPs associated with another class of matrices.
A square matrix A is a P-matrix if every principal minor is positive. A P-matrix is clearly
nondegenerate. It is known that A is a P-matrix if and only if LCP(A, b) has a unique solution forany vector b. Recognizing P-matrices is co-NP-complete [7]. A matrix A is a sign-P-matrix if all
matrices in Q(A) are P-matrices. Then similar statements to Lemma 2.1 and Theorem 2.2 holdfor sign-P-matrices.
Corollary 2.3. A square matrix A is a sign-P-matrix if and only if A is a sign-nonsingular matrix
with positive diagonals.
Corollary 2.4. For a linear complementarity problem LCP(A, b) with positive diagonals, if thematrix M = (A b) is totally sign-nonsingular, then LCP(Ã, b̃) has a unique solution with the same
sign pattern as that of LCP(A, b).

3

Sign-Solvable LCPs with Nonzero Diagonals

In this section, we describe a characterization for a sign-solvable LCP(A, b) with nonzero diagonals.
Recall that M is the matrix in the form of M = (A b), where the column set is indexed by N ∪ {g}.

3.1

The Residual Row-Mixed Matrix

We ﬁrst introduce the residual row-mixed matrix of LCP(A, b) with nonzero diagonals.
For each row index i, the ith equation of LCP(A, b) is represented by∑wi =aij zj + bi .

(4)j∈Γ({i})First assume that M has a nonpositive row i, that is, bi ≤ 0 and aij ≤ 0 for all j ∈ N . Supposethat bi < 0. Since any solution of LCP(A, b) is nonnegative, the ith row implies that LCP(A, b)
has no solutions. Next suppose that bi = 0. Then, if LCP(A, b) has a solution (w, z), the solution(w, z) must satisfy that zj = 0 for any j ∈ Γ({i}).
5Next assume that M has a nonnegative row i, that is, bi ≥ 0 and aij ≥ 0 for all j ∈ N . Let(w, z) be a solution of LCP(A, b). If wi > 0, then the complementarity implies zi = 0. Supposethat wi = 0. Since any solution is nonnegative, (w, z) must satisfy zj = 0 for any j ∈ Γ({i}), andhence zi = 0 by aii 6= 0. Thus, if LCP(A, b) has a solution and M has a nonnegative row i, any
solution of LCP(A, b) must satisfy that zi = 0. Note that there exists j ∈ Γ({i}) with zj > 0 if
and only if the left-hand side of (4) is positive, i.e., wi > 0.
Therefore, if M has a nonnegative or nonpositive row, then we know that some entries of any
solution must be zero. We can repeat this process as follows. Set M (1) = M . For a positive(ν)(ν)
integer ν and a matrix M (ν) , let I− be the set of nonpositive rows in M (ν) , and I+ be the set(ν)
of nonnegative rows that have a nonzero entry in M (ν) . If Γ(I− ) contains the index g, then the
(ν)
(ν)
(ν)
(ν)
LCP has no solutions. Deﬁne I (ν) = I+ ∪ I− and J (ν) = I+ ∪ Γ(I− ). Then any solution (w, z)
of LCP(A, b) satisﬁes zj = 0 for any j ∈ J (ν) . Let M (ν+1) be the matrix obtained from M (ν) by
deleting the rows indexed by I (ν) and the columns indexed by J (ν) . Repeat this for ν = 1, 2, . . .
until I (ν) = J (ν) = ∅, that is, until either M (ν) is row-mixed or M (ν) has no rows.
We call the remaining row-mixed submatrix M 0 the residual row-mixed matrix of LCP(A, b).
Note that, if LCP(A, b) has solutions, the column index g is not deleted in each iteration.
Assume that the column set of M 0 contains the index g. Let M 0 be in the forms of M 0 = (A0 b0 ),where b0 is the subvector of b and A0 is the submatrix of A with row set U 0 and column set V 0 . We
denote Ū 0 = N \ U 0 and V̄ 0 = N \ V 0 . Since A has nonzero diagonals, Ū 0 ⊆ V̄ 0 holds, and hence wehave V 0 ⊆ U 0 . Suppose that M 0 has no rows. Then V̄ 0 = N holds, which means that any solution(w, z) of LCP(A, b) must satisfy z = 0. Since g is not deleted in each iteration, the vector b isnonnegative. Thus (b, 0) is a unique solution of LCP(A, b). Next suppose that M 0 is row-mixed.
Consider the following system:w = A0 z + b0 ,wiT zi = 0, for any i ∈ V 0 ,w ≥ 0, z ≥ 0.

(5)

We claim that there exists a one-to-one correspondence between solutions of LCP(A, b) and (5).
For a solution (w, z) of LCP(A, b), the pair (w[U 0 ], z[V 0 ]) is a solution of (5). Conversely, let(w0 , z 0 ) be a solution of (5). Deﬁne (w, z) to be z[V 0 ] = z 0 , z[V̄ 0 ] = 0, and w = Az + b. Thenw[U 0 ] = A0 z 0 + b0 = w0 ≥ 0 holds. Moreover, since each row in A[Ū 0 , V 0 ] is nonnegative, we havew[Ū 0 ] = A[Ū 0 , V 0 ]z 0 + b[Ū 0 ] ≥ 0. By V 0 ⊆ U 0 , the pair (w, z) satisﬁes the complementarity wT z = 0.
Thus (w, z) is a solution of LCP(A, b).

3.2

Characterization

Using the residual row-mixed matrix M 0 of LCP(A, b), we have the following theorem.
Theorem 3.1. Let LCP(A, b) be a linear complementarity problem with nonzero diagonals, andM 0 be the residual row-mixed matrix. Then LCP(A, b) is sign-solvable if and only if one of thefollowings holds:• The column set of M 0 does not contain the index g.
• The residual row-mixed matrix M 0 has no rows.
• The residual row-mixed matrix M 0 is totally sign-nonsingular.

6In order to prove this theorem, we give some deﬁnitions. A linear system Ax = b has signed
nonnegative solutions if the set of the sign patterns of nonnegative solutions of Ãx = b̃ is the sameas that of nonnegative solutions of Ax = b for any Ã ∈ Q(A) and b̃ ∈ Q(b). A matrix A is said
to have signed nonnegative null space if Ax = 0 has signed nonnegative solutions. Matrices withsigned nonnegative null space were examined by Fisher, Morris, and Shapiro [9]. They showed thata row-mixed matrix has signed nonnegative null space if and only if it is the matrix called mixed
dominating, which is deﬁned to be a row-mixed matrix which does not contain a square row-mixed
submatrix. By the result of mixed dominating matrices, the following two lemmas hold.
Lemma 3.2 (Fischer and Shapiro [10]). If a row-mixed matrix A has signed nonnegative null space,then the rows of A are linearly independent.
A matrix A is said to have row-full term-rank if A has a term-nonsingular submatrix with row
size. A matrix A has column-full term-rank if AT has row-full term-rank.
Lemma 3.3 (Fischer, Morris, and Shapiro [9]). An n × (n + 1) row-mixed matrix has signed
nonnegative null space if and only if it is a totally sign-nonsingular matrix with row-full term-rank.
We have the following lemmas.
Lemma 3.4. Suppose that the matrix (A b) is row-mixed. If the linear system Ax + b = 0 has
signed nonnegative solutions, then it has a solution all of whose entries are positive.
Proof. Since (A b) is row-mixed, there exist Ã ∈ Q(A) and b̃ ∈ Q(b) such that the sum of thecolumns of Ã and b̃ is zero, that is, Ã1 + b̃ = 0, where 1 is the column vector whose entries are allone. This implies that Ãx = b̃ has a solution all of whose entries are positive for any Ã ∈ Q(A)and b̃ ∈ Q(b).
Lemma 3.5. Suppose that M = (A b) is row-mixed. The linear system Ax + b = 0 has signed
nonnegative solutions if and only if M has signed nonnegative null space.
Proof. Suppose (that) the matrix M has signed nonnegative null space. Since {x | Ax + b = 0, x ≥0} = {x | (A b) x1 = 0, x ≥ 0} is contained in the set of nonnegative vectors in the null space ofM , the linear system Ax + b = 0 has signed nonnegative solutions.
Next suppose that Ax + b = 0 has signed nonnegative solutions, and that M does not havesigned nonnegative null space. Then M is not mixed dominating, which means that there exists
a row-mixed square submatrix in M . Note that a row-mixed square submatrix which does notcontain any row-mixed square proper submatrix is term-nonsingular. Choose a row-mixed termnonsingular submatrix M [I, J] such that |J| is maximum. Since M is row-mixed, the maximality
implies that each row of M [N \ I, J] is mixed or zero.
We deﬁne B to be B = M [N, J \ {g}] if g ∈ J, and B = M [N, J] otherwise. Then (B b) does
not have signed nonnegative null space. The set of the nonnegative( ) vectors in the null space of(B b) consists of the union of {x | Bx = 0, x ≥ 0} and {x | (B b) xxg = 0, x ≥ 0, xg > 0}. Since theset of sign patterns in the second one coincides with that of {x | Bx + b = 0, x ≥ 0} and Bx + b = 0
has signed nonnegative solutions, we may assume that B does not have signed nonnegative nullspace. Let B̃ ∈ Q(B) be a matrix such that B̃ has column-full rank. Then the null space of B̃
is empty, and B̃x + b = 0 has a unique solution all of whose entries are positive by Lemma 3.4.
By the assumption, there exists B̂ ∈ Q(B) such that B̂x = 0 has a nonnegative, nonzero solutionx∗ . Lemma 3.4 implies that B̂x + b = 0 has a solution x0 all of whose entries are positive. Thenx0 − µx∗ , where µ = mini∈N x0i /x∗i , is also a nonnegative solution of B̂x + b = 0. Thus the linear
system Bx + b = 0 does not have signed nonnegative solutions, which contradicts that Ax + b = 0
has signed nonnegative solutions.
7

We are now ready to prove Theorem 3.1.
Proof of Theorem 3.1. To show the necessity, suppose that LCP(A, b) is sign-solvable. Assume
that M 0 has a row and that M 0 is in the form of M 0 = (A0 b0 ), where b0 is the subvector of bindexed by g. Let x be a nonnegative vector with A0 x + b0 = 0. Since there exists a one-to-one
correspondence between solutions of LCP(A, b) and (5), (0, x) is a solution of (5). Hence thesign-solvability of LCP(A, b) implies that the linear system A0 x + b0 = 0 has signed nonnegative
solutions. It follows from Lemma 3.5 that M 0 = (A0 b0 ) has signed nonnegative null space. By
Lemma 3.2 and V 0 ⊆ U 0 , it holds that U 0 = V 0 , i.e., A0 is square. Therefore, Lemma 3.3 implies
that M 0 is totally sign-nonsingular.
We next show the suﬃciency. If the column set of M 0 does not contain the index g, thenclearly LCP(A, b) is a sign-solvable LCP with no solutions. Suppose that M 0 is in the forms of
M 0 = (A0 b0 ). If M 0 has no rows, then (b, 0) is a unique solution of LCP(A, b), which meansthat LCP(A, b) is sign-solvable. Next suppose that M 0 = (A0 b0 ) is totally sign-nonsingular. By
V 0 ⊆ U 0 , it holds that |U 0 | = |V 0 | or |U 0 | = |V 0 | + 1. If |U 0 | = |V 0 |, then M 0 is sign-nonsingular,
which contradicts that M 0 is row-mixed. Hence we have |U 0 | = |V 0 | + 1. Since A0 has nonzero
diagonals, (5) forms the linear complementarity problem with nonzero diagonals. By Theorem 2.2,
LCP(A0 , b0 ) is sign-solvable, and hence so is LCP(A, b).
Note that LCP(A, b) is a sign-solvable LCP with no solutions if and only if the column set of

M 0 does not contain g.

If M is row-mixed, then the residual row-mixed matrix is M itself. Hence Theorem 3.1 implies
the following corollary.
Corollary 3.6. Let A have nonzero diagonals, and M = (A b) be a row-mixed matrix. Then
LCP(A, b) is sign-solvable if and only if the matrix M is totally sign-nonsingular.
We close this section with an example of sign-solvable LCPs with nonzero diagonals. Consider
LCP(A, b), where A and b have the sign patterns, respectively,




0
+ + 0 0 0
 + 
 − + + 0 +  + − + − 0  and  0  .




 0 
 − 0 − − + −
0 − + 0 +The residual row-mixed matrix is+ − 0 0
 − − + 0 ,
+ 0 + −

which is obtained from the matrix (A b) by deleting the ﬁrst two rows and the ﬁrst two columns.
This residual row-mixed matrix is totally sign-nonsingular, and hence LCP(A, b) is sign-solvable.

4

Algorithm for Sign-Solvable LCPs with Nonzero Diagonals

In this section, we describe an algorithm for a given LCP(A, b) with nonzero diagonals. The
algorithm tests sign-solvability of LCP(A, b), and ﬁnds the sign pattern of a solution of LCP(A, b)
if it is sign-solvable.
The algorithm starts with ﬁnding the residual row-mixed matrix M 0 as described in the previous
section. If the column set of M 0 does not contain the index g, then LCP(A, b) is sign-solvable and8has no solutions. Let M 0 be in the forms of M 0 = (A0 b0 ), where b0 is the subvector of b and A0 is
the submatrix of A with row set U 0 and column set V 0 . We denote Ū 0 = N \ U 0 and V̄ 0 = N \ V 0 .
Note that V 0 ⊆ U 0 holds. If M 0 has a row and M 0 is not totally sign-nonsingular, then return that
LCP(A, b) is not sign-solvable by Theorem 3.1.
Assume that M 0 has no rows. Then LCP(A, b) is sign-solvable, and (b, 0) is a unique solutionof LCP(A, b). Next assume that M 0 has a row and M 0 = (A0 b0 ) is totally sign-nonsingular. Then
LCP(A, b) is sign-solvable by Theorem 3.1. Since M 0 is row-mixed, there exists M̃ = (Ã b̃) ∈ Q(M )such that the sum of the columns of M̃ 0 ∈ Q(M 0 ) is zero. Hence it follows from (5) that the pair(w, z), deﬁned to be z[V̄ 0 ] = 0, z[V 0 ] = +1, and w = Ãz + b̃, is a solution of LCP(Ã, b̃). This meansthat the vector w satisﬁes that wj > 0 if j ∈ Ū 0 and A[{j}, V 0 ] has nonzero entries, and wj = 0
otherwise. Since LCP(A, b) is sign-solvable, (w, z) is the sign pattern of a solution of LCP(A, b).
We now summarize the algorithm description.
Algorithm: An algorithm for LCPs with nonzero diagonals.
Input: A linear complementarity problem LCP(A, b) with nonzero diagonals.
Output: The sign pattern of a solution if LCP(A, b) is sign-solvable.
Step 1: Set M (1) = M and ν = 1. Repeat the following until I (ν) = J (ν) = ∅.
(ν)

(ν)

(ν)

(ν)

1-1: Find I− and I+ , where I− is the set of nonpositive rows in M (ν) , and I+ is the setof nonnegative rows that have a nonzero entry in M (ν) .
(ν)

1-2: If g ∈ Γ(I− ), then return that LCP(A, b) is sign-solvable and has no solutions.
(ν)

(ν)

(ν)

(ν)

1-3: Let I (ν) = I+ ∪ I− and J (ν) = I+ ∪ Γ(I− ). Deﬁne M (ν+1) to be the matrix obtainedby deleting the rows indexed by I (ν) and the columns indexed by J (ν) from M (ν) .
1-4: Set ν = ν + 1 and go back to Step 1.
Step 2: Let M 0 = (A0 b0 ) be the remaining submatrix, and U 0 , V 0 be the row and column sets of
A0 , respectively. If M 0 has a row and M 0 is not totally sign-nonsingular, then return that
LCP(A, b) is not sign-solvable. Otherwise go to Step 3.
Step 3: Return that LCP(A, b) is sign-solvable and do the following.
3-1: If U 0 is empty, then return the sign pattern of a solution (w, z) = (b, 0).
3-2: Otherwise, return the sign pattern of (w, z) deﬁned to be{{+, if j ∈ V 0+,
sgn zj =and sgn wj =0, otherwise0,

if j ∈ K
otherwise(6)

where K is the set of rows which have nonzero entries in A[Ū 0 , V 0 ], that is, K = {j ∈Ū 0 | Γ({j}) ∩ V 0 6= ∅}.
Applying this algorithm to the example at the end of Section 3, we obtain the sign pattern ofa solution, w = ( 0 + 0 0 0)T and z = ( 0 0 + + +)T .
Based on this algorithm, we can compute a solution of a sign-solvable LCP as well as thesign pattern of a solution. Suppose that M 0 has a row. The solution (w, z) with the obtained signpattern satisﬁes that A0 z[V 0 ]+b0 = 0, z[V̄ 0 ] = 0. Since A0 is nonsingular by total sign-nonsingularityof M 0 , we can compute a solution of LCP(A, b) by performing Gaussian elimination.
9

The running time bound of the algorithm is now given as follows. Note that an n × (n + 1)
row-mixed matrix A is a totally sign-nonsingular matrix with row-full term-rank if and only if all
square submatrices of order n are sign-nonsingular [1, Theorem 5.3.3]. Such matrix is called an
S-matrix in [1, 15], which can be recognized in O(n2 ) time [14].
Theorem 4.1. For a linear complementarity problem LCP(A, b) with nonzero diagonals, let nbe the matrix size of A, and γ the number of nonzero entries in A and b. Then the algorithm
tests sign-solvability in O(n2 ) time, and, if LCP(A, b) is sign-solvable, the algorithm ﬁnds the signpattern of a solution in O(γ) time.
Proof. In the νth iteration in Step 1, it requires O(γν ) time to ﬁnd I (ν) and J (ν) , where γν isthe number of nonzero entries in the columns deleted in the νth iteration. Since each column isdeleted at most once, Step 1 takes O(γ) time in total. In Step 2, if the residual row-mixed matrix
M 0 is totally sign-nonsingular, M 0 has row-full term-rank and the column size is one larger than
the row size. Hence testing total sign-nonsingularity of M 0 is equivalent to recognizing S-matrices.
Thus it requires O(n2 ) time to test sign-solvability in Step 2. Step 3 requires O(γ) time. Thus thisstatement holds.

Acknowledgements
The author is very obliged to Satoru Iwata for his suggestions and reading the draft of the paper.
This work is supported by the 21st Century COE Program on Information Science and Technology
Strategic Core at the University of Tokyo from the Ministry of Education, Culture, Sports, Scienceand Technology of Japan.

References[1] R. A. Brualdi and B. L. Shader, Matrices of Sign-solvable Linear Systems, Cambridge
University Press, Cambridge, 1995.
[2] R. Chandrasekaran, S. N. Kabadi, and K. G. Murty, Some NP-complete problems inlinear programming, Operations Research Letters, 1 (1982), pp. 101–104.
[3] S. J. Chung, NP-completeness of the linear complementarity problem, Journal of Optimization Theory and Applications, 60 (1989), pp. 393–399.
[4] R. W. Cottle, The Principal Pivoting Method of Quadratic Programming, in Mathematics
of Decision Sciences, Part 1, G. B. Dantzig and A. F. Veinott, eds., American MathematicalSociety, Providence R. I., 1968, pp. 142–162.
[5] R. W. Cottle and G. B. Dantzig, Complementary pivot theory of mathematical programming, Linear Algebra and Its Applications, 1 (1968), pp. 103–125.
[6] R. W. Cottle, J.-S. Pang, and R. E. Stone, The Linear Complementarity Problem,
Academic Press, 1992.
[7] G. E. Coxson, The P-matrix problem is co-NP-complete, Mathematical Programming, 64(1994), pp. 173–178.
[8] J. T. J. V. Eijndhoven, Solving the linear complementarity problem in circuit simulation,
SIAM Journal on Control and Optimization, 24 (1986), pp. 1050–1062.
10

[9] K. G. Fischer, W. Morris, and J. Shapiro, Mixed dominating matrices, Linear Algebra
and Its Applications, 270 (1998), pp. 191–214.
[10] K. G. Fischer and J. Shapiro, Mixed matrices and binomial ideals, Journal of Pure andApplied Algebra, 113 (1996), pp. 39–54.
[11] S. Iwata and N. Kakimura, Solving linear programs from sign patterns, Mathematical
Programming, (to appear).
[12] S.-J. Kim and B. L. Shader, Linear systems with signed solutions, Linear Algebra and Its
Applications, 313 (2000), pp. 21–40.
[13], On matrices which have signed null-spaces, Linear Algebra and Its Applications, 353(2002), pp. 245–255.

[14] V. Klee, Recursive structure of S-matrices and O(m2 ) algorithm for recognizing strong signsolvability, Linear Algebra and Its Applications, 96 (1987), pp. 233–247.
[15] V. Klee, R. Ladner, and R. Manber, Sign-solvability revisited, Linear Algebra and Its
Applications, 59 (1984), pp. 131–158.
[16] C. E. Lemke, Bimatrix equilibrium points and mathematical programming, Management
Science, 11 (1965), pp. 681–689.
[17] L. Lovász and M. D. Plummer, Matching Theory, vol. 29 of Annals of Discrete Mathematics, North-Holland, Amsterdam, 1986.
[18] W. McCuaig, Brace decomposition, Journal of Graph Theory, 38 (2001), pp. 124–169.
[19], Pólya’s permanent problem, The Electronic Journal of Combinatorics, 11 (2004), R79.

[20] K. G. Murty, Linear Complementarity, Linear and Nonlinear Programming, Internet Edition, 1997.
[21] G. Pólya, Aufgabe 424, Archiv der Mathematik und Physik, 20 (1913), p. 271.
[22] N. Robertson, P. D. Seymour, and R. Thomas, Permanents, Pfaﬃan orientations, andeven directed circuits, Annals of Mathematics, 150 (1999), pp. 929–975.
[23] J. Rohn, Systems of linear interval equations, Linear Algebra and Its Applications, 126 (1989),
pp. 39–78.
[24] P. A. Samuelson, Foundations of Economics Analysis, Harvard University Press, 1947;
Atheneum, New York, 1971.
[25] P. Seymour and C. Thomassen, Characterization of even directed graphs, Journal of
Combinatorial Theory, Series B, 42 (1987), pp. 36–45.
[26] J.-Y. Shao and L.-Z. Ren, Some properties of matrices with signed null spaces, Discrete
Mathematics, 279 (2004), pp. 423–435.
[27] V. V. Vazirani and M. Yannakakis, Pfaﬃan orientations, 0-1 permanents, and even cycles
in directed graphs, Discrete Applied Mathematics, 25 (1989), pp. 179–190.

11