{"id":1430,"date":"2015-06-24T15:33:06","date_gmt":"2015-06-24T19:33:06","guid":{"rendered":"http:\/\/matroidunion.org\/?p=1430"},"modified":"2015-06-24T15:33:06","modified_gmt":"2015-06-24T19:33:06","slug":"partial-fields-ii-the-lift-theorem","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=1430","title":{"rendered":"Partial fields, II. The Lift Theorem"},"content":{"rendered":"

A long time ago, I wrote about partial fields<\/a>. 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.<\/p>\n

Partial fields first arose in Whittle’s study of matroids having representations over several different fields. In this post I\u00a0will 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:<\/p>\n

Theorem 1.<\/strong>\u00a0The following statements are equivalent for a matroid $M$:
\n<\/em><\/p>\n

    \n
  1. $M$ is representable over both $\\text{GF}(2)$ and $\\text{GF}(3)$;<\/em><\/li>\n
  2. $M$ is representable over $\\text{GF}(2)$ and some field of characteristic other than $2$;<\/em><\/li>\n
  3. $M$ is representable over $\\mathbb{R}$ by a totally unimodular matrix;<\/em><\/li>\n
  4. $M$\u00a0is representable over\u00a0<\/em>every\u00a0field.<\/em><\/li>\n<\/ol>\n

    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:<\/p>\n

    Theorem 2.<\/strong> The following statements are equivalent for a matroid $M$:<\/em><\/p>\n

      \n
    1. $M$ is representable over both $\\text{GF}(3)$ and $\\text{GF}(5)$;<\/li>\n
    2. $M$ is representable over all fields of characteristic other than $2$;<\/li>\n
    3. $M$ is representable over $\\mathbb{Q}$ by a matrix with every square submatrix in $\\{0\\} \\cup \\{\\pm 2^i : i \\in \\mathbb{Z}\\}$.<\/li>\n<\/ol>\n

      Recall from the last post the dyadic partial field<\/em> $\\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.\u00a0To show that $(1)$ implies $(3)$ we need some more work.<\/p>\n

      A\u00a0fundamental element<\/em> 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:<\/p>\n

      Theorem 3.\u00a0<\/strong>Let $\\mathbb{P}_1$ and $\\mathbb{P}_2$ be partial fields, and $\\phi: \\mathbb{P}_1\\to\u00a0\\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:<\/em><\/p>\n

        \n
      1. There exists a $\\mathbb{P}_1$-matrix $A_1$ such that $\\phi(A_1) = A_2$;<\/em><\/li>\n
      2. $A_2$ can be transformed, using pivots, row and column permutations, transposing, and row and column scaling, to a matrix $A$ of the form\u00a0<\/em>$$ \\begin{bmatrix} \u00a01 & 1 & 1\\\\ \u00a01 & a & b\\end{bmatrix} \\textit{ or } \\begin{bmatrix} 1 & 1 & 0 & 1\\\\ 1 & 0 & 1 & 1\\\\ 0 & 1 & 1 & 1 \\end{bmatrix}$$\u00a0such that (1) does not hold for $A$ either.<\/em><\/li>\n<\/ol>\n

        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\u00a0lift theorem<\/em>, 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}$.<\/p>\n

        The proof of the theorem\u00a0follows 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:<\/p>\n

        $$\\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}.$$<\/p>\n

        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$.<\/p>\n

        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:<\/p>\n

        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):<\/p>\n

        $$ \\begin{bmatrix} \u00a01 & * & *\\\\ \u00a01 & * & *\\end{bmatrix} \\textit{ or } \\begin{bmatrix} 1 & 1 & p & q\\\\ 1 & 0 & * & *\\\\ 0 & 1 & * & * \\end{bmatrix}$$<\/p>\n

        Then a little more analysis\u00a0cuts down on the possible values of the entries.<\/p>\n

        Whittle also proved the following characterizations:<\/p>\n

        Theorem 4.<\/strong>\u00a0The following statements are equivalent for a matroid $M$:<\/em><\/p>\n

          \n
        1. $M$ is representable over both $\\text{GF}(3)$ and $\\text{GF}(4)$;<\/li>\n
        2. $M$ is representable over all fields having a root of $x^2 – x + 1$;<\/li>\n
        3. $M$ is representable over $\\mathbb{C}$ by a matrix with every square submatrix in $\\{0\\} \\cup \\{\\zeta^i : i = 1, \\ldots, 6\\}$, where $\\zeta$ is a complex sixth root of unity.<\/li>\n<\/ol>\n

          Theorem 5.<\/strong>\u00a0The following statements are equivalent for a matroid $M$:<\/em><\/p>\n

            \n
          1. $M$ is representable over both $\\text{GF}(3)$, $\\text{GF}(4)$, and $\\text{GF}(5)$;<\/li>\n
          2. $M$ is representable over both $\\text{GF}(3)$ and $\\text{GF}(8)$;<\/li>\n
          3. $M$ is representable over all fields with at least 3 elements;<\/li>\n
          4. $M$ is representable over $\\mathbb{Q}(\\alpha)$, where $\\alpha$ is an indeterminate, by a matrix with every square submatrix in $\\{0\\} \\cup \\{\\pm \\alpha^i(1-\\alpha)^j : i, j \\in \\mathbb{Z}\\}$.<\/li>\n<\/ol>\n

            Theorem 6.<\/strong>\u00a0The following statements are equivalent for a matroid $M$:<\/em><\/p>\n

              \n
            1. $M$ is representable over both $\\text{GF}(3)$ and $\\text{GF}(7)$;<\/li>\n
            2. $M$ is representable over $\\text{GF}(3)$, $\\text{GF}(p^2)$ for all $p > 2$, and over $\\text{GF}(p)$ when $p \\equiv 1 \\pmod 3$;<\/li>\n
            3. $M$ is representable over $\\mathbb{C}$ by a matrix with every square submatrix in $\\{0\\} \\cup \\{\\pm 2^i\\zeta^j : i,j \\in \\mathbb{Z}\\}$.<\/li>\n<\/ol>\n

              Most excitingly, Whittle also managed to prove that these are all theorems of this kind involving $\\text{GF}(3)$:<\/p>\n

              Theorem 7.\u00a0<\/strong>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)\\}$.<\/em><\/p>\n

              An analogous result for\u00a0$\\text{GF}(4)$ and other fields,\u00a0unfortunately, cannot be obtained: because of the presence of the free spikes,\u00a0which 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.<\/p>\n

              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.<\/p>\n

              References<\/strong><\/em><\/p>\n

              [Ger89] Bert Gerards.\u00a0A short proof of Tutte’s characterization of totally unimodular matrices.\u00a0<\/em>Lin. Alg. Appl. 114\/115:207-212, 1989.<\/p>\n

              [Whi95] \u00a0Geoff Whittle.\u00a0A characterisation of the matroids representable over GF(3) and the rationals.<\/em>\u00a0J. Combin. Theory Ser. B, 65(2):222\u2013261, 1995.<\/p>\n

              [Whi97] \u00a0Geoff Whittle.\u00a0On matroids representable over GF(3) and other fields.<\/em>\u00a0Trans. Amer. Math.\u00a0Soc., 349(2):579\u2013603, 1997.<\/p>\n","protected":false},"excerpt":{"rendered":"

              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$. … Continue reading →<\/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-1430","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1430","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=1430"}],"version-history":[{"count":11,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1430\/revisions"}],"predecessor-version":[{"id":1443,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1430\/revisions\/1443"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1430"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1430"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1430"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}