9. Polyhedra and Linear Transformations 37 9. Polyhedra and Linear Transformations We would like to extend the results of Section 8 to certain unbounded sets, specifi- cally to polyhedra. Recall (see Definition 2.2) that a polyhedron is a set of solutions to a finite system of linear inequalities. The main result of this section is that the image of a polyhedron under a linear transformation is a polyhedron. Hence the class of polyhedra is preserved by linear transformations. We will need this result in Section IV.8. The proof is based on “going down one step at a time”. (9.1) Lemma. Let P ⊂ Rd be a polyhedron and let pr : Rd −→ Rd−1 be the projection pr(ξ1,... , ξd) = (ξ1, . . . , ξd−1). Then the image pr(P ) is a polyhedron in Rd−1. Proof. Suppose that P is defined by a system of linear inequalities for vectors x = (ξ1, . . . , ξd) in Rd: P = x : d j=1 αijξj ≤ βi for i = 1, . . . , m , where αij and βj are real numbers. Let us define I+ = {i : αid 0}, I− = {i : αid 0} and I0 = {i : αid = 0}. Hence a point (ξ1, . . . , ξd−1) belongs to the projection pr(P ) if and only if d−1 j=1 αijξj ≤ βi for i ∈ I0, and there exists a number ξd which satisfies the inequalities αidξd + d−1 j=1 αijξj ≤ βi for all i ∈ I+ ∪ I−. The latter of these two conditions is equivalent to ξd ≤ βi αid − d−1 j=1 αij αid ξj for all i ∈ I+ and ξd ≥ βi αid − d−1 j=1 αij αid ξj for all i ∈ I−. Such a number ξd exists if and only if for no pair of numbers consisting of one of the lower bound for ξd and one of the upper bound for ξd does the lower bound exceed the upper bound. Thus ξd exists if and only if βi αid − d−1 j=1 αij αid ξj ≤ βk αkd − d−1 j=1 αkj αkd ξj for all pairs i ∈ I− and k ∈ I+.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2002 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.