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