{"id":2103,"date":"2017-01-09T23:06:47","date_gmt":"2017-01-10T04:06:47","guid":{"rendered":"http:\/\/matroidunion.org\/?p=2103"},"modified":"2017-01-09T23:06:47","modified_gmt":"2017-01-10T04:06:47","slug":"partial-fields-iii-universal-partial-fields","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=2103","title":{"rendered":"Partial Fields, III. Universal partial fields"},"content":{"rendered":"<p>I&#8217;ve talked about partial fields before <a href=\"https:\/\/matroidunion.org\/?p=1430\">here<\/a> and, earlier, <a href=\"https:\/\/matroidunion.org\/?p=238\">here<\/a>. A quick refresher:<\/p>\n<p><strong>Definition 1.\u00a0<\/strong>A\u00a0<em>partial field\u00a0<\/em>is a pair $\\mathbb{P} = (R,G)$ of a commutative ring $R$ and a subgroup $G$ of the invertible elements of $R$ such that $-1 \\in G$.<\/p>\n<p><strong>Definition 2.\u00a0<\/strong>A matrix $A$ over $R$ is a <em>(strong)<\/em> $\\mathbb{P}$-<em>matrix<\/em> if every square submatrix has a determinant in $G\\cup \\{0\\}$.<\/p>\n<p><strong>Definition 3.\u00a0<\/strong>An $r\\times n$ matrix $A$ over $R$ is a <em>weak<\/em>\u00a0$\\mathbb{P}$-<em>matrix<\/em>\u00a0if every $r\\times r$ square submatrix has a determinant in $G\\cup \\{0\\}$, and at least one such matrix has nonzero determinant.<\/p>\n<p>One can check that, if $D$ is a submatrix with nonzero determinant as in the latter definition, then $D^{-1}A$ represents the same matroid, and is a strong $\\mathbb{P}$-matrix. The following was Theorem 10 in Part I:<\/p>\n<p><strong>Proposition 4.\u00a0<\/strong><em>If $A$ is a weak $\\mathbb{P}$-matrix with columns labeled by a set $E$, then $\\mathcal{B} = \\{ B \\subseteq E : |B| = r, \\det(A[B]) \\neq 0\\}$ is the set of bases of a matroid $M$, denoted $M = M[A]$.<\/em><\/p>\n<p>Today, we are interested in the following question:\u00a0given a matroid $M$, can we find a partial field $\\mathbb{P}_M$ that is a &#8220;best fit&#8221; for $M$? The qualities we are looking for are:<\/p>\n<ul>\n<li>$M$ is representable over $\\mathbb{P}_M$;<\/li>\n<li>We can find (information about) other representations of $M$;<\/li>\n<li>We can compute (with) $\\mathbb{P}_M$;<\/li>\n<li>The representation of $M$ over $\\mathbb{P}_M$ is unique.<\/li>\n<\/ul>\n<p>The fourth property turns out to be\u00a0impractical, but we can get the first three. This post is based on Section 4 of [PvZ10]; see also Section 3.3 of my thesis [vZ09].<\/p>\n<h2>Constructing\u00a0the universal partial field<\/h2>\n<p>Let $M$ be a rank-$r$ matroid with ground set $E$. Fix a basis $B$ of $M$. First, let $D^\\#$ be the <em>$B$-fundamental-circuit incidence-matrix\u00a0<\/em>(see [Oxl11, p.182]). Recall that any representation of $M$ of the form $[I\\ D]$ will have the same zero\/nonzero pattern in $D$ as in $D^\\#$, and that we can\u00a0scale rows and columns of $D$ to make certain nonzero entries equal to $1$. Let $T$ be\u00a0the set of coordinates of a maximal set of coordinates that we can scale to be $1$ (see [Oxl11, Theorem 6.4.7] for details).<\/p>\n<p>Next, for each $x \\in B$ and $y \\in E-B$ introduce a variable $a_{xy}$; also introduce variables $i_{B&#8217;}$ for every basis $B&#8217;$ of $M$. Let $\\mathcal{Y}$ be the set of all these variables, and consider the ring of polynomials $\\mathbb{Z}[\\mathcal{Y}]$. Let $\\hat D$ be the $B\\times (E-B)$ matrix with entries $a_{xy}$, and let $\\hat A = [I\\ \\hat D]$.<\/p>\n<p>Now consider the ideal $I_{M,B,T}$ in $\\mathbb{Z}[\\mathcal{Y}]$ generated by the following relations:<\/p>\n<ul>\n<li>$\\det(\\hat A[Z])$ for all $r$-subsets $Z\\subseteq E$ that are nonbases of $M$;<\/li>\n<li>$\\det(\\hat A[Z])i_Z &#8211; 1$ for all bases $Z$ of $M$;<\/li>\n<li>\u00a0$a_{xy} &#8211; 1$ for all $xy \\in T$.<\/li>\n<\/ul>\n<p>Finally, we set $\\mathbb{B}_M = \\mathbb{Z}[\\mathcal{Y}] \/ I_{M,B,T}$ and the partial field<\/p>\n<p>$$\\mathbb{P}_M = (\\mathbb{B}_M, \\langle \\{-1\\}\\cup \\{ i_{B&#8217;} : B&#8217; \\text{ basis of } M\\}\\rangle),$$<\/p>\n<p>where $\\langle\\cdot\\rangle$ denotes &#8220;multiplicative group generated by&#8221;.\u00a0Note that this formalism is nothing other than introducing notation for the steps you would already take to produce a representation of a given abstract matroid. We have the following nice properties (which I won&#8217;t prove):<\/p>\n<p><strong>Proposition 5.\u00a0<\/strong><em>Let $M$ be a matroid and $\\mathbb{P}_M$, $\\hat A$, etc. as above.<br \/>\n<\/em><\/p>\n<ol>\n<li><em>The partial field $\\mathbb{P}_M$ does not depend on the choice of $B$ or $T$.<\/em><\/li>\n<li><em>If $\\mathbb{P}_M$ is not the trivial partial field (that is, if $1 \\neq 0$), then $M$ is represented over $\\mathbb{P}_M$ by the image $A$ of $\\hat A$ under the obvious map from $\\mathbb{Z}[\\mathcal{Y}] \\to \\mathbb{Z}[\\mathcal{Y}] \/ I_{M,B,T}$.<\/em><\/li>\n<li><em>If $M$ is represented over a (partial) field $\\mathbb{P}$ by a matrix $A&#8217;$, then there is a partial field homomorphism $\\phi:\\mathbb{P}_M\\to\\mathbb{P}$ with $\\phi(A) = A&#8217;$.<\/em><\/li>\n<\/ol>\n<p>Here a\u00a0<em>partial field homomorphism $\\phi: (R_1, G_1) \\to (R_2, G_2)$<\/em> is a ring homomorphism $\\phi:R_1 \\to R_2$ such that $\\phi(G_1) \\subseteq G_2$.\u00a0Such homomorphisms preserve matroids, i.e. $M[A] = M[\\phi(A)]$ if $A$ is a $\\mathbb{P}$-matrix. This third property earns $\\mathbb{P}_M$ the name\u00a0<em>universal\u00a0<\/em>partial field:\u00a0<em>every<\/em> representation of $M$ can be obtained from it!<\/p>\n<h3>Computation: Baines and V\u00e1mos and the set of characteristics<\/h3>\n<p>The\u00a0<em>set of characteristics\u00a0<\/em>of a matroid is the subset\u00a0of $\\{p: p = 0$ or $p$ is prime $\\}$ such that $M$ has a representation over some field of\u00a0that characteristic. It is known that the set of characteristics can be any finite subset not containing 0, and any infinite subset containing 0 (see [Oxl11, Section 6.8]). In [BV03], Baines and V\u00e1mos gave an algorithm to compute the set of characteristics from the ideal $I_{M,B,T}$ defined above. A brief summary is as follows:<\/p>\n<ol>\n<li>Compute a <a href=\"https:\/\/en.wikipedia.org\/wiki\/Gr\u00f6bner_basis\">Gr\u00f6bner basis<\/a>\u00a0$G$ over the integers for $I_{M,B,T}$.<\/li>\n<li>If the $G$ contains 1, then $M$ is not representable.<\/li>\n<li>If the $G$ contains a constant $k &gt; 1$, then the prime factors of $k$ are exactly the characteristics over which $M$ is representable.<\/li>\n<li>Otherwise, let $\\gamma$ be the least common multiple of the leading coefficients of the polynomials in $G$. Compute the Gr\u00f6bner basis for the ideal generated by $G \\cup \\{\\gamma\\}$, and let $k$ be its constant member. Then $M$ is representable over characteristic 0 and all prime characteristics,\u00a0<em>except\u00a0<\/em>those dividing $\\gamma$ but not $k$.<\/li>\n<\/ol>\n<p>Note that Gr\u00f6bner basis computations are notoriously difficult to compute and can take up huge amounts of memory. But for small examples this works well. The Gr\u00f6bner basis generates the same ideal as the one we started with, and these computations often give a simpler representation of the partial field.<\/p>\n<h3>Examples<\/h3>\n<p>The universal partial field of $\\text{PG}(2,q)$ is $\\text{GF}(q)$. The non-Fano matroid and $P_8$ both have the\u00a0<em>dyadic<\/em> partial field as their universal partial field, as do the ternary Dowling geometries. The\u00a0<em>Betsy Ross\u00a0<\/em>matroid can be shown to yield the\u00a0<em>Golden Ratio\u00a0<\/em>partial field (that is, it&#8217;s representable over $\\text{GF}(4)$ and $\\text{GF}(5)$), and the matroid represented by the following diagram\u00a0is representable over the partial field $\\mathbb{P}_4$, and is the source of Conjecture 15 in <a href=\"https:\/\/matroidunion.org\/?p=238\">Part I.<\/a>\u00a0The matroid was obtained from Gordon Royle, out of his database of matroids with up to 9 elements, through\u00a0a certain query regarding matroids with only 1 representation over $\\text{GF}(5)$.<\/p>\n<p><a href=\"https:\/\/matroidunion.org\/wp-content\/uploads\/2017\/01\/P4-matroid.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-2111\" src=\"https:\/\/matroidunion.org\/wp-content\/uploads\/2017\/01\/P4-matroid.jpg\" alt=\"p4-matroid\" width=\"316\" height=\"254\" srcset=\"https:\/\/matroidunion.org\/wp-content\/uploads\/2017\/01\/P4-matroid.jpg 316w, https:\/\/matroidunion.org\/wp-content\/uploads\/2017\/01\/P4-matroid-300x241.jpg 300w\" sizes=\"auto, (max-width: 316px) 100vw, 316px\" \/><\/a><\/p>\n<h2>Related results and concepts<\/h2>\n<p>Many people have devoted attention to the\u00a0theory of generic representations of a matroid.\u00a0In [PvZ10] we discuss a construction of the universal partial field that does not rely on the choice of a special basis\u00a0and scaling set. This construction is built on the idea of a\u00a0<em>bracket ring<\/em>, introduced by White [Whi75], where we introduce a variable for each $r$-tuple of elements of $E$, followed by relations that make these $r$-tuples behave like determinants (alternating, 0 for repeated columns, 0 for nonbases, and relations encoding basis exchange). In addition to White&#8217;s construction we introduce symbols to\u00a0make the bracket of each basis invertible.<\/p>\n<p>Dress and Wenzel [DW89] introduce the\u00a0<em>Tutte Group<\/em>, which again introduces a symbol for each basis, but only takes\u00a0<em>multiplicative<\/em> relations into account. This group has received a considerable amount of attention. In particular the <em>torsion<\/em> of this group can give information on characteristics over which $M$ is not representable. Dress and Wenzel give a number of constructions of their group, based on\u00a0various matroid axiomatizations.<\/p>\n<h2><strong>Problems<\/strong><\/h2>\n<p>I&#8217;ll conclude with some (computational) questions I&#8217;ve recently been asking myself.<\/p>\n<ul>\n<li>Can\u00a0we employ scaling techniques as in the definition of $\\mathbb{P}_M$ to obtain a\u00a0(quotient of the) Tutte-group that is faster to compute?<\/li>\n<li>Can we combine computations of the Tutte-group with Gr\u00f6bner basis techniques for\u00a0a faster computation of the set of characteristics, or to determine whether $M$ is representable over any given finite field?<\/li>\n<\/ul>\n<p>Unfortunately, $M$ is not always uniquely representable over $\\mathbb{P}_M$ (up to partial field automorphisms, row- and column-scaling). The only obstacles I know involve partial fields $\\mathbb{P}_M$ with an infinite set of cross ratios, such as the &#8220;near-regular-mod-2&#8221; partial field. Perhaps unique representability is recovered when the set of cross ratios is finite?<\/p>\n<h2>References<\/h2>\n<p>[BV03] R. Baines, P. V\u00e1mos,\u00a0<em>An algorithm to compute the set of characteristics of a\u00a0system of polynomial equations over the integers.\u00a0<\/em>J. Symbolic Computat. 35, pp. 269-279 (2003).<\/p>\n<p>[DW89] A.W.M. Dress, W. Wenzel,\u00a0<em>Geometric Algebra for Combinatorial Geometries.\u00a0<\/em>Adv. in Math. 77, pp. 1-36 (1989).<\/p>\n<p>[Oxl11] J. Oxley, <em>Matroid Theory. Second Edition.\u00a0<\/em>Oxford University Press (2011).<\/p>\n<p>[PvZ10] R.A. Pendavingh, S.H.M. van Zwam,\u00a0<em>Confinement of matroid representations to subsets of partial fields.\u00a0<\/em>J. Comb. Th. Ser. B, vol. 100, pp. 510-545 (2010).<\/p>\n<p>[Whi75] N.L. White.\u00a0<em>The bracket ring of a combinatorial geometry. I.\u00a0<\/em>Trans. Amer. Math. Soc. 214, pp. 233-248 (1975).<\/p>\n<p>[vZ09] S.H.M. van Zwam,\u00a0<em><a href=\"https:\/\/www.math.lsu.edu\/~svanzwam\/pdf\/thesis-online.pdf\">Partial Fields in Matroid Theory<\/a>.\u00a0<\/em>PhD Thesis, Eindhoven University of Technology (2009).<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I&#8217;ve talked about partial fields before here and, earlier, here. A quick refresher: Definition 1.\u00a0A\u00a0partial field\u00a0is a pair $\\mathbb{P} = (R,G)$ of a commutative ring $R$ and a subgroup $G$ of the invertible elements of $R$ such that $-1 \\in &hellip; <a href=\"https:\/\/matroidunion.org\/?p=2103\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-2103","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/2103","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2103"}],"version-history":[{"count":8,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/2103\/revisions"}],"predecessor-version":[{"id":2112,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/2103\/revisions\/2112"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2103"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2103"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2103"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}