Algebraic matroids

Anyone who has studied matroid theory has seen graphic and linear matroids, and probably has a decent intuition for how the concepts in matroid theory relate to graph theory and linear algebra. Algebraic matroids are far less popular and many fundamental questions about them remain unanswered. The goal of this blog post is to introduce algebraic matroids, and give the reader a sense of where the subtlety lies when trying to understand them.

The definition

Let $\mathbb{F} \subseteq \mathbb{K}$ be fields. Let $E$ be a finite subset of $\mathbb{K}$ and let $\{Y_e: e \in E\}$ be a set of indeterminates indexed by $E$. A subset $S \subseteq E$ is algebraically independent over $\mathbb{F}$ if whenever $F \in \mathbb{F}[Y_e: e \in E]$ is a polynomial that only includes the variables $\{x_e : e \in S\}$, then $F$ vanishes when plugging in $e$ for $Y_e$ if and only if $F$ is identically zero. The subsets of $E$ that are algebraically independent over $\mathbb{F}$ are the independent subsets of a matroid, called the algebraic matroid of $E$. A matroid $M$ that can be realized in this way is said to be algebraic over $\mathbb{F}$.

An example and a theorem

Let $\mathbb{F}$ be any field and define $\mathbb{K} := \mathbb{F}(x,y,z,w)$, the field of rational functions in four variables over $\mathbb{F}$. Then define

$E := \{xy^{-1},xz^{-1},xw^{-1},yz^{-1},yw^{-1},zw^{-1}\} \subseteq \mathbb{F}(x,y,z,w)$

The subset $I = \{xw^{-1},yw^{-1},zw^{-1}\}$ is algebraically independent over $\mathbb{F}$, whereas $xy^{-1},yz^{-1},xz^{-1}$ is not because if

$F(Y_{xy^{-1}},Y_{,xz^{-1}},Y_{xw^{-1}},Y_{yz^{-1}},Y_{yw^{-1}},Y_{zw^{-1}}) := Y_{xy^{-1}}Y_{yz^{-1}}-Y_{xz^{-1}}$

then $F(xy^{-1},,xz^{-1},xw^{-1},yz^{-1},yw^{-1},zw^{-1})= 0$.

The algebraic matroid of $E$ is the $\mathbb{Q}$-representable matroid defined by the following matrix over $\mathbb{Q}$

$A:=\begin{pmatrix} 1 & 1 & 1 & 0 & 0 & 0 \\ -1 & 0 & 0 & 1 & 1 & 0 \\ 0 & -1 & 0 & -1 & 0 & 1 \\ 0 &0 & -1 & 0 & -1 & -1\end{pmatrix}$.

To see this, let $v \in \mathbb{Z}^6$ be such that $Av = 0$ and define

$v^+ = \left({\rm max}\{v_i,0\}\right)$     and     $v^- = \left({\rm max}\{-v_i,0\}\right)$

so that $v = v^+-v^-$ and $v^+$ and $v^-$ are nonnegative with disjoint supports. Then the binomial

$Y_1^{v_1^+}Y_2^{v_2^+}Y_3^{v_3^+}Y_4^{v_4^+}Y_5^{v_5^+}Y_6^{v_6^+} \  – \  Y_1^{v_1^-}Y_2^{v_2^-}Y_3^{v_3^-}Y_4^{v_4^-}Y_5^{v_5^-}Y_6^{v_6^-}$

vanishes by plugging in $(Y_1,\dots,Y_6) = (xy^{-1},\dots,zw^{-1})$. For example, if $v = (1,-1,0,1,0,0)$ then $v^+ = (1,0,0,1,0,0)$ and $v^- = (0,1,0,0,0,0)$ and the corresponding binomial is $Y_1Y_4-Y_2$.

This procedure gives us a map $\phi$ from the set of integer vectors in the kernel of $A$ to the set of irreducible binomial differences that vanish on $E$. In fact, this map $\phi$ is a bijection and any irreducible polynomial relation among the elements of $E$ will be an irreducible binomial difference and so $\phi$ can be used to show that dependent sets in the algebraic matroid of $E$ correspond to dependent sets in the column matroid of $A$.

The above example generalizes. In particular, if $E \subseteq \mathbb{F}(x_1,\dots,x_r)$ is a set of monomials, then the algebraic matroid of $E$ is isomorphic to the algebraic matroid of the rational matrix $A$ whose column vectors are the exponent vectors of $E$. Since $\mathbb{F}$ was an arbitrary field, this proves the following.

Theorem. If $M$ is representable over $\mathbb{Q}$, then $M$ is algebraic over every field.

The converse of the above statement is false – the non-Pappus matroid is algebraic over every field, but not representable over $\mathbb{Q}$.

Relationship with linear matroids

Every matroid that is linear over a field $\mathbb{F}$ is algebraic over that same field. In particular, the matroid of some $A \in \mathbb{F}^{r \times n}$ is the algebraic matroid of the entries of

$(x_1 \ \cdots \ x_r) A$

