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:<\/p>\n
Theorem 1.<\/strong>\u00a0The following statements are equivalent for a matroid $M$: 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.<\/p>\n 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.<\/p>\n 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.<\/p>\n The definition of a partial field is straightforward:<\/p>\n Definition 2.\u00a0<\/strong>A\u00a0partial field<\/em> 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$.<\/p>\n I will introduce matroid representations over partial fields through\u00a0chain groups<\/em>. 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.<\/p>\n Definition 3.\u00a0<\/strong>Let $R$ be a ring, and $E$ a finite set. A\u00a0chain group<\/em> is a subset $C \\subseteq R^E$ such that, for $c, d \\in C$ and $r \\in R$,<\/p>\n The elements of a chain group are called\u00a0chains<\/em>.<\/p>\n Definition 4.\u00a0<\/strong>The\u00a0support<\/em> of a chain $c\\in C$ is A nonzero chain with inclusionwise minimal support is called\u00a0elementary.<\/em><\/p>\n Definition 5.\u00a0<\/strong>Let $G \\subseteq R$. A chain $c \\in R^E$ is\u00a0$G$-primitive<\/em> if $c \\in (G\\cup\\{0\\})^E$.<\/p>\n Definition 6.\u00a0<\/strong>Let $\\mathbb{P} = (R, G)$ be a partial field, and $E$ a finite set. A chain group $C \\subseteq R^E$ is a\u00a0$\\mathbb{P}$-chain group\u00a0<\/em>if, for every elementary chain $c$ there exists an $r\\in R$ such that $c = rg$ for some $G$-primitive chain $g$.<\/p>\n I realize this was a fairly long string of definitions, but the payoff is that we can very quickly define matroid representations:<\/p>\n Theorem 7.\u00a0<\/strong>Let $\\mathbb{P}$ be a partial field, and $C$ a $\\mathbb{P}$-chain group. Define<\/em> Proof.<\/em> We verify the (co)circuit axioms.<\/p>\n Definition 8.\u00a0<\/strong>We say a matroid $M$ is $\\mathbb{P}$-representable if there exists a $\\mathbb{P}$-chain group $C$ such that $M = M(C)$.<\/p>\n One thing to note is that everything above holds even if we don’t assume $R$ to be commutative. This theory of\u00a0skew partial fields<\/em> was explored in [PZ13]. For the remainder of this post we’ll stick to the commutative case, though.<\/p>\n If you’ve seen totally unimodular matrices defined, you’ve probably seen a definition involving determinants. This also works for partial fields:<\/p>\n Definition 9. <\/strong>Let $\\mathbb{P} = (R, G)$ be a partial field.\u00a0A $\\mathbb{P}$-matrix\u00a0<\/em>is a matrix $A$ with entries in $R$ such that each square submatrix has a determinant in $G \\cup \\{0\\}$.<\/p>\n We denote by $A[X]$ the submatrix of $A$ with columns indexed by $X$.<\/p>\n Theorem 10. <\/strong>Let $\\mathbb{P} = (R, G)$ be a partial field, and $A$ a $\\mathbb{P}$-matrix with $r$ rows and columns indexed by $E$. Define<\/em> Proof.\u00a0<\/em>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$<\/p>\n The link with the previous section is simple:<\/p>\n Theorem 11.\u00a0<\/strong>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]$.<\/em><\/p>\n We also have a converse:<\/p>\n Theorem 12.\u00a0<\/strong>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)$.<\/em><\/p>\n This post is already getting long, so I will skip the proof and refer to [PZ13, Section 3.4] instead.<\/p>\n The key takeaway from the proof of Theorem 10 is the idea of a\u00a0homomorphism<\/em>:<\/p>\n Definition 13.\u00a0<\/strong>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\u00a0partial field homomorphism.<\/em><\/p>\n Theorem 14.\u00a0<\/em><\/strong>If $\\phi$ is as above, then every $\\mathbb{P}_1$-representable matroid is also $\\mathbb{P}_2$-representable.<\/em><\/p>\n 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}^*)$.<\/p>\n The\u00a0regular<\/em> 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\u00a0any\u00a0<\/em>partial field, so regular matroids are, in fact, representable over every\u00a0partial<\/em>\u00a0<\/em>field too!<\/p>\n The\u00a0dyadic\u00a0<\/em>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.<\/p>\n The\u00a0golden ratio\u00a0<\/em>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:<\/p>\n Conjecture 15.\u00a0<\/strong>A matroid is representable over all fields with at least four elements if and only if it is representable over $\\mathbb{P}_4$.<\/p>\n Note that the partial fields for the corresponding statements for two and three elements are known: they are, respectively, the\u00a0regular\u00a0<\/em>and\u00a0near-regular<\/em> partial fields.<\/p>\n For a bigger catalog of partial fields, including a list of homomorphisms between them, I refer to the appendix of my PhD Thesis, [vZ09].<\/p>\n [SW96]\u00a0Charles Semple and Geoff Whittle. Partial fields and matroid representation.<\/em> Adv. in Appl.\u00a0Math., 17(2):184\u2013208, 1996.<\/p>\n [PZ13] R.A.\u00a0Pendavingh, S.H.M. van Zwam.\u00a0Skew partial fields, multilinear representations of matroids, and a matrix tree theorem.\u00a0<\/i>Advances in Applied Mathematics, Vol. 50, Issue 1, pp. 201-227, 2013 (PDF<\/a>,\u00a0arXiv<\/a>,\u00a0doi<\/a>).<\/p>\n [Whi95] \u00a0Geoff Whittle. A characterisation of the matroids representable over GF(3) and the rationals.<\/em> J. Combin. Theory Ser. B, 65(2):222\u2013261, 1995.<\/p>\n [Whi97] \u00a0Geoff Whittle. On matroids representable over GF(3) and other fields.<\/em> Trans. Amer. Math.\u00a0Soc., 349(2):579\u2013603, 1997.<\/p>\n [vZ09] Stefan H. M. van Zwam. Partial Fields in Matroid Theory<\/i>. PhD thesis, Technische Universiteit Eindhoven, 2009.<\/p>\n","protected":false},"excerpt":{"rendered":" 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 … Continue reading
\n<\/em><\/p>\n\n
\n
1. Definitions<\/h1>\n
\n
\n$$\\| c \\| := \\{e \\in E : c_e \\neq 0\\}.$$<\/p>\n
\n $$\\mathcal{C}^* := \\{ \\|c\\| : c \\in C, \\text{ elementary}\\}.$$<\/em>
\n Then $\\mathcal{C}^*$ is the collection of cocircuits of a matroid, $M(C)$.<\/em><\/p>\n\n
\nAn elementary chain was defined to be nonzero.<\/li>\n
\nThe supports of elementary chains are inclusionwise minimal.<\/li>\n
\nLet $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
\n$$g := c_e^{-1} c – d_e^{-1} d.$$
\nThen $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$<\/li>\n<\/ol>\n2. Restrictions on determinants<\/h1>\n
\n $$\\mathcal{B}_A := \\{ X \\subseteq E : |X| = r \\text{ and } \\det(A[X]) \\neq 0\\}.$$<\/em>
\n If this set is nonempty, then $\\mathcal{B}_A$ is the set of bases of a matroid, $M[A]$.<\/em><\/p>\n3. Examples<\/h1>\n
\n<\/em><\/p>\nReferences<\/h1>\n