If τ is a projection of a closed
convex polyhedron P onto a convex polyhedron Q, then a lifting of 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 lifting τ∗, provided only that there
exists at least one face of P on which τ acts one-to-one. The lifting theorem
represents 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.
