Introduction

In this post, we are going to discuss a bit about the intersection between algebraic geometry and matroid theory. We are all aware that June Huh, in a series of three papers, along with Eric Katz and Karim Adiprasito, developed and extended tools that led to the proof of the Heron–Rota–Welsh unimodality conjecture as well as many other open conjectures [3, 2, 1]. I once asked Huh what type of mathematition he considered himself. I, coming from structural matroid theory, initially viewed his work as a subset of algebraic geometry, but he replied that he viewed himself as a combonatorialist. I have spoken to many other mathematitions who consider themselves matroid theorists, despite not doing structural matroid theory and not having attended the sorts of conferences that I attended as a graduate student doing structural matroid theory. While we will not discuss the tools used to prove the Heron–Rota–Welsh unimodality today, this post is intended to add a bridge to the wide world of matroid theory which makes use of algebraic tools. Of course, many other mathematitions have created tools to help structural matroid theorists understand the type of matroid theory that they do.

A Combinatorial Description of (Minimal) Tropical Basis

Imagine for a moment that you and a mathematical friend are captured by an scheming matroid theorist (SMT). The SMT explains that they are going to tell you a matroid, and your friend the ground est of the matroid. The two of you will be freed when your friend can reveal the matroid to the SMT. To communicate the matroid, you are allowed to tell your friend one circuit of the matroid a day, and allowed to tell your friend when you are done telling them circuits. Your objective is to come up with a strategy that will define a matroid by a subset of the circuits. Of course, we could list every circuit, but we would like to get out of imprisonment sooner, and hence list less than every circuit.

We may be tempted, to make use of fact that binary matroids can be completely determined by listing all fundamental circuits with respect to a particular basis. But this requires, not only that we have a binary matroid, but also requires that we have a promise that our matroid is binary.

For instance, consider the graphic matroid $M(K_4)$, as labeled below. Knowing the fundamental circuits associated with the basis $\{1, 2, 3\}$, isn’t enough information to determine if $\{4, 5, 6\}$ is a circuit or not. To see this, note that both the wheel and the whirl associated with this graph have circuits $\{1,2,6\}$, $\{1,3,5\}$, and $\{2,3,4\}$.

Our strategy will involve giving our friend enough information to determine which subsets of the ground set of $M$ are flats of $M$. Note that knowing that a set $C$ is a circuit of a matroid communicates a number of sets which are not flats of a matroid. For a circuit $C$ of $M$, and a subset $X\subseteq E(M)$, we say that $C$ excludes $X$ when $|C-X|=1$. For instance, the circuit ${0,1,2}$ of $U_2,4$ excludes the subsets $\{\{0,1\}, \{0,2\}, \{1,2\}, \{0,1,3\}, \{0,2,3\}, \{1,2,3\}\}$. That is, we know that the subsets $\{\{0,1\}, \{0,2\}, \{1,2\}, \{0,1,3\}, \{0,2,3\}, \{1,2,3\}\}$ are non-flats of a matroid $M$, just by knowing that $\{0,1,2\}$ is a circuit of $M$.

Example: $U_{2,4}$

Suppose, that the SMT gives us the matroid $M=U_2,4$ on the ground set
$\{0,1,2,3\}$. Then the flats and non-flats of $M$ are:

Flats: $\emptyset$, $\{0\}$, $\{1\}$, $\{2\}$, $\{3\}$, $\{0,1,2,3\}$

Non-Flats: $\{1,2\}$, $\{1,2\}$, $\{1,3\}$, $\{1,2\}$, $\{1,3\}$, $\{2,3\}$, $\{2,3\}$, $\{0,1,2\}$, $\{0,1,3\}$, $\{1,2,3\}$

The circuit $\{0,1,2\}$ excludes 6 of the 10 non-flats.
The circuit $\{0, 1, 3 \}$ will exclude an additional 3 non-flats, namely the flats $\{\{0, 3 \}, \{1, 3 \}, \{0, 1, 2 \} \}$. Finally, the circuit $\{0, 2, 3\}$ will exclude the set $\{2, 3,\}$.

