# What is Minkowski’s Representation Theorem?

Minkowski’s representation theorem is a fundamental result on how polyhedra can be represented.

Preliminary definitions

• In $\mathbb{R}^n$, a polyhedron is a set which can be described as $\mathcal{P} = \{ x \in \mathbb{R}^n: Ax \leq b\}$, where $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$.
• $x \in \mathcal{P}$ is an extreme point of a polyhedron $\mathcal{P}$ if there do not exist $x_1, x_2 \in \mathcal{P}$ such that $x = \frac{1}{2}(x_1 + x_2)$.
• $r \in \mathbb{R}^n$ is a ray of a polyhedron $\mathcal{P} = \{ x \in \mathbb{R}^n: Ax \leq b\}$ if $r$ is non-zero and $Ar \leq 0$. Let $\mathcal{P}^{ray}$ denote the set of rays of $\mathcal{P}$.
• $r \in \mathcal{P}^{ray}$ is an extreme ray of a polyhedron $\mathcal{P}$ if there do not exist linearly independent $r_1, r_2 \in \mathcal{P}^{ray}$ such that $r = \frac{1}{2}(r_1 + r_2)$.

It can be shown that for any polyhedron, the number of extreme points and extreme rays is finite (proof in Reference 1).

Minkowski’s representation theorem

Minkowski’s representation theorem essentially says that a polyhedron can be described by its extreme points and extreme rays.

Theorem: If $\mathcal{P} = \{ x \in \mathbb{R}^n: Ax \leq b\}$ is non-empty and $\text{rank}(A) = n$, then

\begin{aligned} \mathcal{P} = \bigg\{ x \in \mathbb{R}^n: &x = \sum_{k \in K} \lambda_k x_k + \sum_{j \in J} \mu_j r_j, \\ &\sum_{k \in K} \lambda_k = 1, \lambda_k \geq 0 \;\forall k, \mu_j \geq 0 \;\forall j \bigg\}, \end{aligned}

where $\{ x_k \}_{k \in K}$ and $\{ r_j\}_{j \in J}$ are the set of extreme points and extreme rays of $\mathcal{P}$ respectively.

A proof of this theorem can be found in Reference 1. As a special case, if the polyhedron is bounded, then it does not have any extreme rays and so any point in the polyhedron can be described as a convex combination of its extreme points.

Minkowski representation & projection

The theorem tells us that a polyhedron can be expressed as the set of convex combination of its extreme points and rays. For notational convenience, let $x_1, \dots, x_K$ denote the extreme points and extreme rays of the polyhedron $\mathcal{P}$, and let $\delta_k = 1$ if $x_k$ is an extreme point, and $\delta_k = 0$ otherwise. The Minkowski representation of the polyhedron $\mathcal{P} \subseteq \mathbb{R}^n$ consists of variables $\lambda_1, \dots, \lambda_K$, one for each extreme point/ray:

\begin{aligned} \mathcal{P}^{Mk} = \left\{ \lambda \in \mathbb{R}^K : \sum_{k = 1}^K \delta_k \lambda_k = 1, \lambda \geq 0 \right\}, \end{aligned}

and the Minkowski projection $\pi^{Mk}: \mathbb{R}^K \mapsto \mathbb{R}^n$ defined by

\begin{aligned} \pi^{Mk}(\lambda) = \sum_{k=1}^K \lambda_k x_k. \end{aligned}

You can think of the Minkowski representation as expressing each point in the polyhedron in terms of “coordinates” associated with the extreme points/rays.

Note that these coordinates are not unique: each point in the polyhedron may be associated with more than one set of coordinates. For example, consider the bounded triangle in $\mathbb{R}^2$ with coordinates $\begin{pmatrix} 1 \\ 1 \end{pmatrix}$, $\begin{pmatrix} 5 \\ 1 \end{pmatrix}$ and $\begin{pmatrix} 1 \\ 5 \end{pmatrix}$. The point $\begin{pmatrix} 2 \\ 2 \end{pmatrix}$ can be written as

\begin{aligned} \begin{pmatrix} 2 \\ 2 \end{pmatrix} = 2 \begin{pmatrix} 1 \\ 1 \end{pmatrix} + 0 \begin{pmatrix} 5 \\ 1 \end{pmatrix} + 0 \begin{pmatrix} 1 \\ 5 \end{pmatrix}, \end{aligned}

or

\begin{aligned} \begin{pmatrix} 2 \\ 2 \end{pmatrix} = 0 \begin{pmatrix} 1 \\ 1 \end{pmatrix} + \frac{1}{3} \begin{pmatrix} 5 \\ 1 \end{pmatrix} + \frac{1}{3} \begin{pmatrix} 1 \\ 5 \end{pmatrix}. \end{aligned}

References:

1. Nemhauser, G., and Wolsey, L. (1988). Integer and Combinatorial Optimization. (Chapter I.4).
2. Tebboth, J. R. (2001). A Computational Study of Dantzig-Wolfe Decomposition. (Section 3.3).