1. Introduction

The punchline of this blog post is that one can use matroid theory to prove that non-rational polytopes exist. We will unpack exactly what this means, and then see how to prove it.

A polytope is the convex hull of a finite set of points. Perhaps the most fundamental combinatorial data one can associate with a polytope is its face lattice. Given a three-dimensional polytope $ {P}$, this is the partially ordered set consisting of the vertices, edges, and two-dimensional faces of $ {P}$, along with the empty set and $ {P}$ itself, ordered by inclusion. Below, Figure 1 shows a tetrahedron in $\mathbb{R}^3$, with labeled vertices, alongside its face lattice.

Two polytopes are said to be combinatorially equivalent if they have the same face lattice. We begin with the following proposition.

Proposition 1: Given any polytope in $ {\mathbb{R}^3}$, there always exists a combinatorially equivalent polytope with rational vertices.

Proof: Let $ {P \subseteq \mathbb{R}^3}$ be a polytope. The graph $ {G}$ of $ {P}$ is the graph obtained by removing all but the edges and vertices of $ {P}$. We claim that $ {G}$ is planar. Indeed, we can construct a surface $ {S}$ that is homeomorphic to a sphere, that contains all the vertices of $ {G}$. Then, we can stretch the edges of $ {G}$ so that they also lie on $ {S}$ and do not cross each other. Removing a point of $ {S}$ not on this embedding of $ {G}$ gives us an embedding of $ {G}$ into a surface homeomorphic to the plane. This proves that $ {G}$ is planar.

Now take a planar embedding of $ {G}$ with straight edges and rational vertices. Then we can lift the vertices of $ {G}$ to various rational heights so that the vertices in each face of this planar embedding lie on the same plane, and no two faces sharing an edge lie on the same plane. $ \Box$

Proposition 1 does not hold for polytopes in arbitrary dimensions and we will use matroids to see why. We will use the fact that the rank-three matroid shown in Figure 2 below is representable over $\mathbb{R}$ but not $\mathbb{Q}$ to show that a particular eight-dimensional polytope is not combinatorially equivalent to any polytope with rational vertices.

2. A crash course on polytopes

The reader who is comfortable with the definition of faces of a polytope should skip this section.
The convex hull of a set $S \subseteq \mathbb{R}^d$ is the set of points expressible as
\[
{\rm Conv}(S) := \left\{\sum_i t_i x_i : 0 \le t_i \le 1 \ {\rm for \ all \ } i  \ {\rm and } \ \sum_i t_i = 1\right\}.
\]
A V-polytope is a set that is expressible as the convex hull of finitely many points, i.e. a set of the form ${\rm Conv}(\{x_1,\dots,x_n\})$.

Associated to each pair consisting of a nonzero linear functional $f \in (\mathbb{R}^d)^*$ and a real number $c \in \mathbb{R}$, there is a hyperplane $\mathcal{H}_{f,c}$ and two half-spaces $\mathcal{H}_{f,c}^+$ and $\mathcal{H}_{f,c}^-$ defined as
\[
\mathcal{H}_{f,c} := \{x \in \mathbb{R}^d : fx = c\}
\qquad \mathcal{H}_{f,c}^+ := \{x \in \mathbb{R}^d : fx \le c\}
\qquad \mathcal{H}_{f,c}^- := \{x \in \mathbb{R}^d : fx \ge c\}.
\]
An H-polyhedron is an intersection of finitely many half-spaces, and an H-polytope is a bounded $H$-polyhedron. Due to the following theorem, we will no longer make a distinction between H-polytopes and V-polytopes and simply call them polytopes.

Theorem 1: All H-polytopes are V-polytopes and vice versa.

A supporting hyperplane of a polytope $ {P \subseteq \mathbb{R}^d}$ is a hyperplane $ {\mathcal{H}_{f,c}}$ such that $ {P \subset \mathcal{H}_{f,c}^+}$ or $ {P \subset \mathcal{H}_{f,c}^-}$. A face of $ {P}$ is $ {P}$ itself, or a subset $ {F \subseteq P}$ of the form $ {P \cap \mathcal{H}_{f,c}}$ where $ {\mathcal{H}_{f,c}}$ is a supporting hyperplane of $ {P}$. Note that $ {\emptyset}$ is a face of every polytope and that faces of polytopes are polytopes. The vertices of a polytope are the zero-dimensional faces, the edges of a polytope are the one-dimensional faces, and the facets of a $ {d}$-dimensional polytope are the $ {(d-1)}$-dimensional faces. The face lattice $ {\mathcal{F}(P)}$ of a polytope $ {P}$ is the set of faces of $ {P}$, partially ordered by inclusion. It is graded by the function that sends a face to its dimension. Two polytopes $ {P}$ and $ {Q}$ are combinatorially equivalent if $ {\mathcal{F}(P)}$ and $ {\mathcal{F}(Q)}$ are isomorphic as posets.

