{"id":517,"date":"2014-04-07T17:32:11","date_gmt":"2014-04-07T21:32:11","guid":{"rendered":"http:\/\/matroidunion.org\/?p=517"},"modified":"2014-05-24T09:30:52","modified_gmt":"2014-05-24T13:30:52","slug":"matroid-computation-with-sage-comparing-matroids","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=517","title":{"rendered":"Matroid Computation with Sage: comparing matroids"},"content":{"rendered":"<p>I&#8217;m back with more on matroid computation in Sage. Previous installments are <a href=\"https:\/\/matroidunion.org\/?p=514\">here<\/a>, <a href=\"https:\/\/matroidunion.org\/?p=301\">here<\/a>, and <a href=\"https:\/\/matroidunion.org\/?p=286\">here<\/a>. As in the previous post, clicking the &#8220;Evaluate&#8221; buttons below will execute the code and return the answer. The various computations are again linked, so execute them in the right order.<\/p>\n<p>Today we will look at various ways to ask (and answer) the question &#8220;<em>Are these two matroids equal?<\/em>&#8221; There are some subtle aspects to this, since we had to balance efficiency of the code and mathematical interpretation. The result is that we have various ways to compare matroids.<\/p>\n<h1>Isomorphism<\/h1>\n<p>Matroids $M$ and $N$ are <em>isomorphic<\/em> if there is a bijection $\\phi: E(M) \\to E(N)$ mapping bases to bases and nonbases to nonbases. In Sage, we check this as follows:<\/p>\n<div class=\"sage1\"><script type=\"text\/x-sage\">\nM = matroids.named_matroids.Fano() \\ 'f'\nN = matroids.Wheel(3)\nM.is_isomorphic(N)\n<\/script><\/div>\n<p>In other words, every matroid in Sage has a method <code>.is_isomorphic()<\/code> taking another matroid as input and returning True or False. Currently there is no way to extract the actual isomorphism (it is on our wish list), but if you guessed one, you can check its correctness:<\/p>\n<div class=\"sage1\"><script type=\"text\/x-sage\">\nprint \"Groundset of M: \", M.groundset()\nprint \"Groundset of N: \", N.groundset()\nphi = {'a':0, 'b':4, 'c':2, 'd':1, 'e':5, 'g':3}\nM.is_isomorphism(N, phi)\n<\/script><\/div>\n<p>We defined $\\phi$ using a <em>dictionary<\/em>: for instance, <code>phi['c']<\/code> equals <code>2<\/code>. If you defined your map differently (e.g. as a function or a permutation), Sage will probably understand that too.<\/p>\n<h1>Equality<\/h1>\n<p>Matroids $M$ and $N$ are <em>equal<\/em> if $E(M) = E(N)$ and the identity map is an isomorphism. We can check for equality as follows:<\/p>\n<div class=\"sage1\"><script type=\"text\/x-sage\">\nprint M.equals(N)\nN2 = Matroid(groundset=M.groundset(), bases=M.bases())\nprint M.equals(N2)\n<\/script><\/div>\n<h1>==<\/h1>\n<p>The standard way to compare two objects in Sage is through the comparison operator <code>==<\/code>. For instance,<\/p>\n<div class=\"sage1\"><script type=\"text\/x-sage\">\nA = Matrix([[1,0],[0,1]])\nB = identity_matrix(2)\nA == B\n<\/script><\/div>\n<p>When writing the matroid code, we chose to interpret the question <code>M == N<\/code> to mean &#8220;<em>Is the internal <strong>representation<\/strong> of the matroid $M$ equal to the internal <strong>representation<\/strong> of $N$?<\/em>&#8221; This is a very restricted view: the only time <code>M == N<\/code> will return <code>True<\/code> is if<\/p>\n<ul>\n<li>$M$ and $N$ have the same internal data structure (i.e. both are of type <code>BasisMatroid<\/code> or both are of type <code>LinearMatroid<\/code> or &#8230;)<\/li>\n<li>$M$ and $N$ are equal as matroids<\/li>\n<li>The internal representations are equivalent (this is at the moment only relevant for linear matroids).<\/li>\n<\/ul>\n<p>Let&#8217;s consider a few examples:<\/p>\n<div class=\"sage1\"><script type=\"text\/x-sage\">\nM1 = matroids.named_matroids.Fano()\nM2 = Matroid(field=GF(2), groundset='abcdefg', reduced_matrix=[[0,1,1,1],[1,0,1,1],[1,1,0,1]])\nM3 = Matroid(field=GF(2), groundset='abcdefg', reduced_matrix=[[1,1,0,1],[1,0,1,1],[0,1,1,1]])\nM4 = Matroid(field=GF(2), groundset='abcdefg', matrix=[[1,0,0,0,1,1,1],[0,1,0,1,0,1,1],[1,0,1,1,0,1,0]])\nM5 = Matroid(field=GF(4,'x'), reduced_matrix=[[0,1,1,1],[1,0,1,1],[1,1,0,1]])\nM6 = Matroid(groundset=M1.groundset(), bases=M1.bases())\nM7 = Matroid(groundset=M1.groundset(), circuit_closures=M1.circuit_closures())\nL = [M1, M2, M3, M4, M5, M6, M7]\nfor i in range(7):\n    print \"Matroid \", i+1, \" has type \", type(L[i])\nTab = [[(1 if L[i] == L[j] else 0) for j in range(7)] for i in range(7)]\nprint matrix(Tab)\n<\/script><\/div>\n<p>So only matroids $M_1$, $M_2$, and $M_4$ pass the equality test. This is because they are all linear matroids over the field $\\mathrm{GF}(2)$, have the same ground set, and the matrices are <em>projectively equivalent<\/em>: one can be turned into the other using only row operations and column scaling. Matrix $M_3$ is isomorphic to $M_1$ but not equal; matroid $M_5$ is represented over a different field; matroid $M_6$ is represented by a list of bases, and matroid $M_7$ is represented by a list of &#8220;circuit closures&#8221;.<\/p>\n<p>This notion of equality has consequences for programming. In Python, a <code>set<\/code> is a data structure containing at most one copy of each element.<\/p>\n<div class=\"sage1\"><script type=\"text\/x-sage\">\nS = set([M1, M2, M3, M4, M5, M6, M7])\nprint \"Set size: \", len(S)\nprint M1 in S\nprint M2 in S\nprint M6 in S\n<\/script><\/div>\n<p>So $S$ actually contains $M_3, M_5, M_6, M_7$, and one copy of $M_1, M_2, M_4$.<\/p>\n<p>This means, unfortunately, that you cannot rely on Python&#8217;s default filtering tools for sets if you want only matroidally equal objects, or only isomorphic objects. But those equality tests are way more expensive computationally, whereas in many applications the matroids in a set will be of the same type anyway.<\/p>\n<h1>Inequivalent representations<\/h1>\n<p>As mentioned above, each instance of the <code>LinearMatroid<\/code> class is considered a <em>represented<\/em> matroid. There are specialized methods for testing projective equivalence and projective isomorphism. Recall that matroids are projectively equivalent (in Sage&#8217;s terminology, field-equivalent) if the representation matrices are equal up to row operations and column scaling. So below, matroids $M_1$ and $M_3$ are field-equivalent; matroids $M_1$ and $M_4$ are field-isomorphic; and matroid $M_2$ has an inequivalent representation:<\/p>\n<div class=\"sage1\"><script type=\"text\/x-sage\">\nM1 = Matroid(groundset='abcdef', field=GF(7), reduced_matrix=[[-1,0,2],[1,-1,0],[0,1,-1]])\nM2 = Matroid(groundset='abcdef', field=GF(7), reduced_matrix=[[-1,0,3],[1,-1,0],[0,1,-1]])\nM3 = Matroid(groundset='abcdef', field=GF(7), matrix=[[1,0,0,-1,0,6],[0,1,0,1,2,0],[1,0,1,-1,5,3]])\nM4 = Matroid(groundset='pqrstu', field=GF(7), matrix=[[1,0,0,-1,0,6],[0,1,0,1,2,0],[1,0,1,-1,5,3]])\nL = [M1, M2, M3, M4]\nprint \"Matroid equality: \", M1.equals(M2)\nprint \"Matroid equality: \", M1.equals(M3)\nprint \"Matroid equality: \", M1.equals(M4)\nprint \"Projective equality: \", M1.is_field_equivalent(M2)\nprint \"Projective equality: \", M1.is_field_equivalent(M3)\nprint \"Projective equality: \", M1.is_field_equivalent(M4)\nprint \"Isomorphism: \", M1.is_isomorphic(M2)\nprint \"Isomorphism: \", M1.is_isomorphic(M3)\nprint \"Isomorphism: \", M1.is_isomorphic(M4)\nprint \"Projective isomorphism: \", M1.is_field_isomorphic(M2)\nprint \"Projective isomorphism: \", M1.is_field_isomorphic(M3)\nprint \"Projective isomorphism: \", M1.is_field_isomorphic(M4)\n<\/script><\/div>\n<p>I probably caused a lot of confusion, so feel free to ask questions in the comments below. Also, the documentation for the functions discussed above gives more explanations and examples.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I&#8217;m back with more on matroid computation in Sage. Previous installments are here, here, and here. As in the previous post, clicking the &#8220;Evaluate&#8221; buttons below will execute the code and return the answer. The various computations are again linked, &hellip; <a href=\"https:\/\/matroidunion.org\/?p=517\">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-517","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\/517","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=517"}],"version-history":[{"count":16,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/517\/revisions"}],"predecessor-version":[{"id":689,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/517\/revisions\/689"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=517"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=517"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=517"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}