{"id":514,"date":"2013-12-09T23:26:21","date_gmt":"2013-12-10T04:26:21","guid":{"rendered":"http:\/\/matroidunion.org\/?p=514"},"modified":"2014-05-24T09:30:52","modified_gmt":"2014-05-24T13:30:52","slug":"matroid-computation-with-sage-linear-extensions","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=514","title":{"rendered":"Matroid Computation with Sage: Linear Extensions"},"content":{"rendered":"<p>I&#8217;ll continue my exploration of Sage&#8217;s matroid capabilities (see also <a href=\"https:\/\/matroidunion.org\/?p=301\">here<\/a> and <a href=\"https:\/\/matroidunion.org\/?p=286\">here<\/a>). This time I&#8217;ll look at extensions within subclasses of matroids, namely <b>representable matroids<\/b>. Before we get started, let me remind you of the <a href=\"http:\/\/www.sagemath.org\/doc\/reference\/matroids\/index.html\">reference manual<\/a>, in which the capabilities of Sage&#8217;s matroid package are extensively documented.<!--more--><\/p>\n<p>Once again, the code examples can be run, as well as edited. The cells are linked together, so execute them in order.<\/p>\n<h1>Defining linear matroids<\/h1>\n<p>A linear matroid is easily defined from a representation matrix:<\/p>\n<div class=\"sage1\"><script type=\"text\/x-sage\">\nA = Matrix([[1,0,0,1],[0,1,0,1],[0,0,1,1]])\nM = Matroid(A)\nprint M\n<\/script><\/div>\n<p>Ok, so this matroid is over the field $\\mathbb{Q}$. What if I want a different field? There are two places to specify that, either in the Matroid() or in the Matrix() function:<\/p>\n<div class=\"sage1\"><script type=\"text\/x-sage\">\nM = Matroid(A, field=GF(2))\nprint M\n#\nB = Matrix(GF(2), [[1,0,0,1],[0,1,0,1],[0,0,1,1]])\nN = Matroid(B)\nprint N\nprint \"Equal: \", M == N\n<\/script><\/div>\n<p>Even more concise, we can squeeze the matrix definition into the matroid definition. The second line prints the representation, along with column labels.<\/p>\n<div class=\"sage1\"><script type=\"text\/x-sage\">\nM = Matroid(field=GF(2), matrix=[[1,0,0,1],[0,1,0,1],[0,0,1,1]])\nprint M.representation(labels=True)\n<\/script><\/div>\n<p><H1>Linear extensions<\/H1><\/p>\n<p>Like last time, let&#8217;s start by generating all linear extensions:<\/p>\n<div class=\"sage1\"><script type=\"text\/x-sage\">\nS = M.linear_extensions(element='x')\nprint S\n<\/script><\/div>\n<p>Note that, different from last time, we immediately get a list of matroids, instead of a generator. That might change in the future, though! Let&#8217;s examine our list of extensions a little.<\/p>\n<div class=\"sage1\"><script type=\"text\/x-sage\">\nprint len(S)\nS2 = [N for N in S if N.is_simple()]\nprint len(S2)\nfrom sage.matroids.advanced import *\nS3 = get_nonisomorphic_matroids(S2)\nprint len(S3)\n<\/script><\/div>\n<p>There are a few options built into the method to restrict the output. First, we can request only simple extensions:<\/p>\n<div class=\"sage1\"><script type=\"text\/x-sage\">\nS = M.linear_extensions(element=\"x\", simple=True)\nprint len(S)\n<\/script><\/div>\n<p>Second, we can request only extensions that are spanned by a specific subset $F$:<\/p>\n<div class=\"sage1\"><script type=\"text\/x-sage\">\nS = M.linear_extensions(element=\"x\", F=[0,1])\nfor N in S:\n    print N.representation()\n    print \" \"\n<\/script><\/div>\n<p>Our third option deserves its own heading.<\/p>\n<p><H1>Partial fields<\/H1><\/p>\n<p>A while a go, I <a href=\"https:\/\/matroidunion.org\/?p=238\">started writing about partial fields<\/a>. Sage has support for them built in, with some caveats: fields of fractions are very unreliable (because of hashing reasons). This will be fixed in some future release of Sage, see <a href=\"http:\/\/trac.sagemath.org\/ticket\/15296\">this bug report<\/a>. We will use a partial field that&#8217;s safe, the <i>dyadic<\/i> partial field. For a number of others, you can use the product ring code I listed <a href=\"http:\/\/ask.sagemath.org\/question\/2807\/construction-of-product-rings-znz-x-zmz#4075\">here<\/a> (with a more advanced version, supporting loading and saving, in a forthcoming technical report that&#8217;s currently on hold on arXiv.org).<\/p>\n<p>The key to the world of partial fields in sage is the set of <i>fundamental elements<\/i>: given a partial field $\\mathbb{P} = (R, G)$, the set of fundamental elements is $\\{1\\} \\cup \\{x \\in G : 1 &#8211; x \\in G\\}$. These can be used to generate $\\mathbb{P}$-matrices (I&#8217;ll talk about the theory some other time) as follows:<\/p>\n<div class=\"sage1\"><script type=\"text\/x-sage\">\nM = Matroid(field=QQ, reduced_matrix=[[0, 1, 1, 2],\n                                      [1, 0, 1, 1],\n                                      [1, 1, 0, 1],\n                                      [2, 1, 1, 0]])\nS = M.linear_extensions(simple=True, fundamentals=set([1, 2, -1, 1\/2]))\nprint len(S)\n<\/script><\/div>\n<p>We can test whether each of these is a valid dyadic matroid, as follows:<\/p>\n<div class=\"sage1\"><script type=\"text\/x-sage\">\nfor N in S:\n    print N.cross_ratios().issubset(set([1, 2, -1, 1\/2]))\n<\/script><\/div>\n<p><H1>Other formats<\/H1><\/p>\n<p>Sometimes you may not want to see the matroids, but rather just the new vectors that define the extensions. Sage can give you those!<\/p>\n<div class=\"sage1\"><script type=\"text\/x-sage\">\nM = Matroid(groundset='abcde', field=GF(2), reduced_matrix=[[1,0],[1,1],[0,1]])\nS = M.linear_extension_chains(simple=True)\nprint S\n<\/script><\/div>\n<p>Read this as follows: if the chain is $\\{a: 1, b: 2, d:1\\}$, the new column is obtained by adding $1$ times the column labeled by $a$, $2$ times the column labeled by $b$, and $1$ times the column labeled by $d$. The advantage of this representation, rather than just a vector, is that it is independent of row operations on the representation matrix.<\/p>\n<p>To convert a chain, or just a column vector, into an extension, use the linear_extension method:<\/p>\n<div class=\"sage1\"><script type=\"text\/x-sage\">\nc = S[0]\nN = M.linear_extension(element='x', chain=c)\nprint N.representation(reduced=True, labels=True)\n<\/script><\/div>\n<p><H1>Generating all matroids<\/H1><\/p>\n<p>To get all linear matroid over a specific field or partial field, we can easily modify the code from the last post. Two caveats:<\/p>\n<ul>\n<li>We replace is_isomorphic by is_field_isomorphic. That way we get one representative of each representation of the matroid. Of course, this isn&#8217;t an issue until $\\text{GF}(4)$. To get non isomorphic matroids, you&#8217;ll have to post-process the resulting list.<\/li>\n<li>The method we used for canonical ordering is not available for linear matroids. Instead, we use a method called _weak_partition, and check if the new element is in the last part.<\/li>\n<\/ul>\n<div class=\"sage1\"><script type=\"text\/x-sage\">\ndef all_matroids_faster(field, maxsize):\n    D = {}\n    D[(0,0)] = [Matroid(field=field, groundset=[], matrix=[[]])]\n    for n in range(1, maxsize + 1):\n        e = n\n        D[(0,n)] = []\n        for r in range(n):\n            # extend:\n            for M in D[(r, n - 1 - r)]:\n                S = [N for N in M.linear_extensions(element=e) \n                     if e in list(N._weak_partition())[-1]]\n                for N in S:\n                    if not any(N.is_field_isomorphic(NN) for NN in D[(r, n - r)]):\n                        D[(r, n - r)].append(N)\n            # coextend by coloop:\n            D[(r + 1, n - 1 - r)] = [M.linear_coextension(e, cochain={f:0 for f in M.groundset()}) for M in D[(r, n - 1 - r)]]\n    return D\n#\ntimeit('MM = all_matroids_faster(GF(2), 8)', number=1, repeat=1)\n<\/script><\/div>\n<p>And this prints the counts (in a slightly different form from last time &#8212; each line lists the number matroids of a fixed size, broken down by rank):<\/p>\n<div class=\"sage1\"><script type=\"text\/x-sage\">\nMM = all_matroids_faster(GF(2), 9)\nfor n in range(10):\n    s = ''\n    for r in range(n+1):\n        s = s + ' ' + str(len(MM[(r,n-r)]))\n    print s\n<\/script><\/div>\n<h1>Exercises<\/h1>\n<ul>\n<li>Modify the above to generate all dyadic matroids.<\/li>\n<li>Find out the dual version of all methods discussed above. Try to understand what a cochain is.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>I&#8217;ll continue my exploration of Sage&#8217;s matroid capabilities (see also here and here). This time I&#8217;ll look at extensions within subclasses of matroids, namely representable matroids. Before we get started, let me remind you of the reference manual, in which &hellip; <a href=\"https:\/\/matroidunion.org\/?p=514\">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,7],"tags":[],"class_list":["post-514","post","type-post","status-publish","format-standard","hentry","category-matroids","category-sage"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/514","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=514"}],"version-history":[{"count":15,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/514\/revisions"}],"predecessor-version":[{"id":532,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/514\/revisions\/532"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=514"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=514"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=514"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}