3. A crash course on oriented matroids

We will state a handful of basic theorems about oriented matroids without proofs, but the reader who wants to dig deeper is invited to consult chapter 6 in Ziegler’s book Lectures on Polytopes. Just as with ordinary (non-oriented) matroids, one can define a combinatorial structure from a matrix, establish properties that this structure will always satisfy, and define an oriented matroid to be the set of combinatorial objects satisfying those properties, giving us realizable and non-realizable oriented matroids. However, this post only requires realizable oriented matroids so we will skip a discussion of axiomatics.

The sign of a real number $ {x}$ will be denoted $ {{\rm sign}(x)}$. Given $ {v \in \mathbb{R}^n}$, we define $ {{\rm sign}(v) \in \{+,-,0\}^n}$ by $ {{\rm sign}(v)_i:={\rm sign}(v_i)}$. The support of some $ {\sigma \in\{+,-,0\}^n}$ is the subset $ {S \subseteq \{1,\dots,n\}}$ such that $ {\sigma_i \neq 0}$ if and only if $ {i \in S}$. Given a matrix $ {A \in \mathbb{R}^{r \times n}}$, the signed vectors of $ {A}$ is the set

$ \displaystyle \{{\rm sign}(v) : Av = 0\} $

and the signed circuits of $ {A}$ are the signed vectors of minimal nonempty support. Given a real matrix $ {A}$, the oriented matroid of $ {A}$, denoted $ {\mathcal{O}(A)}$ is the set of signed circuits of $ {A}$. For any oriented matroid $ {\mathcal{O}}$, the set

$ \displaystyle \left\{ {\rm supp}(\sigma) : \sigma \ {\rm is \ a \ signed \ circuit \ of \ } \mathcal{O} \right\} $

is the circuit set of a matroid, which denote $ {\mathcal{M}(\mathcal{O})}$.

Given sign vectors $ {\sigma,\tau \in \{+,-,0\}^E}$ we say that $ {\sigma}$ and $ {\tau}$ are orthogonal and write $ {\sigma\cdot \tau = 0}$ if either $ {{\rm supp}(\sigma)\cap{\rm supp}(\tau) = 0}$, or if there exist $ {e,f \in {\rm supp}(\sigma) \cap {\rm supp}(\tau)}$ such that $ {\sigma_e = \tau_e}$ and $ {\sigma_f = -\tau_f}$. If $ {x,y \in \mathbb{R}^n}$ are orthogonal (in the inner product space sense of the word) then $ {{\rm sign}(x)}$ and $ {{\rm sign}(y)}$ are orthogonal too. Given an oriented matroid $ {\mathcal{O}=(E,\mathcal{V})}$, the dual oriented matroid $ {\mathcal{O}^*}$ is the oriented matroid whose set of vectors is

$ \displaystyle \{\sigma \in \{+,-,0\}: \sigma \cdot \tau = 0 \ {\rm for \ all} \ \tau \in \mathcal{V}\}. $

The same construction for realizing the dual of a representable (non-oriented) matroid works for realizing dual oriented matroids, as the following theorem states.

Theorem 2:  Let $A \in \mathbb{R}^{r\times n}$ have rank $r$ and let $B \in \mathbb{R}^{(n-r)\times n)}$ have rank $n-r$ and assume $AB^T = 0$. Then $\mathcal{O}(A)^* = \mathcal{O}(B)$.

It immediately follows from Theorem 2 that $ {\mathcal{O}^{**} = \mathcal{O}}$ for any realizable oriented matroid $ {\mathcal{O}}$. As with ordinary matroids, we use the prefix “co” when talking about objects associated dual oriented matroids. In particular, the signed circuits and signed vectors of $ {\mathcal{O}^*}$ are called the signed cocircuits and signed covectors of $ {\mathcal{O}^*}$.

Just as with ordinary matroids, we can represent oriented matroids of rank three pictorially using lines and dots. Let $ {A \in \mathbb{R}^{3\times n}}$. We will think of the columns of $ {A}$ as points in $ {\mathbb{R}^3}$. If none of the columns are zero, we can pick a linear functional $ {f \in (\mathbb{R}^3)^*}$ such that $ {fa \neq 0}$ for each column $ {a}$ of $ {A}$. Then, we associate $ {A}$ with the point configuration

$ \displaystyle \left\{\frac{a}{fa}: a \ {\rm is \ a \ column \ of \ } A\right\} $

