In this blog post, I’m going to discuss a part of a paper I wrote with Zach Walsh a few years back called “Matroid lifts and representability.” We’ll start by motivating the idea of a matroid lift.

Let $A \in \mathbb{F}^{r_1 \times n}$ and $B \in \mathbb{F}^{r_2 \times n}$ be matrices such that $A$ is a row-submatrix of $B$. Let $E$ denote the column set of $B$, which also naturally indexes the column set of $A$. Let $M_A$ and $M_B$ denote the matroids on ground set $E$ defined by linear independence in $A$ and $B$, respectively. Since $A$ is a row-submatrix of $B$, there is a special relationship between $M_A$ and $M_B$. In particular, every flat of $M_A$ is a flat of $M_B$. This motivates the following definition: given two matroids $M_1$ and $M_2$ on a common ground set $E$, one says that $M_2$ is a lift of $M_1$ if every flat of $M_1$ is a flat of $M_2$.

An Example

Recall that $U_{r,n}$ denotes the uniform matroid of rank $r$ on $n$ elements. One can check that $U_{2,3}$ is a lift of $U_{1,3}$. One can check this by noting that the flats of $U_{1,3}$ are the empty set, the full ground set, and each singleton set and that each of these are also flats of $U_{2,3}$. Alternatively, one can consider the following $\mathbb{Q}$-matrix

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

and note that the matroid of the top row is $U_{1,3}$ and the matroid of the whole matrix is $U_{2,3}$. One interesting thing to note is that even though $U_{1,3}$ and $U_{2,3}$ are both $\mathbb{F}_2$-representable, there is no $2\times 3$ $\mathbb{F}_2$ matrix $B$ that represents $U_{2,3}$, whose top row represents $U_{1,3}$.

Notational Remark

For any matroid $Q$, I will use the notation $r_Q$ and ${\rm cl}_Q$ to denote the rank function and closure operator in $Q$.

Elementary lifts

If $M_2$ is a lift of $M_1$, then the rank of $M_2$ is greater than or equal to that of $M_1$. When $M_2$ is a lift of $M_1$ whose rank is exactly one greater than that of $M_1$, one says that $M_2$ is an elementary lift of $M_1$. I will now describe a classical theorem of Brylawski, the dual version of which was previously stated by Crapo, that gives an elegant combinatorial characterization of all elementary lifts of a matroid $M$.

Let $M$ be a matroid on ground set $E$. A linear class of $M$ is a collection $\mathcal{L}$ of circuits of $M$ such that if $C_1,C_2 \in \mathcal{L}$ satisfy

$|C_1 \cup C_2| – r_M(C_1 \cup C_2) = 2$

then if $C_3$ is a circuit of $M$ contained in $C_1 \cup C_2$, then $C_3 \in \mathcal{L}$. For each such linear class, one can define a function $r_\mathcal{L}: 2^{E} \rightarrow \mathbb{N}$ as follows

$r_\mathcal{L}(X) = \begin{cases}r_M(X) & \textnormal{if each circuit of } M|X \textnormal{ is in } \mathcal{L} \\ r_M(X) + 1 & {\rm otherwise}.\end{cases}$

For each linear class $\mathcal{L}$ of $M$, $r_\mathcal{L}$ is the rank function of a matroid $L$ such that $L$ is an elementary lift of $M$. What is even more interesting is that for every elementary lift $L$ of $M$, there exists a linear class $\mathcal{L}$ of circuits of $M$ such that the rank function of $L$ is $r_{\mathcal{L}}$.

Higher-rank lifts

I became aware of Zach’s existence when his paper “A new matroid lift construction and an application to group-labeled graphs” hit the arXiv. It gave a method for constructing non-elementary lifts of matroids in a way that generalized Brylawski’s construction. At the time, I was on the prowl for matroid theory tools that could be useful in rigidity theory, and matroid lifts had recently played a key role in a groundbreaking paper of Clinch, Jackson, and Tanigawa called “Abstract 3-Rigidity and Bivariate C12-Splines II: Combinatorial Characterization.” So I was very intrigued by Zach’s construction, which is given in the following theorem. 

