---
title: Hyperplanes and Polytopes
module: Geometry of Vector Spaces
moduleNumber: 9
lessonNumber: 4
order: 904
summary: >
  A hyperplane is a level set of a linear functional, the set where an inner
  product equals a constant. Hyperplanes separate disjoint convex sets and support
  them at their boundaries. Polytopes are convex hulls of finite point sets; their
  vertices are the extreme points, and a linear functional attains its extremes
  there.
topics: [Geometry of Vector Spaces]
sources:
  - book: Lay
    ref: "Ch. 8 — The Geometry of Vector Spaces; §8.4 Hyperplanes; §8.5 Polytopes"
draft: false
---

An affine set carries an explicit, parametric description: a point plus a span.
Hyperplanes are better handled implicitly, as
the solution set of a single equation. That equation is the vanishing of a linear
functional, and the implicit form is what makes hyperplanes separate sets and
bound polytopes.[^lay-hyper]

## Hyperplanes as level sets

A **linear functional** on $\mathbb{R}^n$ is a linear transformation $f :
\mathbb{R}^n \to \mathbb{R}$. For a scalar $d$, write $[f : d]$ for the set where
$f$ takes the value $d$:

$$
[f : d] = \{\mathbf{x} \in \mathbb{R}^n : f(\mathbf{x}) = d\}.
$$

The standard matrix of $f$ is a $1 \times n$ matrix $A = [\,a_1\; a_2\; \cdots\;
a_n\,]$, so $f(\mathbf{x}) = A\mathbf{x} = \mathbf{n} \cdot \mathbf{x}$ for the
vector $\mathbf{n}$ with the same entries. Two implicit descriptions of a line in
$\mathbb{R}^2$ and a plane in $\mathbb{R}^3$ fit this pattern:

- In $\mathbb{R}^2$, the line $x - 4y = 13$ is $[f : 13]$ for $f(x,y) = x - 4y$.
- In $\mathbb{R}^3$, the plane $5x - 2y + 3z = 21$ is $[g : 21]$ for $g(x,y,z) =
  5x - 2y + 3z$.

For a nonzero functional, $\operatorname{rank} A = 1$, so $\dim
\operatorname{Nul} A = n - 1$ by the rank theorem. The set $[f : 0] =
\operatorname{Nul} A$ is therefore a hyperplane through the origin, and every
level set $[f : d]$ is a parallel translate of it: if $\mathbf{p}$ is any point
with $f(\mathbf{p}) = d$, then

$$
[f : d] = [f : 0] + \mathbf{p}.
$$

Writing $f(\mathbf{x}) = \mathbf{n} \cdot \mathbf{x}$ shows $[f : 0]$ is the
orthogonal complement of $\operatorname{Span}\{\mathbf{n}\}$. The vector
$\mathbf{n}$ is **normal** to the hyperplane and to all of its parallel
translates, even though $\mathbf{n} \cdot \mathbf{x} = d \neq 0$ on those
translates. When $f(\mathbf{x}) = \mathbf{n} \cdot \mathbf{x}$, the vector
$\mathbf{n}$ is the gradient of $f$.

$$
% caption: The level sets of a linear functional are parallel hyperplanes, each
% orthogonal to the normal $\mathbf{n}$. The value $d$ increases in the direction
% of $\mathbf{n}$.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
\definecolor{acc}{HTML}{2F6DB5}
\definecolor{red}{HTML}{B23A48}
\coordinate (O) at (0,0);
% three parallel lines
\draw[black] (-0.6,2.0) -- (2.4,-1.0);
\draw[acc, thick] (0.2,2.8) -- (3.2,-0.2);
\draw[black] (1.0,3.6) -- (4.0,0.6);
\node[black, anchor=west] at (2.3,-0.85) {$[f:0]$};
\node[acc, anchor=west] at (3.05,-0.1) {$[f:d]$};
\node[black, anchor=west] at (3.85,0.7) {$[f:2d]$};
% normal vector
\draw[->, red, very thick] (1.0,0.9) -- (2.0,1.9);
\node[red, anchor=east] at (1.75,1.75) {$\mathbf{n}$};
\fill[black] (O) circle (1.4pt) node[anchor=north east] {$O$};
\end{tikzpicture}
$$

