In this post I’m going to conclude my investigation of Coxeter matroids and related objects.

We can motivate the definition of Coxeter matroids by thinking about a geometrical problem in the Euclidean space $\mathbb{R}^{n}$. Recall that a (closed) half-space is a set of the form $\{\mathbf{v}\in \mathbb{R}^{n}\colon
\mathbf{v}\cdot \mathbf{a}\geq b\}$, where $\mathbf{a}$ is a fixed (non-zero) vector, $b$ is a real number, and the dot denotes the standard inner product. A polyhedron is an intersection of finitely many half-spaces. A polyhedron is a polytope if it is bounded, meaning that there there must be some ball of finite radius centred on the origin that contains every point of the polytope. A vertex of a polyhedron is a point $\mathbf{p}$ in the polyhedron with the property that some affine hyperplane intersects the polyhedron exactly in $\mathbf{p}$. Similarly, an edge of a polyhedron is a line segment, $l$, such that some affine hyperplane intersects the polyhedron exactly in $l$. The terminal points of an edge are always vertices of the polytope.

Now let $P$ be a polytope. For every edge $l$ of $P$, there is an affine hyperplane that is perpendicular to $l$ and that passes through the mid-point of $l$. This affine hyperplane determines an isometry (a distance-preserving transformation) of $\mathbb{R}^{n}$: namely, reflection through the hyperplane.

What can we say about the group of isometries generated by these reflections? As the composition of any reflection with itself is the identity, this group is a Coxeter group, since the definition of such a group is that it must have a set of generators each of which has order two. When will this Coxeter group be finite? It is easy to find examples of polytopes that lead to finite Coxeter groups: just take any regular polygon. In this case the reflections generate the dihedral group. On the other hand, consider the points with polar coordinates $(0,0)$, $(1,-\alpha)$, $(1,\alpha)$, and $(1,3\alpha)$, where $\alpha$ is an irrational fraction of a full rotation. The intersection of all half-spaces that contain these four points is a polytope. The reflections corresponding to the edges of the polytope include the reflection in the horizontal axis, and also the reflection in the line with an angle of $2\alpha$ from the horizontal. Between them, these reflections generate a rotation of $4\alpha$ around the origin. The way that we chose $\alpha$ means that no finite power of this rotation will ever be equal to the identity isometry. Therefore the generated Coxeter group is infinite. The definition of Coxeter matroids is motivated by a partial solution of this problem of determining whether this generated group of isometries will be finite or infinite.

We have said that any regular polygon gives rise to a finite Coxeter group of isometries.
Let us now develop another method for finding such polytopes. Let $W$ be a finite group of isometries of $\mathbb{R}^{n}$ and assume that $W$ is generated by a collection of reflections. We will show that there is a point that is fixed by every isometry in $W$. Indeed, if $\mathbf{v}\in \mathbb{R}^{n}$ is arbitrarily chosen, then the barycentre of the images of $\mathbf{v}$ is fixed by every isometry in $W$, because
\[
u\left(\frac{1}{|W|}\sum_{w\in W}w(\mathbf{v})\right)
= \frac{1}{|W|}\sum_{w\in W}u(w(\mathbf{v}))
= \frac{1}{|W|}\sum_{w\in W}w(\mathbf{v})
\]
for every $u\in W$. Therefore, by translating, we might as well assume that the reflections that generate $W$ all fix the origin. For each reflection $r\in W$, choose two vectors, $\mathbf{v}_{r}$ and $-\mathbf{v}_{r}$ that are orthogonal to the $r$-invariant hyperplane. Thus $r(\pm\mathbf{v}_{r})=\mp\mathbf{v}_{r}$. We shall call the collection $R=\{\pm \mathbf{v}_{r}\colon r\ \text{is a reflection in}\ W\}$ a root system of $W$. Note that the vectors in $R$ correspond in a natural way to the reflections in $W$. We have given no consideration to the length of the vectors $\mathbf{v}_{r}$, which means that we are not using the standard definition of a root system. This diagram shows a possible root system in $2$ dimensions.