Theorem (Walsh): Let $M$ be a matroid on ground set $E$ with circuit set $\mathcal{C}$. Let $N$ be a matroid on ground set $\mathcal{C}$ such that if $|C_1 \cup C_2| – r_M(C_1 \cup C_2) = 2$, then each $C \in \mathcal{C}$ such that $C \subset C_1 \cup C_2$ satisfies $C \in {\rm cl}_N(\{C_1 \cup C_2\})$. Then the function $\rho_N: 2^E \rightarrow \mathbb{N}$ defined as follows is the rank function of a lift of $M$ of rank $r_M(E) + r_N(\mathcal{C})$

$\rho_N(X) = r_M(X) + r_N(\{C : C \textnormal{ is a circuit of } M|X\}).$

Zach’s construction generalizes Brylawski’s construction in the sense that when $r_N(\mathcal{C}) = 1$, the rank-zero flat of $N$ is a linear class $\mathcal{L}$ of circuits of $M$, and that $r_\mathcal{L} = \rho_N$. Zach had hoped that this construction would completely generalize Brylawski’s result in that every lift of a matroid $M$ would have rank function of the form $\rho_N$ for some matroid $N$ on the circuit set of $M$. As we will see, this is not the case. However, it does hold for matroid lifts that arise from taking the matroid of a matrix, and a row-submatrix. This gives us a way to test that a given lift is “representable” as a lift, and can even be turned into a test for matroid representability.

Theorem (B-Walsh): Let $A \in \mathbb{F}^{r_1 \times n}$ and $B \in \mathbb{F}^{r_2 \times n}$ such that $A$ is a row-submatrix of $B$. Let $M_A,M_B$ respectively denote the column matroids of $A$ and $B$ and let $\mathcal{C}$ denote the set of circuits of $A$. Then there exists a matroid $N$ on ground set $\mathcal{C}$ such that $\rho_N$ is the rank function of $M_B$.

Here is a sketch of the proof. Since $A$ is a row-submatrix of $B$ we may without loss of generality assume that $B$ has the following form for some matrix $C$

$B = \binom{A}{C}$.

For each circuit $C$ of $M_A$ let $x_C$ be a fixed element of $\mathbb{F}^n$ such that $Ax = 0$. Then $Bx_C$ can be written in the following form for some $x_C’ \in \mathbb{F}^{r_2-r_1}$

$Bx_C = \binom{0}{x_C’}$.

This enables us to define a matroid $N$ on the circuit set $\mathcal{C}$ of $A$ by asserting that $\{C_1,\dots,C_k\}$ is independent in $N$ if and only if the set of vectors $\{x_{C_1}’,\dots,x_{C_k}’\}$ is linearly independent in $\mathbb{F}^{r_2-r_1}$. Then, the rank function of $M_B$ is $\rho_N$.

Non-representable higher rank lifts

The proof of the above theorem heavily depends on access to a linear representation of the higher rank matroid, that has a row-submatrix representing the lower rank matroid. This dependence on a representation cannot be avoided, at least not in full generality. In particular, we can obtain a counterexample from the Vámos matroid.

Given any matroid $M$ on ground set $E$ and an independent subset $I \subset E$, $M\setminus I$ is always a lift of $M / I$ and the difference in ranks is $|I|$ and all lifts can be obtained in this way. Let $V_8$ be the matroid with ground set $\{1,2,\dots,8\}$ of rank $4$, such that every subset of size four or smaller is independent, with the exceptions of the following four-element subsets

$1234,3456,5678,1278,3478.$

