LIFTING PROJECTIONS OF CONVEX POLYHEDRA

If τ is a projection of a closed convex polyhedron P onto a convex polyhedron Q, then a liftingof Q into P is defined to be a single-valued inverse τ* of τ such that τ* (Q) is the union of closed faces of P. The main result of this paper, designated the Lifting Theorem, asserts that there always exists a liftingrτ*, provided only that there exists at least one face of P on whichτ acts one-to-one. The liftingtheoremrep esents a unifying generalization of a number of results in the theory of convex polyhedra and should prove useful as an investigative as well as a conceptual tool. In the course of the proof, a special case of the Lifting Theorem is translated into linear programming terms and stated as the Basis Decomposition Theorem, which summarizes the behavior of a linear program as a function of its right-hand sides. In particular, the fact that a lifting is necessarily a piecewise linear homeomorphism is reflected in the Basis Decomposition Theorem as the observation that the optimal solution of a linear program can always be chosen as a continuous function of the right-hand sides. © 1969 by Pacific Journal of Mathematics.