Now let $\mathbf{a}$ be a fixed and arbitrary vector, and let $R^{+}=\{\mathbf{u}\in R\colon \mathbf{u}\cdot\mathbf{a}>0\}$ be the set of positive roots. The positive roots generate the positive cone, consisting of all linear combinations of vectors in $R^{+}$ with all coefficients non-negative. This positive cone is a polyhedron. Those vectors in $R^{+}$ that are parallel with an edge of the positive cone form a simple system of roots. In the following diagram, we have chosen $\mathbf{a}$ to be the vector $(1,0)$. There are three positive roots, and they generate the shaded positive cone. The two vectors coloured red form the corresponding simple system.

Let $I$ be the simple system of roots, and let $J$ be a non-empty subset of $I$. The roots in $J$ correspond to a collection of reflections in $W$. Let $P$ be the subgroup of $W$ generated by these reflections. This subgroup is called a standard parabolic subgroup of $W$. In our example, let $P$ be the subgroup generated by the reflection along the line parallel to $(1,1)$, that is, the reflection corresponding to the blue vector in the diagram below. Let $\mathcal{M}$ be a collection of cosets of $P$. In our example, we will keep things simple, and just let $\mathcal{M}$ be the collection of all cosets. We choose a point $\mathbf{v}$ that is fixed by $P$. For every coset $wP$ in $\mathcal{M}$, we find the image of $\mathbf{v}$ under $w$. Note that this image is well-defined, in the sense that it does not depend on the representative $w$, since $\mathbf{v}$ will be fixed by every isometry in $P$. Now we have generated a collection of images of $\mathbf{v}$. We construct the convex hull of these images: that is, we take the polytope consisting of the intersection of all half-spaces that contain the images of $\mathbf{v}$. It turns out that the Coxeter group generated by the edges of this polytope is finite (a subgroup of $W$ in fact). In the diagram below, the vector $\mathbf{v}$ is marked. There are four images of $\mathbf{v}$ under cosets of $P$, and the convex hull of those images is the shaded square.

What is surprising about this construction, is that every polytope generating a finite Coxeter group can essentially be constructed in this way. This is a consequence of a theorem due to Gelfand and Serganova (details are in the book Coxeter matroids).
So far, the link to matroids is not at all obvious, so I will conclude by drawing a connection back to my first post. Let $w_{1},\ldots, w_{t}$ be the reflections in $W$ that correspond to the vectors in a simple root system. Then $W$ is generated by $w_{1},\ldots, w_{t}$, so every $u\in W$ can be expressed as a word in these reflections. Such a word is said to be reduced if it is as short as possible. Now for $u,v\in W$ we say that $v\leq u$ in the Bruhat ordering if there is a reduced word that represents $u$, with the property that I can obtain a word representing $v$ by deleting some characters. If $w\in W$, then we write $v\leq^{w} u$ to mean $w^{-1}v\leq w^{-1}u$. If $A$ and $B$ are cosets, then $A\leq^{w} B$ means that $v\leq^{w} u$ for some representatives $v\in A$ and $u\in B$. The connection to matroids comes from the collection $\mathcal{M}$ of cosets. In our construction, $\mathcal{M}$ has the following property: if $w$ is any reflection in $W$, then there is a coset $B\in \mathcal{M}$ with the property that $A\leq^{w} B$ for all $A\in \mathcal{M}$. Now the resemblance to matroids, as axiomatised via Gale’s Theorem, is quite striking. The cosets in $\mathcal{M}$ play the role of bases in Gale’s Theorem. Now we can finally give the definition of a Coxeter matroid, which is justified by this resemblance to Gale’s axiomatization. If $W$ is a Coxeter group with $P$ as a parabolic subgroup, and $\mathcal{M}$ is a collection of cosets, then $\mathcal{M}$ is a Coxeter matroid if, for every $w\in W$, there is a coset $B\in \mathcal{M}$ such that $A\leq^{w} B$ for all $A\in \mathcal{M}$.

