A GEOMETRIC PROBLEM IN SIMPLICIAL CONES WITH APPLICATION TO LINEAR COMPLEMENTARITY PROBLEMS Katta G. Murty, University of Mighigan Layne T. Watson, University of Michigan L. M. Kelly, Michigan State University Technical Report 86-16 April 28, 1986

A GEOMETRIC PROBLEM IN SIMPLICIAL CONES WITH APPLICATION TO LINEAR COMPLEMENTARITY PROBLEMS Katta G. MURTYt Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI 48109, USA Layne T. W7ATSONt Departments of Electrical Engineering and Computer Science, Industrial and Operations Engineering, and Mathematics, University of Michigan, Ann Arbor, MI 48109, USA L. M. KELLY Department of Mathematics, Michigan State University, East Lansing, MI 48824, USA Abstract. We consider the following geometric question: suppose we are given a simplicial cone K in Rn. Can we find a point p in the interior of K satisfying the property that the orthogonal projection of p onto the linear hull of every face of K is in the relative interior of that face? This question plays an important role in determining whether a certain class of linear complementarity problems (LCP's) can be solved efficiently by a pivotal algorithm. The answer to this question is always in the affirmative if n<2, but not so for n>3. We establish some conditions for the answer to this question to be yes, and relate them to other well known properties of square matrices. Key words: simplicial cones, orthogonal projections, faces, linear complementarity problem, LCP, pivotal algorithms, P-matrices, symmetric positive definite matrices, Z-matrices, M-matrices. 1. The geometric question Let D be any real nonsingular square matrix of order n. The cone Pos(D) = y: y = Dx, x E R", 0} is a simplicial cone in R". We study the following geometric question: is there a point b in the interior of Pos(D) satisfying the property that for every face F of Pos(D), the orthogonal projection of b onto the linear hull of F is in the relative interior of F? As an example, let n = 2 and consider D ( ). Pos(D) is an angle in the twodimensional Cartesian plane, in this case an obtuse angle. See Figure 1. The point (1,1/2) is in the interior of Pos(D), but it does not satisfy the properties required of b given above, since the orthogonal projection of (1, 1/2)t onto the linear hull of (-1, 1)t is the point d, a negative multiple of (-1, 1)t. In the same way, it can be verified that the point (0, 1)t in the interior of Pos(D) also does not satisfy the properties required of b given above. However, the point b = (-1 -t V2, 1)" on the bisector line of the angle Pos(D) does satisfy all the properties mentioned above. Our geometric question is very simple when n = 2. If Pos(D) is an acute or right angle, every point in the interior of Pos(D) satisfies the properties required of b given above. If Pos(D) is an obtuse angle, any point b such that Dtb > 0 (which includes any nonzero point on the bisector ray of the angle Pos(D)) satisfies the properties of b required above. When n > 3, the concept of a bisector line does not generalize to the cone Pos(D). However, when n = 2, the important property of a nonzero point on the bisector line of Pos(D) is that it t Supported in part by NSF Grant ECS-8521183. t Supported in part by Control Data Corporation Grant 84V101 and AFOSR Grant 85-0250. 1

\ 1 (-1, (~,1)) b 0i... *,-) x 2 \ N (1, 0) d \ \ Figure 1. D =(- l ) Pos(D) is the cone marked by the angle sign. The point b is on the bisector line of the angle. 2

