CP-RAYS IN SIMPLICIAL CONES Leroy M. Kelly Department of Mathematics Michigan State University East Lansing, Michigan 48824-1027, USA Katta G. Murty * Department of Industrial and Operations Engineering University of Michigan Ann Arbor, Michigan 48109-2117, USA Layne T. Watson ** Department of Computer Science Virginia Polytechnic Institute and State University Blacksburg, Virginia 24061, USA Technical Report No. 87-17 * Partially supported by NSF grants ECS-8521183 and ECS- 8704052 ** Supported in part by Control Data Corporation grant 84V101 and AFOSR grant 85-0250.

ABSTRACT: An interior point of a triangle is called a CP-point if its orthogonal projection on the line containing each side lies in the relative interior of that side. In classical mathematics, interest in the concept of regularity of a triangle is mainly centered on the property of every interior point of the triangle being a CP-point. We generalize the concept of regularity using this property, and extend this work to simplicial cones in Rn, and derive necessary and sufficient conditions for this property to hold in them. These conditions highlight the geometric properties of Z - matrices. We show that these concepts have important ramifications in algorithmic studies of the linear complementarity problem. We relate our results to other well known properties of square matrices. KEY WORDS: Simplicial cones, faces, orthogonal projections, CP- points and rays, linear complementarity problem, Positive definite matrices, Z-matrices, P-matrices.

1. INTRODUCTION Consider the equilateral triangle in R2 shown in Figure 1. The point b in Figure 1 satisfies the following properties. i) it is in the interior of the triangle ii) for each side of the triangle, the orthogonal projection of b on the straight line containing that side, is in the relative interior of that side. We will call a point satisfying these two properties, a CP- point (abbreviation for "centrally (or interiorly) projecting point", since it projects into the interior of each side) for the triangle. See Figure 2 for a triangle in R2 and a point c in it which is not a CP-point, since it violates (ii). / I 90g*.-n —- - Figure 1: An equilateral triangle and a CP-point b in it. Figure 2: A triangle in R2 and a point c in it which is not a CPpoint. However, the point b where all the bisectors lines of the angles meet, is a CP-point 1

Every triangle in R2 has a CP-point. By a well-known result in classical geometry, the bisector lines of the three angles of a triangle have a common point, b, and clearly that point b is a CPpoint for the triangle. See Figure 2. Also, it can be verified that every interior point of the equilateral triangle in Figure 1 is a CP-point for it, but this property does not hold for the triangle in Figure 2. In this paper we generalize the concept of CP-points for triangles in R2 to simplicial cones in Rn. We show that CP- points in simplicial cones play an important role in studies aimed at developing efficient algorithms for linear complementarity problems associated with positive definite symmetric matrices and P-matrices. We investigate several geometric properties associated with CP-points in simplicial cones, and relate them to classical results in matrix theory. 2. NOTATION We will use the following notation. LCP Linear Complementarity problem, defined in Section 4. LCP(q, M) an LCP for which the input data is the column vector q and square matrix M. Ei., E1j If E is any matrix, Ei denotes its ith row vector, Ej denotes its jth column vector. ELj If E=(eij)isanymatrixoforder m x n, given Lc {,,m}, J c {1; l In}, ELJ denotes the submatrix (eij: iEL,jEJ) of E determined by these subsets. Dj. submatrix of D with row vectors Di. for iEJ. D j Submatrix of D with Column vectors D j forj EJ xj If x=(xj)ERn, Jc { 1,' n), xj denotes the column vector (xj: jJ) 2

Pos(D) LH(D) I IJI K\A P-matrix Z-matrix M-matrix Pn, Zn, Mn Ix l I given the matrix D, this is the cone {x: x=Dy for some y>0} the linear hull of the set of column vectors of the matrix D, it is the subspace (x: x = Dy, for some vector y }. Unit matrix of order n. Cardinality of the set J. When K and A are two sets, KA is the set of elements of K which are not in A. a square matrix, all of whose principal subdeterminants are >0. a square matrix, all of whose off-diagonal elements are < 0. a Z-matrix which is also a P-matrix these are respectively the classes of P-, Z-. and M- matrices of order n. The Euclidean norm of the vector x=(x ), it is + i ) i+ XJ r the set {1,..., n) ray ofb for bERn, b * 0, therayofb is Pos(b)= (x:x=abforsome a > 0}. C pi, the length of the circumference of a circle in R2 with diameter 1. PD positive definite 3. CP-POINTS AND CP-RAYS IN SIMPLICIAL CONES Let D be a real square nonsingular matrix of order n. Pos(D) is a simplicial cone in Rn. For each j = 1 to n, the ray Pos(Dj) = {x: x = a Dj, a 2 0} is a generator or a generator ray for 3

Pos(D). In this section we define CP-points and CP-rays for Pos(D), and various other geometric entities related to Pos(D), which are used later in studying CP-points. Since Pos(D) is a simplicial cone, a face of Pos(D) is Pos(DJ) for some J c r and vice versa. For any J c r, we will say that Pos(Dj) is the face of Pos(D) corresponding to the subset J. When I J I = n - 1, Pos (Dj) is called a facet of Pos(D), it is a face of Pos(D) whose dimension is one less than the dimension of Pos(D). The point b EPos(D) is said to be a CP-point for Pos(D) if it satisfies the following properties 1, 2. 1. b is in the interior of Pos(D) 2. for every face F of Pos(D), the orthogonal projection of b on the linear hull of F, is in the relative interior of F. Since there are 2n - 2 nonempty proper faces of Pos(D), property 2 consists of 2n - 2 conditions. Here again, "CP-point" is an abbreviation for "centrally (or interiorly) projecting point", since this point projects into the relative interior of every face of Pos(D). As an example, consider the simplicial cone, Pos(D) in R2, given in Figure 3, which is an obtuse angle. The point (1, 1/4)T violates property 2, since its orthogonal projection on the linear hull of Pos(D 1) is d, which is not even in Pos(D.1). The point (0, 1)T also violates property 2, since its orthogonal projection on the linear hull of Pos(D.2) is 0, which is not in the relative interior of Pos(D.2). However, the point b = ( -1+, 1)T on the bisector line of the angle Pos(D) does satisfy both properties 1,2, and is therefore a CP-point for Pos(D) in this example. 4

