On the Dimension of K Katta G. Murty * Department of Industrial and Operations Engineering 1205 Beal Avenue The University of Michigan Ann Arbor, MI 48109-2117, USA Technical Report 85-5 February 1985 *Research Partially Supported by NSF Grant No. ECS-8401081

On the Dimension of K Katta G. Murty* Technical Report 85-5 February 1985 ABSTRACT Let K be a convex polyhedron specified by a system of linear constraints. Let K be the convex hull of its extreme points. We derive a formula for the dimension of K, but show that computing it may be a hard problem. KEY WORDS: convex polyhedron, its dimension, convex hull of its extreme points, NP-complete problem. Research Partially Supported by NSF Grant No. ECS-8401081. Research Partially Supported by NSF Grant No. ECS-8401081.

INTRODUCTION Let K denote a convex polyhedron specified by a system of linear A constraints, and let K denote the set of its extreme points. Here we study A the problem of determining the dimension of K, using the data specifying K. If the constraint system specifying K consists of equality constraints only, K is an affine space and has no extreme points, in this case K = 0, and the problem is trivial. So we assume that the constraint system specifying K consists of at least one inequality constraint. If there are any equality constraints in the system, using them some variables can be eliminated, thus reducing the system. So, for the sake of this study, we can, without any loss of generality, assume that the system specifying K consists of inequality constraints only. Suppose that K is the set of feasible solutions of Dx _ d (1) where D, d are given integer matrices of orders mxn and mxl respectively. We assume that K + 0. We use the symbols D., D j, to denote the ith row vector, the j column vector of the matrix D respectively. It is well known that the dimension of K is < n iff there exists at least one constraint in (1) which holds as a strict equality constraint at all points in K, that is, there exists an i such that D. x = d. for all x e K. In that case, that constraint can be treated as an equality constraint, and a variable eliminated using it, and the process can be repeated. We assume that such reduction steps have been carried out as far as possible. 1

i So, we assume that for each i = 1 to m, there exists an x E K satisfying D. x > d.. Hence, the dimension of K is n. 1. 1 It is well known (see, for example, [3]) that K has an extreme point iff the set of column vectors of D is linearly independent. If K has no A extreme points, K = 0, and our problem becomes trivial. So, we assume that this condition holds, that is that K has at least one extreme point. Also, it is well known that K is bounded iff the system DE > 0 (2) A has i = 0 as its unique solution. See [3]. If K is bounded, K = K, in this case the dimension of K = dimension of K. Our problem becomes interesting if K is unbounded, that is, when (2) has at least one nonzero solution. In this case K is a proper subset of K, it is the set of feasible solutions of a system of constraints consisting of (1) and some additional constraints. The number of these additional constraints needed to represent K could be very large, but so far there is no systematic method known for generating them in a reasonable manner. We derive a formula for the dimension of K, which only needs the data in (1), and the solution to some problems on the convex polyhedron K, however, these problems are NP-complete. THE RESULTS LEMMA 1: Let K, the set of feasible solutions of (1), be unbounded, and suppose i is such that D. x is unbounded above over K. The problem of checking whether there exists of extreme point of K satisfying D. x > di, is NP-complete. PROOF: Clearly, this problem is in NP. Let F be the set of feasible solutions of 2

t x > dt, t + i Then by hypothesis, F is an unbounded convex polyhedron and D. x is unbounded above on it. Since the problem of finding the extreme point of F that maximizes D. x is NP-hard, see [1], the problem of checking whether there exists an extreme point of F satisfying D. x > d. is NP-complete. By 41o 1 the results of [2, 3], each extreme point of K has to belong to one of the following types. a) extreme points of F satisyfing D. x > d. 1. 1 b) extreme points of F satisyfing D. x = d. 1. 1 c) points of intersection of edges of F (bounded or unbounded) which do not totally lie in the hyperplane {x: D. x = d.}, with that hyperplane. So the only extreme points of K which satisfy D. x > di, are those of type (a) above, that is, those extreme points of F satisfying D. x > d.. But from the argument made above, the problem of checking whether there exists an extreme point of F satisfying D. x > d. is NP-complete. So the problem of checking whether there exists an extreme point of K satisfying Di. x > di, is NP-complete. Since we assumed that the dimension of K, defined by (1), is n, there exists an x ~ K satisfying Dx > d, or equivalently, for each i = 1 to m there exists an x ~ K satisfying D. x > d.. We have the following result. THEOREM 1: Let K, the set of feasible solutions of (1), be of dimension n. The dimension of K is also n iff for each i = 1 to m, there exists an extreme point x of K satisfying D. x > d.. 1. 1 PROOF: Since K C K, every point in K satisfies (1), this implies that if the dimension of K is n, there must exist a point x E K satisfying Dx > d. 3

