38 I. Convex Sets at Large

Hence the projection pr(P ) is the polyhedron in

Rd−1

defined by the following

linear inequalities for (ξ1, . . . , ξd−1):

d−1

j=1

αijξj ≤ βi for all i ∈ I0 and

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

If I0 is empty, then there are no inequalities of the first kind, and if I−,I+ or both

are empty, then there are no inequalities of the second kind.

PROBLEMS.

1◦.

Let P ⊂

Rd

be a polyhedron defined by m ≥ 4 linear inequalities, and let

Q = pr(P ) ⊂

Rd−1

be its projection. Prove that Q can be defined by not more

than

m2/4

linear inequalities.

2◦.

Let P ⊂

Rn,

P = x : ai,x ≤ βi,i = 1, . . . , m be a polyhedron and let

T :

Rn

−→

Rn

be an invertible linear transformation. Prove that Q = T (P ) is a

polyhedron defined by Q = x : ci,x ≤ βi,i = 1, . . . , m , where ci = (T

∗)−1ai

and T

∗

is the conjugate linear transformation.

Now we can prove the result in full generality.

(9.2) Theorem. Let P ⊂

Rn

be a polyhedron and let T :

Rn

−→

Rm

be a linear

transformation. Then T (P ) is a polyhedron in

Rm.

Proof. If n = m and T is invertible, the result follows by Problem 2 of Section

9.1. If ker T = {0}, then the restriction T :

Rn

−→ im T ⊂

Rm

is an invertible

linear transformation and the result follows as above. For a general T , let us define

a transformation T :

Rn

−→

Rm

⊕

Rn

=

Rm+n

by T (x) =

(

T (x), x

)

. Then

ker T = {0} and hence T (P ) is a polyhedron in

Rm+n.

Now we observe that T (P )

is obtained from T (P ) by a series of n successive projections

Rm+n

−→

Rm+n−1

−→ . . . −→

Rm

via

(ξ1, . . . , ξm+n) −→ (ξ1, . . . , ξm+n−1) −→ . . . −→ (ξ1, . . . , ξm).

Applying Lemma 9.1 m times, we conclude that T (P ) is a polyhedron.

The procedure of obtaining the description of T (P ) from the description of P

which we employed in Lemma 9.1 and Theorem 9.2 is called the Fourier-Motzkin

Elimination.

PROBLEMS.

1. Let P ⊂

Rn

be a polyhedron defined by k linear inequalities and let T :

Rn

−→

Rm

be a linear transformation. Estimate the number of linear inequalities

needed to define T (P ) using the construction of Theorem 9.2.