Converting an explicit line into implicit form means finding the normal, then
the constant.

> **Worked example.** Let $\mathbf{v}_1 = (1,2)$ and $\mathbf{v}_2 = (6,0)$, and
> let $L$ be the line through them. Find a functional $f$ and constant $d$ with
> $L = [f : d]$.
>
> The direction of $L$ is $\mathbf{v}_2 - \mathbf{v}_1 = (5, -2)$. A normal
> $\mathbf{n} = (a,b)$ must satisfy $\mathbf{n} \cdot (5,-2) = 5a - 2b = 0$. By
> inspection $\mathbf{n} = (2, 5)$ works, so $f(x,y) = 2x + 5y$. The constant is
> the value of $f$ at any point of the line:
> $$
> d = f(\mathbf{v}_1) = 2(1) + 5(2) = 12.
> $$
> As a check, $f(\mathbf{v}_2) = 2(6) + 5(0) = 12$. The line is $2x + 5y = 12$.

Every hyperplane admits this description, which is the content of the next
theorem.

> **Theorem (Characterization of hyperplanes).** A subset $H$ of $\mathbb{R}^n$ is a hyperplane if and only if
> $H = [f : d]$ for some nonzero linear functional $f$ and scalar $d$.
> Equivalently, there exist a nonzero vector $\mathbf{n}$ and scalar $d$ with $H =
> \{\mathbf{x} : \mathbf{n} \cdot \mathbf{x} = d\}$.

Given a hyperplane $H$, pick $\mathbf{p} \in H$ and set $H_0 = H - \mathbf{p}$, an
$(n-1)$-dimensional subspace. Any vector $\mathbf{n}$ orthogonal to $H_0$ defines
$f(\mathbf{x}) = \mathbf{n} \cdot \mathbf{x}$; then $[f : 0]$ is a hyperplane
containing $H_0$, hence equal to it by dimension, and $d = f(\mathbf{p})$ gives $H
= [f : 0] + \mathbf{p} = [f : d]$.

Translating a hyperplane shifts its constant.

> **Worked example.** Let $\mathbf{n} = (3,4)$ and $H = [f : 12]$ with $f(x,y) =
> 3x + 4y$, so $H$ is the line $3x + 4y = 12$. Describe the translate $H_1 = H +
> \mathbf{v}$ for $\mathbf{v} = (1, -6)$.
>
> Find any point of $H$: $(0, 3)$ works, since $3(0) + 4(3) = 12$. Translate it:
> $\mathbf{p} = (0,3) + (1,-6) = (1, -3)$ lies in $H_1$. Evaluate $f$ there:
> $$
> f(\mathbf{p}) = 3(1) + 4(-3) = -9.
> $$
> So $H_1 = [f : -9]$, the line $3x + 4y = -9$, parallel to $H$ with the same
> normal $\mathbf{n}$.

## Separation

A hyperplane splits $\mathbb{R}^n$ into two closed half-spaces. Writing $f(A) \le
d$ to mean $f(\mathbf{x}) \le d$ for every $\mathbf{x} \in A$, the hyperplane $H =
[f : d]$ **separates** sets $A$ and $B$ if $f(A) \le d$ and $f(B) \ge d$, or the
reverse. Replacing the weak inequalities by strict ones gives **strict
separation**. Strict separation forces the sets to be disjoint; ordinary
separation does not, since two externally tangent circles share their common
tangent line.

$$
% caption: A separating hyperplane places $A$ in one closed half-space and $B$ in
% the other; strict separation keeps both off the hyperplane itself.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
\definecolor{acc}{HTML}{2F6DB5}
\definecolor{red}{HTML}{B23A48}
% set A
\fill[acc!12] (0.7,1.4) circle (0.85);
\draw[acc, thick] (0.7,1.4) circle (0.85);
\node[acc] at (0.7,1.4) {$A$};
% set B
\fill[red!10] (4.4,1.5) -- (5.6,1.0) -- (5.9,2.4) -- (4.7,2.7) -- cycle;
\draw[red, thick] (4.4,1.5) -- (5.6,1.0) -- (5.9,2.4) -- (4.7,2.7) -- cycle;
\node[red] at (5.15,1.85) {$B$};
% separating line
\draw[black, thick] (2.7,-0.2) -- (3.1,3.4);
\node[black!70, anchor=south] at (3.05,3.3) {$H=[f:d]$};
\end{tikzpicture}
$$

