Skip to content

Getting started with sage_matroids: I

October 16, 2013

Sage 5.12 has just been released, and this is the first release that automatically incorporates the sage_matroids package that was primarily written by Rudi Pendavingh and Stefan van Zwam. Over at The Matroid Union, Stefan has written an introductory post along with some examples of using the package, and I’m going to complement this with some additional examples. Unlike Stefan though, I’m not an expert in Python, so this post is really to show how easy it is to just get started, even if you don’t know all that much about Python.

I’ll assume that you’ve installed Sage 5.12 and you either have a notebook (the browser interface) or command line working; on the command line Sage prompts you for input with the “sage: ” or “…” when multiline input is incomplete.

I’m mostly interested in binary matroids, which are basically just sets of binary vectors; traditionally a binary matroid is represented by the columns of a binary matrix. Let’s start with an easy binary matroid, namely the Fano plane which is, of course, the “standard” starting example in matroid theory. We can build it in two steps by typing in the representing matrix row-by-row and then creating the matroid.

sage: mat = Matrix([[0,0,0,1,1,1,1],[0,1,1,0,0,1,1],[1,0,1,0,1,0,1]])
sage: bm = sage.matroids.advanced.BinaryMatroid(mat)
sage: bm
Binary matroid of rank 3 on 7 elements, type (3, 0)

Notice that I have to use the “full name” of the constructor for a binary matroid, but if I get tired of typing the whole thing, then I can just tell Sage once-and-for-all where to find it and then just use the “short name”.

sage: from sage.matroids.advanced import BinaryMatroid
sage: bm = BinaryMatroid(mat)

Either way, the ¬†variable “bm” now reports that it represents a binary matroid of rank 3 with 7 elements and gives some additional information that it is of “type (3,0)” (of which more later).

Now I can ask Sage lots of things about this matroid, such as confirming that I entered the matrix correctly, by asking for the representing matrix: notice that the syntax is the common object-oriented style whereby the object “bm” is asked to run the method “representation” and the value returned by the method is then displayed (or assigned to a variable etc.)

sage: bm.representation()
[0 0 0 1 1 1 1]
[0 1 1 0 0 1 1]
[1 0 1 0 1 0 1]

So the elements of this matroid — the groundset — is the set of columns of the matrix. To refer to a particular subset of the columns, I’ll need to know the “names” of the elements.

sage: bm.groundset()
frozenset([0, 1, 2, 3, 4, 5, 6])

This tells me that the groundset is an immutable set (the “frozen” part) containing the elements 0, 1, \ldots, 6. Mostly the end-user doesn’t need to know about immutable sets or why the groundset is immutable, so this is just a bit of the implementation showing and can safely be ignored. Or just use the alternative version of the command

sage: bm.groundset_list()
[0, 1, 2, 3, 4, 5, 6]

Now I know the groundset, I can find out all the usual “matroidy things” about the matroid, such as the rank of an arbitrary subset of the groundset.

sage: bm.rank([0,2,4])
3
sage: bm.rank([0,1,2])
2

The bases of the matroid are all the independent subsets of columns, and I can find out how many of these there are, and also which they are.

sage: bm.bases_count()
28
sage: bm.bases()
Iterator over a system of subsets

Ah, the first one is clear – there are 28 bases, but the second one didn’t give me what I expected, which was the list of bases, but rather an iterator. An iterator¬†is a container object that supplies the objects it contains “one-by-one” (the container object can thereby represent a huge collection by not actually storing any of the objects but only producing them when called for). In this case though, we just want to see them all and so we use Python’s standard syntax for working with iterables.

