A long time ago, I wrote about partial fields. I defined a partial field as a pair $\mathbb{P} = (R, G)$ of a commutative ring $R$ and a subgroup $G$ of the units of $R$, such that $-1 \in G$. I defined a $\mathbb{P}$-matrix as a matrix over $R$ such that every square sub matrix has a determinant in the set $G \cup \{0\}$, and showed that there is an associated matroid $M[A]$ if some $r\times r$ sub matrix has nonzero determinant.

Partial fields first arose in Whittle’s study of matroids having representations over several different fields. In this post I will discuss the main results of his work on ternary matroids [Whi95, Whi97]. First, let me remind you of Tutte’s characterization of the regular matroids:

Theorem 1. The following statements are equivalent for a matroid $M$:

1. $M$ is representable over both $\text{GF}(2)$ and $\text{GF}(3)$;
2. $M$ is representable over $\text{GF}(2)$ and some field of characteristic other than $2$;
3. $M$ is representable over $\mathbb{R}$ by a totally unimodular matrix;
4. $M$ is representable over every field.

In addition, Tutte showed that there are exactly three excluded minors for the class of regular matroids: $\{U_{2,4}, F_7, F_7^*\}$. If you’ve never done so, you should definitely read Bert Gerards’ concise proof of this fact [Ger89]. Geoff Whittle wondered if similar theorems would hold when the set of fields in the fourth outcome were changed. In particular, what if we don’t require the matroid to be binary? Here is one of his theorems:

Theorem 2. The following statements are equivalent for a matroid $M$:

1. $M$ is representable over both $\text{GF}(3)$ and $\text{GF}(5)$;
2. $M$ is representable over all fields of characteristic other than $2$;
3. $M$ is representable over $\mathbb{Q}$ by a matrix with every square submatrix in $\{0\} \cup \{\pm 2^i : i \in \mathbb{Z}\}$.

Recall from the last post the dyadic partial field $\mathbb{D} = (\mathbb{Z}[\frac{1}{2}], \{\pm 2^i : i \in \mathbb{Z}\})$. Let $\mathbb{F}$ be a field of characteristic $p$ other than 2, and define the ring homomorphism $\phi: \mathbb{Z}[\frac{1}{2}] \to \mathbb{F}$ by sending $x \in \mathbb{Z}$ to $x \pmod p$ and $\frac{1}{2}$ to the inverse of $\phi(2)$ in $\mathbb{F}$. Then $\phi$ is a partial-field homomorphism, and therefore any dyadic matrix $A$ will have $M[A] = M[\phi(A)]$. With this homomorphism, the implication $(3) \implies (2)$ follows immediately. The implication $(2) \implies (1)$ is trivial. To show that $(1)$ implies $(3)$ we need some more work.

A fundamental element of a partial field $\mathbb{P}$ is an element $p \in G$ such that $1-p \in G$ as well. Together with Rudi Pendavingh I proved the following theorem, generalizing Whittle’s proof techniques:

Theorem 3. Let $\mathbb{P}_1$ and $\mathbb{P}_2$ be partial fields, and $\phi: \mathbb{P}_1\to \mathbb{P}_2$ a partial-field homomorphism whose restriction to the fundamental elements of $\mathbb{P}_1$ and $\mathbb{P}_2$ is a bijection. Let $A_2$ be a $\mathbb{P}_2$-matrix. Then exactly one of the following holds:

1. There exists a $\mathbb{P}_1$-matrix $A_1$ such that $\phi(A_1) = A_2$;
2. $A_2$ can be transformed, using pivots, row and column permutations, transposing, and row and column scaling, to a matrix $A$ of the form $$ \begin{bmatrix}  1 & 1 & 1\\  1 & a & b\end{bmatrix} \textit{ or } \begin{bmatrix} 1 & 1 & 0 & 1\\ 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 1 \end{bmatrix}$$ such that (1) does not hold for $A$ either.

The associated matroid is $M[I\ A_1]$. To use this theorem for Whittle’s result, let $\mathbb{P}_1 = \mathbb{D}$ and $\mathbb{P}_2 = \text{GF}(3)\times \text{GF}(5)$, where addition and multiplication are componentwise. Then all we have to check is that there is a bijection between the matrices of the forms above between these two partial fields, which is a finite task (because the entries $a$ and $b$ have to be fundamental elements). We called this result the lift theorem, because it allows us to “lift” the finite representation over the partial field $\text{GF}(3) \times \text{GF}(5)$ to a representation over the infinite partial field $\mathbb{D}$.

