# Whittle’s Stabilizer Theorem

Representable matroids are an attractive subclass of matroids, because in their study you have access to an extra tool: a matrix representing this matroid. This is a concise way to describe a matroid: $O(n^2)$ numbers as opposed to $O(2^{2^n})$ bits declaring which subsets are (in)dependent. Let $M$ be a matroid, and $A$ a representation matrix of $M$. The following operations do not change the matroid:

• Add a multiple of a row of $A$ to another row of $A$;
• Scale a row of $A$ by a nonzero constant;
• Scale a column of $A$ by a nonzero constant;
• Add or remove all-zero rows;
• Apply a field automorphism to each entry of $A$.

If a matrix $A_1$ can be turned into a matrix $A_2$ through such operations, then we say $A_1$ and $A_2$ are equivalent. If we don’t use any field automorphisms, then we say they are projectively equivalent. Generally, a matroid can have multiple inequivalent representations over a field. The exceptions are the finite fields $\textrm{GF}(2)$ and $\textrm{GF}(3)$ (shown in [BL]).

When we try to prove some theorem about a matroid or class of matroids, inequivalent representations can be a major complicating factor. For instance, the excluded-minor characterization of ternary matroids can be proven in under five pages [Oxley, pp. 380-385], whereas the excluded-minor characterization of quaternary matroids takes over fifty [GGK]. It is not surprising, then, that significant efforts have been made to get a handle on inequivalent representations. In this post I will focus on one such effort, namely a very attractive theorem by Geoff Whittle, who recently celebrated his 65th birthday with a wonderful workshop. First, a definition.

Definition. Let $\mathbb{F}$ be a field, and $\mathcal{M}$ a minor-closed class of $\mathbb{F}$-representable matroids. Let $N \in \mathcal{M}$. We say $N$ is a stabilizer for $\mathcal{M}$ if, for every 3-connected matroid $M \in \mathcal{M}$ that has $N$ as a minor, each representation of $N$ (over $\mathbb{F}$) extends to at most one representation of $M$ (up to the equivalence defined above).

In other words, once we select a representation for $N$, we have uniquely determined a representation of $M$. A small example: let $\mathbb{F} = \textrm{GF}(5)$, let $\mathcal{M}$ be the set of all minors of the non-Fano matroid $F_7^-$, and let $N$ be the rank-3 wheel. Now $N$ has the following representation:

$$\begin{bmatrix} 1 & 0 & 0 & 1 & 0 & 1\\ 0 & 1 & 0 & 1 & 1 & 0\\ 0 & 0 & 1 & 0 & 1 & a \end{bmatrix}$$

where $a \in \{1, 2, 3\}$. The only 3-connected matroids in $\mathcal{M}$ that have $N$ as a minor are $N$ itself and $F_7^-$. We need to check that each representation of $N$ extends to at most one representation of $F_7^-$. Up to equivalence, the latter representation must look like

$$\begin{bmatrix} 1 & 0 & 0 & 1 & 0 & 1 & 1\\ 0 & 1 & 0 & 1 & 1 & 0 & b\\ 0 & 0 & 1 & 0 & 1 & a & c \end{bmatrix}$$

and it is readily checked that we must have $b = c = a = 1$. Hence two of the representations of $N$ do not extend to a representation of $M$, whereas one extends uniquely to a representation of $M$. So $N$ is a stabilizer for $\mathcal{M}$.

If $\mathcal{M}$ is an infinite class, we cannot do an exhaustive check as in the example to verify a stabilizer. But Geoff Whittle managed to prove that a finite check still suffices:

Whittle’s Stabilizer Theorem [Whi]. Let $\mathcal{M}$ be a minor-closed class of $\mathbb{F}$-representable matroids, and $N \in \mathcal{M}$ a 3-connected matroid. Exactly one of the following holds:

• $N$ is a stabilizer for $\mathcal{M}$ over $\mathbb{F}$;
• There is a 3-connected matroid $M \in \mathcal{M}$ such that either:
• $N = M\backslash e$ and some representation of $N$ extends to more than one representation of $M$;
• $N = M / e$ and some representation of $N$ extends to more than one representation of $M$;
• $N = M / e \backslash f$, $M / e$ and $M \backslash f$ are 3-connected, and some representation of $N$ extends to more than one representation of $M$.

I will conclude this post with two applications. I will leave the finite case checks to the reader.

Lemma. The matroid $U_{2,4}$ is a stabilizer for the class of quaternary matroids.

Corollary [Kah]. A 3-connected, quaternary, non-binary matroid has a unique representation over $\textrm{GF}(4)$.

Proof. A non-binary matroid $M$ has a $U_{2,4}$-minor. The matroid $U_{2,4}$ has the following representation:

$$\begin{bmatrix} 1 & 0 & 1 & 1\\ 0 & 1 & 1 & a \end{bmatrix}$$
where $a \not\in \{0,1\}$. This leaves two choices for $a$, that are related through a field automorphism. Hence $U_{2,4}$ has (up to equivalence) a unique representation over $\textrm{GF}(4)$. But $U_{2,4}$ is a stabilizer, so $M$ is uniquely representable over $\textrm{GF}(4)$ as well. $\square$

Lemma. The matroids $U_{2,5}$ and $U_{3,5}$ are stabilizers for the class of quinary matroids.

Lemma. The matroid $U_{2,4}$ is a stabilizer for the class of quinary matroids with no minor isomorphic to $U_{2,5}$ and $U_{3,5}$.

Corollary [OVW]. A 3-connected, quinary matroid has at most six inequivalent representations over $\textrm{GF}(5)$.

Proof. $U_{2,5}$ and $U_{3,5}$ have six inequivalent representations and are stabilizers. If $M$ does not have such a minor, then either $M$ is regular (and thus uniquely representable over any field) or $M$ has a $U_{2,4}$-minor, which is has three inequivalent representations. $\square$

### References

• [BL] Tom Brylawski and Dean Lucas, Uniquely representable combinatorial geometries. In Teorie Combinatorie (proc. 1973 internat. colloq.) pp. 83-104 (1976).
• [GGK] Jim Geelen, Bert Gerards, Ajai Kapoor, The excluded minors for $\textrm{GF}(4)$-representable matroids. J. Combin. Th. Ser. B, Vol. 79, pp. 247-299 (2000).
• [Kah] Jeff Kahn, On the uniqueness of matroid representations over $\textrm{GF}(4)$. Bull. London Math. Soc. Vol. 20, pp. 5–10 (1988).
• [OVW] James Oxley, Dirk Vertigan, Geoff Whittle, On inequivalent representations of matroids over finite fields.J. Combin. Theory Ser. B. Vol. 67, pp. 325–343 (1996).
• [Oxley] James Oxley, Matroid Theory, 2nd edition. Oxford University Press (2011).
• [Whi] Geoff Whittle, Stabilizers of classes of representable matroids. J. Combin. Theory Ser. B, Vol. 77, pp. 39–72 (1999).

This site uses Akismet to reduce spam. Learn how your comment data is processed.