This post continues the discussion from my last post. I’m going to continue using the same notation: in particular, if $w$ is a permutation on the set $[n]=\{1,\ldots, n\}$, and $k\in \{0,\ldots, n\}$, then $\leq^{w}$ is a partial order on the $k$-element subsets of $[n]$. Gale’s Theorem states that if $\mathcal{B}$ is a collection of $k$-element subsets of $[n]$, then $\mathcal{B}$ is the collection of bases of a matroid if and only if, for every permutation, $w$, of $[n]$, there exists a subset $B\in\mathcal{B}$ such that $A\leq^{w} B$ for every $A\in \mathcal{B}$.

Symplectic matroids

Symplectic matroids can be seen as a generalization of ordinary matroids obtained by removing the full symmetric group that implicitly appears in Gale’s Theorem, and replacing it with another group, namely the hyperoctahedral group, $BC_{n}$. This group consists of permutations of the set $\{-n,-(n-1),\ldots,-1,1,\ldots,n-1,n\}$. Let $J$ denote this set. The permutation $w$ belongs $BC_{n}$ if and only if $w(-i)=-w(i)$, for every $i \in J$. We can see $BC_{n}$ as the group of symmetries of the hypercube in $\mathbb{R}^{n}$. The hypercube is the set of vectors $\mathbf{v}\in\mathbb{R}^{n}$ where every entry of $\mathbf{v}$ lies in the interval $[-1,1]$. The vertices of the hypercube are the vectors having every entry equal to $1$ or $-1$. Thus, for every $i\in\{1,\ldots, n\}$, $BC_{n}$ contains the reflection through the hyperplane consisting of all vectors with the $i$th entry equal to zero. We may also apply an arbitrary permutation of the entries. In fact, permutations of these two types generate the entire hyperoctahedral group. You might recognise that this means that $BC_{n}$ is the wreath product of the full symmetric group $\mathrm{Sym}(n)$ and the group of order two, $\mathrm{Sym}(2)$.

With the group definition out of the way, let’s define symplectic matroids. A subset of $J=\{-n,-(n-1),\ldots,-1,1,\ldots,n-1,n\}$ is admissible if it does not contain $\{i,-i\}$ for any $i\in \{1,\ldots,n\}$. If $A$ and $B$ are admissible $k$-element subsets, and $w\in BC_{n}$, then we write $A\leq^{w} B$ if, for every $i$, the $i$th element of $A$ appears no later than the $i$th element of $B$ in the sequence $w(-n),\ldots, w(-1),w(1),\ldots,w(n)$. Let $\mathcal{B}$ be a collection of admissible $k$-element subsets of $J$. If, for every permutation $w\in BC_{n}$, there is a subset $B\in\mathcal{B}$ such that $A\leq^{w}B$ for every $A\in \mathcal{B}$, then we call the set system $(J,\mathcal{B})$ a symplectic matroid.