The proof of the theorem follows Gerards’ proof of Tutte’s theorem (mentioned above) very closely. A new ingredient, though, is the construction of the matrix $A_1$ out of the matrix $A_2$. I will briefly sketch this construction. Let $G= (V, E)$ be the bipartite graph whose vertices are the rows and columns of the matrix $A_2$, and whose edges correspond to the nonzero entries. We may scale so that the entries corresponding to a spanning tree $H$ of $G$ are 1. We fill $A_1$ with $1$s corresponding to the spanning tree, $0$s corresponding to the zero entries of $A_2$, and question marks for the other entries. We repeatedly select a question mark for which the shortest path in $H$ between its terminal vertices is minimal. Up to row and column permutations, this matrix has the following shape: $$\begin{bmatrix} * & 0 & \cdots & 0 & *\\ * & * & 0 & & 0\\ 0 & * & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & * & 0\\ 0 & \cdots & 0 & * & * \end{bmatrix}$$ (where the top right entry corresponds to the question mark in $A_1$). We scale the rows and columns of both this sub matrix of $A_2$ and of $A_1$ to get the following pair:

$$\begin{bmatrix} -1 & 0 & \cdots & 0 & p\\ 1& -1 & 0 & & 0\\ 0 & 1 & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & -1 & 0\\ 0 & \cdots & 0 & 1 & -1 \end{bmatrix}, \begin{bmatrix} -1 & 0 & \cdots & 0 & ?\\ 1& -1 & 0 & & 0\\ 0 & 1 & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & -1 & 0\\ 0 & \cdots & 0 & 1 & -1 \end{bmatrix}.$$

The determinant of the left matrix is $\pm (1-p)$, so $p$ is a fundamental element of $\mathbb{P}_2$. Since there is a unique $q$ such that $\phi(q) = p$, we can replace the question mark with $q$. Then we revert the scaling, and add the corresponding edge to $H$.

We can show that, if a $\mathbb{P}_1$-matrix $A_1$ exists with $\phi(A_1) = A_2$, then this construction finds it. Moreover, the construction commutes with pivoting because it is unique up to row and column scaling. The rest of the proof roughly goes as follows:

Take a minimal counterexample $A_2$. We may assume the bipartite graph is connected and not a path or cycle. Possibly after transposing we can find two columns $u$ and $v$ such that $G – u, G – v, G – \{u,v\}$ are all connected. Scale as above, where the spanning tree has $u$ and $v$ as leaves. Find a matrix $A_1 – u$ corresponding to $A_2 – u$ (by which we mean the matrix with column $u$ removed), and a matrix $A_1 – v$ corresponding to $A_2 – v$. These matrices will agree on the columns other than $u, v$. If the matrix $A_1$ obtained by overlaying these two is not a $\mathbb{P}_1$-matrix, some determinant is wrong. By pivoting, we can ensure this determinant is $2\times 2$ and involves columns $u$ and $v$. Let $a,b$ be the rows of this sub matrix. In $G – u,v$ find a path from $a$ to $b$. More pivots result in a path of length $2$ or $4$, and a sub matrix of the following form (the $*$ symbols correspond to the bad sub matrix):

$$ \begin{bmatrix}  1 & * & *\\  1 & * & *\end{bmatrix} \textit{ or } \begin{bmatrix} 1 & 1 & p & q\\ 1 & 0 & * & *\\ 0 & 1 & * & * \end{bmatrix}$$

Then a little more analysis cuts down on the possible values of the entries.

Whittle also proved the following characterizations:

Theorem 4. The following statements are equivalent for a matroid $M$:

1. $M$ is representable over both $\text{GF}(3)$ and $\text{GF}(4)$;
2. $M$ is representable over all fields having a root of $x^2 – x + 1$;
3. $M$ is representable over $\mathbb{C}$ by a matrix with every square submatrix in $\{0\} \cup \{\zeta^i : i = 1, \ldots, 6\}$, where $\zeta$ is a complex sixth root of unity.

Theorem 5. The following statements are equivalent for a matroid $M$:

1. $M$ is representable over both $\text{GF}(3)$, $\text{GF}(4)$, and $\text{GF}(5)$;
2. $M$ is representable over both $\text{GF}(3)$ and $\text{GF}(8)$;
3. $M$ is representable over all fields with at least 3 elements;
4. $M$ is representable over $\mathbb{Q}(\alpha)$, where $\alpha$ is an indeterminate, by a matrix with every square submatrix in $\{0\} \cup \{\pm \alpha^i(1-\alpha)^j : i, j \in \mathbb{Z}\}$.