Two theorems give conditions for strict separation. Both turn a geometric
question about sets into an algebraic one about their convex hulls.

> **Theorem (Strict separation of a compact and a closed convex set).** Let $A$ and $B$ be nonempty convex sets with $A$ compact and
> $B$ closed. A hyperplane strictly separates $A$ and $B$ if and only if $A \cap B
> = \varnothing$.

> **Theorem (Strict separation via convex hulls).** Let $A$ and $B$ be nonempty compact sets. A hyperplane strictly
> separates $A$ and $B$ if and only if $(\operatorname{conv} A) \cap
> (\operatorname{conv} B) = \varnothing$.

The convex-hull separation theorem follows from the compact–closed separation theorem applied to the compact convex hulls. If
$H = [f:d]$ strictly separates $A$ and $B$ with $f(A) < d < f(B)$, then for any
convex combination $\mathbf{x} = \sum c_i\mathbf{x}_i$ of points of $A$,

$$
f(\mathbf{x}) = \sum c_i f(\mathbf{x}_i) < \sum c_i d = d,
$$

so $f(\operatorname{conv} A) < d$, and likewise $f(\operatorname{conv} B) > d$.
The functional that separates the sets separates their hulls.

> **Worked example.** Let $A = \operatorname{conv}\{(0,0), (1,0), (0,1)\}$ and $B
> = \operatorname{conv}\{(2,2), (3,2), (2,3)\}$, and take $f(x,y) = x + y$. On the
> vertices of $A$, $f$ takes values $0, 1, 1$, so $f(A) \le 1$. On the vertices
> of $B$, $f$ takes values $4, 5, 5$, so $f(B) \ge 4$. Any $d$ with $1 < d < 4$
> gives a strictly separating hyperplane; the line $x + y = 2$ is one. By the
> convex-hull separation theorem, $\operatorname{conv} A$ and $\operatorname{conv} B$ are disjoint.

Disjointness alone is not enough for closed convex sets that are both unbounded.
The region above a hyperbola and its horizontal asymptote are disjoint closed
convex sets that no line strictly separates, since they approach each other
without limit. Compactness of one set, as in the compact–closed separation theorem, rules this out.

## Polytopes

A **polytope** in $\mathbb{R}^n$ is the convex hull of a finite set of points. In
$\mathbb{R}^2$ a polytope is a polygon, in $\mathbb{R}^3$ a polyhedron. Its
structure is described through supporting hyperplanes.

Let $S$ be a compact convex set. A nonempty subset $F \subsetneq S$ is a **face**
of $S$ if there is a hyperplane $H = [f : d]$ with $F = S \cap H$ and $f(S) \le d$
(or $f(S) \ge d$); the hyperplane $H$ is a **supporting hyperplane**, touching
$S$ without cutting into it. A face of dimension $k$ is a **$k$-face**. For a
polytope:

- **Vertex**: a $0$-face.
- **Edge**: a $1$-face.
- **Facet**: an $(n-1)$-face, one dimension below the polytope.

A cube shows the three low-dimensional cases at once. Slide a plane toward the
cube until it just touches: depending on orientation, the contact $H \cap S$ is a
square facet, an edge, or a single vertex.

