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