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+.
Previous Page Next Page