Partial fields give a more flexible theory of matroid representation than mere fields. Rather than committing to a field, a partial field allows you to capture several representations at once. They were first introduced by Semple and Whittle [SW96]. The archetypical example is the following theorem by Tutte:
Theorem 1. The following statements are equivalent for a matroid $M$:
- $M$ is representable over both $\text{GF}(2)$ and $\text{GF}(3)$;
- $M$ is representable over $\text{GF}(2)$ and some field of characteristic other than $2$;
- $M$ is representable over $\mathbb{R}$ by a totally unimodular matrix;
- $M$ is representable over every field.
Matroid representations over partial fields generalize totally unimodular matrices, as we will see below. We know that regular matroids (i.e. the matroids from Theorem 1) possess many interesting properties. Let $\mathcal{M}$ be the class of regular matroids.
- The excluded minors for $\mathcal{M}$ are $U_{2,4}$, $F_7$, and $F_7^*$.
- Every regular matroid is uniquely representable over every field (up to row operations and column scaling).
- All regular matroids can be obtained from graphic matroids and $R_{10}$ by dualizing and 1-, 2-, 3-sums (this is Seymour’s Decomposition Theorem).
- A simple, regular matroid of rank $r$ has at most ${r+1 \choose 2}$ elements, with equality for the graphic matroids of complete graphs.
- If $A$ is a totally unimodular matrix of full row rank representing $M$, then $\det(A A^T)$ equals the number of bases of $M$.
For every partial field $\mathbb{P}$, one may ask if analogues of these properties exist for the class of $\mathbb{P}$-representable matroids. This is an area of research with a number of interesting results and many unsolved problems.
In this post I will limit myself to introducing matroid representation over partial fields, linking them to the definition of totally unimodular matrices, and giving some examples. In my next post I will discuss Whittle’s characterization [Whi95, 97] of the representations of ternary matroids.
1. Definitions
The definition of a partial field is straightforward:
Definition 2. A partial field is a pair $\mathbb{P} = (R, G)$, where $R$ is a commutative ring, and $G$ is a subgroup of the invertible elements of $R$ such that $-1 \in G$.
I will introduce matroid representations over partial fields through chain groups. For fields, this corresponds to the row space of the representation matrix. The advantage is a very clean basic theory, plus an extension to noncommutative rings at no extra cost. Incidentally, this is how Tutte himself thought about regular matroids.
Definition 3. Let $R$ be a ring, and $E$ a finite set. A chain group is a subset $C \subseteq R^E$ such that, for $c, d \in C$ and $r \in R$,
- $0 \in C$;
- $c+d \in C$;
- $rc \in C$.
The elements of a chain group are called chains.
Definition 4. The support of a chain $c\in C$ is
$$\| c \| := \{e \in E : c_e \neq 0\}.$$
A nonzero chain with inclusionwise minimal support is called elementary.
Definition 5. Let $G \subseteq R$. A chain $c \in R^E$ is $G$-primitive if $c \in (G\cup\{0\})^E$.
Definition 6. Let $\mathbb{P} = (R, G)$ be a partial field, and $E$ a finite set. A chain group $C \subseteq R^E$ is a $\mathbb{P}$-chain group if, for every elementary chain $c$ there exists an $r\in R$ such that $c = rg$ for some $G$-primitive chain $g$.
I realize this was a fairly long string of definitions, but the payoff is that we can very quickly define matroid representations:
Theorem 7. Let $\mathbb{P}$ be a partial field, and $C$ a $\mathbb{P}$-chain group. Define
$$\mathcal{C}^* := \{ \|c\| : c \in C, \text{ elementary}\}.$$
Then $\mathcal{C}^*$ is the collection of cocircuits of a matroid, $M(C)$.
Proof. We verify the (co)circuit axioms.
- $\emptyset\not\in \mathcal{C}^*$.
An elementary chain was defined to be nonzero.
- If $C, D \in \mathcal{C}^*$ and $C \subseteq D$ then $C = D$.
The supports of elementary chains are inclusionwise minimal.
- If $C, D \in \mathcal{C}^*$ are distinct, and $e \in C \cap D$ then there is a member $F \in \mathcal{C}^*$ with $F \subseteq (C\cup D) – \{e\}$.
Let $c, d$ be chains with $\|c\| = C$ and $\|d\| = D$. Since these chains are elementary, we may assume they are $G$-primitive, i.e. every nonzero entry is invertible. Now write
$$g := c_e^{-1} c – d_e^{-1} d.$$
Then $g$ is nonzero, and therefore there is an elementary chain $f$ whose support is contained in that of $g$. We simply take $F = \|f\|$. $\square$
Definition 8. We say a matroid $M$ is $\mathbb{P}$-representable if there exists a $\mathbb{P}$-chain group $C$ such that $M = M(C)$.
One thing to note is that everything above holds even if we don’t assume $R$ to be commutative. This theory of skew partial fields was explored in [PZ13]. For the remainder of this post we’ll stick to the commutative case, though.
2. Restrictions on determinants
If you’ve seen totally unimodular matrices defined, you’ve probably seen a definition involving determinants. This also works for partial fields:
Definition 9. Let $\mathbb{P} = (R, G)$ be a partial field. A $\mathbb{P}$-matrix is a matrix $A$ with entries in $R$ such that each square submatrix has a determinant in $G \cup \{0\}$.
We denote by $A[X]$ the submatrix of $A$ with columns indexed by $X$.
Theorem 10. Let $\mathbb{P} = (R, G)$ be a partial field, and $A$ a $\mathbb{P}$-matrix with $r$ rows and columns indexed by $E$. Define
$$\mathcal{B}_A := \{ X \subseteq E : |X| = r \text{ and } \det(A[X]) \neq 0\}.$$
If this set is nonempty, then $\mathcal{B}_A$ is the set of bases of a matroid, $M[A]$.
Proof. We use a trick from commutative algebra. Let $I$ be a maximal ideal of $R$. Such an ideal is guaranteed to exist (assuming the axiom of choice). Then $\mathbb{F} := R/I$ is a field. Consider the ring homomorphism $\phi: R \to \mathbb{F}$ sending $r$ to $r + I$. Since this is a homomorphism, it commutes with addition and multiplication. Hence, if we apply it to the entries of $A$, we preserve the nonzero determinants. Since we have a matroid after applying $\phi$, we must have had a matroid before. $\square$
The link with the previous section is simple:
Theorem 11. Let $C$ be the chain group generated by the rows of a $\mathbb{P}$-matrix $A$. Then $C$ is a $\mathbb{P}$-chain group and $M(C) = M[A]$.
We also have a converse:
Theorem 12. Let $C$ be a $\mathbb{P}$-chain group, let $B$ be a basis of $M(C)$, and let $A$ be the matrix whose rows are $G$-primitive chains such that their supports form the $B$-fundamental cocircuits of $M(C)$. Then $A$ is a $\mathbb{P}$-matrix, and $M[A] = M(C)$.
This post is already getting long, so I will skip the proof and refer to [PZ13, Section 3.4] instead.
3. Examples
The key takeaway from the proof of Theorem 10 is the idea of a homomorphism:
Definition 13. Let $\mathbb{P}_1 = (R_1, G_1)$ and $\mathbb{P}_2 = (R_2, G_2)$ be partial fields, and let $\phi: R_1 \to R_2$ be a ring homomorphism such that $\phi(G_1) \subseteq G_2$. Then $\phi$ is a partial field homomorphism.
Theorem 14. If $\phi$ is as above, then every $\mathbb{P}_1$-representable matroid is also $\mathbb{P}_2$-representable.
We omit the proof, which is only a slight modification of the proof of Theorem 10. Note that we can identify a field $\mathbb{F}$ with the partial field $(\mathbb{F}, \mathbb{F}^*)$.
The regular partial field is $\mathbb{U}_0 = (\mathbb{Z}, \{-1, 1\})$. The $\mathbb{U}_0$-matrices are precisely the totally unimodular matrices. There is clearly a partial field homomorphism to any partial field, so regular matroids are, in fact, representable over every partial field too!
The dyadic partial field is $\mathbb{D} = (\mathbb{Z}[\frac{1}{2}], \langle -1, 2 \rangle)$. This means that we extended the ring of integers with all powers of $\frac{1}{2}$, and consider matrices where all subdeterminants are, in absolute value, a (positive or negative) power of $2$. There is a ring homomorphism to every field of characteristic other than 2.
The golden ratio partial field is $\mathbb{G} = (\mathbb{Z}[\tau], \langle -1, \tau\rangle)$, where $\tau$ is the golden ratio, i.e. the positive root of $x^2 – x – 1 = 0$. There is a homomorphism to a number of fields, notably $\text{GF}(4)$ and $\text{GF}(5)$. In fact, it can be shown that a matroid has a golden ratio representation if and only if it is representable over both $\text{GF}(4)$ and $\text{GF}(5)$.
The partial field $\mathbb{P}_4$ is defined as follows. Let $\alpha$ be an indeterminate, let $G$ be the subgroup of the units of $\mathbb{Q}(\alpha)$ generated by $\{-1, \alpha, \alpha-1, \alpha + 1, \alpha – 2\}$, and let $R$ be the smallest subring of $\mathbb{Q}(\alpha)$ containing $G$. There is a partial field homomorphism to every field with at least four elements (obtained by mapping $\alpha$ to any element other than $0, 1, -1, 2$). Let me end with a conjecture about this partial field:
Conjecture 15. A matroid is representable over all fields with at least four elements if and only if it is representable over $\mathbb{P}_4$.
Note that the partial fields for the corresponding statements for two and three elements are known: they are, respectively, the regular and near-regular partial fields.
For a bigger catalog of partial fields, including a list of homomorphisms between them, I refer to the appendix of my PhD Thesis, [vZ09].
References
[SW96] Charles Semple and Geoff Whittle. Partial fields and matroid representation. Adv. in Appl. Math., 17(2):184–208, 1996.
[PZ13] R.A. Pendavingh, S.H.M. van Zwam. Skew partial fields, multilinear representations of matroids, and a matrix tree theorem. Advances in Applied Mathematics, Vol. 50, Issue 1, pp. 201-227, 2013 (PDF, arXiv, doi).
[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.
[vZ09] Stefan H. M. van Zwam. Partial Fields in Matroid Theory. PhD thesis, Technische Universiteit Eindhoven, 2009.