and label those for which $ {fa > 0}$ “positive” and those for which $ {fa < 0}$ “negative.” This new point configuration lies in the affine plane $ {\{x \in \mathbb{R}^d: fx = 1\}}$ which we view simply as $ {\mathbb{R}^{2}}$. We then draw this point configuration in $ {\mathbb{R}^2}$, coloring the positive vertices black and the negative ones white. We then draw all the lines that contain three or more points. At this point, if we ignore the distinction between positive and negative points, we have the usual pictorial representation of the (non-oriented) matroid $ {\mathcal{M}(\mathcal{O})}$.

We will use an example to explain how to read the oriented matroid from such a picture. Let $ {A}$ be the following matrix

$ \displaystyle A = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix} $

and denote its columns by $ {a_1,\dots,a_6}$. Let $ {e_1,e_2,e_3}$ be the standard basis of $ {\mathbb{R}^3}$ with dual basis $ {e_1^*, e_2^*,e_3^*}$. Define $ {f := e_1^* + e_2^* – 5e_3^*}$. Then the positive points are $ {a_1,a_2,a_4}$ and the negative points are $ {a_3,a_5,a_6}$. Normalizing by $ {f}$ gives the new point configuration

$ \displaystyle \begin{pmatrix} 1 & \frac{1}{2} & -\frac{1}{3} & 0 & 0 & 0 \\ 0 & \frac{1}{2} & -\frac{1}{3} & 1 & -\frac{1}{4} & 0 \\ 0 & 0 & -\frac{1}{3} & 0 & -\frac{1}{4} & -\frac{1}{5} \end{pmatrix}. $

We drop the third row to get a point configuration in $ {\mathbb{R}^2}$. We now draw this, coloring the positive points black and the negative ones white to get the picture in Figure 3.

We now discuss how to see the signed circuits of $ {\mathcal{O}(A)}$ from this picture. Given disjoint subsets $ {P}$ and $ {N}$ of points whose convex hulls intersect, and are minimal with respect to this property, let $ {\tau}$ be the sign vector that is positive on $ {P}$ and negative on $ {N}$. Let $ {\sigma}$ be obtained from $ {\tau}$ by negating all the negative points. Then $ {\sigma}$ is a signed circuit of $ {\mathcal{O}(A)}$ matroid and all signed circuits of $ {\mathcal{O}(A)}$ are obtained this way. For example, from Figure 3, we can see that e.g.~the following are signed circuits of $ {\mathcal{O}(A)}$

$ \displaystyle (+-0+00) \qquad (+-00+-) \qquad (000+-+). $

We can also read off the signed cocircuits from such a picture. Let $ {L}$ be a line through at least two points and choose one side to be “positive” and the other to be “negative.” Create a sign vector $ {\tau}$ by setting all points on $ {L}$ to zero, all points on the positive side to $ {+}$ and all points on the negative side to $ {-}$. Then define $ {\sigma}$ to be obtained from $ {\tau}$ by negating all entries corresponding to negative points in the picture. Then $ {\sigma}$ is a signed cocircuit of $ {\mathcal{O}}$. This enables us to e.g.~read off the following signed cocircuits from Figure 3

$ \displaystyle (+00–0) \qquad (0++++0) \qquad (0+0+0-). $

4. Gale diagrams of polytopes

Oriented matroids give us a way to construct and visualize polytopes in more than three dimensions, as long as they don’t have too many vertices. The main result of this section will be a construction of an eight-dimensional polytope with twelve vertices that is not combinatorially equivalent to any polytope with rational vertices.

Given an oriented matroid $ {\mathcal{O}}$ and an ordered field $ {\mathbb{F}}$ (we will only consider $ {\mathbb{R}}$ and $ {\mathbb{Q}}$), we say that $ {\mathcal{O}}$ is $ {\mathbb{F}}$-realizable if there exists a matrix $ {A \in \mathbb{F}^{d \times n}}$ such that $ {\mathcal{O} = \mathcal{O}(A)}$.

Let $ {P \subseteq \mathbb{R}^d}$ be a $ {d}$-dimensional polytope with vertex set $ {\{v_1,\dots,v_n\}}$. The oriented matroid of $ {P}$, denoted $ {\mathcal{O}(P)}$, is $ {(\mathcal{O}(A))^*}$ where $ {A \in \mathbb{R}^{(d+1) \times n}}$ is defined as follows

$ \displaystyle A := \begin{pmatrix} 1 & 1 & \dots & 1 \\ v_1 & v_2 & \dots & v_n \end{pmatrix}. $

We construct our non-rational polytope by first constructing its oriented matroid. For this reason, we need to know exactly which oriented matroids actually arise as $ {\mathcal{O}(P)}$ for some polytope $ {P}$. Fortunately, such oriented matroids have a simple characterization as follows.