sage: [b for b in bm.bases()]
[frozenset([0, 2, 3]),
 frozenset([1, 2, 3]),
 frozenset([0, 1, 3]),
 frozenset([1, 3, 4]),
 frozenset([2, 3, 4]),
 frozenset([0, 2, 4]),
 frozenset([1, 2, 4]),
 frozenset([0, 1, 4]),
 frozenset([0, 4, 5]),
 frozenset([1, 4, 5]),
 frozenset([3, 4, 5]),
 frozenset([0, 3, 5]),
 frozenset([2, 3, 5]),
 frozenset([0, 2, 5]),
 frozenset([1, 2, 5]),
 frozenset([0, 1, 5]),
 frozenset([1, 5, 6]),
 frozenset([2, 5, 6]),
 frozenset([3, 5, 6]),
 frozenset([4, 5, 6]),
 frozenset([0, 4, 6]),
 frozenset([2, 4, 6]),
 frozenset([3, 4, 6]),
 frozenset([0, 3, 6]),
 frozenset([1, 3, 6]),
 frozenset([0, 2, 6]),
 frozenset([1, 2, 6]),
 frozenset([0, 1, 6])]
sage:

The notation is simple for mathematicians because it is so similar to set notation – the command can be essentially translated directly into mathematics as \{b : b \in {\rm bases(bm)}\}. Of course, listing the contents of an iterable object is such a common activity that you can just use

sage: list(bm.bases())

to get the same result.

The circuits of the matroid are the minimal dependent sets of columns, and unsurprisingly can be accessed by

sage: bm.circuits()
Iterator over a system of subsets
sage: len(bm.circuits())
14

What if we want to know the lines of the binary matroid, which are the circuits of size 3. Again the Python notation is straightforward for mathematicians:

sage: [c for c in bm.circuits() if len(c) == 3]
 [frozenset([0, 1, 2]),
 frozenset([0, 3, 4]),
 frozenset([2, 4, 5]),
 frozenset([1, 3, 5]),
 frozenset([0, 5, 6]),
 frozenset([1, 4, 6]),
 frozenset([2, 3, 6])]

And there, we have the list of the lines of the Fano plane, exactly as expected. A frozen set is iterable, and so we can smarten up the output easily enough.

sage: [list(c) for c in bm.circuits() if len(c) == 3]
[[0, 1, 2], [0, 3, 4], [2, 4, 5], [1, 3, 5], [0, 5, 6], [1, 4, 6], [2, 3, 6]]

So there we have our first run through the absolute basics of using sage_matroids. Next time, I’ll move on to using – and building on – some of the more sophisticated built-in functions.

About these ads
3 Comments leave one →
  1. October 16, 2013 9:22 pm

    For the record, you don’t need to call the “advanced” BinaryMatroid class in this example. There’s a function Matroid that, like Matrix, has a bit of built-in intelligence. To see its documentation, type

    sage: Matroid?

    And press enter (command line) or tab (notebook).

    In this example, Gordon didn’t specify the base ring of his matrix. Let’s see what it is:

    sage: mat.base_ring()
    Integer Ring

    So you need to tell Matroid to treat it like a binary matrix:

    sage: bm = Matroid(field=GF(2), matrix=mat)
    sage: bm
    Binary matroid of rank 3 on 7 elements, type (3, 0)

    Alternatively, you can specify the ring of the matrix:

    sage: bmat = Matrix(GF(2), [[0,0,0,1,1,1,1],[0,1,1,0,0,1,1],[1,0,1,0,1,0,1]])

    And then the function Matroid is fast enough so it doesn’t need any hints!

    sage: bm = Matroid(bmat)
    sage: bm
    Binary matroid of rank 3 on 7 elements, type (3, 0)

    For the record, if Matroid gets a matrix over the Integer Ring (called ZZ in Sage), something else happens:

    sage: m = Matroid(mat)
    sage: m
    Linear matroid of rank 3 on 7 elements represented over the Rational Field
    sage: m.is_isomorphic(matroids.named_matroids.NonFano())
    True

  2. October 16, 2013 9:44 pm

    Nice run-through, Gordon. And for the record, if you do not want to install Sage anywhere, you can use tthe SageMath Cloud, where you can have a terminal in which to run Sage 5.12, or a worksheet where you can run the same commands. Start a “project” instantly with a free account at: http://cloud.sagemath.com/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 38 other followers

%d bloggers like this: