October 7, 2013, marked a day that I have long been looking forward to: the release of Sage 5.12. This is the first version of Sage to support matroid theory!

This is the culmination of 2 1/2 years of work by Rudi Pendavingh and myself, with further help from Michael Welsh and Gordon Royle. In this post I’m going to demonstrate why you should be as excited as we are.

What is Sage?

From the Sage homepage:

There are several ways to interact with Sage:

• Download and install it on your own computer. There are plenty of installation instructions available.
• Use Sage online, through the Sage Notebook (runs version 5.11, without the matroids, and is down at the time of writing).
• Use Sage online, through the SageMathCloud .

The third option is the fastest way to get started. To get an idea what Sage is capable of, look at the considerable documentation on the Sage website (including a tour, a tutorial, and much more).

Matroids in Sage

Matroid computation is not new. I have a list of previous efforts on these slides, and currently the most widely used software is Petr Hliněný’s MACEK. It is very powerful when it can already do what you want, but its functionality has its bounds, and it is very hard to teach it new tricks. Moreover, the original author no longer supports it.

To avoid ending up with the same fate, we wanted to tie our efforts in with other open-source software. GAP and Sage were the obvious candidates, with Sage winning out because 1) it includes GAP, and 2) Sage appeared to have a more suitable programming language.

Sage gives us a big developer community, regular updates that are tested on many different systems, a bug tracker, a question-and-answer site (be sure to add the “matroid” tag to your questions), a support newsgroup, and did I mention extensive documentation? Like the Matroid Theory part of the Reference Manual.

Some examples

The best way to get to work with the software is to “get your hands dirty”: install it, run it, and experiment, with the Reference Manual at hand. To get you going, I include a few examples of the capabilities below. Lines starting with “sage: ” or “….:” are input, and other lines are output. Anything from a # symbol to the end of the line is a comment. Let’s get started with a theorem:

Theorem. The Fano matroid, $F_7$, is a splitter for the class of matroids with no $U_{2,5}$-, $U_{3,5}$-, and $F_7^*$-minors.

Proof. By Seymour’s Splitter Theorem, we only need to inspect the single-element extensions and coextensions. And since $F_7$ is 3-connected, a single-element extension is 3-connected if and only if it is simple, and a single-element coextension is 3-connected if and only if it is cosimple.

sage: F7 = matroids.named_matroids.Fano()
sage: U25 = matroids.Uniform(2,5)
sage: U35 = matroids.Uniform(3,5)
sage: F7d = F7.dual()
sage: S = [U25, U35, F7d]
sage: Ext = F7.extensions()
sage: print [M for M in Ext if M.is_simple() and not 
....:            any(M.has_minor(N) for N in S)]
[]
sage: CoExt = F7.coextensions()
sage: print [M for M in CoExt if M.is_cosimple() and not
....:            any(M.has_minor(N) for N in S)]
[]

The two lines containing “[ ]” are output. They show that the lists we just constructed are empty, and the result is proved. $\square$

What happened here? In the first three lines, we assigned easy names to several built-in matroids. To get to the built-in matroids, you can type “matroids.” in Sage (note the dot), and hit the TAB key. Likewise, typing “matroids.named_matroids.” and hitting TAB will bring up the list of named matroids. For help, you can always type the name of an object or function followed by “?”, and hit the TAB key (note: in all these examples, do not hit ENTER at any point). For instance, typing

F7?

will print this section of the reference manual.

Each matroid has many methods associated with it. For instance, in the fourth line of our example, we compute the dual of $F_7$. And in the sixth line we compute the single-element extensions. Similar to before, to get a list of all methods you can type

F7.<TAB>

and to get help for any method, type

F7.contract?<TAB>

Easy! The remaining lines show off some aspects of the programming language underlying Sage, Python. It has a very pleasant, mathematical syntax, with excellent support for working with lists and sets of objects.

Let’s look at some more examples. At this point, there is no built-in method to compute the lattice of flats of a matroid. But it is very straightforward to implement this (I spent more time hunting through the documentation on Sage’s posets than on writing the code):

sage: def lattice_of_flats(M):
....:     F = [] 
....:     for i in range(M.rank()+1): 
....:         F.extend([frozenset(X) for X in M.flats(i)]) 
....:     P = Poset((F, lambda x, y: x <= y)) 
....:     return P
....:
sage: lattice_of_flats(F7).plot()

This will yield the following picture (which could be improved, of course):

The first line of this code indicates that we are defining a function with one input, $M$. We use that “M.flats(i)” returns the set of all flats of a matroid $M$ rank $i$. By calling this method for each $i$, doing a little conversion on the output, and gluing the resulting list onto the end of $F$, we make $F$ equal to the list of all flats of $M$. Then we create a poset with a custom partial order, using that Python’s built-in “frozenset” type uses set inclusion as the interpretation of its “<=” operator. The “lambda” notation means we have an inline function taking two inputs, $x$ and $y$. This is another standard Python feature.

Finally, let’s verify for one example that the weight enumerator of a linear code is an evaluation of the Tutte polynomial:

For linear codes, the Weight Enumerator is an evaluation of the Tutte Polynomial of the corresponding matroid. Example:

sage: C = HammingCode(3, GF(3))
sage: x, y = var('x,y')
sage: p = C.weight_enumerator('xy')

sage: M = matroids.PG(2,3).dual() 
sage: t = M.tutte_polynomial(x,y) 
sage: u = t.substitute({x: 3*y/(x-y)+1, 
....:                   y: (x-y)/y+1   }) * y^3 * (x-y)^10 
sage: q = u.full_simplify()

sage: p - q
0

This example also shows Sage’s capabilities for symbolic math. The two variables $x$, $y$ are declared as symbols, and we can use them in polynomials and other functions.

Unfortunately, it also shows that Sage, because it is so big and has so many developers, does not always have a consistent interface. The syntax for the weight enumerator differs from that of the Tutte polynomial.

In conclusion

I didn’t show off the powerful isomorphism tests, the additional capabilities that linear matroids bring to the table, or how to define your own matroids. The latter is pretty easy. In most cases, just use the “Matroid” function, which accepts a variety of inputs:

sage: G = graphs.PetersenGraph()
sage: M = Matroid(G)
sage: M
Regular matroid of rank 9 on 15 elements with 2000 bases

I invite you to give Sage, and its matroid functionality in particular, a try! Make sure to let us know what you accomplish with the code, and what you would like to see added. As for me, together with Carolyn, Deb, and Dillon, I hope to finish a first research paper that uses Sage computations in the next few weeks.

edited on October 15 to reflect that SageMathCloud runs Sage 5.12 now.