As part of the 7th European Congress of Mathematics in Berlin, Germany, a minisymposium on Recent Developments in Matroid Theory will be held, organized by Matthias Lenz and Felipe Rincón, with speakers Nathan Bowler, Petter Brändén, Alex Fink, and Anna de Mier. The minisymposium will run on Tuesday, July 19, 2016 from 9-11am.
Go to this page for more information.
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:
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:
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$
I was asked to share information about a Seminar on Matroids in Algebra, Representation Theory and Topology, to be held January 24-29 in Les Diablerets, Switzerland. The deadline for registration is October 4.
All information can be found on the website: http://www.combinatorialmethods.ch/sm-art/
A long time ago, I wrote about partial fields. I defined a partial field as a pair $\mathbb{P} = (R, G)$ of a commutative ring $R$ and a subgroup $G$ of the units of $R$, such that $-1 \in G$. I defined a $\mathbb{P}$-matrix as a matrix over $R$ such that every square sub matrix has a determinant in the set $G \cup \{0\}$, and showed that there is an associated matroid $M[A]$ if some $r\times r$ sub matrix has nonzero determinant.
Partial fields first arose in Whittle’s study of matroids having representations over several different fields. In this post I will discuss the main results of his work on ternary matroids [Whi95, Whi97]. First, let me remind you of Tutte’s characterization of the regular matroids:
Theorem 1. The following statements are equivalent for a matroid $M$:
In addition, Tutte showed that there are exactly three excluded minors for the class of regular matroids: $\{U_{2,4}, F_7, F_7^*\}$. If you’ve never done so, you should definitely read Bert Gerards’ concise proof of this fact [Ger89]. Geoff Whittle wondered if similar theorems would hold when the set of fields in the fourth outcome were changed. In particular, what if we don’t require the matroid to be binary? Here is one of his theorems:
Theorem 2. The following statements are equivalent for a matroid $M$:
Recall from the last post the dyadic partial field $\mathbb{D} = (\mathbb{Z}[\frac{1}{2}], \{\pm 2^i : i \in \mathbb{Z}\})$. Let $\mathbb{F}$ be a field of characteristic $p$ other than 2, and define the ring homomorphism $\phi: \mathbb{Z}[\frac{1}{2}] \to \mathbb{F}$ by sending $x \in \mathbb{Z}$ to $x \pmod p$ and $\frac{1}{2}$ to the inverse of $\phi(2)$ in $\mathbb{F}$. Then $\phi$ is a partial-field homomorphism, and therefore any dyadic matrix $A$ will have $M[A] = M[\phi(A)]$. With this homomorphism, the implication $(3) \implies (2)$ follows immediately. The implication $(2) \implies (1)$ is trivial. To show that $(1)$ implies $(3)$ we need some more work.
A fundamental element of a partial field $\mathbb{P}$ is an element $p \in G$ such that $1-p \in G$ as well. Together with Rudi Pendavingh I proved the following theorem, generalizing Whittle’s proof techniques:
Theorem 3. Let $\mathbb{P}_1$ and $\mathbb{P}_2$ be partial fields, and $\phi: \mathbb{P}_1\to \mathbb{P}_2$ a partial-field homomorphism whose restriction to the fundamental elements of $\mathbb{P}_1$ and $\mathbb{P}_2$ is a bijection. Let $A_2$ be a $\mathbb{P}_2$-matrix. Then exactly one of the following holds:
The associated matroid is $M[I\ A_1]$. To use this theorem for Whittle’s result, let $\mathbb{P}_1 = \mathbb{D}$ and $\mathbb{P}_2 = \text{GF}(3)\times \text{GF}(5)$, where addition and multiplication are componentwise. Then all we have to check is that there is a bijection between the matrices of the forms above between these two partial fields, which is a finite task (because the entries $a$ and $b$ have to be fundamental elements). We called this result the lift theorem, because it allows us to “lift” the finite representation over the partial field $\text{GF}(3) \times \text{GF}(5)$ to a representation over the infinite partial field $\mathbb{D}$.
The proof of the theorem follows Gerards’ proof of Tutte’s theorem (mentioned above) very closely. A new ingredient, though, is the construction of the matrix $A_1$ out of the matrix $A_2$. I will briefly sketch this construction. Let $G= (V, E)$ be the bipartite graph whose vertices are the rows and columns of the matrix $A_2$, and whose edges correspond to the nonzero entries. We may scale so that the entries corresponding to a spanning tree $H$ of $G$ are 1. We fill $A_1$ with $1$s corresponding to the spanning tree, $0$s corresponding to the zero entries of $A_2$, and question marks for the other entries. We repeatedly select a question mark for which the shortest path in $H$ between its terminal vertices is minimal. Up to row and column permutations, this matrix has the following shape: $$\begin{bmatrix} * & 0 & \cdots & 0 & *\\ * & * & 0 & & 0\\ 0 & * & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & * & 0\\ 0 & \cdots & 0 & * & * \end{bmatrix}$$ (where the top right entry corresponds to the question mark in $A_1$). We scale the rows and columns of both this sub matrix of $A_2$ and of $A_1$ to get the following pair:
$$\begin{bmatrix} -1 & 0 & \cdots & 0 & p\\ 1& -1 & 0 & & 0\\ 0 & 1 & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & -1 & 0\\ 0 & \cdots & 0 & 1 & -1 \end{bmatrix}, \begin{bmatrix} -1 & 0 & \cdots & 0 & ?\\ 1& -1 & 0 & & 0\\ 0 & 1 & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & -1 & 0\\ 0 & \cdots & 0 & 1 & -1 \end{bmatrix}.$$
The determinant of the left matrix is $\pm (1-p)$, so $p$ is a fundamental element of $\mathbb{P}_2$. Since there is a unique $q$ such that $\phi(q) = p$, we can replace the question mark with $q$. Then we revert the scaling, and add the corresponding edge to $H$.
We can show that, if a $\mathbb{P}_1$-matrix $A_1$ exists with $\phi(A_1) = A_2$, then this construction finds it. Moreover, the construction commutes with pivoting because it is unique up to row and column scaling. The rest of the proof roughly goes as follows:
Take a minimal counterexample $A_2$. We may assume the bipartite graph is connected and not a path or cycle. Possibly after transposing we can find two columns $u$ and $v$ such that $G – u, G – v, G – \{u,v\}$ are all connected. Scale as above, where the spanning tree has $u$ and $v$ as leaves. Find a matrix $A_1 – u$ corresponding to $A_2 – u$ (by which we mean the matrix with column $u$ removed), and a matrix $A_1 – v$ corresponding to $A_2 – v$. These matrices will agree on the columns other than $u, v$. If the matrix $A_1$ obtained by overlaying these two is not a $\mathbb{P}_1$-matrix, some determinant is wrong. By pivoting, we can ensure this determinant is $2\times 2$ and involves columns $u$ and $v$. Let $a,b$ be the rows of this sub matrix. In $G – u,v$ find a path from $a$ to $b$. More pivots result in a path of length $2$ or $4$, and a sub matrix of the following form (the $*$ symbols correspond to the bad sub matrix):
$$ \begin{bmatrix} 1 & * & *\\ 1 & * & *\end{bmatrix} \textit{ or } \begin{bmatrix} 1 & 1 & p & q\\ 1 & 0 & * & *\\ 0 & 1 & * & * \end{bmatrix}$$
Then a little more analysis cuts down on the possible values of the entries.
Whittle also proved the following characterizations:
Theorem 4. The following statements are equivalent for a matroid $M$:
Theorem 5. The following statements are equivalent for a matroid $M$:
Theorem 6. The following statements are equivalent for a matroid $M$:
Most excitingly, Whittle also managed to prove that these are all theorems of this kind involving $\text{GF}(3)$:
Theorem 7. Let $M$ be a matroid representable over $\text{GF}(3)$ and some field of characteristic other than 3. Then $M$ is representable over at least one of $\{\text{GF}(2), \text{GF}(4), \text{GF}(5), \text{GF}(7)\}$.
An analogous result for $\text{GF}(4)$ and other fields, unfortunately, cannot be obtained: because of the presence of the free spikes, which are representable over all sufficiently large prime fields, there is an infinite number of different classes of matroids representable over $\text{GF}(4)$ and $\text{GF}(p)$, as $p$ ranges over the primes.
Rudi Pendavingh recently implemented the lift construction mentioned above in Sage (it is part of the latest developer beta version). I will write about that in some future post.
References
[Ger89] Bert Gerards. A short proof of Tutte’s characterization of totally unimodular matrices. Lin. Alg. Appl. 114/115:207-212, 1989.
[Whi95] Geoff Whittle. A characterisation of the matroids representable over GF(3) and the rationals. J. Combin. Theory Ser. B, 65(2):222–261, 1995.
[Whi97] Geoff Whittle. On matroids representable over GF(3) and other fields. Trans. Amer. Math. Soc., 349(2):579–603, 1997.