Example 1. This example comes from an exercise in the book Coxeter Matroids. Let $\mathcal{B}$ be a family of bases of an ordinary matroid on the ground set $[n]$. If we consider $\mathcal{B}$ as a family of subsets of $J=\{-n,\ldots,1,1,\ldots, n\}$, then $(J,\mathcal{B})$ is a symplectic matroid. To see this, let $w$ be an arbitrary permutation in $BC_{n}$. Let $a_{1},\ldots, a_{s}$ be the members of $[n]$ that are fixed by $w$, and let $b_{1},\ldots, b_{t}$ be the members that are taken to their negation, where $a_{1} < a_{2} < \cdots < a_{s}$ and $b_{1}< b_{2} <\cdots < b_{t}$. Now let $w'$ be the permutation of $[n]$ that takes $1,\ldots, n$ to $b_{t},b_{t-1},\ldots, b_{1},a_{1},a_{2},\ldots, a_{s}$. By Gale's Theorem, there is a subset $B\in \mathcal{B}$ such that $A\leq^{w'} B$ for all $A\in \mathcal{B}$. It is not difficult to see that $A\leq^{w} B$ for all $A\in \mathcal{B}$, so $(J,\mathcal{B})$ is a symplectic matroid, as claimed. Example 2. Let $\mathcal{B}$ be the collection of bases of a matroid on the ground set $\{1,\ldots, n\}$. Add the elements $\{-n,\ldots, -1\}$ to this matroid in such a way that $-i$ is either a loop, or parallel to $i$, for every $i$. Let’s say that the resulting matroid is $M$. If $\mathcal{B}$ is the set of bases of $M$, then obviously every member of $\mathcal{B}$ is admissible, considered as a subset of $J$. Because every permutation in $BC_{n}$ is also a permutation in the symmetric group of $J$, Gale’s Theorem implies that $(J,\mathcal{B})$ is a symplectic matroid.

Actually, a converse to the previous example holds. If $(J,\mathcal{B})$ is a symplectic matroid, and $\mathcal{B}$ is also the family of bases of an ordinary matroid with ground set $J=\{-n,\ldots, -1,1,\ldots, n\}$, then every basis is admissible, which means that no basis can contain a set of the form $\{i,-i\}$. Thus every set $\{i,-i\}$ is dependent, so if a symplectic matroid is also an ordinary matroid, then it arises from that ordinary matroid in the way illustrated by Example 2.

Example 3. How about an example of a symplectic matroid that can not be interpreted as a matroid? Let $J$ be $\{-2,-1,1,2\}$, and let $\mathcal{B}$ be the admissible collection $\{\{1,-2\},\{2,-1\},\{-1,-2\}\}$. This is not the set of bases of a matroid; if it were, then $\{1,2\}$ and $\{1,-1\}$ would be parallel pairs, and $\{2,-1\}$ would be a basis. Next we check that $\mathcal{B}$ is the set of bases of a symplectic matroid. Let $w$ be an arbitrary permutation of $\{-2,-1,1,2\}$ from $BC_{2}$ and consider $\{w(1),w(2)\}$. It must be one of the sets $\{1,2\}$, $\{1,-2\}$, $\{2,-1\}$, or $\{-1,-2\}$. Since $A\leq^{w}\{w(1),w(2)\}$ for every $2$-element admissible subset $A$, we are done if $\{w(1),w(2)\}$ is in $\mathcal{B}$. Therefore let us assume that $\{w(1),w(2)\}=\{1,2\}$. Now $w(-1)=-w(1)$, so $\{w(-1),w(2)\}$ is in $\mathcal{B}$, and $A\leq^{w}\{w(-1),w(2)\}$ for every $A\in \mathcal{B}$. Therefore $(\{-2,-1,1,2\},\mathcal{B})$ is a symplectic matroid, as claimed.

The authors of Coxeter Matroids define a Lagrangian matroid to be a symplectic matroid on $\{-n,\ldots,-1,1,\ldots,n\}$ consisting of $n$-element subsets. So Example 3 gave an instance of a Lagrangian matroid. In that example, $\{-1,-2\}$ is an $n$-element admissible set. The intersections of $\{-1,2,\}$ with the members of $\mathcal{B}$ are $\{\}$, $\{-1,2\}$, and $\{-1\}$. If we complete this collection downwards, by including all subsets of those listed, then we generate the family of independent sets of a matroid. This is a particular case of a theorem that appears in Coxeter Matroids: if $\mathcal{B}$ is a collection of $n$-element admissible subsets, then the set system $(J,\mathcal{B})$ is a Lagrangian matroid if and only if, for every $n$-element admissible set, $T$, the downwards completion
\[\{I\subseteq J\mid \text{there exists}\ B\in \mathcal{B}\ \text{such that}\ I\subseteq T\cap B\}\]
is the family of independent subsets of an ordinary matroid. The proof of this equivalence only seems to appear in hard-to-find sources, so I’m not sure how complicated it is. It would be interesting to see a proof; I wonder if the equivalence holds when we relax the constraint that $(J, \mathcal{B})$ is a Lagrangian matroid, and instead ask only that it is a symplectic matroid.

Next time I’ll wrap up by talking about Coxeter matroids and their connections to algebraic geometry.

For a while now I’ve been curious about some objects in algebraic geometry that have the word “matroid” attached to them, although they are not strictly speaking matroids in Whitney’s sense. There are several varieties of such objects: flag matroids, symplectic matroids, Coxeter matroids, and so on. I’m going to make it my mission to learn about these objects, and seeing as they best way to learn a new topic is to write about it, the fruits of my labours will appear here. For the most part, I’m going to be relying on the book Coxeter Matroids, by Borovik, Gelfand, and White.

I’ll start with something fairly simple: flag matroids. The most straightforward definition (at least from the perspective of an “ordinary matroid” theorist) involves quotients. Let $M$ be an ordinary matroid. We say that the matroid $Q$ is a quotient of $M$ if there exists a matroid, $N$, such that $N\backslash X=M$ for some $X\subseteq E(N)$, and $N/X=Q$. In other words, $Q$ is a quotient of $M$ if it can be obtained from $M$ by extending with a set of elements, and then contracting that set. There are many equivalent conditions for $Q$ to be a quotient of $M$. For example, we could equivalently say that $M$ and $Q$ have the same ground set, and every circuit in $M$ is a union of circuits in $Q$.

Now a flag matroid is easily understood: a flag matroid is a sequence $(M_{1},\ldots, M_{m})$ of ordinary matroids, such that $M_{i}$ is a quotient of $M_{i+1}$ for all $i\in\{1,\ldots, m-1\}$. Note that this implies that $M_{i}$ is a quotient of $M_{j}$ for all $j>i$. An ordinary matroid is therefore just a flag matroid in the case that $m=1$.

Stated in this way, the definition doesn’t seem very appealing. However there is an equivalent characterization (used by Borovik et al. use as their primary definition) which is more promising from the point of view of allowing generalizations. For this characterization, we need to introduce an ordering on $k$-element subsets of a finite set. Let $[n]$ be the set $\{1,\ldots, n\}$, and let $w$ be a permutation of $[n]$. Let $A$ and $B$ be $k$-element subsets of $[n]$. We will assume that $A=\{a_{1},\ldots, a_{k}\}$ and $B=\{b_{1},\ldots, b_{k}\}$, where
\begin{multline*}
w^{-1}(a_{1}) < w^{-1}(a_{2}) < \cdots < w^{-1}(a_{k})\quad \text{and}\\ w^{-1}(b_{1}) < w^{-1}(b_{2}) < \cdots < w^{-1}(b_{k}). \end{multline*} Then we declare that $A\leq^{w} B$ if $w^{-1}(a_{i})\leq w^{-1}(b_{i})$ for all $i\in \{1,\ldots, k\}$. It helps me to conceptualise this definition in the following way: arrange two copies of the sequence $w(1),w(2),\ldots, w(n)$ on top of each other. In the top row, highlight the members of $A$, and in the bottom row highlight the members of $B$. Draw a line from the first member of $A$ to the first member of $B$, from the second member of $A$ to the second member of $B$, and so on. If $A\leq^{w} B$, then all the lines that you have just drawn are either vertical or slope down from left to right. If we use this trick, then it becomes trivial to see that $\leq^{w}$ is a partial order on the $k$-element subsets of $[n]$. In 1968, Gale characterized matroids as follows: Theorem. Let $\mathcal{B}$ be a collection of $k$-element subsets from $[n]$. Then $\mathcal{B}$ is the family of bases of a matroid if and only if, for every permutation $w$ of $[n]$, there is a subset $B\in \mathcal{B}$ such that $A\leq^{w} B$ for every $A\in \mathcal{B}$.

Gale’s proof is short, and quite pleasant, so I include it. Given $\mathcal{B}$, a collection of $k$-element subsets of $[n]$, and $w$, a permutation of $[n]$, I will use the phrase upper bound to mean a subset $B\in \mathcal{B}$ such that $A\leq^{w} B$ for every $A\in\mathcal{B}$. By maximal member, I mean a subset $B\in \mathcal{B}$ such that $A\in \mathcal{B}$ and $B\leq^{w} A$ implies $A=B$.

Proof. First assume that $\mathcal{B}$ is the family of bases of a matroid, but that there is a permutation, $w$, such that $\mathcal{B}$ has no upper bound under $\leq^{w}$. Because there are only finitely many $k$-element subsets of $[n]$, there exists a maximal member of $\mathcal{B}$ under $\leq^{w}$. In fact, there must be at least two maximal members of $\mathcal{B}$, for if there is only one, then that member is an upper bound. Let $A$ and $B$ be distinct maximal members of $\mathcal{B}$. Let $x$ be the first element in the sequence $w(1),\ldots, w(n)$ that is in the symmetric difference of $A$ and $B$. Without loss of generality we can assume that $x\in A$. By basis-exchange, there is an element $y\in B-A$ such that $(A-x)\cup y$ is in $\mathcal{B}$. However $A\leq^{w} (A-x)\cup y$, so we have a contradiction to the maximality of $A$.

Now we prove the converse. Let $A$ and $B$ be members of $\mathcal{B}$, and let $x$ be in $A-B$. Assume that $t=|B-A|$. Choose the permutation $w$ so that the last $k+t$ elements in the sequence $w(1),\ldots, w(n)$ are $x$, then the $t$ elements of $B-A$, and then the $k-1$ elements of $A-x$. Let $C$ be the upper bound in $\mathcal{B}$ relative to $\leq^{w}$. Because $A\leq^{w} C$ it follows that $A-x\subseteq C$. Because $B\leq^{w} C$ it follows that the element in $C-A$ must be in $B-A$. Therefore $C=(A-x)\cup y$ for some $y\in B-A$, and the basis-exchange property holds.$\quad\square$

Now let us a define a flag on the set $[n]$ to be a sequence, $(F_{1},\ldots, F_{m})$, of subsets such that $F_{1}\subset F_{2}\subset \cdots \subset F_{m}\subseteq [n]$. Let $\mathcal{F}$ be a collection of flags on $[n]$ and assume that there is a sequence of integers, $(k_{1},\ldots, k_{m})$, such that $|F_{i}|=k_{i}$ whenever $(F_{1},\ldots, F_{m})$ is in $\mathcal{F}$ and $i$ is in $\{1,\ldots, m\}$. This means that the $i$-th components of flags in $\mathcal{F}$ all have the same cardinality. If $F=(F_{1},\ldots, F_{m})$ and $G=(G_{1},\ldots, G_{m})$ belong to $\mathcal{F}$, and $w$ is again a permutation of $[n]$, then we say that $F\leq^{w} G$ if $F_{i}\leq^{w} G_{i}$, for every $i\in \{1,\ldots, m\}$. We can define a flag matroid in the following way: $\mathcal{F}$ is a flag matroid if and only if, for every permutation $w$ of $[n]$, there is a flag $G\in \mathcal{F}$ such that $F\leq^{w} G$ for every $F\in \mathcal{F}$.

From this definition and from Gale’s theorem, we see that if we take the $i$-th components of all flags in $\mathcal{F}$, we obtain the family of bases of a matroid, $M_{i}$. The sequence $(M_{1},\ldots, M_{m})$ is the sequence of quotients I referred to earlier. The fact that the definitions are equivalent follows from Theorem 1.7.1 in Borovik et al.

Generalizations such as symplectic matroids and Coxeter matroids arise from this definition by removing the requirement that $w$ comes from the symmetric group $Sym([n])$, and instead using another permutation group. I’ll write more about these generalizations next time.