Theorem 3: Let $ {\mathcal{O}}$ be an $ {\mathbb{R}}$-representable oriented matroid on $ {n}$ elements. Then there exists a polytope $ {P}$, with $ {n}$ vertices, such that $ {\mathcal{O} = \mathcal{O}(P)}$ if and only if every cocircuit of $ {\mathcal{O}}$ has at least two positive elements. In this case, the dimension of $ {P}$ is $ {r-1}$ where $ {r}$ is the rank of $ {\mathcal{M}(\mathcal{O})}$.

Proposition 2: Let $ {P,Q \subseteq \mathbb{R}^d}$ be polytopes of dimension $ {d}$. If $ {P}$ and $ {Q}$ are combinatorially equivalent, then $ {\mathcal{O}(P)}$ and $ {\mathcal{O}(Q)}$ have the same positive cocircuits.

The converse of Proposition 3 is false. In other words, two combinatorially equivalent polytopes may have Gale diagrams with different positive cocircuits. Indeed, consider the family $ {\{A_\varepsilon\}_{0 \le \varepsilon \le 1}}$ of matrices defined below

$ \displaystyle A_\varepsilon := \begin{pmatrix} 1 & -1 & 0 & 0 \\ \varepsilon & 0 & 1 & -1 \end{pmatrix} $ The polytope obtained by taking the convex hull of the columns of $ {A_\varepsilon}$ will be denoted $ {P_\varepsilon}$. Every polytope $ {P_\varepsilon}$ is a four-gon. In particular, they are combinatorially equivalent. However, $ {(++00)}$ is a cocircuit of the gale diagram of $ {P_\varepsilon}$ if and only if $ {\varepsilon = 0}$.

Theorem 4:  Let $\mathcal{O}$ be as in Figure 4. Then:

1. $\mathcal{O}$ is the Gale diagram of an $8$-dimensional polytope $P$,
   
2. any $\mathbb{R}$-representable oriented matroid $\hat{\mathcal{O}}$ of rank $3$ with the same positive circuits as $\mathcal{O}$ has $\mathcal{M}(\hat{\mathcal{O}}) = \mathcal{M}(\mathcal{O})$, and
   
3. any polytope combinatorially equivalent to $P$ has a non-rational vertex.
   

Proof: Theorem 3 implies the first claim once we verify that every cocircuit of $ {\mathcal{O}}$ has at least two positive elements. This can be done by checking the lines in Figure 4. For the second claim, let $ {\mathcal{O}’}$ be an oriented matroid with the same positive circuits as $ {\mathcal{O}}$ and let $ {B}$ be a matrix such that $ {\mathcal{O}(B) = \mathcal{O}’}$. Then $ {\mathcal{M}(\mathcal{O}’)}$ has no rank-zero flats aside from the empty set. The rank-one flats of $ {\mathcal{M}(\mathcal{O}’)}$ are precisely those of $ {\mathcal{M}(\mathcal{O})}$ (in particular note that those with two elements are $ {\{6,9\},\{7,10\},\{8,11\}}$ since these are the only two-element positive circuits). The following are all positive circuits of $ {\mathcal{O}}$ and therefore of $ {\mathcal{O}’}$

$ \displaystyle \begin{array}{ c c c c c} 1,2,9 & 1,8,12 & 1,4,10 & 2,5,9 & 2,7,12 \cr 2,3,11 & 3,5,10 & 3,6,12 & 4,5,12 & 4,6,11. \end{array} $

This implies that all rank-two flats of $ {\mathcal{M}(\mathcal{O})}$ with three or more elements also have rank two in $ {\mathcal{M}(\mathcal{O})}$. Since $ {B}$ has rank three, its only rank-three flat is the whole ground set. Thus $ {\mathcal{M}(\mathcal{O}) = \mathcal{M}(\mathcal{O}’)}$ since they have the same lattice of flats, the same parallel elements, and no loops. Since $ {\mathcal{M}(\mathcal{O}’)\setminus \{9,10,11\}}$ is matroid given in Figure~2, $ {\mathcal{M}(\mathcal{O})}$, and therefore $ {\mathcal{O}}$, is not $ {\mathbb{Q}}$-representable. Therefore neither is $ {\mathcal{O}’}$. Thus the second claim is proven.

Now let $ {P’}$ be a polytope that is combinatorially equivalent to $ {P}$. Proposition 2 and the second claim imply that the oriented matroid of any Gale diagram of $ {P’}$ is not $ {\mathbb{Q}}$-representable. In particular, if the columns of $ {A}$ are the vertices of $ {P’}$ and $ {B}$ is a Gale diagram of $ {P’}$, then $ {AB^T = 0}$ and therefore $ {A}$ has an irrational entry. Thus $ {P}$ is not combinatorially equivalent to any polytope with rational vertices. $ \Box$