Since the collection $\{ \{0, 1, 2\}, \{0, 1, 3\}, \{0, 2, 3\} \}$ collectively excludes all the non-flats of $U_{2,4}$, we can give just these three circuits to our friend, and they will be able to determine the matroid.

Combinatorial Definition and Some Intuition

It is often useful for us to think of subsets of $[n]$ as 0-1 vectors where a vector is identified with its support. That is, a 0-1 vector $(a_0, a_2, \ldots, a_{n-1}$ represents the subset $\{x\in[n]: a_x=1\}$. For instance, $(1,0,1,0)$ represents the subset ${0,2}$ of $[4]$ because the non-zero entries of $(1,0,1,0)$ occur in the 0th and 2nd entries.

Let $M$ be a matroid on $\{0,1,\ldots, n-1\}$. We say a circuit $C$ of $M$ excludes a vector $x=(x_0, x_2, \ldots, x_{n-1})\in\{0,1\}^n$ if for exactly one $e\in C$, the entry $x_e=0$.

A collection $\mathscr{C}’\subset\mathscr{C}(M)$ is a tropical basis of $M$ if for every non-flat $S$ of $M$, there is a circuit in $\mathscr{C}’$ that excludes $S$. This was not the original definition of a tropical basis, but rather was due to Josephine Yu and Debbie S. Yuster [5].

To test if they understand the definition of a tropical basis, the reader can ask themselves why $\mathscr{C}$ is always a tropical basis of $M$.

If $e$ is a loop, then $\{e\}$ is in every tropical basis of $M$. To see this, note that
if $e$ is a loop, then $E(M)-e$ is a non-flat of $M$. The only circuit $C$ with $|C-(E-e)|=1$ is $\{e\}$.

For a tropical basis $\mathscr{C}’$ of $M$,
we say that $\mathscr{C}’$ is minimal if
for all $C\in\mathscr{C}’$,
the collection $\mathscr{C}’-C$ is not a tropical basis of $M$.

We might imagine that all minimal tropical bases of a matroid $M$ would have the same cardinality, but this in not the case. To see this, we will consider different tropical bases on $U_{2,5}$. This example is from Yu and Yuster’s paper [5].

Example: Minimal Tropical Bases for $U_{2,5}$

The nonflats of $M=U_{2,5}$ consist of all subsets of $\{0,1,2,3,4\}$ of size two, three, or four. Let $\mathscr{C}_1=\{C\in\mathscr{C}: 0\in C\}$, and let $\mathscr{C}_2=\{ \{0, 1, 2\}, \{0, 1, 3\}, \{0, 1, 4\}, \{0, 2, 3 \}, \{2, 3, 4\} \}$. Note that $\mathscr{C}_1\cap \mathscr{C}_2=\{ \{0, 1, 2\}, \{0, 1, 3\}, \{0, 1, 4\}, \{0, 2, 3 \} \}$. To see that $\mathscr{C}_1$ and $\mathscr{C}_2$ are tropical basis, we first note that every non-flat of $M$ besides $\{2,4\}$ and $\{3,4\}$ is excluded by a circuit in $\mathscr{C}_1\cap \mathscr{C}_2$. Both of these non-flats are excluded by $\{2,3,4\}$, so $\mathscr{C}_2$ is a tropical basis of $M$. Lastly, $\{2,4\}$ is excluded by $\{0,2,3\}$ but not by $\{0,3,4\}$, and $\{3,4\}$ is excluded by $\{0,3,4\}$ but not by $\{0,2,3\}$. So $\mathscr{C}_1$ is a tropical basis of $M$.

To see that these Tropical bases are minimal, we note that the set $\{a,b\}\in\{ \{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}\}$ is excluded by the circuit $\{0,a,b\}$, but not by any other circuit in in $\mathscr{C}_1\cup\mathscr{C}_2$.

Origional Definiton of Tropical Basis

To give the original definition, we must first understand some basic definitions in algebraic geometry. A reader who has no interest in algebraic geometry can safely skip this section.

A set is a variety if it is the solution set to some system of polynomials. For instance, the types of graphs that we drew in pre-algebra would be varieties over $\mathbb{R}^2$.

From these examples, one might guess that the union or intersection of two varieties is itself a variety. This turns out to be true.

The Tropical Semi Ring is defined by:

$$\mathbb{T}=\{\mathbb{R}\cup\infty,\oplus,\odot\}$$

$$x\oplus y=min\{x,y\}\quad\quad\quad x\odot y=x+y$$

For example, $2\oplus 7=2$ and $2\odot 7=9$.
Note that $\infty$ is the additive identity, and $0$ is the multiplicative identity.

When working with tropical numbers, generally, $(x-a)=0$ has no solution. Instead, we define a Tropical Variety as the set of points when a polynomial obtains its minimum at least twice.
For example, consider the linear polynomial

$$f(x,y)=2\odot x\oplus 1\odot y\oplus 4.$$
The variety of $f$ is equal to the set when $\min\{2+x, 1+y, 4\}$ occurs twice in the set $\{2+x, 1+y, 4\}$. When drawing tropical varieties, it can help to begin by drawing in dotted lines when any two monomials have the same value, and then fill in the parts of those dotted lines, when that value achieves the value of the polynomial. In this case, that gives us:

For a linear polynomial $f$, we call the tropical variety associated with $f$ a tropical hyperplane.

Now, for a circuit $C$ of a matroid $M$, define
$f_C(\vec{v})=\bigoplus_{e\in E} c_e\odot x_e$, where
$c_e=
\begin{cases}
0 & e\in C \\
1 & e\not\in C
\end{cases}.
$

For example, if we take $M=U_{2,5}$ and $C=\{1,2,3\}$, then
$$f_C=(0\odot x_1)\oplus (0\odot x_2)\oplus (0\odot x_3)\oplus (\infty\odot x_4)\oplus (\infty\odot x_5).$$

Consider the non-flat $\{1,2,4\}$ as an indicator vector $(1,1,0,1,0)$.
We compute $f_C(1,1,0,1,0)=(0\odot 1)\oplus (0\odot 1)\oplus (0\odot 0)\oplus (\infty\odot 1)\oplus (\infty\odot 0).$

The $min\{0+1,0+1,0+0,\infty + 1, \infty +0\}$ achieves it’s minimum only once, so $(1,1,0,1,0)$ is not in the tropical hyperplane associated with $\{1,2,4\}$.

We denote the tropical hyperplane associated with $f_C$ as $T(C)$. That is, $T(C)$ is the space of all vectors $v$ where $f_C(v)$ achieves it’s minimum twice.

For $\mathscr{C}’\subseteq\mathscr{C}(M)$, we define $T(\mathscr{C}’)$ as $\bigcap_{C\in\mathscr{C}}’T(C)$.
A set $\mathscr{C}’\subseteq\mathscr{C}$ is a tropical basis for $M$ if $T(\mathscr{C}’)=T(\mathscr{C})$.

Lemma[5]
For any $\mathscr{C}’\subseteq \mathscr{C}$,

$$T(\mathscr{C}’)\cap\{0,1\}^n=T(\mathscr{C})\cap\{0,1\}^n$$ if and only if $$T(\mathscr{C}’)=T(\mathscr{C}).$$

Before we give the proof of this lemma, it is important to note that this lemma is the essential reason why we are able to use the combinatorial definition of a tropical basis. Intersecting spaces with indicator vectors allows us to only consider the vectors which can be viewed as as subsets of the ground set of a matroid.

Proof
Of course $T(\mathscr{C})\subseteq T(\mathscr{C}’)$. So suppose that $x \in T(\mathscr{C}’)-T(\mathscr{C})$. We need to find an $\tilde{x}\in (T(\mathscr{C}’)\cap\{0,1\}^n)-(T(\mathscr{C})\cap\{0,1\}^n)$.

Since $x\not\in T(\mathscr{C})$, there is some circuit $C_x\in \mathscr{C}$, that excludes $x$, that is $\{x_i:i\in C_x\}$ has a unique minimum $m$.

\[\tilde{x}= \begin{cases}
1 & \text{if } x_i>m\\
0 & \text{if } x_i \leq m.
\end{cases}
\]

$\tilde{x}$ is excluded by $C_x$ because $\{\tilde{x}_i:i\in C_x\}$ achieves it’s minimum exactly when $\{x_i:i\in C_x\}$ has its unique minimum. So $\tilde{x}$ is not in $T(\mathscr{C})$. For any circuit $D$ where $\{x_i:i\in D\}$ achieves its minimum twice, so does $\{\tilde{x}_i:i\in D\}$. So no circuit of $\mathscr{C}’$ excludes $\tilde{x}$. ♦

Open Questions

People have been interested in finding canonical minimal tropical bases for common classes of matroids. In particular, Yu and Yuster [5] asked as an open question to find a minimal tropical basis for an arbitrary transversal matroid. They gave a rather nice description o a canonical minimal tropical basis for uniform matroids.

Yu and Yuster [5] also showed that graphic matroids, cographic matroids, and $R_{10}$ have unique minimal tropical basis. They hypothesised that all regular matroids would have a unique minimal tropical basis. In fact, Yasuhito Nakajima [4] showed that all binary matroids have a unique minimal tropical basis.

Nakajima [4] also showed that having a unique minimal tropical basis was not closed under taking minors. The example that they gave also shows that some non-binary matroids have a unique minimal tropical basis.

It would be nice to have a characterization of which matroids had a unique minimal tropical basis.

References

Anyone who has studied matroid theory has seen graphic and linear matroids, and probably has a decent intuition for how the concepts in matroid theory relate to graph theory and linear algebra. Algebraic matroids are far less popular and many fundamental questions about them remain unanswered. The goal of this blog post is to introduce algebraic matroids, and give the reader a sense of where the subtlety lies when trying to understand them.

The definition

Let $\mathbb{F} \subseteq \mathbb{K}$ be fields. Let $E$ be a finite subset of $\mathbb{K}$ and let $\{Y_e: e \in E\}$ be a set of indeterminates indexed by $E$. A subset $S \subseteq E$ is algebraically independent over $\mathbb{F}$ if whenever $F \in \mathbb{F}[Y_e: e \in E]$ is a polynomial that only includes the variables $\{x_e : e \in S\}$, then $F$ vanishes when plugging in $e$ for $Y_e$ if and only if $F$ is identically zero. The subsets of $E$ that are algebraically independent over $\mathbb{F}$ are the independent subsets of a matroid, called the algebraic matroid of $E$. A matroid $M$ that can be realized in this way is said to be algebraic over $\mathbb{F}$.

An example and a theorem

Let $\mathbb{F}$ be any field and define $\mathbb{K} := \mathbb{F}(x,y,z,w)$, the field of rational functions in four variables over $\mathbb{F}$. Then define

$E := \{xy^{-1},xz^{-1},xw^{-1},yz^{-1},yw^{-1},zw^{-1}\} \subseteq \mathbb{F}(x,y,z,w)$

The subset $I = \{xw^{-1},yw^{-1},zw^{-1}\}$ is algebraically independent over $\mathbb{F}$, whereas $xy^{-1},yz^{-1},xz^{-1}$ is not because if

$F(Y_{xy^{-1}},Y_{,xz^{-1}},Y_{xw^{-1}},Y_{yz^{-1}},Y_{yw^{-1}},Y_{zw^{-1}}) := Y_{xy^{-1}}Y_{yz^{-1}}-Y_{xz^{-1}}$

then $F(xy^{-1},,xz^{-1},xw^{-1},yz^{-1},yw^{-1},zw^{-1})= 0$.

The algebraic matroid of $E$ is the $\mathbb{Q}$-representable matroid defined by the following matrix over $\mathbb{Q}$

$A:=\begin{pmatrix} 1 & 1 & 1 & 0 & 0 & 0 \\ -1 & 0 & 0 & 1 & 1 & 0 \\ 0 & -1 & 0 & -1 & 0 & 1 \\ 0 &0 & -1 & 0 & -1 & -1\end{pmatrix}$.

To see this, let $v \in \mathbb{Z}^6$ be such that $Av = 0$ and define

$v^+ = \left({\rm max}\{v_i,0\}\right)$     and     $v^- = \left({\rm max}\{-v_i,0\}\right)$

so that $v = v^+-v^-$ and $v^+$ and $v^-$ are nonnegative with disjoint supports. Then the binomial

$Y_1^{v_1^+}Y_2^{v_2^+}Y_3^{v_3^+}Y_4^{v_4^+}Y_5^{v_5^+}Y_6^{v_6^+} \  – \  Y_1^{v_1^-}Y_2^{v_2^-}Y_3^{v_3^-}Y_4^{v_4^-}Y_5^{v_5^-}Y_6^{v_6^-}$

vanishes by plugging in $(Y_1,\dots,Y_6) = (xy^{-1},\dots,zw^{-1})$. For example, if $v = (1,-1,0,1,0,0)$ then $v^+ = (1,0,0,1,0,0)$ and $v^- = (0,1,0,0,0,0)$ and the corresponding binomial is $Y_1Y_4-Y_2$.

This procedure gives us a map $\phi$ from the set of integer vectors in the kernel of $A$ to the set of irreducible binomial differences that vanish on $E$. In fact, this map $\phi$ is a bijection and any irreducible polynomial relation among the elements of $E$ will be an irreducible binomial difference and so $\phi$ can be used to show that dependent sets in the algebraic matroid of $E$ correspond to dependent sets in the column matroid of $A$.

The above example generalizes. In particular, if $E \subseteq \mathbb{F}(x_1,\dots,x_r)$ is a set of monomials, then the algebraic matroid of $E$ is isomorphic to the algebraic matroid of the rational matrix $A$ whose column vectors are the exponent vectors of $E$. Since $\mathbb{F}$ was an arbitrary field, this proves the following.

Theorem. If $M$ is representable over $\mathbb{Q}$, then $M$ is algebraic over every field.

Relationship with linear matroids

Every matroid that is linear over a field $\mathbb{F}$ is algebraic over that same field. In particular, the matroid of some $A \in \mathbb{F}^{r \times n}$ is the algebraic matroid of the entries of

$(x_1 \ \cdots \ x_r) A$

as elements of $\mathbb{F}(x_1,\dots,x_r)$. So every $\mathbb{F}$-linear matroid is also $\mathbb{F}$-algebraic. When $\mathbb{F}$ has characteristic zero, the converse is almost true. Namely, we have the following.

Theorem. Let $\mathbb{F}$ be a field of characteristic zero, let $\mathbb{K}$ be a field containing $\mathbb{F}$ and let $E$ be a finite subset of $\mathbb{K}$. Then the algebraic matroid of $E$ is linearly representable over $\mathbb{F}(t_1,\dots,t_r)$ where each $t_i$ is an indeterminate.

Here is a proof sketch for the special case where $\mathbb{K} = \mathbb{F}(t_1,\dots,t_r)$ where each $t_i$ is an indeterminate. Let $M$ denote the algebraic matroid of $E$. For each $e \in E$, let $v_e \in \mathbb{F}(t_1,\dots,t_r)$ be the formal gradient vector of $e$ (note that each $e$ is a polynomial in the $t_i$ variables). Then $\{v_e\}_{e \in E}$ is an $\mathbb{F}(t_1,\dots,t_r)$-linear representation of $M$. Indeed, if there is a polynomial relation among some subset $S \subseteq E$, then the gradient of that polynomial relation is a linear relation among $\{v_e : e \in S\}$. Conversely, each linear relation among a subset of $\{v_e: e \in E\}$ can be made into a polynomial relations among the corresponding subset of $E$.

The general case is proven using essentially the same idea, i.e. take derivatives to reduce to the linear case. Doing this without making assumptions on $\mathbb{K}$ requires the theory of derivations from commutative algebra

What fails in positive characteristic is that not every linear relation among the gradient vectors lifts to an algebraic relation among the corresponding polynomials. Consider for example the following set of monomials in $\mathbb{F}_2(x,y,z)$

$E := \{x,y,z,xy,xz,yz,xyz\} \subset \mathbb{F}_2(x,y,z)$

The corresponding matrix of exponent vectors is the following

$A = \begin{pmatrix} 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 &1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1\end{pmatrix}$.

Since $A$ lives in $\mathbb{Q}^{3 \times 7}$, its matroid is the non-Fano matroid, and since this matroid is isomorphic to the algebraic matroid of $E$, this gives us an $\mathbb{F}_2$-algebraic representation of the non-Fano matroid. Since this is not representable over $\mathbb{F}_2$, we know that the above proof sketch should fail on this example. And it does. The matrix of gradient vectors for $E$, which lives in $\mathbb{F}_2(x,y,z)^{3 \times 7}$, is the following

$Gr = \begin{pmatrix} 1 & 0 & 0 & y & z & 0 & yz \\ 0 & 1 & 0 & x & 0 &z & xz \\ 0 & 0 & 1 & 0 & x & y & xy\end{pmatrix}$

The 3rd, 4th, and 5th columns are the gradients of $xy,xz$, and $yz$. Since this matrix has entries in a field of characteristic two, this 3×3 matrix has zero determinant. But $\{xy,xz,yz\}$ is an algebraically independent subset of $E$. To see this, look at the corresponding columns of the exponent vector matrix $A$:

$\begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix}$.

