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+.