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

AbstractThe relationship between the number of solutions to the complementarity problem, w = Mz + q, w⩾0, z⩾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 ϵ 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 ϵ Rn is that all principal subdeterminants of M are strictly positive. When M⩾0, there is at least one complementary feasible solution for each q ϵ 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 ϵ Rn which are nondegenerate. Also, if the number of complementary feasible solutions is a constant for each q ϵ 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