$$
% caption: A supporting plane meets a cube in a facet, an edge, or a vertex,
% depending on its orientation; each is a face of the cube.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=0.9]
\definecolor{acc}{HTML}{2F6DB5}
\definecolor{red}{HTML}{B23A48}
% cube 1: face contact
\begin{scope}
\draw[acc, thick] (0,0) rectangle (1.4,1.4);
\draw[acc, thick] (0,1.4) -- (0.5,1.9) -- (1.9,1.9) -- (1.4,1.4);
\draw[acc, thick] (1.4,0) -- (1.9,0.5) -- (1.9,1.9);
\draw[red, very thick] (2.25,0.5) -- (2.25,1.9);
\node[red, anchor=west, font=\scriptsize] at (2.3,1.2) {facet};
\end{scope}
% cube 2: edge contact
\begin{scope}[shift={(4.4,0)}]
\draw[acc, thick] (0,0) rectangle (1.4,1.4);
\draw[acc, thick] (0,1.4) -- (0.5,1.9) -- (1.9,1.9) -- (1.4,1.4);
\draw[acc, thick] (1.4,0) -- (1.9,0.5) -- (1.9,1.9);
\draw[red, very thick] (1.55,2.3) -- (2.7,1.15);
\node[red, anchor=west, font=\scriptsize] at (2.15,2.0) {edge};
\end{scope}
% cube 3: vertex contact
\begin{scope}[shift={(8.8,0)}]
\draw[acc, thick] (0,0) rectangle (1.4,1.4);
\draw[acc, thick] (0,1.4) -- (0.5,1.9) -- (1.9,1.9) -- (1.4,1.4);
\draw[acc, thick] (1.4,0) -- (1.9,0.5) -- (1.9,1.9);
\draw[red, very thick] (1.3,2.55) -- (2.85,2.0);
\node[red, anchor=west, font=\scriptsize] at (2.2,2.4) {vertex};
\fill[red] (1.9,1.9) circle (1.7pt);
\end{scope}
\end{tikzpicture}
$$

Vertices carry the essential information because they are the extreme points. A
point $\mathbf{p}$ in a convex set $S$ is an **extreme point** if it is not in the
interior of any segment lying in $S$: whenever $\mathbf{p} \in
\overline{\mathbf{xy}}$ with $\mathbf{x}, \mathbf{y} \in S$, either $\mathbf{p} =
\mathbf{x}$ or $\mathbf{p} = \mathbf{y}$. The set of extreme points is the
**profile** of $S$. The profile of a polygon is its vertices; the profile of a
closed disk is its boundary circle; an open set and a half-space have empty
profile.

> **Theorem (Vertices, extreme points, and the minimal representation).** Let $M = \{\mathbf{v}_1, \dots, \mathbf{v}_k\}$ be the minimal
> representation of a polytope $P$ (no $\mathbf{v}_i$ is a convex combination of
> the others). For a point $\mathbf{p}$, the following are equivalent: $\mathbf{p}
> \in M$; $\mathbf{p}$ is a vertex of $P$; $\mathbf{p}$ is an extreme point of $P$.

> **Theorem (Recovery of a compact convex set from its profile).** A nonempty compact convex set is the convex hull of its
> profile.

The extreme points are thus the smallest set whose hull recovers $S$. For a
polytope that set is finite, and a linear functional is pinned to it.

> **Theorem (Linear functionals attain extrema at extreme points).** A linear functional $f$ on a nonempty compact convex set $S$
> attains its maximum and its minimum at extreme points of $S$.

If $\mathbf{v}_0$ maximizes $f$, write it as a convex combination of extreme
points $\mathbf{v}_0 = \sum c_i\mathbf{v}_i$. Were $f(\mathbf{v}_i) < m$ for every
extreme point, linearity would give $f(\mathbf{v}_0) = \sum c_i f(\mathbf{v}_i) <
m$, contradicting $f(\mathbf{v}_0) = m$. So some extreme point attains $m$.

$$
% caption: Level lines of $f$ sweep across a polygon; the last line to touch it
% meets it at an extreme point (or along an edge), where the maximum is attained.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
\definecolor{acc}{HTML}{2F6DB5}
\definecolor{red}{HTML}{B23A48}
\coordinate (P1) at (0,0.4);
\coordinate (P2) at (2.4,0);
\coordinate (P3) at (3.4,1.6);
\coordinate (P4) at (2.0,3.0);
\coordinate (P5) at (0.3,2.2);
\fill[acc!10] (P1) -- (P2) -- (P3) -- (P4) -- (P5) -- cycle;
\draw[acc, thick] (P1) -- (P2) -- (P3) -- (P4) -- (P5) -- cycle;
% level lines
\draw[black] (0.2,-0.5) -- (-0.9,1.7);
\draw[black] (1.6,-0.5) -- (0.5,1.7);
\draw[red, thick] (3.7,0.9) -- (2.6,3.1);
\node[red, anchor=west, font=\scriptsize] at (3.5,1.4) {max here};
\fill[red] (P3) circle (1.9pt);
\draw[->, black] (-0.4,0.2) -- (0.4,-0.05) node[anchor=west, font=\scriptsize] {increasing $f$};
\end{tikzpicture}
$$

