Convex and discrete geometry Polytopes and polyhedra Theorem

Minkowski–Weyl theorem

Builds on Convex hull Convex cone Convex polytope H-representation and V-representation

Statement

Let $n \ge 1$ , and let $P \subseteq \R^n$ be nonempty. The following are equivalent.

There are a real $m \times n$ matrix $A$ and $b \in \R^m$ , for some $m \ge 0$ , with $P = \set{x \in \R^n : A x \le b}$ , where $\le$ is taken coordinatewise.
There are finite sets $V, W \subseteq \R^n$ with $V \ne \emptyset$ and $P = \mathrm{conv}(V) + \mathrm{cone}(W)$ .

Here $\mathrm{conv}(V)$ is the convex hull of $V$ , and $\mathrm{cone}(W)$ is the convex cone of all nonnegative linear combinations of $W$ , with $\mathrm{cone}(\emptyset) = \set{0}$ . In particular, $P$ is a convex polytope if and only if it is a bounded set of the form in 1.

Remarks

For 2 implies 1, write $P$ as the projection to $\R^n$ of the set of all $(x, \lambda, \mu)$ with $x = \sum_v \lambda_v v + \sum_w \mu_w w$ , $\lambda, \mu \ge 0$ and $\sum_v \lambda_v = 1$ . Fourier–Motzkin elimination shows that the projection of a set given by finitely many linear inequalities is again such a set. For 1 implies 2, one can apply the first direction to a suitable polar cone. The polytope case follows, because a bounded set $\mathrm{conv}(V) + \mathrm{cone}(W)$ must have $\mathrm{cone}(W) = \set{0}$ . Example: the square $[0, 1]^2$ is $\set{x : 0 \le x_1 \le 1, \ 0 \le x_2 \le 1}$ , given by four inequalities, and also $\mathrm{conv}\set{(0, 0), (1, 0), (0, 1), (1, 1)}$ . The quadrant $\set{x : x_1 \ge 0, x_2 \ge 0}$ is $\mathrm{conv}\set{0} + \mathrm{cone}\set{(1, 0), (0, 1)}$ . Finiteness is needed: the closed unit disc is an intersection of infinitely many half-planes and the convex hull of infinitely many points, but of neither form above.

Going deeper

For a student

The two descriptions are the V-representation and H-representation of a polytope. Linear programming uses both: the feasible region is given by inequalities, while the simplex method moves between vertices. Changing from one description to the other is the vertex and facet enumeration problem. The sizes can differ a lot: the cube $[0, 1]^n$ needs $2n$ inequalities but has $2^n$ vertices. The theorem is a finite-dimensional cousin of Farkas' lemma, and the two can be derived from each other.

Reading path

To understand this page from the ground up, read these 5 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Convex cone concept
Convex hull concept
Convex polytope concept
H-representation and V-representation concept
Minkowski–Weyl theorem statement

Tag	`5DFMMGGD9Y`
URI	`m2://5DFMMGGD9Y`
Kind	statement, theorem
Writing	W0 stub
MSC	52B11, 90C05
Status	This copy of the site has no build data. Run `m2 status 5DFMMGGD9Y`.
About	Convex polytope, H-representation and V-representation
Uses	Convex hull, Convex cone, Convex polytope, H-representation and V-representation