On the number of solutions to the complementarity problem and spanning properties of complementary cones

Abstract

The relationship between the number of solutions to the complementarity problem, w = Mz + q, w[ges]0, z[ges]0, wTz=0, the right-hand constant vector q and the matrix M are explored. The main results proved in this work are summarized below.The number of solutions to the complementarity problem is finite for all q [epsilon] Rn if and only if all the principal subdeterminants of M are nonzero. The necessary and sufficient condition for this solution to be unique for each q [epsilon] Rn is that all principal subdeterminants of M are strictly positive. When M[ges]0, there is at least one complementary feasible solution for each q [epsilon] Rn if and only if all the diagonal elements of M are strictly positive; and, in this case, the number of these solutions is an odd number whenever q is nondegenerate. If all principal subdeterminants of M are nonzero, then the number of complementary feasible solutions has the same parity (odd or even) for all q [epsilon] Rn which are nondegenerate. Also, if the number of complementary feasible solutions is a constant for each q [epsilon] Rn, then that constant is equal to one and M is a P-matrix.In the cartesian system of coordinates for Rn, an orthant is a convex cone generated by a set of n-column vectors in Rn, {A.1,...,A.n}, where for each j = 1 to n,A.j is either the jth column vector of the unit matrix of order n (denoted by I.j) or its negative - I.j. There are thus 2n orthants in Rn, and they partition the whole space. It is interesting to know what properties these orthants possess if we obtain them after replacing - I.j by some given column vector - M.j for j = 1 to n. Orthants obtained in this manner are called complementary cones, and their spanning properties are studied.