This is known as the Vámos matroid, which is known to not be representable over any field. Then $V_8 \setminus \{7,8\}$ is a lift of $V_8 / \{7,8\}$, and as Zach and I show in our paper, there is no matroid $N$ of rank $2$ on the circuit set of $V_8 / \{7,8\}$ such that the rank function of $V_8 \setminus \{7,8\}$ is $\rho_N$. We generalize this construction to construct a two-parameter infinite antichain (in the minor partial order) of sparse paving matroids that are not representable over any field, that satisfy Ingleton’s inequality.

Concluding remarks

As with many papers I’ve written, the bulk of the time I spent “writing” this paper was spent chasing something I wound up being unable to prove. In particular, I was hoping to generalize the theorem about representable lifts of matroids being obtainable via Zach’s construction to the family of algebraic matroids. Alas, not only was I unable to prove that, I’m not so sure if it’s true anymore. But I really don’t have any reason to make a conjecture either way.

Matroids from irreducible varieties

Let $E$ be a finite set, let $\mathbb{F}$ be a field and let $\mathbb{F}^E$ denote the vector space with a fixed set of coordinates, indexed by $E$. For each $S \subseteq E$, $\pi_S: \mathbb{F}^E \rightarrow \mathbb{F}^S$ denotes the corresponding coordinate projection. 

A variety is a subset of $\mathbb{F}^E$ defined by the vanishing of a system of polynomial functions. A variety is said to be irreducible if it is not the proper union of subvarieties. Each irreducible variety $V \subseteq \mathbb{F}^E$ defines a matroid $\mathcal{M}(V)$ on ground set $E$. In particular, $S \subseteq E$ is independent in $\mathcal{M}(V)$ if $\pi_S(V)$ has dimension $|S|$, and $S \subseteq E$ is spanning in $\mathcal{M}(V)$ if $\pi_S(V)$ has the same dimension as $V$.

Representable matroids can be constructed in this way. In particular, if $A$ is an $\mathbb{F}$-matrix with column set $E$, then its rowspan is a linear subspace $L$ of $\mathbb{F}^E$. Since linear subspaces can be defined by the vanishing of linear polynomials, $L$ is a variety and it is moreover irreducible. The matroid $\mathcal{M}(L)$ is isomorphic to the column matroid of $A$.

An example from rigidity theory

Another example of matroids from irreducible varieties comes from rigidity theory. Fix an integer $n$ and consider the following $(n+1)\times (n+1)$ Cayley-Menger matrix

$\begin{pmatrix} 0 & 1 & 1 & 1 & \cdots & 1 \\ 1 & 0 & x_{12} & x_{13} & \cdots & x_{1n} \\ 1 & x_{12} & 0 & x_{23} & \cdots & x_{2n} \\ 1& x_{13} & x_{23} & 0 & \cdots & x_{3n} \\ \vdots & \vdots &\vdots &\vdots & \ddots & \vdots \\ 1 & x_{1n} & x_{2n} & x_{3n} & \cdots & 0 \end{pmatrix}$

Every minor of such a matrix is a polynomial in the variables $\{x_{ij} \vert 1 \le i < j \le n\}$, which is in natural bijection with the edge set $E_n$ of the complete graph on vertex set $\{1,\dots,n\}$. The vanishing of the $(d+3)\times (d+3)$ minors of such a matrix define what’s often called the Cayley-Menger variety of $n$ points in $d$-dimensional space, and we denote it by ${\rm CM}_n^d$. It lives in the vector space $\mathbb{C}^{E_n}$ whose coordinates are indexed by $E_n$.

The significance of the variety ${\rm CM}_n^d$ is that if $p_1,\dots,p_n \in \mathbb{R}^d$ and $y_{ij} = \|p_i-p_j\|$, then the point $(y_{ij} | 1 \le i < j \le n)$ lies in ${\rm CM}_n^d$. Its irreducible, so we can talk about the matroid $\mathcal{M}({\rm CM}_n^d)$. A subset $S \subseteq E_n$ is spanning in $\mathcal{M}({\rm CM}_n^d)$ if and only if the graph $([n],S)$ is generically rigid in $d$-dimensional space. Informally speaking, what this means is that if one were to physically construct the graph $([n],S)$ in $d$-dimensional space using rigid bars for edges that are free to move around their incident vertices, then the result would be a rigid structure assuming that the vertices are placed in a sufficiently “generic” way.