The determinant of this matrix (which has entries in $\mathbb{Q}$, not $\mathbb{F}_2$) is $-2$, which is non zero in this field.

The big open question

It is unknown if the dual of an algebraic matroid is algebraic. I see no reason for this to be the case, and I think we lack a counterexample showing this for two reasons. The first is that any such counterexample would have to be algebraic but non-linear. Over characteristic zero, the class of algebraic and linear matroids are the same, so this counterexample would have to come from a field of positive characteristic, where geometric interpretations of the algebraic picture are often misleading. The second reason is a lack of ways to certify that a matroid is not algebraic – the methods from the literature are specific to the examples they work on.

One example of a matroid that is algebraic but not linear is the algebraic matroid of the following subset of $\mathbb{F}_2(x,y,z)$

$E := \{x,y,z,x+y,x+z,y+z,x+y+z,xy,xz,yz,xyz\}$.

The matroid on the subset $\{x,y,z,x+y,x+z,y+z,x+y+z\}$ is the Fano matroid (which is only linear over characteristic 2) and the matroid on $\{x,y,z,xy,xz,yz,xyz\}$ is the non-Fano matroid (which is only representable over characteristics other than 2). So this matroid cannot be linear. I conjecture, perhaps a little too boldly, that the dual of this matroid is not algebraic.

Update:

Since publishing this blog post, Winfried Hochstättler reached out to me to share an example of a matroid of rank five on nine elements whose dual is known to be non-algebraic. It is unknown whether the matroid itself is algebraic. Click here to download a pdf describing this matroid.