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