Combinatorial shadows of geometric operations

There are many situations in algebraic geometry and its applications where one creates new irreducible varieties from old ones. It can be interesting and useful to study how these operations manifest combinatorially on the varieties’ matroids. For example, let $V \subseteq \mathbb{C}^E$ be an irreducible variety and let $S \subseteq E$. The closure of $\pi_S(V) \subseteq \mathbb{C}^E$ is also an irreducible variety, and its matroid is the restriction of $\mathcal{M}(V)$ to $S$. We will now discuss a more interesting example.

Let $V,W \subseteq \mathbb{C}^E$ be irreducible Varieties. The Hadamard product of $V$ and $W$, denoted ${V \star W}$, is defined to be the closure of the following set

$\left\{(v_e\cdot w_e)_{e \in E} \  | \ v \in V \ {\rm and} \ w \in W \right\}.$

Certain irreducible varieties whose matroids are interesting for rigidity purposes appear as a Hadamard product of two linear spaces, see [1]. The $d= 2$ case ${\rm CM}_{n}^2$ of Cayley-Menger variety is one such example. This raises the question: given two linear spaces, $L_1$ and $L_2$, can the matroid of the Hadamard product $L_1 \star L_2$ be described in terms of the individual matroids $\mathcal{M}(L_1)$ and $\mathcal{M}(L_2)$? And if so, can this be generalized to allow for more than two linear spaces? For varieties other than linear spaces?

For now, all we can say is that an old technique of Edmonds for constructing matroids from submodular functions works for the Hadamard product of two linear spaces. Let $E$ be a finite set, and let $f: 2^E \rightarrow \mathbb{Z}$ be a function satisfying the following properties:

1. $f(S) \ge 0$ if $S \neq \emptyset$
2. $f(S) \le f(T)$ if $S \subseteq T$, and
3. $f$ is submodular.

Then the set of sets $\mathcal{I}$, defined as follows, is the independent sets of a matroid [2], which we denote by $\mathcal{M}(f)$

$\mathcal{I} := \{I \subseteq E: |I’| \le f(I’) \ {\rm for \ all \ } I’ \subseteq I\}$.

If $r_1,r_2: 2^E \rightarrow \mathbb{Z}$ are rank functions of matroids $M_1$ and $M_2$, then $r_1$ and $r_2$ satisfy the necessary properties to apply Edmonds’ construction, and $\mathcal{M}(r_i) = M_i$. The sum $r_1 + r_2$ also satisfies these conditions but is no longer the rank function of a matroid. The matroid $\mathcal{M}(r_1 + r_2)$ should be familiar to readers of this this blog especially – it is the matroid union of $M_1$ and $M_2$. The function $r_1 + r_2 – 1$ also satisfies the conditions required for Edmond’s construction. We can now state how the matroid of a Hadamard product of linear spaces relates to the matroids of the individual linear spaces.

Theorem [1]: Let $L_1,L_2 \subseteq \mathbb{C}^E$ be linear spaces and let $r_i$ denote the rank function of $\mathcal{M}(L_i)$. Then $\mathcal{M}(L_1 \star L_2) = \mathcal{M}(r_1 + r_2 -1)$.

The above theorem fails if one does not require $L_1$ and $L_2$ to be linear spaces. For example, if $L_1 = L_2 = V$ is a toric variety, then $V \star V = V$ and so the formula above cannot work. It also fails if one tries to naively generalize to more than two linear spaces. More specifically, if $L_1,\dots,L_d \subseteq \mathbb{C}^E$ are all linear spaces and $r_i$ denotes the rank function of $\mathcal{M}(L_i)$, then I once conjectured that $\mathcal{M}(L_1 \star \dots \star L_d) = \mathcal{M}(r_1 + \dots + r_d – (d-1))$. This was recently proven false in [3].

