Algebraic matroids

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.

The converse of the above statement is false – the non-Pappus matroid is algebraic over every field, but not representable over $\mathbb{Q}$.

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.

Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.