I I I b (-1,1) (O,1), / f / Pos (D) ~' (1,1/4) l,, e * 0 - Pos (D) Oe's (1,21/4) 90 (1,0) I I * *0 * Figure 3: D = -1 1 Pos(D) is the thick obtuse angled cone. The open cone bounded 1 0 by the dashed lines, y: DTy > 0} is the set of all CP-points for Pos(D). If b is a CP-point for Pos(D), the ray Pos( b ) ={x: x = ab, for a > 0} is said to be a CP-ray for Pos(D). LEMMA 1: Every nonzero point on a CP-ray for Pos(D) is a CP- point for it. PROOF: By direct verification. [ 5

3.1 PROJECTION AND NON-PROJECTION FACES OF POS (D) RELATIVE TO A GIVEN POINT b. Given bE Rn, the face Pos(D j) of Pos(D) corresponding to J c r,is said to be a projection face relative to b if the orthogonal projection of b in LH(Dj) is in the relative interior of Pos (Dj); non-projection face relative to b otherwise. The face of Pos(D) corresponding to F is Pos(D) itself. By the above definition, Pos(D) is a projection face relative to b iff b is in the interior of Pos(D). Thus b is a CP-point iff every face of Pos(D) is a projection face relative to b, that is, iff there are no non- projection faces relative to b. The concept of a projection face is algorithmically very important in the study of the linear complementarity problem. In K. G. Murty and Y. Fathi [14] and P. Wolfe [19] it has been used to develop efficient algorithms for nearest point problems in simplicial cones, and special types of linear complementarity problems. These algorithms, and consequently projection faces, play an important role in a new algorithm for linear programming developed by S. Y. Chang and K. G. Murty [1]. 3.2 THE SET OF CP-POINTS OF POS (D) WHEN n = 2. If n = 2, and Pos(D) is an acute or right angle, every point in the interior of Pos(D) is a CPpoint for it. If Pos(D) is an obtuse angle, any point b in the interior of Pos((DT)l ) (these are points b satisfying DT b > 0) is a CP-point for Pos(D). See Figure 3. In this case (n = 2), the bisector ray of the angle Pos(D), is always a CP-ray for Pos(D). A nonzero point on this bisector ray is b = (1/2) ((D.1/ IID.111) + (D.2/llD.211)), the bisector ray is the ray of this point b. 3.3 INCENTER AND CIRCUMCENTER OF POS (D). Facets of Pos(D) are its faces of dimension n - 1. Forj = 1 to n, let Kj = Pos(D, * * 6

D j., Dj+ * *' D.n ) and let Hj be the linear hull of Kj.KI,..., Kn are the facets and H1, * *, Hn are the facetal hyperplanes for Pos(D). The concept of the bisector ray of the angle Pos(D) when n = 2, does not directly generalize for n > 3. However, when n = 2, the important property of a nonzero point on the bisector ray of Pos(D) is that it is equidistant from each facet of Pos(D), and this property can be generalized for n > 3. There is a point in the interior of Pos(D) which is equidistant (say, at a distance of 1) from each of the facetal hyperplanes for Pos (D), this point is called the incenter for Pos(D) and its ray is called the incenter ray for Pos(D). Each point on the incenter ray is equidistant from each of the facetal hyperplanes. See Figure 4. o - --— _ Figure 4: A simplicial cone in R3 and its incenter a. 7

Let P = ( ij ) = D -1. Then, forj = 1 to n, the facetal hyperplane Hj for Pos(D) is Hi= (x: i.x= 0. The incenter of Pos(D) which is at a distance of 1 from each facetal hyperplane of Pos(D) is a = D (8,...,86)T where by = II P.. II. This point a is clearly in the interior of Pos(D), and the ray of a is the incenter ray for Pos(D). When n = 2, the incenter ray for Pos(D) is exactly its bisector ray, and it is a CP-ray. One may be tempted to conjecture that the incenter ray is always a CP-ray for Pos(D). Unfortunately, this conjecture may be false when n > 3. Let -1 1 20 A D= 0 3 1 (2) o0 0 1 A A The incenter ray is not a CP-ray for Pos(D). Surprisingly, we found that Pos(D) has no CP-point at all. This can be seen from the following. If b = (b1, b2, b3)T is a CP-point for A Pos (D), b must satisfy -bl > 0 b2 >0 (3) b2 -b3 >0 >0 177b1 -59b2 +b3 besides other inequalities imposed by properties 1, 2. The first inequality in (3) comes from the A requirement that the orthogonal projection of b in the linear hull of { D1 ) lies in the relative A interior of Pos( D.1). The second and third inequalities above come from the requirement that b 8

A must be in the interior of Pos( D), that is, b = (-(x + a2 +20a3, 3a2 + 0X3, a3)T for some ( al, A A A a2, a3) > 0. Finally, the orthogonal projection of b in the linear hull of {D.2, D.3} is Y2 D.2 + A y3 D 3where y2 = (-56 b1 + 1189 b2 -23 b3)/3511 and y3 = (177 bl -59 b2 + b3)/3511, and since A A this point should be in the relative interior of Pos(D2, D3), we need y2 >0, y3 > 0; and y3 > 0 leads to the last inequality in (3). Multiplying the inequalities in (3) by 177, 58, 1, 1 in that order and summing leads to the inconsistent inequality 0 > 0, hence there exists no b satisfying (3), that A is no CP-point for Pos( D). At this stage we were quite tempted to conjecture that if D is a square nonsingular matrix such that the incenter ray is not a CP-ray for Pos(D), then Pos(D) has no CP-points at all. Unfortunately, this conjecture also turned out to be false. Let 1 -1 -1 D= 0 1 1 (4) 0 0 1 When D is the matrix given in (4), the incenter a = (-1, 1+ 2 2,1)T, is not a CP-point for Pos(D). But b = (2, 8, 1)T is a CP-point for Pos(D). Given the square nonsingular matrix D, the point d O0 is said to be the circumcenter of Pos(D) if: a) d is equidistant (say, at a distance of 1) from each of the generator rays of Pos(D) and b) the ray of d makes an acute angle with each of the generator rays of Pos(D). The ray of the circumcenter is known as the circumcenter ray for Pos(D). While the incenter is always contained in the interior of Pos(D), the circumcenter may not even be in Pos(D). The circumcenter ray makes equal acute angles with all the generator rays of Pos(D) (this provides another equivalent definition of the circumcenter ray for a simplicial cone). From this it can be verified that the circumcenter ray for Pos(D) is the ray of (DT)-1 r where T = (T 1 *,Tn)T Tj = I I D I I,j =1 to n. So the circumcenter ray is in the cone Pos(D) iff (DTD)-1 T > 0. 9

3.4 POLAR CONE Let D be a square nonsingular matrix of order n. The cone { y: yTx > O for every xE Pos(D) I is known as the Polar Cone of the cone Pos(D). Clearly, y is contained in the polar cone of Pos(D) iff yTD i 2 0, for all j = 1 to n, that is DTy > 0. This implies that the polar cone of Pos(D) is Pos (DT)-1 ). The Gale-Nikaido theorem ( [4] ) states that if A is a P- matrix, then the system Ax < 0, x > 0, has the unique solution x = 0. Using this and Gordan's theorem of the alternatives ( [8, 12] ), since (DTD)-1 is a PD matrix and hence a P-matrix, we conclude that the system: D-1 (DT)-1 x > 0, x > 0, has a solution x. This implies that the point (DT)1 x is both in the interior of Pos(D) and the interior of its polar cone. Thus, the interiors of Pos(D) and its polar cone always have a nonempty intersection. We will prove later (Corollary 1) that every CP-point for Pos(D) must be an interior point of its polar cone Pos((DT)l ). Here are some important properties of the polar cone of Pos(D). The circumcenter ray for Pos(D) can be verified to lie always in the polar cone of Pos(D) by definition. Let P = D-1 and let H1= {x: 1. x = 0} be the facetal hyperplane containing Pos(D2, * *, D.n). If y I H1, the orthogonal projection of y on H1 is y = y - (/113.I112) (PI)T f. y. Since P1. D =0 for allj =2 to n, it can be verified that if yTD > 0, then (y)TDj 2 0 also, for all j = 2 to n. This implies that the orthogonal projection of the polar cone of Pos(D) on H1 = LH{D2, ~* *, D.n is the polar cone of the face Pos(D., * *, D.n). In the same way it can be verified that the orthogonal projection of the polar cone of Pos(D) on the linear hull of any face of Pos(D) is the polar cone of that face. Consider pecial case 2. In this case if Pos(D) is a non-actute angle (see Figure 3) the polar cone Pos(T)1) c Pos(D), and from Section 3.2 the set of CP-points of Pos(D) is the interior of the polar cone. If Pos(D) is a non-obtuse angle, Pos((DT)-l) D Pos(D), and the set of CP-points for Pos(D) is its own interior. 10

3.5 DIHEDRAL ANGLES AND INWARD NORMALS TO FACETAL HYPERPLANES As before, let D be a square nonsingular matrix of order n and 3 = D-1. The hyperplane H1 defined in (1) are the facetal hyperplanes for Pos(D). For i, j f r, i ~j, the intersection of the closed half-spaces defined by Hi and Hj containing the Cone Pos(D) is known as the dihedral angle defined by the pair of facetal hyperplanes Hi and Hi. Let G1 = (3,1 )T / I I 3, 11 2. The ray of G is normal to the facetal hyperplane H., and is on the same side of H1 as Pos(D), hence it is known as an inward normal to thefacetal hyperplane H. n\ There are (2) Dihedral angles associated with any simplicial cone in Rn. For i, jE r, i ~j, a measure of the dihedral angle between Hi, Hj in radians is 9 = 7 - (angle between inward normals to Hi, Hj in radians). = z - Cos1( (Gi )T Gj) The polar cone of Pos(D), Pos( (DT)-1 ), is a subset of Pos(D) iff, for every y > 0, (DT)-1y = Dx for some x 2 0, that is, iffD- 1 (DT)- y > 0 for all y > 0. This holds iff D-1 (DT)-1 = P 3T ~ 0, that is, iff all the dihedral angles associated with Pos(D) are non-acute (i.e., obtuse or right). Similarly, it can be verified that the polar cone of Pos(D) is in the interior of Pos(D) iff all the dihedral angles associated with Pos(D) are strictly obtuse, and in this case the circumcenter ray of Pos(D) is in its interior. 3.6 CP-OWNING, OR CP-LACKING SIMPLICIAL CONES Given the square nonsingular matrix D of order n, we will say that the simplicial cone Pos(D) is CP-owning (or a CP-owner) if it has at least one CP-point. It is CP-lacking (or a CP-lacker) otherwise. We have already shown that every two dimensional simplicial cone is a CP-owner. But for n 2 3, simplicial cones may or may not be CP- owners. 11

3.7 CP-POINTS FOR LOWER DIMENSIONAL CONES Let A be an n xr matrix where r < n, whose set of column vectors is linearly independent. Then Pos(A) is an r- dimensional cone in Rn which has empty interior. A CP- point for Pos(A) is defined exactly as before, with the exception that property 1 now requires the point to be in the relative interior of Pos(A). 3.8 SUMMARY OF OUR MAIN RESULTS ON CP-POINTS Let D be a square nonsingular matrix of order n. Let K = Pos(D); and K* = Pos((D.'))-', its polar. Let C, C* denote the sets of CP-points of K, K* respectively. As seen in Section 3.2, there are only two possibilities when n=2. They are i) K* c K, C = C* = interior of K*. ii) K c K*, C = C* = interior of K. Of course, there are many more possibilities when n 2 3. However, our main results on CPpoints in the following sections fall into two main streams corresponding to these two possibilities (i) and (ii). One stream is concerned with the case where the angles between every pair of generator rays of K (i.e., the generator angles of K) are non-acute, that is, when M = DTD is a Z-matrix. In this case K* c K, and C = C* = K*. In this case the dihedral angles associated with every face of Pos (D) are all non-acute. The second stream is concerned with the case where all the dihedral angles associated with K are non-obtuse. This property is inherited by all the faces of K. In this case M-1 = (DTD)-l is a Z-matrix, and all the generator angles in K are non-obtuse. Here K C K* and C = C* = interior of K. 4. APPLICATION TO LCP Let M = (m ) be a given real square matrix of order n and q = (qj ) a given column vector in R". The LCP with data q, M, denoted by (q, M), is the problem of finding vectors 12

w = (w ), z = (z;) E Rn, satisfying w-Mz=q (5) w, z >0, wTz = The LCP is a fundamental problem in mathematical programming, it has been the focus of extensive research over the last 25 years. CP-points came up in a study dealing with the construction of efficient pivotal algorithms for solving certain classes of LCPs. In this section we review this application of CP-points in LCP. In (5), the pair of variables (wj, zj ) is known as the jth complementary pair of variables, for j =1,..., n. In (5), the column vector associated with wj is Ilj, and the column vector associated with zj is -Mj. The pair { Ij, -Mj } is the jth complementary pair of column vectors in (5). A complementary vector of variables in (5) is a vector y = (y..., y)T where yj E {w, zj ) for each j = 1,..., n. If Aj is the column in (5) associated with yj, the matrix A = (A.1... A n) is known as the complementary matrix associated with y. The complementary vector y is said to be a complementary basic vector in (5) 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 (5) corresponding to y is given by all variables in (5) not in y are = 0 (6) y= A'1 q. Clearly, the solution in (6) satisfies the complementarity condition wTz = 0, because y is a complemlnty vector. If A-lq > 0, the solution in (6) is a solution of the LCP (q, M) (it satisfies all te conditions in (5)). It is then said to be a complementary basic feasible solution, and y is said to be a complementary feasible basic vector for (5). The complementary basic feasible solution in (6), and complementary feasible basic vector y are nondegenerate if A-q > 0. When M E Pn, it is well know that the LCP (q, M) has a unique solution for all q E Rn. Hence for M E P, if y is a complementary feasible basic vector for the LCP (q, M), which is nondegenerate, it is the unique complementary feasible basic vector for this LCP. 13

For any J c r the LCP of order I J I, WJ - MJ Zj =qj (7) Wj,ZjO, (wJ)T zj = 0 which is the LCP (qj, MJ), is known as the principle subproblem of (5) corresponding to the subset J. One method for solving the LCP (q, M) when M is a P-matrix is the following. Select a column vector p > 0 in Rn. Consider the following parametric LCP, where a is a nonnegative parameter w z I I -M q+a p (8) W, Z > 0, WTz = O When a > 0 is sufficiently large, w is a complementary feasible basic vector for (8), and the method is inititated with this. The method moves through complementary basic vectors for (8), exchanging one basic variable by its complement in each pivot step, in an effort to find a complementary feasible basic vector for (8) for smaller and smaller values of a until it reaches the value 0. In some general stage, let (w j, zJ ) be the complementary basic vector for (4) at this stage, for some J c r, J = r \J. The corresponding basic solution for (8) is (wj,Zj )=0 { \ z qJ + ap (9) h\ wj;+apj where ( qJj) = - (MJJ)-1 (qj, P ) (qj, Pj) =(q, pj)+Mijj(q pj) 14

The smallest value of a for which the right hand side of (9) remains 2 0 is e given by Maximum {-qj / p: j such that pj > 0O 0= -oo,if p <0 (10) If 0 < 0, (w j, zJ ) is a complementary feasible basic vector for (8) for a = 0, that is, a complementary feasible basic vector for (5), terminate. Otherwise, let r be the maximizing index in (10) (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 [9]. Even though this method is finite, in the worst case, it may take up to 2" pivot steps before termination [10, 12]. However, in [15] J. S. Pang and R. Chandrasekaran observed that if the column vector p is selected so that it satisfies the following property 3, then the method will terminate after at most n pivot steps, for any qE Rn. 3. (Mjj )-pJ > 0, for all nonempty JcF. Since M = (mij) is a P-matrix, mij > 0 for all i = 1 to n. Taking J = {i) in Property 3 implies that p > 0, hence any vector p satisfying property3 is automatically > 0. If the column vector p satisfies property 3, in the above method, when (wj, Zj) is the complementary basic vector, in the basic solution (9), Pi< 0 for all jEJ; and the maximizing index r giving the value of E in (10) 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. 15

PC-VECTORS FOR A P-MATRIX Given a P-matrix M of order n, the column vector pE Rn is said to be a PC-vector for M if it satisfies property 3 given above. Such a column vector was first defined in the Pang and Chandrasekaran paper [15], and hence the name "PC-vector". The following Lemmas 2, 3, and Theorem 1 relating PC-vectors to CP-points follow from the results established in K. G. Murty [11]. LEMMA 2: Let MEPn, pERn. The column vector p is a PC-vector for M iff the vector composed of the z-variables only, is a nondegenerate complementary feasible basic vector in every principal subproblem of the LCP (11). w - Mz =-p w, z 0, wT = 0 (11) PROOF: Follows by direct verification. I We will now show that for the class of PD symmetric matrices M, PC-vectors correspond to CPpoints of a related simplicial cone. Let M be a PD symmetric matrix of order n. Let D denote a real nonsingular square matrix of order n satisfying DTD = M, (for example, the Cholesky factor of M is a candidate for D). Let pERn, p > 0, and b = (DT)-lp (12) LEMMA 3: For Jcr, Pos(Dj) is a projection face of Pos(D) relative to b iff (MJJ)-1 PJ > 0, or equivalently, iff z is the nondegenerate complementary feasible basic vector for the principal subproblem of (11) corresponding to J. 16

PROOF: If J = 0, the result holds by convention. So, assume J ~ 0 and let I J I = s. The orthogonal projection of b in LH(DJ ) is Dj \J, where IJ is the optimum solution of the problem minimize (b - D.j\j )T (b - D J \j ) over AJ ( RS which is =(MJJ)1 (D )T b (13) So, the orthogonal projection of b in LH(D ), is in the relative interior of the face Pos (Dj ), if Aj given by (13) is > 0, that is, iff (MJJ)- 1 (DJ )T b = (Mjj)-1 pj > 0, or equivalently, iff Zj is the nondegenerate complementary feasible basic vector for the principal subproblem of (11) corresponding to J. I1 THEOREM 1: Let D be a real nonsingular square matrix of order n and pERn. Let M = DTD, b = (DT)-lp. The vector p is a PC-vector for M iff b is a CP- point for Pos(D). PROOF: Follows directly from Lemmas 2, 3. U COROLLARY 1: Let D be a real nonsingular square matrix of order n. Every CP-point for Pos(D) must be an interior point of the polar cone of Pos(D),Pos( (DT)-1 ). PROOF: Let b be a CP-point for Pos(D). Then by Theorem 1, p = DT b is a PC-vector for M = DTD, and hence p = DT b > 0. Since b = (DT)-l p, this implies that b is an interior point of Pos( (DT)-'). Corollary 1 can also be proved very directly. If b is a CP-point for Pos(D), each of the generator rays Pos(D ), j = 1 to n, must be a projection face relative to b, by definition. This implies that (Dj)T b > 0 for all j =1 to n, that is, DT b > 0, or b must be in the interior of the polar cone of Pos(D), Pos( (DT)1 ). 17

Geometrically, Corollary 1 says that every CP-ray for Pos(D) must make a strict acute angle with each of the generator rays of Pos(D). COLLARY 2: Let D be a real nonsingular square matrix of order n. The set of CP-points for Pos(D) is a subset of the intersection of the interiors of Pos(D) and Pos( (DT)1). PROOF: Follows from the definition and Corollary 1. [ Let D be a square nonsingular matrix of order n. When n = 2, in Section 3 we have seen that the set of CP-points of Pos(D) is always (interior of Pos(D)) n (interior of Pos( (DT)-1) ). In Sections 7, 8 we establish that this result also holds for some special classes of matrices D when n > 2. Also, when n = 2, the set of CP-points of Pos(D) is either the interior of Pos(D) (when Pos (D) is an acute or right angle), or the interior of Pos( (DT-1) (when Pos(D) is an obtuse angle). In Sections 7, 8 we derive some necessary and sufficient conditions on D, for these properties to hold, when n > 2. THEOREM 2: Let M be a PD symmetric matrix of order n, and let D be a square matrix satisfying DTD = M. There exists a PC-vector for M iff Pos(D) is a CP-owner. PROOF: Follows directly from Theorem 1. " THEOREM 3: Let M be a P-matrix of order n. The set of all PC-vectors for M is either 0 or is an open polyhedral cone. PROOF: A vector pf Rn is a PC-vector for M iff it is a feasible solution of the system (MlJJ)'pj >0, for all 0 Jcr (14) (14) is a finite system of strict linear inequalities, and its set of feasible solutions is the set of PCvectors for M. Hence, if this set is nonempty, it is an open polyhedral cone. E 18

THEOREM 4: Let D be a square nonsingular matrix of order n. The set of CP-points for Pos(D) is either empty, or is an open polyhedral cone. PROOF: Let M = DTD, and let A be the set of PC-vectors for M. By Theorem 1, the set of all CP-points for Pos(D) is {x: x = (DT)-1 p, pEA} and this is an open polyhedral cone when it is nonempty, since the same property holds for A. [ 5. PC-VECTORS FOR P-MATRICES OF ORDER 2. Suppose M = (Mij) is a P-matrix of order 2. Then from the definitions, p = (PI, p2)T is a PC-vector for M iff it is feasible to (15). m22 P-m12 P2 -m21Pl+mll P2 P1 >0 >0 (15) >0 >0 P2 Using Gordan's theorem of the alternatives [8, 12], and the Gale-Nikaido theorem [4], it can be verified that (15) is always feasible. Hence, every P-matrix M of order 2 has a PC-vector p, which can be found by solving (15). 6. THE HEREDITARY FEATURE OF THESE PROPERTIES. Let D be a square nonsingular matrix of order n. THEOREM 5: If Pos(D) is a CP-owner, so is every face of Pos(D). PROOF: Consider the facet Pos(D.2,, D.n ) = K1 of Pos(D) and the facetal hyperplane H1 containing it. Suppose b is a CP-point for Pos(D). Let bl be the orthogonal projection of 19

b in H1. Since b is a CP-point for Pos(D), bl is in the relative interior of K1. By Pythagoras theorem, I x - b 112 = I x - bl 112 + II b - bl 112 for all xH1. So, if F is any face of K1, the orthogonal projections of b, bl in the linear hull of F, are the same. So, by the hypothesis, b1 is a CP-point for K1. A similar proof holds for all facets of Pos (D), so all facets of Pos (D) are CP- owners if Pos (D) is a CP-owner. Repeating this argument, we conclude that all faces of Pos (D) are CP-owners if Pos (D) is. L1 THEOREM 6: If every interior point of Pos (D) is a CP-point for it, then for every face of Pos (D), every relative interior point is a CP-point. PROOF: Consider the facet K1 = Pos (D2,, D.n) of Pos (D). Let bl be any point in the relative interior of K1. Erect the inward normal at b1 to the facetal hyperplane containing K1 and let b be a point on this normal in the interior of Pos (D). By the hypothesis of the theorem, b is a CP-point for Pos (D), so by the arguments in the proof of Theorem 5, bl is a CP-point for K1. So, every point in the relative interior of K1 is a CP-point for K1. A Similar proof holds for all'facets of Pos (D); so, every facet inherits the property that all points in its relative interior are its CP-points. Repeating this argument, we conclude that every relative interior point of any face of Pos (D) is a CP-point of that face, if every interior point of Pos (D) is its CP-point. D THEOREM 7: Let M be a P-matrix of order n. If M has a PC-vector, so does every principal submatrix of M. PROOF: Let p be a PC-vector for M. Then, for every Jcr, it follows directly from the definition; that pJ is a PC- vector for the principal submatrix MJJ of M corresponding to the subset J. E 20

7. CP-POINTS FOR POS(D) WHEN EVERY PAIR OF GENERATORS MAKE A NONACUTE ANGLE. THEOREM 8: Let D be a square nonsingular matrix of order n. If every pair of generators of Pos(D) make a non- acute (i.e., either obtuse or right) angle, then Pos(D) is a CP- owner, and the set of CP-points of Pos(D) is the interior of the polar cone of Pos(D), Pos( (DT)-1). PROOF: Suppose every pair of generators of Pos(D) make a non- acute angle. So (D.i)T Dj < 0 for all i j. Therefore, M = DTD is a P-matrix which is also a Z-matrix, and hence an M- matrix. By the results in [3] this implies that M'1 2 0, and by the same argument (Mjj)-1 2 0 for all 0 * JcF. Let pERn, p > 0. Let M-1 p = y = (i ). Since M-1 is also a P-matrix, each of its diagonal elements is > 0. Sincce M-1 2 0 and has positive diagonal elements and p > 0, we have y = M-l p > 0. A similar argument shows that (MJJ)1PlJ > 0 for all 0 ~JcF, p > 0. Hence every pE R", p > 0, is a PC-vector for M = DTD. Consequently by Theorem 1, all b in the interior of Pos( (DT)l ) are CP-points for Pos(D). By Corollary 1, this implies that the set of all CP-points for Pos(D) in this case is the interior of Pos( (DT)-1 ). [1 The converse of Theorem 8, namely that if D is square and nonsingular, and every interior point of the polar cone Pos( (DT)-l ) is a CP-point of Pos(D), then every pair of generators of Pos(D) make a non-acute angle, is also true. This is proved along with several other equivalent statements, under Theorem 18 in Section 9. 8. CP-POINTS FOR POS(D) WHEN EVERY PAIR OF GENERATORS MAKE A NONOBTUSE ANGLE. In this section, D is a square nonsingular matrix of order n. In Section 3, we have seen that if n = 2, and Pos(D) is an acute or right angle (i.e., (D 1)T D 20), every interior point of Pos(D) is a CP-point for it. An intuitive generalization of this result to higher dimensions states that if the rays of Di1 and D j make an acute or right angle (i.e., (D i ) Dj.> 0) for all i j, then Pos(D) is a CP-owner. This result is true for n = 2, and established for n = 3, but may be false for n 2 4. Consider matrix D, given below. 21

-1 1 20 0 0 3 1 0 (16) D= 0 0 1 0 \5 5 5 5 Even though (D.i)T Dj > 0 for all i ~j, in this matrix D, Pos(D) is a CP-lacker. This can be seen from the following argument. Let M = DTD. For a vector pER4 to be a PC-vector for M, it must satisfy: -48p2 +35p3 >0 250p1 +25P2 -275p4 >0 87275p1 -1450p2 +4425p3 -90250p4 >0 90250p +1475P2 -4575p3 +93359P4 >0 The first and the second of these inequalities come from the requirement that (MJJ)-1 PJ > 0 for J = {2,3), {1,2,4) respectively, while the last two are from the same requirement but correspond to J = (1,2,3,4). Muliplying the inequalities in this system by 13275, 37923, 19720, 19175 in that order and summing leads to the inconsistent inequality 0 > 0. Thus no PC-vector exists for M, and so by Theorem 1 there is no CP-ray for Pos(D). In order to guarantee that Pos(D) is a CP-owner in this case, we need to impose more conditions on the matrix D. Our work on this class of matrices D was motivated by the following conjecture made by Soo Y. Chang. CONJECTURE (proved below): Let Kj = Pos(D 1,', Dj 1' D,, D n) and Hj the facetal hyperplane. of Pos(D) containing K.. If for each j = 1 to n, the orthogonal projection of the generator Pos(Dj) in H1 lies in the relative interior of K, then Pos(D) is a CP-owner. 22

While it may not be immediately apparent, we will show that the hypothesis in this conjecture implies that every pair of generators of D make an acute angle, so this conjecture legitimately belongs in this section. We will provide a proof of a stronger form of this conjecture and derive several related results. For ease of reading, we will summarize the notation for this section. Kj and Hj are as stated in the above conjecture. = (Pij) = D1. Then, Hj= {x: x=0 (17) Pos(D) = { x: Pj x > 0, j = 1 to n (18) Kj={x: i. x > 0, i = 1 ton, i jj; and x = 0 (19) Gj = ( Pj. )T / I I P. I1 2, a nonzero point on the inward normal to Hj (20) Consider the hyperplane { x: a1 x+ * * + axn = a x = d } and let xERn. The orthogonal projection of x in this hyperplane is x +aT (d - a x )/llall2. We will now investigate the simplicial cones Pos(D) satisfying one of these properties. 4. For each j = 1 to n, the orthogonal projection of the ray Pos(Dj ) in H. is in the relative interior of K. 5. For each j = 1 to n, the orthogonal projection of the ray Pos(Dj ) in H1 is in Kj. 6. Al the dihedral angles associated with Pos(D) are acute. 7. All the dihedral angles associated with Pos(D) are non- obtuse (acute or right). 8. Every interior point of Pos(D) is a CP-point for it. 9. Every interior point of Pos(D) is a CP-point for the polar cone Pos((DT)1) 23

n v THEOREM 9: If property 4 holds, all the ( 2 ) dihedral angles associated with Pos(D) are acute, and conversely. PROOF: The orthogonal projection of D 1 on H1 is D 1 - (P 1 )T (3 13 D 1 )/11 1 112, = D - G 1 (since f3. D. = 1, as 3 = D-1). Under property 4 the orthogonal projection of D.1 on H1 is in the relative interior of K1, and hence from (19), Pi. (D.1 - G.1) > 0 for all i * 1. But i. D.l = 0for all i l 1, since = D-1. So 3i. G.1 < 0 for all i 1, that is, ( Gi)T G< O, for all i ~ 1. In the same way, under property 4, we have ( G )T G1 < 0 for all ixj, that is, all the dihedral angles associated with Pos(D) are acute. The converse is established by essentially reversing the steps of the proof. n \ THEOREM 10: If property 5 holds, all the 2 ) dihedral angles associated with Pos(D) are non-obtuse (i.e., acute or right), and conversely. PROOF: Similar to the proof of Theorem 9. 0 Thus, properties 4 and 6 are equivalent. Likewise, properties 5 and 7 are equivalent. LEMMA 4: Let x be any interior point of Pos(D). If the orthogonal projection of D 1 in H1 is in the relative interior of K1, the orthogonal projection of x in H1 is also in the relative interior of K1. PROOF: Suppose the orthogonal projection of D1 in H1 is in the relative interior of K1. Then, from the proof of Theorem 9, we have, p3i (31 )T < 0 for all i ~ 1. Now, the orthogonal projection of x in H1 is x = x - ( P ((1. x ) /II 31 II2. We have, for i 1, Pi. X = Pi X +(-3i.(P1 ) (PlX )/11. 112 >0 24

because Pi. x > 0 ( from (18), since x is in the interior of Pos(D) ) for all i, and A (-PL ( P. )T ) > 0 (established above). So, x is in the relative interior of K1, completing the proof of this lemma. - THEOREM 11: If property 5 holds, then every interior point of Pos(D) is a CP-point for it, and conversely. PROOF: The proof is essentially similar to the proof of Lemma 4. Suppose property 5 holds. Let x be an interior point of Pos(D). Let F be a proper face of Pos(D). So, from (18), there must exist a 0~J cF such that F={x: x x=0, Pi x O,iEr\J. (21) Let I J I = r. So PJ. is of order r x n and of full row rank. Hence the matrix A = Pj ([j)T is PD symmetric. By Theorem 10, we have 3Pi (13j )T < 0, for all i ~j. This implies that A is a Zmatrix, and hence an M-matrix. By the results in [3], this implies that A-120. The orthogonal projection of x in the linear hull of F is the optimum solution of the problem minimize (x- x )T(x- x) subject to Pj x = 0. A A which isx = x - (j3j)T A-1 3J.x. Let iEr \J. We have 3i x = Pi. x -i. (j.)T A-1 j. x >0, because P1i > 0 (since x is in the interior of Pos(D)), Pio(Pj. )T < 0 (since Pli.(p3 )T<0 for allj i ), A'1 2 0 (established above), and P. x > 0 (since x is in the interior of Pos(D) ). So, x is in the relative interior of F, that is, F is a projection face relative to x. Since this holds for all faces F of Pos(D), x is a CP-point for Pos(D). Hence every interior point of Pos(D) is a CP-point for Pos(D) in this case. To prove the converse, suppose every interior point of Pos(D) is a CP-point for it. Suppose there is a j such that the orthogonal projection 6f D in H1 is not in K1, say for j = 1. Since orthogonal projection is a continuous operation, we can find an open ball B containing D.1 such that the orthogonal projection of every point inside B in H1 is outside of K1. Since B is an open 25

ball containing D 1, it contains some points from the interior of Pos(D), and the orthogonal projection of these points are outside K1, contradicting the hypothesis. So, if every interior point of Pos(D) is a CP-point, property 5 must hold. D Hence, properties 5 and 8 are equivalent. We can think of each face of Pos(D) as being a full dimensional simplicial cone in its linear hull. If F is an r-dimensional face of Pos(D), we can define the ( 2) dihedral angles of F relative to its linear hull, just as we defined the dihedral angles for Pos(D). We will now show that properties 5 and 7 are facially hereditary, in the sense that if Pos(D) has the property, then every face of Pos(D) also has the corresponding property. THEOREM 12: If the simplicial cone Pos(D) has property 5, then every face of Pos(D) has the corresponding property. PROOF: This follows from Theorems 11 and 6. ] THEOREM 13: If all the dihedral angles defined by pairs of facets of the simplicial cone Pos(D) are non-obtuse, every face of Pos(D) also has the same property. PROOF: Follows directly from Theorems 11, 10 and 12. [ THEOREM 14: For any simplicial cone Pos(D), properties 5, 7 and 8 are equivalent, and these properties are inherited by all faces of Pos(D). PROOF: Follows from Theorems 10, 11, 12 and 13. E THEOREM 15: Property 9 holds iff (DTD)-1 is a Z-matrix PROOF: Let K* = Pos((DT)l) be the polar cone of Pos(D). Define B = (DT)-, M = DTD, N = BTB = (DTD)-l = Ml 26

Suppose N = M-1 is a Z-matrix. Since N is also PD, by the results in [3], (NJJ)'1 > 0 for all nonempty JcF, and since (NJJ)-1 is also PD, each of its diagonal elements is > O0. Hence, in this case (NJJ)-' qj > 0 for all qE Rn, q > 0, and nonempty JcF. Hence, by Theorem 1, (BT)-lq = Dq is a CP-point for K* for all q > 0, that is every interior point of Pos(D) is a CP-point for the polar cone K* in this case. Suppose Dq is a CP-point for K* for all q > 0. Then by Theorem 1 we must have: (NJJ)-1 qj > 0, for all nonempty J c r and all q > 0. (22) In particular N-q > 0 for every q > 0. Let 1 < j < n. Define q(e) = (qt(e): t = 1 to n) where qt (e) = e for t j, and 1 for t=j. Since Nlq(e) > 0 for all e > 0, by making e tend to zero through positive values, we conclude that (N'-).j > 0. Hence N1 > 0. Using the same argument, we conclude that (23) implies that (Njj)-1 2 0 for every nonempty J C r. Now consider J1 = { 1,2). Then denoting the i, j-th element in the matrix N by nij, we have: nll n12 NJI i = n21 n22 Since N = BTB is symmetric, n12 = n21, and denote their common value by y. Also, N is PD, hence, n1l > 0, n22 > 0, and nll n22 - y2 > 0. Using these and (NJ J )1 ~ 0, we conclude that y < 0. By the same argument we can show that all off-diagonal elements of N are < 0, that is N = (DTD)-1 is a Z-matrix, in this case, completing the proof. - COROLLARY 3: Let A be a P-matrix of order n. It is a Z-matrix iff (AJ)-1 > 0 for all nonempty Jcr. PROOF: Follows from the results in [3], and using the argument made in the proof of Theorem 15. 27

We will now explain the relationship of these properties to the condition mentioned in the heading of this section, and the role that Z-matrices play in these properties. From the results in this section, we see that the basic condition for properties 5 or 7 or 8 to hold is that Pi. (j.)T<o for all i j. (23) that is, that pAT is a Z-matrix. Since P is nonsingular, this is equivalent to requiring that ppT be an M-matrix. But 3pT= (D-I) (D-1)T= (DTD)-L.M-l where M=DTD. So, if (23) holds, (DTD)-1 is an M-matrix, and by the results in [3], DTD 2 0, in other words, every pair of generators for Pos(D) makes a non-obtuse angle. Hence all the results in this section relate to a subclass of simplicial cones in which every pair of generators make a non-obtuse angle. One noteworthy feature. Let DTD = M. In Section 7 we dealt with the case where M is a Zmatrix. In this Section 8, we are dealing with the case where M-1 is a Z-matrix. We now provide a theorem which summarizes this section. THEOREM 16: Every interior point of Pos(D) is a CP-point for it, iff (DTD)-1 is a Z-matrix. Also, properties 5, 7, 8 and 9, and the condition that (DTD)-' is a Z-matrix, are all equivalent PROOF: Requiring (DTD)-1 to be a Z-matrix is equivalent to requiring property 7 as explained above. So, these results follow from Theorems 14 and 15. ] GENERALIZATION OF THE CONCEPT OF REGULARITY OF A SIMIPLICIAL CONE. In classical geometry, a simplex is called a regular simplex if all its edges are of equal length, and the simplicial cone Pos(D) is called a regular simplicial cone if the convex hull of {D j / IIDI4: j =1 to n } is a regular simplex. Property 8 of course holds for regular simplicial cones, and thi is of principal interest when referring to regularity in simplicial cones. So, the conditions given in Theorem 16 (namely that (DTD)-l should be a Z- matrix) provide a proper generalization of the traditional concept of regularity in simplicial cones. It identifies the class of simplicial cones satisfying property 8. 28

9. SIMPLICIAL CONES POS(D) WITH ALL DIHEDRAL ANGLES NON-ACUTE. Let D be a square nonsingular matrix of order n. THEOREM 17: If n = 3, and all the dihedral angles associated with Pos(D) are non-acute, then the circumcenter ray of Pos(D) is a CP- ray for it. PROOF: From the definition of the dihedral angles associated with Pos(D) (Section 3), we know that they are all non-acute iff (DTD)-l > 0 (24) Let T = (T1,, Tn)T where T = 11 D.j II,j = 1 to n, and b=(DT)-1 T (25) The ray of b is the circumcenter ray for Pos(D). Since D-1 b = (DTD)-lT>O (because r > 0. (24), and since (DTD)-l is a PD symmetric matrix, its main diagonal is >0), b is in the interior of Pos(D). Let M = (mij) = DTD. We will now show that (Mjj)-1 Tr > 0forall J { 1,2,3 }. (26) Since M-l T = D-1 b > 0, we know that (26) holds for J ={1, 2, 3). When J =(1, 2), it can be verified that (Mjj)-1 TJ = (T2, T1)T / (T 1 2 + (D 1)TD2) > 0 because T and T2 are >O and rT T2 + (D.1)TD.2 >0 by Cauchy-Schwartz inequality, so (26) holds. By symmetry, (25) holds whenever IJI = 2. When J = j), (Mjj)-'1T = (1/Tj) >, for allj =1, 2. 3. so (26) holds. Hence r is a PC-vector for M, and by Theorem 1, b = (DT)1lT is a CP-point for Pos(D). So, the circumcenter ray is a CP-ray for Pos(D) in this case. a For any n, if all the dihedral angles associated with Pos(D) are non-obtuse, (24) holds. Under (24), the circumcenter ray for Pos(D) is an interior ray for Pos(D). Unfortunately, under these conditions, the circumcenter ray is not guaranteed to be a CP-ray if n 2 4. Consider the following matrix D of order 4 29

-1 1 20 -20 0 3 1 -4 D= 0 0 1 -1 0 0 0 1/3 It can be verified that this matrix satisfies (24), so all the dihedral angles associated with its pos cone are non-acute. Yet, this cone Pos(D), has no CP-point. This follows from Theorem 5 since its face Pos(D 1, D2, D 3) has no CP-point (in its linear hull this face Pos(D 1, D.2, D3) is A A the same as the cone Pos(D) where D is the matrix given in (2), and it was shown in Section 3.3 A that Pos(D) is a CP-lacker). Thus, when n 2 4, to guarantee that CP-point exists for a simplicial cone Pos (D), condition (24) is not adequate by itself, we need to impose more conditions. This leads us to the next theorem, which includes the converse of Theorem 8 in Section 7, and provides several other equivalent results. THEOREM 18: Let D be a real square nonsingular matrix of order n. The following statements are equivalent i) Every pair of generators of Pos(D) make a non-acute angle, or equivalently M = DTD is a Z-matrix. ii) Every point in the interior of the polar cone, Pos((DT)l) is a CP-point for Pos(D). iii) Every pE R, p > 0, is a PC-vector for M = DTD. iv) Every face of Pos(D) satisfies the property that all the dihedral angles associated with it are non-acute. v) Every interior point of the polar cone Pos((DT)'1) is a CP-point for it. PROOF: (ii) and (iii) are equivalent by Theorem 1. By Theorem 8, (i) implies (ii). 30

We will now prove that (iii) implies (i). Assume that (iii) holds. By the definition of a PCvector, we have (Mjj)-1 PJ > 0 for every p > 0 and every nonempty J c F. Using the argument made in the proof of Theorem 15, this implies that M is a Z-matrix, which is equivalent to the statement that every pair of generators of Pos(D) make a non-acute angle. Hence (iii) implies (i). If (iv) holds, (MJJ)- 1 2 0 for all J c r, and hence (iii) holds. If (iii) holds, for every J C rF, we have, (MJJ)-1 PJ > O for all pJ > 0, this implies that (MJJ)-1 ~ 0 by the argument given above, which in turn implies that the dihedral angles associated with the face of Pos(D) corresponding to J are all non-acute. Hence (iv) holds if (iii) does. Thus, (iii) and (iv) are equivalent. Assume that (i) holds. Then DTD is a Z-matrix. Let B = (DT)-1. Therefore DTD = (BTB)-1, hence (BTB)-1 is a Z-matrix. This implies that all the dihedral angles associated with Pos (B) = polar cone of Pos(D), are non-obtuse, and hence by the results in Section 8 every interior point of the polar cone is a CP-point for it, thus (v) holds. Now, if (v) holds, by applying Theorem 16 to the polar cone we conclude that ((DT)-1)T ((DT)-l)-1 = DTD must be a Z-matrix, so (i) holds. Thus (i) and (v) are equivalent. Hence conditions (i) to (v) are all mutually equivalent. [ As stated in the summary in Section 3.8, the results in Section 7 and this section correspond to the case where the Polar cone Pos((DT)-l) C Pos(D), and the sets of CP-points of Pos(D) and Pos((DT)1) are both the same as the interior of the Polar cone. The results in Section 8 correspond to the case where Pos(D) is a subset of the polar cone, and the sets of CP-points of Pos(D) and its polar cone are both the same as the interior of Pos(D). 10. OPEN QUESTIONS Given a rational square nonsingular matrix D of order n and a rational point b in the interior of Pos(D), b has to satisfy Property 2 of Section 3 to be a CP-point for Pos(D). Property 2 consists of 2n-2 sets of conditions. It is not known whether there is a polynomially bounded algorithm for checking property 2. 31

J. S. Pang posed the following question: What is the class of real square nonsingular matrices D of order n, for which the set of CP-points of K = Pos(D) is the innterior of KfK*, where K* is the polar cone of K? A mathematical characterization for this class is easy to provide using Theorem 1. Denoting DTD by M, this is exactly the class of all matrices D for which pERn, p > 0 and M-1 p > 0 implies (Mjj)-1 PJ > 0 for all nonempty JcF From the results of Sections 7, 8, 9, we know that this class contains the matrices all of whose generator angles are non-acute, and the matrices all of whose dihedral angles are non-obtuse. It is not known whether this class contains any matrices other than these two streams. Another interesting problem is the following: if a simplicial cone is a CP-owner, is its polar cone also a CP-owner? A further intriguing question is whether the sets of CP-points for a simplicial cone and its polar are the same. The answers to these questions are not known yet. Let D be a real square nonsingular matrix of order n, and let C be the set of CP-points of Pos (D). We have shown that if C ~ 0, it is an open polyhedral cone defined by a system consisting of a large number of constraints (2n sets of constraints). In the earlier version of this paper, we conjectured that whenever C ~ 0, it is a simplicial cone This conjecture has been settled in the affirmative by J. Lawrence and W. D. Morris, Jr. in their recent paper [7]. 11. A GENERALIZATION In this section, we will discuss a generalization of the properties of being a CP-point or a PC-vector. Here, R"m denotes real square matrices of order n, which may or may not be nonsingular. We now state two properties 10, and 11. 10. The pair (D,q), where DER"x and qER", is said to have this property if for each nonempty J cr the orthogonal projection of q onto the subspace LH(DJ) lies in the relative interior of the cone Pos(DJ). 32

11. The pair (M, q), where M E Rnxn and qE Rn, is said to have this property if for each nonempty J cF, the linear complementarity problem (-q, Mjj) has a solution (wJ, z ) with zj > 0. Note that the definition of property 10 is minimal in the sense the at 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 D= 2 SO 2 4 3 4 0 1 10 q= 10 -1 J= {1,2,3} 0 D= 1 1 D=1 O 1 4 5 4 0 1 -1 -10 1 10 0 1 13 q= 18 3 q —'-0 J= (1,2) J=(1) Notice that in Property 10, D is not required to be nonsingular. Likewise in Property 11, M may not be nonsingular. We define P 1On=(DER"n": there exists at least one qERn such that (D, q) satisfies property 10). P 1 1t=(MER1": there exists at least one qERn such that (M, q) satisfies property 11). By our earlier results, ifDE Rn" is nonsingular, (D, q ) has property 10 iff (DTD, DTq) has property 11. 33

CONVEXITY RESULTS PROPOSITION 1: For DERnx the set of qERn such that (D, q ) has property 10 is convex and open. PROOF: Let (D, q ) have property 10 and 0 ~ U c r. Let J c U be a maximal subset such that DJ has independent columns. Then LH(D U) = LH(D ) and the projection of q onto LH(D. ) is DJ aJ where, oc = DtJ q, where Dt = (( DJ)TDJ)' (DJ)T is the pseudoinverse of DJ. The projection DJ aJ is in the relative interior of Pos (DJ) iff ac > 0. For i E U \ J, there exist constantsfij such that D.i + fijD.= 0, jEJ from the definition of J. Choose i > 0, i E U \J, such that aj + S eifij>0, iEU for all jEJ which is possible since aJ > 0. Let aU be a vector with components Ei for if U\J, and cj + Z i efij iU 1 for jEJ Then aU> 0 and D J aJ = D u aU. Therefore the projection of q onto LH(D.U) is given by D.U aU1, aU >. By continuity, there is a neighborhood BU of q such that aJ = D.Jt q > 0 and ca constructed as above satsifies D.jaJ = D.U U and U > 0for all q BU. Then for any pE nu BU, the projection of p onto LH(D.U) is.given by D.ucU for cU > 0, for each nonempty U c r. Therefore the set of q such that (D, q) has property 10 is open. 34

If (D, ql) and (D, q2) have property 10, then for fixed UcF, U~0, the projections of ql and q2 onto LH(D.U), are given by D.ua1, al > 0 and D.aC2, a2 > 0 respectively. Since projection is a linear operation, the projection of (1 - A) q1 +Aq2 onto LH(D.U) is (1 - A) D.ual1+A\D. 2 = D.U ( (1 - A)a1+Aa2), where (1 - A)a1 + Aa2 > 0 for 0 < \ 1. Since U was arbitrary, (D, (1 - \)ql+Aq2) has property 10 for 0 < A < 1, which proves the convexity. ] Observe that for n > 2, the set Pn is not convex. Let: 1 -15) M 1 1 2 -15 2 M1 and M2 are P-matrices, but (1/2) (M1 + M2) is not. Since Pn is not convex, it turns out that for n 2 2 and fixed qERn, the set of matrices M Pnn P n such that (M, q) has property 11 is not necessarily convex. CONJECTURE: For fixed qE~Rn, the set of PD symmetric MER"nn such that (M, q) has property 11 is convex. DEFINITION: A set A c Rn is starlike if there exists a point c A such that for any point pf A the line segment cp also lies in A. The set of points c A with this property is called the kernel of A. PROPOSITION 3: The set Pn is starlike with the identity matrix I in its kernel. PROOF: Let MEPn and 0 a < 1. A characterization of Pn is that MEPn if and only if the real eigenvalues of every principal submatrix of M are positive [3, 16]. If A> 0 is an eigenvalue of a principal submatrix MJJ, then (1 - a) + a\ > 0 is an eigenvalue of [ (1 - a)I + a M ]JJ. Therefore the real eigenvalues of every principal submatrix of (1 - a) I + a M, for 0 < a 1, are positive, and (1- a)I +aMEPn for 0 < 1. - 35

PROPOSITON 4: For fixed qE R, q > 0, the set of matrices ME Pn such that (M, q) has property 11 is starlike with I in its kernel. PROOF: Let (M, q) have property 11, where MEPn, qER", q > O0. It suffices to prove that ( (1 - A) M + A I, q) also has property 11, for 0 ~ A < 1. The proof of this is by induction on n. Since (M, q) and (I, q) have property 11, consider only 0 < A < 1. The result is trivial for n = 1. Assume it holds for P-matrices of order < n. Property 11 for (M, q) means that MjJ-1 qj > 0 for every subset J, 0 ~ J c r. Since property 11 is hereditary with respect to principal submatrices, the induction hypothesis yields that [ (1 - A) Mjj + AIJJ]-I qj > 0 for every subset J, 0 o J c r, of cardinality IJI < n. Thus all that remains is to prove [(1 - A) M + A/]-1 q > 0. The kth component of z = [ (1 - A) M +Ai ]-1 q is, by Cramer's rule, det([(l-A)M+AI].{l,...,k } q:q:[(1 -A)M+A ].k+l,...., n)) Zk = det[( 1 - A) M + A] (27) 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 Aji = (1 - A) M.i or A.i = Ali for i, k, and Ak = q. Let J={,..., k,..., jr be the indices such that A i = Ai for i 0 J. Then det A = An - UI (1 - A)U -1 (MJJ-lqJ)k det MJJ > 0 since 0 < A ~ 1, (M, q) has property 11, and M is a P-matrix. (The subscript k here refers to the element k in the index set J = ( j,..., k,..., j }.) Therefore the numerator in (27) is positive, and so [ (1 - A) M+Al]'1 q > 0, which completes the induction step. D 36

Note that Zn is convex but Mn is not. Let: -16\ M 3 -2 M3 = M4 = -2 11/ 1 -16 11 M3 and M4 are M-matrices, but (1/2) (M3 + M4) is not. The following theorem from M. Fiedler and V. Ptak [3] will be useful. THEOREM 19: Let A, B E Zn, all the real eigenvalues of A be positive, and A < B. Then 1) A-12B-'1 0; 2) all the real eigenvalues of B are positive; 3) det B det A > 0. PROPOSITION 5: The set Mn is starlike with the identity matrix I in its kernel. PROOF: Let ME Mn = Zn n Pn It is straightforward to verify that (1 - A)I + \M for 0 < A < 1 is in both Zn and Pn. PROPOSITION 6: For any MEMn and qER", q > 0, the pair (M, q) has property 11. PROOF: Lce MEM, qERR q > 0, and 0~ J c r. Then Mjj is also an M-matrix, hence a Z-matrix with positive real eigenvalues. By Theorem 19 above, Mjj-1 > (diag (Mjj) )-1 > 0 is nonnegative with positive diagonal elements, and therefore Mjj-1 qj > 0. This proves property 11 for the pair (M, q). El 37

Generalization of the class Mn M-matrices 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 P1 1i n P, is the natural generalization of Mn, and that P 1 n Pn contains the essence of the class Mn as far as linear complementarity is concerned. Both Mn and P11n n Pn are nonconvex, both are starlike fromI. When MEMn, for every q > O, (M, q) has property 11; whereas for MEP1,1 n Pn, there exists a qERn, q > O, such that (M, q) has property 11. When MEMn, for all 0 ~ J c r and every qERn, q > 0, (MJJ)Y1 qj > 0; whereas, for MEP 1n n Pn, there exists a qERn, q >0 such that for all 0 ~ J c r, (Mjj)'1 q > O0. Similarly, when MEMn, the statement "for any qERn, the LCP (q, M) can be solved with at most n complementary pivot steps via the parametric LCP (q+ ap, M), is true for every p > 0" whereas, for ME P11 n Pn, there exists ap > 0 such that the above statement within quotes is true. Acknowledgement We thank the referees for their thorough reports. 38

REFERENCS [1] S. Y. Chang and K. G. Murty, "The Steepest descent gravitational method for linear programming," Discrete Applied Mathematics, to appear. [2] B. C. Eaves, F. J. Gould, H. O. Peitgen and, M. J. Todd (Eds.), Homotopy methods and global convergence (Plenum, New York, 1983). [3] M. Fiedler and V. Ptak, "On matrices with non-positive off- diagonal elements and positive principal minors," Czech. Math. J. 12 (1962) 382-400. [4] D. Gale and H. Nikaido, "The Jacobian matrix and global univalence of mappings," Mathematische Annalen, 159 (1965) 81- 93. [5] L. M. Kelly and L. T. Watson, "Q-matrices and spherical geometry," Linear Algebra and its Appl. 25 (1979) 175-190. [6] L. M. Kelly and L. T. Watson, "Erratum: Some perturbation theorems for Q-matrices," SIAM J. Appl. Math. 34 (1978) 320-321. [7] J. Lawrence and W. D. Morris, Jr., " Geometric Properties of Hidden Minkowski matrices," Dept. of Math Sciences, George Mason University, Fairfax, VA-22030, May 1988. [8] 0. L. Mangasarian, Nonlinear Programming, McGraw-Hill, New York, 1969. [9] K. G. Murty, "On the parametric complementarity problem," Engineering Summer Conference notes, University of Michigan, Ann Arbor, 1971. [10] K. G. Murty, "Computational complexity of complementary pivot methods," Mathematical Programming Study 7 (1978) 61-73. [11] K. G. Murty, "On the linear complementarity problem," Methods of Operations Research 31 (1978) 425-439. [12] K. G. Murty, Linear Complementarity, Linear and Nonlinear Programming, (Heldermann Verlag, West Berlin, 1988) [13] K. G. Murty, Linear Programming (Wiley, New York, 1983). [141 K G. Murty and Y. Fathi, "A critical index algorithm for nearest point problems in simplicial cones," Mathematical Programming, 23 (1982) 206-215. [15] J. S. Pang and R. Chandrasekaran, "Linear complementarity problems solvable by a polynomially bounded pivoting algorithm," Mathematical Programming Study 25 (1985) 13-27. [16] L. T. Watson, "A variational approach to the linear complementarity problem," Doctoral dissertation, Department of Mathematics, University of Michigan, Ann Arbor, Michigan, 1974. [17] L. T. Watson, "Some perturbation theorems for Q-matrices," SIAMJ. Appl. Math. 31 (1976) 379-384. 39

UNIVERSITY OF MICHIGAN 3 9015 04732 7583 [18] L. T. Watson, "An algorithm for the linear complementarity problem," International J. Computer Math. 6 (1978) 319-325. [19] P. Wolfe, "Finding the nearest point in a polytope," Mathematical Programming 11 (1976) 128-149 40