References

[1] Bernstein, Daniel Irving. “Generic symmetry-forced infinitesimal rigidity: translations and rotations.” SIAM Journal on Applied Algebra and Geometry 6.2 (2022): 190-215.

[2] Jack Edmonds. Matroids, submodular functions and certain polyhedra. Combinatorial Structures and Their Applications, pages 69–87, 1970.

[3] Antolini, Dario, Sean Dewar, and Shin-ichi Tanigawa. “Dilworth truncations and Hadamard products of linear spaces.” arXiv preprint arXiv:2508.04798 (2025).

My PhD student, Nate Vaduthala, and I have been working on a paper about flag matroids that will (hopefully) hit the arXiv in the next week or two. In this blog post, I will give an introduction to flag matroids with particular attention to representability questions, and then state one of our results about flag matroids that are representable over the field of order 2.

Given a field $\mathbb{K}$ and a finite set $E$, we let $\mathbb{K}^E$ denote the $\mathbb{K}$-vector space with a distinguished set of coordinates indexed by $E$. Each $S \subseteq E$ gives a coordinate projection $\pi_S: \mathbb{K}^E \rightarrow \mathbb{K}^S$ that sends each $(x_e)_{e \in E}$ to $(x_e)_{e \in S}$. Each linear subspace $L \subseteq \mathbb{K}^E$ defines a representable matroid $\mathcal{M}_L$ where $S \subseteq E$ is independent whenever $\pi_S(L)$ has dimension $|S|$. Thus one can view matroids as a combinatorial abstraction of linear subspaces.

Now suppose we have two nested linear subspaces $L_1 \subsetneq L_2 \subseteq \mathbb{K}^E$. Then every flat of $\mathcal{M}_{L_2}$ is a flat of $\mathcal{M}_{L_1}$, as the reader might be able to deduce. In light of this, given two matroids $\mathcal{M}$ and $\mathcal{N}$ on the same ground set $E$, one says that $\mathcal{N}$ is a lift of $\mathcal{M}$ if every flat of $\mathcal{N}$ is a flat of $\mathcal{M}$.

Finally, suppose we have a flag, i.e. a sequence of nested linear subspaces $L_1 \subsetneq \dots \subsetneq L_k \subseteq \mathbb{K}^E$. Then $\mathcal{M}_{L_{i+1}}$ is a lift of $\mathcal{M}_{L_i}$ for each $i$. Then, a sequence of matroids $\mathfrak{F} = (M_1,\dots,M_k)$ on the same ground set $E$ is called a flag matroid if $M_{i+1}$ is a lift of $M_i$ for each $i$. This implies that ${\rm rank}(M_i) < {\rm rank}(M_{i+1})$. If ${\rm rank}(M_{i+1}) = {\rm rank}(M_i) + 1$ for each $i$, then we say that $\mathfrak{F}$ is saturated. A flag matroid $\mathfrak{F}$ that can be expressed as $\mathcal{M}_{L_1},\dots,\mathcal{M}_{L_k}$ for a flag $L_1 \subsetneq \dots \subsetneq L_k$ of subspaces of a $\mathbb{K}$-vector space are called $\mathbb{K}$-representable and the corresponding sequence of linear spaces is called a $\mathbb{K}$-representation of $\mathfrak{F}$.

On a concrete level, a $\mathbb{K}$-representation of a flag matroid $\mathfrak{F} = (M_1,\dots,M_k)$ is a matrix $A \in \mathbb{K}^{r\times n}$ such that the first ${\rm rank}(M_i)$ rows of $A$ are a representation of $M_i$ for each $i$. For example, recall that $U_{r,n}$ denotes the uniform matroid of rank $r$ on $n$ elements and consider the flag matroid

$\mathfrak{F} = (U_{1,3},U_{2,3})$.

