ON THE DIMENSION OF PROJECTED POLYHEDRA

We address several basic questions that arise in the use of projection in combinatorial optimization. Central to these is the connection bet ween the dimension of a polyhedron Q and the dimension of its projecti on on a subspace. We give the exact relationship between the two dimen sions. As a byproduct we characterize the relationship between the equ ality subsystem of a polyhedron and that of its projection. We also de rive a necessary and sufficient condition for a face (in particular, a facet) of a polyhedron Q to project into a face (a facet) of the proj ection of Q, and give a necessary and sufficient condition for the exi stence of a 1-1 correspondence between the faces of Q and those of its projection. More generally, we characterize the dimensional relations hip between the projection of Q and that of an arbitrary proper face o f Q. We also show that the projection of a monotonized polyhedron on a subspace is the monotonization of the projection of the polyhedron on the same subspace. (C) 1998 Elsevier Science B.V All rights reserved.