Matroid Computation with Sage: Linear Extensions

I’ll continue my exploration of Sage’s matroid capabilities (see also here and here). This time I’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 the capabilities of Sage’s matroid package are extensively documented.

Once again, the code examples can be run, as well as edited. The cells are linked together, so execute them in order.

Defining linear matroids

A linear matroid is easily defined from a representation matrix:

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:

Even more concise, we can squeeze the matrix definition into the matroid definition. The second line prints the representation, along with column labels.

Linear extensions

Like last time, let’s start by generating all linear extensions:

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’s examine our list of extensions a little.

There are a few options built into the method to restrict the output. First, we can request only simple extensions:

Second, we can request only extensions that are spanned by a specific subset $F$:

Our third option deserves its own heading.

Partial fields

A while a go, I started writing about partial fields. 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 this bug report. We will use a partial field that’s safe, the dyadic partial field. For a number of others, you can use the product ring code I listed here (with a more advanced version, supporting loading and saving, in a forthcoming technical report that’s currently on hold on arXiv.org).

The key to the world of partial fields in sage is the set of fundamental elements: given a partial field $\mathbb{P} = (R, G)$, the set of fundamental elements is $\{1\} \cup \{x \in G : 1 – x \in G\}$. These can be used to generate $\mathbb{P}$-matrices (I’ll talk about the theory some other time) as follows:

We can test whether each of these is a valid dyadic matroid, as follows:

Other formats

Sometimes you may not want to see the matroids, but rather just the new vectors that define the extensions. Sage can give you those!

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.

To convert a chain, or just a column vector, into an extension, use the linear_extension method:

Generating all matroids

To get all linear matroid over a specific field or partial field, we can easily modify the code from the last post. Two caveats:

  • We replace is_isomorphic by is_field_isomorphic. That way we get one representative of each representation of the matroid. Of course, this isn’t an issue until $\text{GF}(4)$. To get non isomorphic matroids, you’ll have to post-process the resulting list.
  • 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.

And this prints the counts (in a slightly different form from last time — each line lists the number matroids of a fixed size, broken down by rank):

Exercises

  • Modify the above to generate all dyadic matroids.
  • Find out the dual version of all methods discussed above. Try to understand what a cochain is.

One thought on “Matroid Computation with Sage: Linear Extensions

  1. I added a section on generating all representable matroids. I didn’t finish that yesterday, because of some weird error: M._weak_partition()[-1] will crash Sage. I couldn’t pin down the bug in the online version.

Leave a Reply

Your email address will not be published. Required fields are marked *