Zonotope

A zonotope is a convex polytope that can described as the Minkowski sum of a finite set of line segments in ${\mathbb{ℝ}}^d$ or, equivalently as a projection of a hypercube. Zonotopes are intimately connected to hyperplane arrangements and matroid theory.

Definition and basic properties

The Minkowski sum of a finite set of line segments in ${\mathbb{ℝ}}^d$ forms a type of convex polytope called a zonotope. More precisely, a zonotope $Z$ generated by the vectors $w_1,...,w_n\in {\mathbb{ℝ}}^d$ is a translation of

$$Z=\{a_1{w}_1+\cdots +a_n{w}_n|0\le a_j\le 1\text{ for all }j\}=\mathbf{𝐖}[0,1{]}^n,$$

where $\mathbf{𝐖}$ is the $d\times n$ matrix whose j'th column is $w_j$. The latter description makes it clear that a zonotope is precisely the translation of a projection of an n-dimensional cube.

In the special case where $w_1,...,w_n\in {\mathbb{ℝ}}^d$ are linearly independent, the zonotope $Z$ is a (possibly lower-dimensional) parallelotope.

The facets of any zonotope are themselves zonotopes of one lower dimension. Examples of four-dimensional zonotopes include the tesseract (Minkowski sums of mutually perpendicular equal length line segments), the omnitruncated 5-cell, and the truncated 24-cell. Every permutohedron is a zonotope.

Zonotopes and matroids

Fix a zonotope $Z$ generated by the vectors $w_1,\dots ,w_n\in {\mathbb{ℝ}}^d$ and let $\mathbf{𝐖}$ be the $d\times n$ matrix whose columns are the $w_i$. Then the vector matroid ${ℳ}$ on the columns of $\mathbf{𝐖}$ encodes a wealth of information about $Z$, that is, many properties of $Z$ are purely combinatorial in nature.

For example, pairs of opposite facets of $Z$ are naturally indexed by the cocircuits of ${ℳ}$ and if we consider the oriented matroid ${ℳ}$ represented by $\mathbf{𝐖}$, then we obtain a bijection between facets of $Z$ and signed cocircuits of ${ℳ}$ which extends to a poset anti-isomorphism between the face lattice of $Z$ and the covectors of ${ℳ}$ ordered by component-wise extension of $0\prec +,-$. In particular, if $M$ and $N$ are two matrices that differ by a projective transformation then their respective zonotopes are combinatorially equivalent. The converse of the previous statement does not hold: the segment $[0,2]\subset \mathbb{ℝ}$ is a zonotope and is generated by both $\{2{\mathbf{𝐞}}_1\}$ and by $\{{\mathbf{𝐞}}_1,{\mathbf{𝐞}}_1\}$ whose corresponding matrices, $[2]$ and $[11]$, do not differ by a projective transformation.

Tilings

Tiling properties of the zonotope $Z$ are also closely related to the oriented matroid ${ℳ}$ associated to it. First we consider the space-tiling property. The zonotope $Z$ is said to tile ${\mathbb{ℝ}}^d$ if there is a set of vectors $\mathrm{\Lambda }\subset {\mathbb{ℝ}}^d$ such that the union of all translates $Z+\lambda$ ($\lambda \in \mathrm{\Lambda }$) is ${\mathbb{ℝ}}^d$ and any two translates intersect in a (possibly empty) face of each. Such a zonotope is called a space-tiling zonotope. The following classification of space-tiling zonotopes is due to McMullen: The zonotope $Z$ generated by the vectors $V$ tiles space if and only if the corresponding oriented matroid is regular. So the seemingly geometric condition of being a space-tiling zonotope actually depends only on the combinatorial structure of the generating vectors.

Dissections

Every d-dimensional zonotope generated by a finite set A of vectors can be partitioned into parallelepipeds, with one parallelepiped for each linearly independent subset of A. This yields another family of tilings associated to the zonotope $Z$, given by a zonotopal tiling of $Z$, i.e., a polyhedral complex with support $Z$: the union of all zonotopes in the collection is $Z$ and any two intersect in a common (possibly empty) face of each. The Bohne-Dress Theorem states that there is a bijection between zonotopal tilings of the zonotope $Z$ and single-element lifts of the oriented matroid ${ℳ}$ associated to $Z$.

Volume

Zonotopes admit a simple analytic formula for their volume.

Let $Z(S)$ be the zonotope $Z=\{a_1{w}_1+\cdots +a_n{w}_n|\mathrm{\forall }(j)a_j\in [0,1]\}$ generated by a set of vectors $S=\{w_1,\dots ,w_n\in {\mathbb{ℝ}}^d\}$. Then the d-dimensional volume of $Z(S)$ is given by

$\sum _{T\subset S:|T|=d}|\det (Z(T))|$

The determinant in this formula makes sense because (as noted above) when the set $T$ has cardinality equal to the dimension $n$ of the ambient space, the zonotope is a parallelotope.