A polytope has two dual descriptions: explicitly as the convex hull of its
vertices, and implicitly as the intersection of finitely many closed half-spaces
$A\mathbf{x} \le \mathbf{b}$. Passing between them is a standard computation.

> **Worked example.** Let $P$ be the set of points in $\mathbb{R}^2$ with
> $\mathbf{x} \ge \mathbf{0}$ and
> $$
> x_1 + 3x_2 \le 18, \qquad x_1 + x_2 \le 8, \qquad 3x_1 + 2x_2 \le 21.
> $$
> Find the vertices (the minimal representation).
>
> The constraint $\mathbf{x} \ge \mathbf{0}$ confines $P$ to the first quadrant,
> giving the vertices $(0,0)$, $(7,0)$ on the $x_1$-axis, and $(0,6)$ on the
> $x_2$-axis. The remaining candidates are intersections of the boundary lines,
> each tested against the constraint not used to form it:
> $$
> \begin{array}{lll}
> (1)\cap(2): & (3,5), & 3(3)+2(5)=19 \le 21 \ \checkmark \\
> (2)\cap(3): & (5,3), & (5)+3(3)=14 \le 18 \ \checkmark \\
> (1)\cap(3): & \big(\tfrac{27}{7}, \tfrac{33}{7}\big), & \tfrac{27}{7} +
> \tfrac{33}{7} = \tfrac{60}{7} > 8 \ \times
> \end{array}
> $$
> The point $\big(\tfrac{27}{7}, \tfrac{33}{7}\big)$ violates the second
> constraint, so it is outside $P$. The minimal representation is
> $$
> \{(0,0),\ (7,0),\ (5,3),\ (3,5),\ (0,6)\}.
> $$

$$
% caption: The polytope defined by three inequalities and the first-quadrant
% condition, with its five vertices. The rejected line intersection lies outside.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=0.42]
\definecolor{acc}{HTML}{2F6DB5}
\definecolor{red}{HTML}{B23A48}
% axes
\draw[->, black] (0,0) -- (10,0) node[anchor=north] {$x_1$};
\draw[->, black] (0,0) -- (0,8) node[anchor=east] {$x_2$};
% polytope
\fill[acc!12] (0,0) -- (7,0) -- (5,3) -- (3,5) -- (0,6) -- cycle;
\draw[acc, thick] (0,0) -- (7,0) -- (5,3) -- (3,5) -- (0,6) -- cycle;
% vertices
\foreach \p/\l in {(0,0)/{},(7,0)/{},(5,3)/{},(3,5)/{},(0,6)/{}}
  \fill[acc] \p circle (3pt);
\node[acc, anchor=north east] at (0,0) {(0,0)};
\node[acc, anchor=north] at (7,0) {(7,0)};
\node[acc, anchor=west] at (5,3) {(5,3)};
\node[acc, anchor=south east] at (3,5) {(3,5)};
\node[acc, anchor=east] at (0,6) {(0,6)};
% rejected point
\fill[red] (3.857,4.714) circle (3pt);
\node[red, anchor=west, font=\scriptsize] at (4.1,4.4) {outside};
\end{tikzpicture}
$$

Every vertex is a candidate location for the optimum of a linear objective, which
is the geometric core of linear programming: a linear functional on a polytope
attains its extremes at vertices, so an optimizer walks from vertex to vertex
along edges. The curved boundaries excluded by "finite set of points" call for a
different construction, the
[Bézier curves](/linear-algebra/geometry-of-vector-spaces/curves-and-surfaces)
built from control points.

[^lay-hyper]: **Lay**, _Linear Algebra and Its Applications_, §8.4 Hyperplanes
(linear functionals, level sets, Theorem 11, separation Theorems 12–13) and §8.5
Polytopes (faces and supporting hyperplanes, extreme points and profile, Theorems
14–16, dual descriptions). Worked examples adapt §8.4 Examples 3, 5 and §8.5
Example 5.