Zonotope

A zonotope is a convex polytope that can described as the Minkowski sum of a finite set of line segments in ${\displaystyle \mathbb {R} ^{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 ${\displaystyle \mathbb {R} ^{d}}$ forms a type of convex polytope called a zonotope. More precisely, a zonotope ${\displaystyle Z}$ generated by the vectors ${\displaystyle w_{1},...,w_{n}\in \mathbb {R} ^{d}}$ is a translation of

$${\displaystyle Z=\{a_{1}w_{1}+\cdots +a_{n}w_{n}|\;0\leq a_{j}\leq 1{\text{ for all }}j\}=\mathbf {W} \,[0,1]^{n},}$$

where ${\displaystyle \mathbf {W} }$ is the ${\displaystyle d\times n}$ matrix whose j'th column is ${\displaystyle 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 ${\displaystyle w_{1},...,w_{n}\in \mathbb {R} ^{d}}$ are linearly independent, the zonotope ${\displaystyle 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 ${\displaystyle Z}$ generated by the vectors ${\displaystyle w_{1},\dots ,w_{n}\in \mathbb {R} ^{d}}$ and let ${\displaystyle \mathbf {W} }$ be the ${\displaystyle d\times n}$ matrix whose columns are the ${\displaystyle w_{i}}$. Then the vector matroid ${\displaystyle {\mathcal {M}}}$ on the columns of ${\displaystyle \mathbf {W} }$ encodes a wealth of information about ${\displaystyle Z}$, that is, many properties of ${\displaystyle Z}$ are purely combinatorial in nature.

For example, pairs of opposite facets of ${\displaystyle Z}$ are naturally indexed by the cocircuits of ${\displaystyle {\mathcal {M}}}$ and if we consider the oriented matroid ${\displaystyle {\mathcal {M}}}$ represented by ${\displaystyle \mathbf {W} }$, then we obtain a bijection between facets of ${\displaystyle Z}$ and signed cocircuits of ${\displaystyle {\mathcal {M}}}$ which extends to a poset anti-isomorphism between the face lattice of ${\displaystyle Z}$ and the covectors of ${\displaystyle {\mathcal {M}}}$ ordered by component-wise extension of ${\displaystyle 0\prec +,-}$. In particular, if ${\displaystyle M}$ and ${\displaystyle 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 ${\displaystyle [0,2]\subset \mathbb {R} }$ is a zonotope and is generated by both ${\displaystyle \{2\mathbf {e} _{1}\}}$ and by ${\displaystyle \{\mathbf {e} _{1},\mathbf {e} _{1}\}}$ whose corresponding matrices, ${\displaystyle [2]}$ and ${\displaystyle [1~1]}$, do not differ by a projective transformation.

Tilings

Tiling properties of the zonotope ${\displaystyle Z}$ are also closely related to the oriented matroid ${\displaystyle {\mathcal {M}}}$ associated to it. First we consider the space-tiling property. The zonotope ${\displaystyle Z}$ is said to tile${\displaystyle \mathbb {R} ^{d}}$ if there is a set of vectors ${\displaystyle \Lambda \subset \mathbb {R} ^{d}}$ such that the union of all translates ${\displaystyle Z+\lambda }$ (${\displaystyle \lambda \in \Lambda }$) is ${\displaystyle \mathbb {R} ^{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: ^[1] The zonotope ${\displaystyle Z}$ generated by the vectors ${\displaystyle 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. ^[2] This yields another family of tilings associated to the zonotope ${\displaystyle Z}$, given by a zonotopal tiling of ${\displaystyle Z}$, i.e., a polyhedral complex with support ${\displaystyle Z}$: the union of all zonotopes in the collection is ${\displaystyle 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 ${\displaystyle Z}$ and single-element lifts of the oriented matroid ${\displaystyle {\mathcal {M}}}$ associated to ${\displaystyle Z}$. ^{[3] [4]}

Volume

Zonotopes admit a simple analytic formula for their volume. ^[5]

Let ${\displaystyle Z(S)}$ be the zonotope ${\displaystyle Z=\{a_{1}w_{1}+\cdots +a_{n}w_{n}|\;\forall (j)a_{j}\in [0,1]\}}$ generated by a set of vectors ${\displaystyle S=\{w_{1},\dots ,w_{n}\in \mathbb {R} ^{d}\}}$. Then the d-dimensional volume of ${\displaystyle Z(S)}$ is given by

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

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

1. McMullen, Peter (1975). "Space tiling zonotopes". Mathematika . 22 (2): 202–211. doi:10.1112/S0025579300006082.
2. Coxeter, H.S.M. (1948). Regular Polytopes (3rd ed.). Methuen. p. 258.
3. J. Bohne, Eine kombinatorische Analyse zonotopaler Raumaufteilungen, Dissertation, Bielefeld 1992; Preprint 92-041, SFB 343, Universität Bielefeld 1992, 100 pages.
4. Richter-Gebert, J., & Ziegler, G. M. (1994). Zonotopal tilings and the Bohne-Dress theorem. Contemporary Mathematics, 178, 211-211.
5. McMullen, Peter (1984-05-01). "Volumes of Projections of unit Cubes" . Bulletin of the London Mathematical Society. 16 (3): 278–280. doi:10.1112/blms/16.3.278. ISSN   0024-6093.