Then if $\mathbb{K}$ is a field with at least three elements, the following is a $\mathbb{K}$-representation of $\mathfrak{F}$

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

Note that if $\mathbb{K}$ is the field with two elements, then there is no $\mathbb{K}$-representation of $\mathfrak{F}$ even though both $U_{1,3}$ and $U_{2,3}$ are both $\mathbb{K}$-representable as matroids. Indeed, since the first row of such a matrix has to be a representation of $U_{1,3}$, this implies that the first row must be all ones, which will then imply that at least two of the columns are the same so the full matrix will not be a representation of $U_{2,3}$.

Given a field $\mathbb{K}$, one can ask: does there exist a “nice” characterization of the $\mathbb{K}$-representable flag matroids? Just as with matroids, we can do this by establishing a theory of minors for flag matroids, and then give a forbidden minor characterization. So far, we have been able to do this for saturated flag matroids that are representable over the fields with two and three elements.

Duals and Minors of flag matroids

The notions of deletion, contraction, and duality extend to flag matroids. Let $\mathfrak{F} = (M_1,\dots,M_k)$ be a flag matroid on ground set $E$. The dual of $\mathfrak{F}$, denoted $\mathfrak{F}^*$, is $(M_k^*,\dots,M_1^*)$ where $M^*$ denotes the dual of a matroid $M$. Given $e \in E$, we define the deletion and contraction $\mathfrak{F}\setminus e$ and $\mathfrak{F} / e$ by doing the corresponding operations on their constituent matroids, i.e.

$\mathfrak{F} \setminus e := (M_1 \setminus e, \dots, M_k \setminus e)$

and

$\mathfrak{F} / e := (M_1 /e, \dots, M_k / e)$.

If two constituent matroids become the same after deleting or contracting an element, we remove that matroid and reindex. Just as with matroids, contraction and deletion are dual operations, i.e.

$\mathfrak{F} / e = (\mathfrak{F}^*\setminus e)^*$.

Our theory of minors for flag matroids requires one more operation that does not have an analogue in the matroid setting. In particular, a flag matroid obtained from $\mathfrak{F}$ by removing a constituent matroid is called a chopping. Note that a chopping of a saturated flag matroid will only be saturated if the highest or lowest matroid is removed. Any flag matroid obtained from $\mathfrak{F}$ via a sequence of deletion, contraction, and chopping operations is called a minor of $\mathfrak{F}$.

Proposition. Let $\mathfrak{F}$ be a flag matroid and let $\mathbb{K}$ be a field. Then if $\mathfrak{F}$ is $\mathbb{K}$-representable, so is $\mathfrak{F}^*$ and any minor of $\mathfrak{F}$.

In principle, the above proposition allows us to characterize the class of $\mathbb{K}$-representable flag matroids by giving a list of minimally non-$\mathbb{K}$-representable minors. When $\mathbb{K}$ has two elements, we have the following forbidden minor characterization of the $\mathbb{K}$-representable flag matroids.

Theorem: Let $\mathfrak{F}$ be a saturated flag matroid. Then $\mathfrak{F}$ is representable over the two-element field if and only if $\mathfrak{F}$ has no minors of the form $(U_{1,3},U_{2,3})$ or $U_{2,4}$.

We also have a forbidden-minor characterization for the saturated flag matroids that are representable over the field with three elements. We use the notation $F_7$ to denote the fano matroid and $F_7^*$ to denote its dual.

Theorem: Let $\mathfrak{F}$ be a saturated flag matroid. Then $\mathfrak{F}$ is representable over the three element field if and only if $\mathfrak{F}$ has no minors of the form $R$ or $(R/e, R \setminus e)$ where $R \in \{U_{2,5},U_{3,5},F_7,F_7^*\}$.

Within the next week or two, we hope to have our preprint on the arXiv, so stay tuned! Flag matroids are an interesting and potentially quite fruitful line of research for matroid theorists, as many of the same questions about representability can be asked.

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.