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:<\/p>\n
If a matrix $A_1$\u00a0can be turned into a matrix $A_2$ through such operations, then we say $A_1$ and $A_2$ are\u00a0equivalent<\/em>. If we don’t use any field automorphisms, then we say they are\u00a0projectively equivalent.\u00a0<\/em>Generally, a matroid can have multiple inequivalent representations over a field. The\u00a0exceptions are the finite fields\u00a0$\\textrm{GF}(2)$ and $\\textrm{GF}(3)$ (shown in [BL]).<\/p>\n When\u00a0we try to prove\u00a0some theorem about a matroid or class of matroids, inequivalent representations can be\u00a0a major complicating factor. For instance, the excluded-minor characterization of ternary matroids can be proven in under five\u00a0pages [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<\/a>. First, a definition.<\/p>\n Definition.\u00a0<\/strong>Let $\\mathbb{F}$ be a field, and $\\mathcal{M}$ a\u00a0minor-closed class of $\\mathbb{F}$-representable matroids. Let $N \\in \\mathcal{M}$. We say $N$ is a\u00a0stabilizer<\/em> 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).<\/p>\n In other words, once we\u00a0select 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:<\/p>\n $$ 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<\/p>\n $$ and it is readily checked that we must have $b = c = a = 1$. Hence two of the representations of $N$\u00a0do not extend to a representation of $M$, whereas one extends uniquely to a representation of $M$. So $N$ is a stabilizer for $\\mathcal{M}$.<\/p>\n If $\\mathcal{M}$ is an infinite\u00a0class, we cannot\u00a0do an exhaustive check as in the example to verify a stabilizer. But Geoff Whittle managed to prove that a finite check still suffices:<\/p>\n Whittle’s Stabilizer Theorem [Whi].\u00a0<\/strong>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:<\/em><\/p>\n I will conclude this post with two applications. I will leave the finite case checks to the reader.<\/p>\n Lemma.\u00a0<\/strong>The matroid $U_{2,4}$ is a stabilizer for the class of quaternary matroids.<\/em><\/p>\n Corollary [Kah].\u00a0<\/strong>A 3-connected, quaternary, non-binary matroid has a unique representation over $\\textrm{GF}(4)$.<\/em><\/p>\n Proof.\u00a0<\/em>A non-binary matroid $M$ has a $U_{2,4}$-minor. The matroid $U_{2,4}$ has the following representation:<\/p>\n $$ Lemma.\u00a0<\/strong>The matroids $U_{2,5}$ and $U_{3,5}$ are stabilizers for the class of quinary matroids.<\/em><\/p>\n Lemma.\u00a0<\/strong>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}$.<\/em><\/p>\n Corollary [OVW].\u00a0<\/strong>A 3-connected, quinary matroid has at most six inequivalent representations over $\\textrm{GF}(5)$.<\/em><\/p>\n Proof. <\/em>$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$<\/p>\n 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 … Continue reading
\n\\begin{bmatrix}
\n1 & 0 & 0 & 1 & 0 & 1\\\\
\n0 & 1 & 0 & 1 & 1 & 0\\\\
\n0 & 0 & 1 & 0 & 1 & a
\n\\end{bmatrix}
\n$$<\/p>\n
\n\\begin{bmatrix}
\n1 & 0 & 0 & 1 & 0 & 1 & 1\\\\
\n0 & 1 & 0 & 1 & 1 & 0 & b\\\\
\n0 & 0 & 1 & 0 & 1 & a & c
\n\\end{bmatrix}
\n$$<\/p>\n\n
\n
\n\\begin{bmatrix}
\n1 & 0 & 1 & 1\\\\
\n0 & 1 & 1 & a
\n\\end{bmatrix}
\n$$
\nwhere $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$<\/p>\nReferences<\/h3>\n
\n