Since x ~ K, it is a convex combination of extreme points of K, so Dx > d holds iff for each i = 1 to m, there exists an extreme point x of K satisfying D. x > d.. Conversely, suppose for each i = 1 to m there exists an extreme point ^i x of K satisfying D. x > d.. It is well known that between every pair of extreme points of K, there exists an edge path of K joining them, consisting of only bounded edges of K. See [3]. Using this and the hypothesis, we can prove that the dimension of K is n. T Introducing the vector of slack variables s = (s,., S m, the system (1) can be expressed as Dx - I s = d m s 0 where I is the unit matrix of order m. In this, the equality constraints m can be used to eliminate the unrestricted variables x1,...,x. Suppose this leads to a system Es = p ( s -0 where E, p are matrices of orders rxm and rxl respectively, where r = m - n, and E has rank r. Every extreme point of K corresponds to a basic feasible 0 o o T solution (BFS) of (3). Let s (sl..,sm) be a BFS of (3) corresponding to a basic vector (s,...,sr) for (3). Suppose the system (3) is nondegen0 erate. In s, the nonbasic variables sr+l,...,s are all zero. By the hypothesis, for each t = r + 1 to m, there exists a BFS of (3) in which the variable st > 0. And each BFS of (3) is connected to s~ by an edge path as mentioned above. So, among the nonbasic variables s r+l...,s, at least some of them must enter the basic vector (l,...,sr) of (3) leading to adjacent BFSs of s, and not to unbounded edges. Suppose these are the nonbasic variables s+j, j = 1 to q. Let sj = (s,...,sJ) be the BFS r~~j' 1 ~m 4

obtained when the nonbasic variable s+j is entered into the basic vector (s1,...,Sm), for j = 1 to q. So sj = 0, for i = r + 1 to m, i + r + j (4) > 0, for i = r + j In each of the BFSs s, s, j = 1 to q, all the variables sr+q+l...,s are zero, and by the hypothesis there are BFSs of (3) in which these variables are > 0. By the edge path connectedness property, there must exist adjacent extreme points of si, j = 1 to q, in which exactly one of the variables among sr+q+,...,s is > 0 and the others are zero. Suppose these are BFSs q+t q+ t q+t T sq = (s,...,sq ), t = 1 to u, such that ~q+ m st =0 for i = r+q+l to m, i r r+q+t (5) > 0 for i = r+q+t And this process can be repeated. Eventually we get BFSs si = (si,... )T of (3), j = 1 to m - r, satisfying the property that j = 0, for i = r+j+l to m 1 (6) > 0, for i = r+j By (6) we conclude that the rank of the set {sj - s: j = 1 to m- r} is m - r which implies that the dimension of the convex hull of BFSs of (3) is m - r = n, and hence the dimension of the convex hull of extreme points of K is n. A similar proof applies even when (3) is degenerate. THEOREM 2: Let K be the set of feasible solutions of (1), and assume that K has at least one extreme point. Let J = {i: there exists no extreme point of K satisfying Di x > d.}. Then the dimension of K = n - rank of i. 1 {D.: i ~ J}. 1. PROOF: By the definition of the set J, all the extreme points of K satisfy 5

Dix x di, i ~ J i. i' D. x = d. i, J (7) 1. 1) The result follows by applying Theorem 1 to the reduced system obtained by eliminating variables using the equality constraints in (7). B By Theorem 1, to check whether the dimension of K is n, we must check whether there exists an extreme point of K satisfying D. x > di, for each i = 1 to m. However, by Lemma 1, for any i, the problem of checking whether there exists an extreme point of K satisfying Di. x > di, is NP-complete. This suggests that the problem of checking whether the dimension of K is n, or computing the dimension of K, may be hard problems. 6

REFERENCES [1] S. J. Chung and K. G. Murty, "On KA", Technical Report 85-4, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, MI 48109-2117, USA, February 1985. [21 K. G. Murty, "Adjacency on convex polyhedra", SIAM Review, 13, 3 (July 1971) 377-386. [3] K. G. Murty, "Linear Programming", Wiley, 1983. 7