as elements of $\mathbb{F}(x_1,\dots,x_r)$. So every $\mathbb{F}$-linear matroid is also $\mathbb{F}$-algebraic. When $\mathbb{F}$ has characteristic zero, the converse is almost true. Namely, we have the following.

Theorem. Let $\mathbb{F}$ be a field of characteristic zero, let $\mathbb{K}$ be a field containing $\mathbb{F}$ and let $E$ be a finite subset of $\mathbb{K}$. Then the algebraic matroid of $E$ is linearly representable over $\mathbb{F}(t_1,\dots,t_r)$ where each $t_i$ is an indeterminate.

Here is a proof sketch for the special case where $\mathbb{K} = \mathbb{F}(t_1,\dots,t_r)$ where each $t_i$ is an indeterminate. Let $M$ denote the algebraic matroid of $E$. For each $e \in E$, let $v_e \in \mathbb{F}(t_1,\dots,t_r)$ be the formal gradient vector of $e$ (note that each $e$ is a polynomial in the $t_i$ variables). Then $\{v_e\}_{e \in E}$ is an $\mathbb{F}(t_1,\dots,t_r)$-linear representation of $M$. Indeed, if there is a polynomial relation among some subset $S \subseteq E$, then the gradient of that polynomial relation is a linear relation among $\{v_e : e \in S\}$. Conversely, each linear relation among a subset of $\{v_e: e \in E\}$ can be made into a polynomial relations among the corresponding subset of $E$.

The general case is proven using essentially the same idea, i.e. take derivatives to reduce to the linear case. Doing this without making assumptions on $\mathbb{K}$ requires the theory of derivations from commutative algebra

What fails in positive characteristic is that not every linear relation among the gradient vectors lifts to an algebraic relation among the corresponding polynomials. Consider for example the following set of monomials in $\mathbb{F}_2(x,y,z)$

$E := \{x,y,z,xy,xz,yz,xyz\} \subset \mathbb{F}_2(x,y,z)$

The corresponding matrix of exponent vectors is the following

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

Since $A$ lives in $\mathbb{Q}^{3 \times 7}$, its matroid is the non-Fano matroid, and since this matroid is isomorphic to the algebraic matroid of $E$, this gives us an $\mathbb{F}_2$-algebraic representation of the non-Fano matroid. Since this is not representable over $\mathbb{F}_2$, we know that the above proof sketch should fail on this example. And it does. The matrix of gradient vectors for $E$, which lives in $\mathbb{F}_2(x,y,z)^{3 \times 7}$, is the following

$Gr = \begin{pmatrix} 1 & 0 & 0 & y & z & 0 & yz \\ 0 & 1 & 0 & x & 0 &z & xz \\ 0 & 0 & 1 & 0 & x & y & xy\end{pmatrix}$

The 3rd, 4th, and 5th columns are the gradients of $xy,xz$, and $yz$. Since this matrix has entries in a field of characteristic two, this 3×3 matrix has zero determinant. But $\{xy,xz,yz\}$ is an algebraically independent subset of $E$. To see this, look at the corresponding columns of the exponent vector matrix $A$:

$\begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix}$.

The determinant of this matrix (which has entries in $\mathbb{Q}$, not $\mathbb{F}_2$) is $-2$, which is non zero in this field.

The big open question

It is unknown if the dual of an algebraic matroid is algebraic. I see no reason for this to be the case, and I think we lack a counterexample showing this for two reasons. The first is that any such counterexample would have to be algebraic but non-linear. Over characteristic zero, the class of algebraic and linear matroids are the same, so this counterexample would have to come from a field of positive characteristic, where geometric interpretations of the algebraic picture are often misleading. The second reason is a lack of ways to certify that a matroid is not algebraic – the methods from the literature are specific to the examples they work on.

One example of a matroid that is algebraic but not linear is the algebraic matroid of the following subset of $\mathbb{F}_2(x,y,z)$

$E := \{x,y,z,x+y,x+z,y+z,x+y+z,xy,xz,yz,xyz\}$.

The matroid on the subset $\{x,y,z,x+y,x+z,y+z,x+y+z\}$ is the Fano matroid (which is only linear over characteristic 2) and the matroid on $\{x,y,z,xy,xz,yz,xyz\}$ is the non-Fano matroid (which is only representable over characteristics other than 2). So this matroid cannot be linear. I conjecture, perhaps a little too boldly, that the dual of this matroid is not algebraic.


Since publishing this blog post, Winfried Hochstättler reached out to me to share an example of a matroid of rank five on nine elements whose dual is known to be non-algebraic. It is unknown whether the matroid itself is algebraic. Click here to download a pdf describing this matroid.

Matroid representability and non-rational polytopes

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.

Figure 1: A tetrahedron, 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.

Figure 2: A matroid that is realizable over the reals, but not the rationals.

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\}.
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.

Figure 3: Two-dimensional picture of a rank-three oriented matroid

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}$.

Figure 4: The Gale diagram of an eight-dimensional polytope with twelve vertices that has a non-rational vertex

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$