Non-matroidal matroids II

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.

Leave a Reply

Your email address will not be published. Required fields are marked *