is equidistant from each facet of Pos(D), and this property can be generalized for n > 3. Let D-1 = (i3,) and i = il,..,in) Then the point which is at a distance of 1 from each facet of Pos(D) is a = D(61,...,)t. The point a is in the interior of Pos(D), and one is tempted to conjecture that a satisfies all the properties required of b given above, but this conjecture is false for -1 1 20 D- 0 3 1 0 0 1 In fact for this matrix D, surprisingly, there exists no point in the interior of Pos(D) satisfying the properties required of b given above. Again, when I -1 -1 D= 0 1 1 0 0 1 the point b = (2, 8, 1) is in the interior of Pos(D) and satisfies all the required properties of b. In this case, the point which is at a distance of 1 from each facet of Pos(D) is a = (-1,1 + 2, 1)t, and even though a is in the interior of Pos(D), it does not satisfy all the properties required of b. Hence, for n > 3, if a point equidistant from the facets of Pos(D) does not satisfy the properties required of b given above, we cannot conclude that there is no such point b. Thus our geometric question is trivial when n = 2, but non-trivial for n > 3. This geometric question came up in the study of constructing efficient pivotal algorithms for solving certain classes of linear complementarity problems (LCP's). The LCP is a fundamental problem in mathematical programming; it has been the focus of extensive research over the last 20 years. 2. Application to LCP Let M = (mi) be a given real square matrix of order n, and q = (qj) a given column vector in R". The linear complementarity problem (LCP) with data q, M, denoted by (q, M), is the problem of finding vectors w = (Wj), z = (zj) e Rn satisfying w - Mz = q w,z~O (1) wtz= 0. We will use the following notation. If D = (dij) is any matrix, D.j denotes its jth column vector. For any subset of row indices L and subset of column indices J, DLJ is the submatrix (dij: i e L,j E J) of D determined by these subsets, and D. denotes the matrix with column vectors Dj for j c J. For any matrix D, Pos(D) = C(D) = {x x = Dy for some y > 0}, and S(D) = {x: x = Dy for some real y} is the linear hull of the columns of D. If x = (xj) C R, and J C {1,...,n}, zJ denotes the vector (zj: j E J), |J| denotes the cardinality of J, and MJJ is the principal submatrix of M corresponding to J. I denotes the unit matrix of order n. If K and A are any two sets, K\A denotes the set of all elements of K which are not in A. r = {1,..., n}. Rmxn is the class of real m x n matrices. 3

In (1), the pair of variables {wj, Zj} is known as the jth complementary pair of variables, for j 1=,..., n. In (1), the column vector associated with wj is Ij, and the column vector associated with zj is -Mj. The pair {I.j, -M} is the jth complementary pair of column vectors in (1). A complementary vector of variables in (1) is a vector y = (yi,..., y)t where yj E {wj, zj} for each j = 1,..., n. If Aj is the column in (1) associated with yj, the matrix A = (A.... A.,) is known as the complementary matrix associated with y. The complementary vector y is said to be a complementary basic vector in (1) if the corresponding complementary matrix is nonsingular. If y is a complementary basic vector associated with the complementary matrix A, the complementary basic solution of (1) corresponding to y is given by all variables in (1) not in y are 0 y = A-1 q (2) y=-A-lq. Clearly, the solution in (2) satisfies the complementarity condition wtz = 0, because y is a complementary vector. If A-1q _ 0, the solution in (2) is a solution of the LCP (q, AMl) (it satisfies all the conditions in (1)). It is then said to be a complementary basic feasible solution, and y is said to be a complementary feasible basic vector for (1). The complementary basic feasible solution in (2) and complementary basic feasible vector y are nondegenerate if A-1q > 0. For any J c r, the LCP of order IJI, wj - Mjjzj = qj > _, n- o (3) wJi zJ0, _O WJJ = 0 which is the LCP (qJ, AfJJ), is known as the principle subproblem of (1) corresponding to the subset J. DEFINITIONS: A real square matrix of order n is said to be a P-matrix if all its principal subdeterminants are positive. It is said to be a Z-matrix if all its off-diagonal elements are nonpositive. It is said to be an M-matrix if it is both a P-matrix and a Z-matrix. The classes of all n x n P-matrices, Z-matrices, A-matrices are denoted by P, Z,, 3in, respectively. One method for solving the LCP (q, M) when Al is a P-matrix is the following. Select a column vector p > 0 in R". Consider the following parametric LCP, where a is a nonnegative parameter w z I -M q + ap wz 0,Wtz = 0 (4) When a > 0 is sufficiently large, w is a complementary feasible basic vector for (4), and the method is initiated with this. The method moves through complementary basic vectors for (4), exchanging one basic variable by its complement in each pivot step, in an effort to find a complementary feasible basic vector for (4) for smaller and smaller values of a until it reaches the value 0. In some general 4

stage, let (ula, zj) be the complementary basic vector for (4) at this stage, for some J c r, J = r\J. The corresponding basic solution for (4) is (wJ, Z) - 0 ) - 4J+pJ) (5) \wj + apc where (J, - pj) = - (jj)-1(qj, pj), (4J, y) = (qj, pJ) + jJJ(. j, pJ) The smallest value of a for which (5) remains > 0 is 0 given by -} {f Maximum {-' j/p:j such that pj > 0} (6) -1c, if< 0 If 0 < 0, (ui, zj) is a complementary feasible basic vector for (4) when a = 0, that is, a complementary feasible basic vector for (1), terminate. Otherwise, let r be the maximizing index in (6)(or the maximum among these indices, if there is a tie). Perform a pivot step replacing the basic variable from the pair {wr, Zr} in the current complementary basic vector by its complement, and continue the method with the new complementary basic vector. This method is known to solve the LCP (q, M), when M is a P-matrix, in a finite number of pivot steps. Even though this method is finite, in the worst case, it may take up to 2" pivot steps before termination [8]. However, in [11] J. S. Pang and R. Chandrasekaran observed that if the vector p is selected so that the pair (M, p) satisfy property 1 given below, then the method will terminate after at most n pivot steps, for any q G R". PROPERTY 1: Let M e P,, p e R", p > 0. Then the pair (M, p) is said to satisfy property 1 if (AMjj)-1pj > 0 for all nonempty J {1,..., n}. If the pair (Al, p) satisfies property 1, then in the above method, when (wy, zj) is the complementary basic vector in the basic solution (5), pj < 0 for all j E J, and the maximizing index r giving the value of 0 in (6) will not be in J. That is, once a z-variable becomes basic in the above method, it will stay basic until termination. This guarantees that the method terminates after at most n pivot steps. PROPERTY 2: Let M Pn,, p e Rn, p > 0. Then the pair (Al, p) is said to satisfy property 2 if the vector composed of the z-variables only is a nondegenerate complementary feasible basic vector in every principal subproblem of the LCP: w z I -M -p w,z > 0,WtZ = 0 (7) Clearly (M, p) satisfies property 1 iff it satisfies property 2. So, properties 1 and 2 are equivalent. The important question now is to identify the class of P-matrices M for which there exists a vector p such that (A, p) satisfies property 1 or 2. For the special case when Al is positive definite 5

symmetric, we will provide a geometric characterization for this question, using the results from [9, 10j. If AM is a real positive definite and symmetric matrix of order n, there exists a real nonsingular square matrix D of order n such that M = DtD. One choice for D is the Cholesky factor of AM. In this section D denotes a real nonsingular square matrix of order n. M = DtD. Pos(D) is the simplicial cone C(D) = {y: y = Dx for some x _ 0}. For each 0 7 J C r, Pos(DrJ) is the face of Pos(D) determined by J. Let p E Rn, p > 0, and let b = (Dt)-lp. LEMMA 1: For J c r, the orthogonal projection of b in the linear hull of Pos(DrJ) lies in the relative interior of Pos(Drj) iff (AMjj)-1p > 0, or equivalently, iff zj is the nondegenerate complementary feasible basic vector for the principal subproblem of (7) corresponding to J. PROOF: If J = 0, the result holds by convention. So, assume that J i- 0, and let J = s. The linear hull of Pos(DrJ) is LJ = {DrJAJ AJ E RS}. So, to find the orthogonal projection of b in LJ, we have to solve the problem: minimize (b6 - DrjAj)t(b - DrjAj) over AJ E RS. The optimum solution of this problem is Ax= (Ajj)-1(Dr j)tb (8) and the orthogonal projection of b in Lj is DrjAj. This point is in the relative interior of Pos(Drj) iff A1 > 0, that is, iff (AMj)-l(Dt)Jrb = (AIjj)-l p > 0, or equivalently, iff zj is the nondegenerate complementary feasible basic vector for the principal subproblem of (7) corresponding to J. U We now define a geometric property. PROPERTY 3: Let D be a real nonsingular square matrix of order n and b C Rn. The pair (D, b) is said to satisfy property 3 iff b is in the interior of Pos(D), and for every face of Pos(D), the orthogonal projection of b on the linear hull of that face is in the relative interior of that face. THEOREM 1: Let D be a real nonsingular square matrix of order n and p C R", p > 0. Let = DtD, b = (Dt) - p. The pair (M, p) satisfies property 1 or 2 iff the pair (D, b) satisfies property 3J. PROOF: This result follows directly from Lemma 1. U THEOREM 2: Let M be a real positive definite symmetric matrix of order n and let D C Rnxn be such that M = DtD. There exists a p such that the pair (AM, p) satisfies property 1 or 2 iff there exists a b such that the pair (D, b) satisfies property 3. PROOF: This result follows from Theorem 1 directly. U 3. The special case n = 2 Let n = 2, and D be any real nonsingular square matrix of order 2. As discussed in Section 1, Pos(D) is an angle, acute or obtuse, in the two dimensional Cartesian plane. Let b be any nonzero point on the bisector ray of the angle Pos(D). Then it is well known that the pair (D, b) satisfies property 3. Thus when n = 2, for every nonsingular square matrix D there exists a b such that the pair (D, b) satisfies property 3, and the b can be found easily. In fact b= 1(D., + D2) 6

will do, and this vector is on the bisector ray of the angle Pos(D). Consequently, when M is a real symmetric posive definite matrix of order 2, there always exists a point p such that the pair (M, p) satisfies property 1 or 2, for example p = Dtb, where D is such that h = DtD and b is given above, will do. Suppose M = (myj) is a P-matrix of order 2. Then from the definitions, the set of all p = (pi, p2)t such that (M, p) satisfies property 1 or 2 is the set of feasible solutions of m22pl - ml2P2 > 0 -m2ipl + m11p2 > 0 Pi > 0( P2 > 0 and it can be verified using Gordan's theorem of the alternative [61 that this system always has a solution (P1 P2). Thus when M is a P-matrix of order 2, there always exists a vector p such that the pair (M, p) satisfies property 1 or 2, and a point p like that can be found easily by solving (9) given M. 4. Results for n > 2 THEOREM 3: Given a P-matrix M of order n, the set of all p such that the pair (M, p) satisfies property 1 or 2 is either empty or an open polyhedral cone. Given a real nonsingular square matrix D of order n, the set of all b such that the pair (D, b) satisfies property 3 is either empty or an open polyhedral cone. PROOF: Given Al, the set of all p such that (AM, p) satisfies property 1 or 2 is the set of all feasible solutions of the system (IJJ)-IP > 0 for all 0 3 Jc {1,...,n} p > 0 Since these are all strict linear inequality constraints, if the set of feasible solutions of this system is nonempty, it is an open polyhedral cone. Given D, let A = DtD, which is a P-matrix. Let K = {p: (M,p) satisfies property 1 or 2 }. Then by Theorem 1, the set of all b such that (D, b) satisfies property 3 is {(Dt)-'p: p K}, and this is an open polyhedral cone when it is nonempty, since the same property holds for K. U THEOREM 4: Let D be a real square nonsingular matrix of order n. If the rays of D., and D. make an obtuse angle for all i f j, then there exists a b such that (D, b) satisfies property 3. PROOF: So, for every i f j, (D.i)tDj < 0. Thus M = DtD is a P-matrix which has nonpositive off-diagonal elements (i.e., M is an M- matrix) and hence Ml-1 > 0 (see [11), and by the same argument (Mjj)-1 > 0 for all 0 7 J c r. So, for every p C R", p > 0, we have (AlMj)-1p > 0 in this case. Thus (M,p) satisfies property 1 in this case for every p > 0, p C Rn. Consequently, by Theorem 1, (D, b) satisfies property 3 for all b in the interior of Pos((Dt)-1), which proves this theorem. C As mentioned in Section 1, if D is a real nonsingular square matrix of order 2 and Pos(D) is an acute angle (i.e., (D21)tD2 > 0), (D, b) satisfies property 3 for all b in the interior of Pos(D). The intuitive generalization of this result to higher dimensions is that if D is a real nonsingular 7

square matrix of order n such that the rays of D.i and Dj make an acute angle for all i: j (i.e., (D.i)tDj > 0 for all i j), then there exists a b such that (D, b) has property 3. This conjecture is certainly true for n = 2 and n = 3, and seems intuitive for higher dimensions also. However, by an approach similar to that in [2, 4, 5] (reducing R4 to S3 to R3), it can be verified that a counterexample to this conjecture for n = 4 is -1 1 20 0 0 3 1 0 0 0 1 0' 5 5 5 5 The following conjecture has been made by Soo Chang: CONJECTURE (Soo Chang): Let D C R"lX be invertible and ri r\{i} for i = 1,.., n. If the orthogonal projection of D. onto S(Dr) lies in the relative interior of C(D.r) for all i E r, then there exists a b E R" such that (D, b) has property 3. If a counterexample to this conjecture exists, it seems that it must exist in dimension 5 or higher. 5. A slight generalization We will now generalize these properties a little bit. Here D G RnXn may or may not be nonsingular. PROPERTY 4: The pair (D, q), where D C RnXn and q G R", is said to have property 4 if for each nonempty S C {1,..., n} the orthogonal projection of q onto the subspace S(D.s) lies in the relative interior of the cone C (D.s). PROPERTY 5: The pair (M, q), where M C Rnxn and q C Rn, is said to have property 5 if for each nonempty S C {1,..., n}, the linear complementarity problem (qs, Ass) has a solution (ws, Is) with zs > 0. DEFINITION: A matrix D C Rn"X is said to have property 4 (property 5) if there exists q e R" such that the pair (D, q) has property 4 (property 5, respectively). Let P4n = {D Rnxn D has property 4}, P5, = {D C RnXn D has property 5}. Note that the definition of property 4 is minimal in the sense that every subset J must be checked, as the following examples show%. The listed D and q have the projection property for every subset of {1,2, 3} except the ones listed: /3 2 4'10 D= 2 3 4, q= 10, J= {1,2,3), 0 0 1 -l 0 1 4 13\ D= 1 5 4, -= 18, J={1,2}), \0 0 1 i I -1 - 10 -1 D= 0 1 10, q= 100, J={1}. 0 0 1I 18

By our earlier results, if D E Rn is nonsingular, (D, q) has property 4 iff (DtD, -Dtq) has property 5. 6. Convexity results THEOREM 5: For D E R`nX the set of q G Rn such that (D, q) has property 4 is convex and open. PROOF: Let (D,q) have property 4 and 0 # T c {1,...,n}. Let S c T be a maximal subset such that D.s has independent columns. Then S(D.T) = S(D.S) and the coordinates of the projection of q onto S(D.T) with respect to the columns of D.s are given by a S _ Dtq as- Dsq where D!s = ((D.s)tD.s)-1 (D.s)t is the pseudo-inverse of D.s. The projection D.saS is in the relative interior of C(D.s) if and only if cas > 0. For i C T\S, there exist constants fij such that D.i D.ij - O, jes from the definition of S. Choose ei > 0, i E T\S, such that a + 2 iij > ie T\S for all j E S. Let ca be a vector with components Ei for i E T\S and as -+ E T\S Eiij for j E S. Then acT > 0 and D. sa = D.Ta T. Therefore the projection of q onto S(D.T) is given by D. TaT, aT > 0. By continuity, there is a neighborhood BT(q) of q such that aS = Dtq > 0 and &T constructed as above satisfies D.s&s - D.T&T and &T > 0 for all q E BT(q). Then for any p E nfTBT(q), the projection of p onto S(D.T) is given by D.T^T for aT > 0, for each nonempty T c {1,..., n}. Therefore the set of q such that (D, q) has property 1 is open. If (D, q1) and (D, q2) have property 4, then for fixed T c {1,..., n}, T 7 0, the projections of ql onto S(D.T) and q2 onto S(D.T) are given by D. Tca, C1 > 0 and D.Ta2, a2 > 0 respectively. Since projection is a linear operation, the projection of (1 -X)ql+ A q2 onto S(D T) is (1- )D T1- + AD. T2 = D.T((1 - A)a1 + Aa2), where (1 - A)a1 + Aa2 > 0 for 0 < A < 1. Since T was arbitrary, (D, (1 - A)q1 + Aq2) has property 4 for 0 < A < 1, which proves the convexity.' An example of a matrix which does not have property 4 is -1 1 20 D= 0 3 1. O 0 1 Note that -3 1 59 D-1 0 1 -1 0 0 3 9

also does not have property 4. By Theorem 2, 1 -1 -20 M DtD - 1 10 23 -20 23 4026 does not have property 5. PROPOSITION 1: For fixed q E R", n > 2, the set of matrices M e PFn P5,n such that (AM, q) has property 5 is not convex. PROOF: Take -2 1 -15 0 1 1 0 -3 M= 1 2;) N-( -15 2. K = -1. -12 M and N are P-matrices, (M, q) and (NA, q) have property 5, but (1/2 M + 1/2 N, q) does not have property 5. 1 CONJECTURE: For fixed q G R", the set of symmetric positive definite Al e RnXn such that (M, q) has property 5 is convex. DEFINITION: A set S c Rn is starlike if there exists a point c c S such that for any point p E S the line segment cp also lies in S. The set of points c E S with this property is called the kernel of S. THEOREM 6: The set Pn is starlike with the identity matrix I in its kernel. PROOF: Let M C Pn and 0 < a < 1. A characterization of P, is that AM E P if and only if the real eigenvalues of every principal submatrix of Al are positive [1, 13]. If As > 0 is an eigenvalue of a principal submatrix Mss, then (1 - a)+aAs > 0 is an eigenvalue of [(1 - a)-I+ aMss. Therefore the real eigenvalues of every principal submatrix of (1 - a)JI+ aAl, for 0 < a < 1, are positive, and (1 - C)I aM C Pn for 0 < a< 1. Observe that the set PO is not convex for n > 2: (1 ) and ( 15 1) are P-matrices, 2ni -15 n 2 cv 9 bt 1 5) ( 1 1) ( 1 - 7 is not. THEOREM 7: For fixed q C Rn, q < 0, the set of matrices M E Pn such that (Ml, q) has property 5 is starlike with I in its kernel. PROOF: Let (M,q) have property 5, where M C P,, q C R", q < 0. It suffices to prove that ((1 - A)M -+ AI, q) also has property 5, for 0 < A < 1. The proof of this is by induction on n. Since (M, q) and (I, q) have property 5, consider only 0 < A < 1. The result is trivial for n = 1. Assume it holds for P-matrices of dimension < n. Property 2 for (M, q) means that -MJ]Jqj > 0 for every subset J, 0 # J C {1,..., n}. Since property 2 is hereditary with respect to principal submatrices, the induction hypothesis yields that -[(1 - A)Mjj + AIJj -1q > 0 for 10

every subset J, 0 ~ J c {1,...,n}, of cardinality IJI < n. Thus all that remains is to prove - [(1 -A)M i- I]-q > 0. The kth component of z = - [(1 - A)M + A] q is, by Cramer's rule, det [(1 -A )M + AI].{ -l} q [(1 - A)M + A/]{k+. zk -. (10) %=: —--— Zk --— det [(1 - A)M -1- AI] Note that the denominator is positive since (1 - A)M + AI is also a P-matrix. The determinant is a multilinear form, and the numerator expands into a sum of determinants of the form det A, where A.i = (1 - A)Mi or A.i = Ali for i F k, and A.k = - q. Let J = j{il,..., k,...,jr} be the indices such that Ai = AIi for i J. Then det A = An-lJI(l - A)IJI-l(-MJ )det AJ > 0 since 0 < A < 1, (M, q) has property 5, and M is a P-matrix. (The subscript k here refers to the index set J = {l,..., k,...,jr}.) Therefore the numerator in (10) is positive, and so - - A)M + AI] l q > 0, which completes the induction step. (3 _i16 / 3 -2\ Note that Zn is convex, but vtrn is not: ( 2 ) and -16 are M-matrices but ( 3 -16)4 1( 3 2 -)9 is not. -2 11 2 -16 11 - -9 11 ) The following theorem from Fiedler and Ptak [1] will be useful. THEOREM 8: Let A, B E Z,, all the real eigenvalues of A be positive, and A < B. Then 1) A-1 > B-1 > 0; 2) all the real eigenvalues of B are positive; 3) det B > det A > 0. THEOREM 9: The set 3M, is starlike with the identity matrix I in its kernel. PROOF: Let M c Jin = Znf Pn. It is straightforward to verify that (1-A)I+AM for 0 < A < 1 is in both Zn and Pn. THEOREM 10: For any M GE Jt, and q < 0, q E Rn, the pair (M, q) has property 5. PROOF: Let M CE.M,, q E Rn, q < 0, and 0 S c {1,..., n}. Then Mss is also an M-matrix, hence a Z-matrix with positive real eigenvalues. By Theorem 8 above M1 > (diag(Mss))1 > 0 is nonnegative with positive diagonal elements, and therefore -M`lqs > 0. This proves property 5 for the pair (A, q). U 7. Generalization of the class JMn M-i11atrices have many nice properties with respect to the linear complementarity problem. However, they have more structure than is really needed for linear complementarity proofs. We argue that PF5n fn is the natural generalization of Min, and that P5n n Pn contains the essence of the class.tfn as far as linear complementarity is concerned. As support for this claim we offer: 11

UNIVERSITY OF MICHIGAN 1IIfIIIIIIII1 II II I1111111 III IIIII 3 9015 03994 8024 Properties of JMn Properties of P, n P5n 1. Min is not convex. Pn 5 P5 is not convex. 2. JMn is starlike from I. Pn n P5n is starlike from I. 3. Let M E JMi,. For every q < 0, (M, q) has Let M E P n P5n. For some q < 0, (M, q) has property 5. property 5. 4. Let M E Min, q E Rn. For every p > 0, Let M E Pn n P5n, q E Rn. For some p > 0, the LCP (q, M) can be solved with at most the LCP (q, M) can be solved with at most n complementary pivots via the parametric n complementary pivots via the parametric LCP (q c ap, M). LCP (q + cap, M). 5. Let M E,Mn. V 0 # J c {1,..., n} and Let M E PVn P5n. V 0: J C {1,...,n}and every q < 0, -Mj-Jqj > 0. some q < 0, -MJlqj > 0. References [1] M. Fiedler and V. Ptak, "On matrices with non-positive off-diagonal elements and positive principal minors", Czech. Math. J. 12 (1962) 382-400. [2] J. T. Fredricksen, L. T. \atson, and K. G. Murty, "A finite characterization of K-matrices in dimensions less than four", Math. Programming, to appear. 13] N. W. Kappel and L. T. Watson, "Iterative algorithms for the linear complementarity problem", Internat. J. Computer Math., to appear. [4] L. MI. Kelly and L. T. Watson, "Q-matrices and spherical geometry", Linear Algebra Appl. 25 (1979) 175-190. 15] L. M. Kelly and L. T. Watson, "Erratum: Some perturbation theorems for Q-matrices", SIAM J. Appl th.a. 34 (1978) 320-321. I6] O. L. Mangasarian, Nonlinear Programming, McGraw-Hill, New York, 1969. 17] K. G. Murty, "On the parametric complementarity problem", Engineering Summer Conference notes, University of Michigan, Ann Arbor, 1971.!8] K. G. Murty, "Computational complexity of complementary pivot methods", Mathematical Programming Study 7 (1978) 61-73. [9] K. G. Murty, "On the linear complementarity problem", Methods of Operations Research 31 (1978) 425-439. [10] K. G. Murty, Linear Complementarity, Linear and Nonlinear Programming, Heldermann Verlag, West Berlin, 1986. [11] J. S. Pang and R. Chandrasekaran, "Linear complementarity problems solvable by a polynomially bounded pivoting algorithm", Mathematical Programming Study 25 (1985) 13-27. [12] A. C. Stickney and L. T. Watson, "Digraph models of Bard-type algorithms for the linear complementarity problem", Math. Operations Res. 3 (1978) 322-333. [13] L. T. Watson, "A variational approach to the linear complementarity problem", Doctoral dissertation, Department of Mathematics, University of Michigan, Ann Arbor, Michigan, 1974. [14] L. T. Watson, "Some perturbation theorems for Q-matrices", SIAM J. Appl. Math. 31 (1976) 379-384. [15] L. T. Watson, "An algorithm for the linear complementarity problem", Internat. J. Computer Math. 6 (1978) 319-325. 12