In this post I want to continue exploring the new-found capabilities of Sage with respect to matroid computation. It follows up on this post; Gordon Royle started a different sequence of posts on sage-matroids here. Following a comment by Jason Grout, I decided to experiment with the Sage Cell Server. The result? All computations in this post can be carried out live, by clicking the “Evaluate” button, and you can edit them to play with them! How awesome is that? A word of warning: the cells in each section of this post are linked together, so if you didn’t evaluate a previous cell, the ones below it might not work. For technical reasons, we use # signs on otherwise empty lines. These symbols (and anything following) are comments, and don’t do anything.

The topic for today is matroid extensions.

Generating extensions

It is very straightforward to generate all extensions of a fixed matroid. In this example, we specified the name of the new element to be ‘x’. If we hadn’t done that, the code would have chosen an arbitrary, previously unused, name for the new element.

Aside: The output looks strange; this is because we are provided with an iterator. This is a very nice feature of the Python language on which Sage was built: it is possible for code to construct the next item in a list of items only when that item is requested. This can have serious memory benefits. Suppose there are two billion gizmos, but you’re only interested in the 753 green ones. If you first generate the list of all gizmos, and then filter out the ones you need, you’ll have two billion of them stored in your computer’s memory halfway through the computation. If, instead, you generate them one by one and only keep the ones you want, you’ll never have more than 754 of them in memory.

In this case, the list of extensions is quite manageable, so let’s keep them all. I’ll recycle the variable name S.

Let’s filter the list. Suppose we are only interested in the extensions that are simple:

Next, suppose we are only interested in the pairwise nonisomorphic matroids in this set. This is, in fact, such a common request that Sage has a built-in function for it. To get it, we import the advanced functionality:

This answer makes sense: we can place the new element ‘x’ either freely in the span of $F_7$, or freely on one of the lines of $F_7$. Note that each of these has a 5-point line minor:

In view of Peter’s posts on growth rates, it makes sense to investigate matroids with no long line minors. As it happens, Sage has an option for that:

Generating all matroids

A basic algorithm to generate all matroids of rank $r$ and corank at most $c$ is the following:

Let’s see how much time it costs to generate all matroids of up to 7 elements:

If we generate all matroids up to 8 elements in this way, it will take about 25 seconds, and you’d better not attempt 9 elements. The real time-killer here is the get_nonisomorphic_matroids function, which does a number of isomorphism tests that is quadratic in the length of its input. In the generation of combinatorial objects, we often try to cut down on this by way of a canonical labeling. For each matroid extension, we compute a matroid invariant in which some elements are distinguished. Suppose $M$ is a single-element extension of $N$. If the new element $e$ of $M$ is not distinguished, then we know that there exists a different matroid, $N’$, such that an extension of $N’$ is isomorphic to $M$, and has been (or will be) generated in another stage of the algorithm. In that case we need not even add $M$ to the temporary list!

There is a slight complication: if $M$ contains coloops, then the only distinguished elements are the coloops! To get all matroids, then, we must change the order of generation. The matroids of rank $r$ and corank $c$ are created by adding a coloop to each matroid of rank $r-1$ and corank $c$, and by extending the matroids of rank $r$ and corank $c-1$.

In fact, this code is fast enough to generate all matroids up to 8 elements. On the Sage cell server, this should take under 7 seconds; the entry in position $(r,c)$ of the table is the number of nonisomorphic matroids of rank $r$ and corank $c$.

If you want 9 elements, be prepared to wait for much, much longer (2 days should do it). I advise you to run it from your own computer, and then save the result to disk through the command save(MM, "/path/to/filename.sobj"). Next time you need them, just load them back through MM = load("/path/to/filename.sobj").

That’s all I want to say about general extensions for now. Sage has more advanced functionality in the sage.matroids.extension package; some documentation is here. A more optimized algorithm to find all matroids can be found in this file (time to build all matroids up to 9 elements: about half an hour).

More control: linear subclasses

Suppose, next, that you don’t want just any extension, but you have more information. This information could be of the form “the new element needs to be in the span of the following subsets”. If so, you’re in luck: Sage has support for that. In the next example, since $a,b$ are in the closure of both specified subsets (as can be checked), every extension, such that $i$ is in the closure of each specified set, must place $i$ on the line through $a$ and $b$.

How does this work? Well, extensions are defined by modular cuts. The set of hyperplanes of a modular cut is called a linear subclass, and internally Sage works with linear subclasses. When you provide a collection of subsets, Sage will find all modular cuts containing the closures of these sets, and work from there. You can compute the smallest modular cut generated by these sets as follows:

Let me conclude this blog post with some homework. I think I’ve presented pretty much all necessary ingredients above.

Exercise: Write a function to generate all frame matroids of specified rank and maximum size.

Next time, I plan to look at linear extensions and partial fields.