Theorem 6. The following statements are equivalent for a matroid $M$:

1. $M$ is representable over both $\text{GF}(3)$ and $\text{GF}(7)$;
2. $M$ is representable over $\text{GF}(3)$, $\text{GF}(p^2)$ for all $p > 2$, and over $\text{GF}(p)$ when $p \equiv 1 \pmod 3$;
3. $M$ is representable over $\mathbb{C}$ by a matrix with every square submatrix in $\{0\} \cup \{\pm 2^i\zeta^j : i,j \in \mathbb{Z}\}$.

Most excitingly, Whittle also managed to prove that these are all theorems of this kind involving $\text{GF}(3)$:

Theorem 7. Let $M$ be a matroid representable over $\text{GF}(3)$ and some field of characteristic other than 3. Then $M$ is representable over at least one of $\{\text{GF}(2), \text{GF}(4), \text{GF}(5), \text{GF}(7)\}$.

An analogous result for $\text{GF}(4)$ and other fields, unfortunately, cannot be obtained: because of the presence of the free spikes, which are representable over all sufficiently large prime fields, there is an infinite number of different classes of matroids representable over $\text{GF}(4)$ and $\text{GF}(p)$, as $p$ ranges over the primes.

Rudi Pendavingh recently implemented the lift construction mentioned above in Sage (it is part of the latest developer beta version). I will write about that in some future post.

References

[Ger89] Bert Gerards. A short proof of Tutte’s characterization of totally unimodular matrices. Lin. Alg. Appl. 114/115:207-212, 1989.

[Whi95]  Geoff Whittle. A characterisation of the matroids representable over GF(3) and the rationals. J. Combin. Theory Ser. B, 65(2):222–261, 1995.

[Whi97]  Geoff Whittle. On matroids representable over GF(3) and other fields. Trans. Amer. Math. Soc., 349(2):579–603, 1997.

This post is another installment in my series on matroid computation in SageMath [1], with older posts here, here, here, and here. As always, clicking the “Evaluate” buttons below will execute the code and return the answer (or, in today’s post, draw the picture). The various computations are linked, so execute them in the right order.

Last summer, Jayant Apte was selected to participate in the Google Summer of Code program. During the summer he extended SageMath’s matroid capabilities in two major ways.

• Drawing geometric representations of rank-3 matroids
• A more efficient minor test for binary matroids

The first of these has been part of Sage for a while; the second is awaiting review but should be included fairly soon.

Let’s get started with everyone’s favorite matroid.

That was easy! We can deal with parallel elements too:

Loops are no problem either:

Note that we resort to a slightly different method of display for large parallel classes. The point in the geometric representation will receive a label that is not an element of the matroid, and below the diagram it will state that this label actually represents a parallel class of elements.

The examples above were chosen because the default positioning algorithm gives a decent picture. Unfortunately, that is not always the case:

In these instances, the options of the show() method come in handy. To get a full list, type M.show? in your own session of SageMath, and hit the key. This will bring up the help page of the method (assuming you defined $M$ to be a matroid in an earlier command). We will go through these options one by one.

This is not bad, but we don’t need a curved line to draw this diagram. The solution is to specify a different basis, whose elements will be placed at the corners of a triangle:

Trying different bases is not going to help the Pappus matroid too much. In that case, after inspecting, for instance, M.circuit_closures(), we can come up with custom coordinates for the points. To tell Sage that we’re doing this, we add the option pos_method=1.

A second example, just because:

Our final option today deals with betweenness. In projective geometry this is a meaningless concept, of course, but in a concrete diagram it can matter whether we draw a line from $a$ through $b$ to $c$ or from $b$ through $a$ to $c$. In SageMath, we can specify this through the line_orders option. An example should make this clear.

We specify the order on the line $\{d,e,f\}$:

A slightly less contrived example is provided by $\textrm{AG}(2,3)$.

I prefer a rotational symmetry to the curved lines:

It’s not perfect (I’d like the curved lines to protrude out of the square), but it’s in the ballpark.

Note: after you have drawn a matroid, the options for drawing so are saved. So next time,

will produce the same graphic.

There are many ways in which the drawing routines can be improved. Options like color, aspect ratio, letting the user decide how to handle parallel elements, and functionality like saving plot information when you save a matroid, adding “nice” plots to the built-in library of matroids, special plots for Dowling geometries, plots for rank-4 matroids, and the list goes on. Interested? There’s another Google Summer of Code coming up soon!

[1] SageMath is now the official name of the Sage Mathematical Software System.