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.

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.