Linear Algebra › Section H · The geometry of vector spaces › Topic H.5
Polytopes
Triangles, cubes and pyramids are the familiar members of a family that exists in every dimension. Polytopes are convex hulls of finitely many points, and their corners decide where linear quantities such as cost or profit reach their extremes, the key fact behind linear programming.
Polygons, polyhedra and beyond
A convex polygon in the plane and a convex polyhedron in space, such as a cube or a pyramid, share one description: each is the convex hull of finitely many points, its corners. That description makes sense in any \(\mathbb{R}^n\). A polytope is the convex hull of a finite set of points. The dimension of a polytope is the dimension of its affine hull, so a triangle sitting in \(\mathbb{R}^3\) is still a 2-dimensional polytope. Polytopes in four or more dimensions cannot be drawn directly, but they can be counted, computed with and projected, and they appear whenever several linear constraints act at once, as in scheduling, diet planning and logistics.
Extreme points
A point \(\mathbf{p}\) of a convex set \(S\) is an extreme point if it is not strictly inside any segment lying in \(S\): whenever \(\mathbf{p} = (1 - t)\mathbf{x} + t\mathbf{y}\) with \(\mathbf{x}, \mathbf{y} \in S\) and \(0 < t < 1\), we must have \(\mathbf{x} = \mathbf{y} = \mathbf{p}\). The corners of a square are extreme; the midpoint of an edge is not, since it lies halfway between two corners. Every point of a circle bounding a solid disc is extreme, so a disc has infinitely many. The set of extreme points of \(S\) is called its profile. For a polytope \(P = \operatorname{conv} S\) with \(S\) finite, the extreme points all belong to \(S\), but some points of \(S\) may be interior or on an edge and so not extreme.
A polytope is the hull of its corners
Hermann Minkowski proved that a compact convex set in \(\mathbb{R}^n\) is the convex hull of its extreme points. For a polytope this gives a minimal description: \(P\) is the convex hull of its extreme points, its vertices, and no smaller set will do, because a vertex is never a convex combination of other points of \(P\). So to describe a polytope given as \(\operatorname{conv} S\), discard every point of \(S\) that is a convex combination of the others; what remains are the vertices. For instance, the convex hull of \((0, 0)\), \((4, 0)\), \((0, 4)\) and \((1, 1)\) is the triangle with the first three as vertices, because
Faces and the two descriptions
A face of a polytope \(P\) is its intersection with a supporting hyperplane, one that touches \(P\) while keeping all of \(P\) in one closed half-space. Faces are polytopes themselves: vertices have dimension 0, edges dimension 1, and in a \(k\)-dimensional polytope the faces of dimension \(k - 1\) are facets. The two descriptions of a polytope match. The vertex description lists its vertices; the half-space description writes it as the intersection of finitely many closed half-spaces, one per facet when the polytope is full-dimensional. The Minkowski-Weyl theorem says every polytope has both descriptions, and every bounded intersection of finitely many closed half-spaces is a polytope. Converting between them is a standard computing task.
Worked example: vertices from inequalities
Find the vertices of the region \(P\) given by \(x_1 \ge 0\), \(x_2 \ge 0\), \(x_1 + 2x_2 \le 10\) and \(3x_1 + x_2 \le 15\). 1. Each vertex lies on two of the boundary lines, so intersect them in pairs and keep the points satisfying every inequality. 2. \(x_1 = 0\) and \(x_2 = 0\) give \((0, 0)\). 3. \(x_2 = 0\) and \(3x_1 + x_2 = 15\) give \((5, 0)\); the line \(x_1 + 2x_2 = 10\) would give \((10, 0)\), which breaks \(3x_1 + x_2 \le 15\). 4. \(x_1 = 0\) and \(x_1 + 2x_2 = 10\) give \((0, 5)\), and \(3(0) + 5 = 5 \le 15\); the line \(3x_1 + x_2 = 15\) would give \((0, 15)\), which breaks \(x_1 + 2x_2 \le 10\). 5. The two slanted lines meet where \(x_2 = 15 - 3x_1\) and \(x_1 + 30 - 6x_1 = 10\), so \((4, 3)\). 6. The polygon is the quadrilateral with vertices \((0, 0)\), \((5, 0)\), \((4, 3)\) and \((0, 5)\).
Worked example: linear programming
A linear functional \(f\) on a polytope attains its maximum, and its minimum, at a vertex. The reason: every point of \(P\) is a convex combination \(\sum c_i\mathbf{v}_i\) of vertices, so \(f(\mathbf{x}) = \sum c_if(\mathbf{v}_i)\) is an average of vertex values and cannot exceed the largest of them. A workshop makes \(x_1\) tables and \(x_2\) chairs per week under the constraints of the previous card, with profit \(f = 4x_1 + 5x_2\) hundred dollars. 1. Evaluate at the vertices: \(f(0, 0) = 0\), \(f(5, 0) = 20\), \(f(4, 3) = 31\), \(f(0, 5) = 25\). 2. The maximum is $3,100 a week, at 4 tables and 3 chairs. George Dantzig's simplex method, from 1947, walks from vertex to vertex along edges, never letting \(f\) decrease.
Simplices
A simplex is the convex hull of an affinely independent set of points. A \(k\)-simplex has \(k + 1\) vertices and dimension \(k\). Build them up: a 0-simplex is a point; add a point off its affine hull to get a 1-simplex, a segment; add a point off that line to get a triangle; then a tetrahedron; and in \(\mathbb{R}^4\), a 4-simplex with 5 vertices. Every subset of the vertices spans a face, so a \(k\)-simplex has \(\binom{k+1}{j+1}\) faces of dimension \(j\). The 4-simplex therefore has 5 vertices, 10 edges, 10 triangles and 5 tetrahedral facets. Because its vertices are affinely independent, every point of a simplex has unique barycentric coordinates, all non-negative.
Hypercubes and Euler's formula
The hypercube \(C_k\) is the set of points in \(\mathbb{R}^k\) with every coordinate between 0 and 1. Sweep a segment along a perpendicular direction to get a square; sweep the square to get a cube; sweep the cube along a fourth axis to get \(C_4\). Each sweep doubles the vertices and doubles the old edges while adding one new edge per old vertex. So \(C_4\) has 16 vertices, \(2 \times 12 + 8 = 32\) edges, 24 square faces and 8 cubic facets. Euler's formula checks such counts: for a 3-dimensional polytope, vertices − edges + faces = 2, as for the cube, \(8 - 12 + 6 = 2\). For 4-dimensional polytopes the alternating sum is 0: \(16 - 32 + 24 - 8 = 0\), and \(5 - 10 + 10 - 5 = 0\) for the 4-simplex.
Common mistakes to avoid
First, listing every generating point as a vertex: a point of \(S\) that is a convex combination of the others, such as \((1, 1)\) above, is not extreme. Second, keeping intersection points of boundary lines that break another constraint, such as \((10, 0)\) in the worked example. Third, thinking a linear functional's maximum must be at a unique vertex; it may be attained along a whole edge or face, though always at a vertex too. Fourth, confusing a simplex, which needs affinely independent vertices, with any polytope having \(k + 1\) vertices. Fifth, applying the 3-dimensional Euler formula, with total 2, to a 4-dimensional polytope.
Key takeaways
A polytope is the convex hull of a finite set of points; its dimension is that of its affine hull. An extreme point lies strictly inside no segment of the set, and the set of extreme points is the profile. By Minkowski's theorem a compact convex set is the convex hull of its extreme points, so a polytope is the hull of its vertices, its minimal description. Faces come from supporting hyperplanes, and facets have dimension one less than the polytope. Every polytope is also a bounded intersection of finitely many closed half-spaces. A linear functional reaches its maximum and minimum on a polytope at vertices, the basis of linear programming. A k-simplex has k + 1 affinely independent vertices; the hypercube C₄ has 16 vertices and 32 edges.
Flashcards
Flashcard
The convex hull of a finite set of points
Test your understanding
Question 1 of 5
What are the extreme points of conv{(0, 0), (2, 0), (2, 2), (0, 2), (1, 1), (2, 1)}?
Question 2 of 5
Maximise f = 3x₁ + 2x₂ over the polygon with vertices (0, 0), (5, 0), (4, 3) and (0, 5). What is the maximum?
Question 3 of 5
How many edges does a 3-simplex, a tetrahedron, have?
Question 4 of 5
Which statement about a polytope P in R⁴ is true?
Question 5 of 5
Using the sweeping construction, how many vertices and edges does the 5-dimensional hypercube C₅ have?
