Guest Post by Matt Baker.

In this post I’d like to explain a new generalization of matroids developed in this recent paper with Nathan Bowler (referred to henceforth as [BB]). We show that by working over certain algebraic structures which we call tracts, linear subspaces, matroids, valuated matroids, oriented matroids, and matroids over partial fields all become special cases of a single general concept. Actually, there are at least two natural notions of matroids over tracts, which we call weak and strong matroids, but in many cases of interest (such as all the ones mentioned above) the two notions coincide.

Two important special cases of tracts are hyperfields and partial fields. We assume familiarity with the theory of partial fields (see for example this post and its sequels by Stefan van Zwam).

Hyperfields

Roughly speaking, a hyperfield is an algebraic structure satisfying similar axioms to a field, but where addition is allowed to be multi-valued. Like fields, hyperfields come equipped with an additive identity element called zero and a negation map $x \mapsto -x$. However, one does not require that the hypersum of $ x$ and $ -x$ is zero, only that zero is contained in the hypersum. Before giving a precise axiomatic definition, let us give some motivating examples.

1. (Fields) Any field $ K$ is in particular a hyperfield.
2. (The Krasner hyperfield) The Krasner hyperfield $ {\mathbb K}$ records the arithmetic of “zero” versus “nonzero”. Specifically, define $ {\mathbb K} = \{ 0,1 \}$ together with the binary operation $ 0 \odot 0 = 0, 0 \odot 1 = 0, 1 \odot 1 = 1$ and the binary hyperoperation $ 0 \boxplus 0 = \{ 0 \}, 0 \boxplus 1 = \{ 1 \}, 1 \boxplus 1 = \{ 0,1 \}$. If we think of $ 1$ as representing “nonzero”, the hyperaddition rules just say that zero plus zero is zero and zero plus something nonzero is always nonzero, but the sum of two things which are nonzero could be either zero or nonzero. The negation operator is the identity map, since negative zero is zero and the negative of something nonzero is again nonzero.
3. (The hyperfield of signs) The hyperfield of signs $ {\mathbb S}$ records the arithmetic of “zero”, “positive”, and “negative”, represented by the symbols $ 0, 1, -1$, respectively. The product $ x \odot y$ is defined in the obvious way for $ x,y \in {\mathbb S} := \{ 0, 1, -1 \}$. Addition is also defined in the “obvious” way except we have $ 1 \boxplus -1 = \{ 0, 1, -1 \}$ since the sum of a positive number and a negative number could be either zero, positive, or negative. The negation operator takes $ 0$ to itself and interchanges $ 1$ and $ -1$.
4. (The tropical hyperfield) The tropical hyperfield $ {\mathbb T}$ records the arithmetic of valuations. More precisely, if $ v : K \to {\mathbb T} := {\mathbb R} \cup \{ \infty \}$ is the valuation map on a valued field $ K$ with value group $ {\mathbb R}$, the hypersum $ a \boxplus b$ consists of all possible values of $ v(\alpha+\beta)$ where $ \alpha,\beta$ are elements of $ K$ with $ v(\alpha)=a$ and $ v(\beta)=b$. (Note that the axioms for a valuation tell us that $ v(\alpha \cdot\beta) = a + b$.) Concretely, this means that we should define $ a \odot b := a + b$ (with the evident conventions when one of $ a,b$ equals $ \infty$), and we define $ a \boxplus b := {\rm min}(a,b)$ if $ a \neq b$ and $ a \boxplus a := \{ z \in {\mathbb T} \; : \; z \geq a \}$. The multiplicative identity element is $ 0$ and the additive identity element is $ \infty$. The negation operator is the identity map, since the unique value of $ b$ such that $ \infty \in a \boxplus b$ is $ b = a$.

The above examples all have an additional property not shared by all hyperfields: they are doubly distributive (see below for the definition). Here are two examples of hyperfields which are not doubly distributive:

5. (The triangle hyperfield) Let $ {\mathbb V}$ be the set $ {\mathbb R}_{\geq 0}$ of nonnegative real numbers with the usual multiplication and the hyperaddition rule $ a \boxplus b := \{ c \in {\mathbb R}_{\geq 0} \; : \; |a-b| \leq c \leq a+b \}.$ In other words, $ a \boxplus b$ is the set of all real numbers $ c$ such that there exists a (possibly degenerate) Euclidean triangle with side lengths $ a, b, c$. Then $ {\mathbb V}$ is a hyperfield.

6. (The phase hyperfield) The phase hyperfield $ {\mathbb P}$ records the arithmetic of phases of complex numbers. If $ \pi : {\mathbb C} \to {\mathbb P} := S^1 \cup \{ 0 \}$ is the map taking 0 to 0 and $ z \in {\mathbb C}^*$ to $ z/|z|$, and if $ a,b \in {\mathbb P}$, the hypersum $ a \boxplus b$ consists of all possible values of $ \pi(\alpha + \beta)$ where $ \alpha,\beta$ are elements of $ {\mathbb C}$ with $ \pi(\alpha)=a$ and $ \pi(\beta)=b$. More precisely, multiplication in $ {\mathbb P}$ is defined as usual, and the hyperaddition law is defined for $ x,y \neq 0$ by setting $ x \boxplus -x := \{ 0, x, -x \}$ and $ x \boxplus y := \{ \frac{\alpha x + \beta y}{\| \alpha x + \beta y \|} \; | \; \alpha, \beta \in {\mathbb R}_{>0} \}$ otherwise.
Motivated by Proposition 1, if $ F$ is a tract we define a strong $ F$-matroid (or strong matroid over $ F$) of rank $ r$ on $ E$ to be a projective equivalence class of Grassmann-Plücker functions $ \varphi : E^r \to F$. Thus strong matroids over fields are the same as linear subspaces, and strong matroids over the Krasner hyperfield are the same as matroids in the usual sense. (By a matroid over a partial hyperfield $ F$, we mean a matroid over the corresponding tract.) One can also show that strong matroids over a partial field $ P$ are the same as matroids representable over $ P$ in the usual sense.

Definition of hyperrings and hyperfields

A hyperoperation on a set $ S$ is a map $ \boxplus$ from $ S \times S$ to the collection of non-empty subsets of $ S$.

If $ A,B$ are non-empty subsets of $ S$, we define $ A \boxplus B := \bigcup_{a \in A, b \in B} (a \boxplus b)$ and we say that $ \boxplus$ is associative if $ a \boxplus (b \boxplus c) = (a \boxplus b) \boxplus c$ for all $ a,b,c \in S$.

A (commutative) hyperring is a set $ R$ together with:

1. A commutative and associative binary operation $ \odot$
2. A commutative and associative binary hyperoperation $ \boxplus$
3. Distinguished elements $ 0,1 \in R$

such that:

1. $ (R, \odot, 1)$ is a commutative monoid.
2. $ 0 \odot x = x \odot 0 = 0$ and $ 0 \boxplus x = x \boxplus 0 = \{ x \}$ for all $ x \in R.$
3. For every $ x \in R$ there is a unique element of $ R$ (denoted $ -x$) such that $ 0 \in x\boxplus -x.$
4. $ a \odot (x \boxplus y) = (a \odot x) \boxplus (a \odot y)$ for all $ a,x,y \in R.$

A hyperring $ R$ is called a hyperdomain if $ xy=0$ in $ R$ implies that $ x=0$ or $ y=0$.

A hyperring $ R$ is called doubly distributive if it satisfies $ (a \boxplus b)\odot (c \boxplus d) = (a\odot c) \boxplus (a \odot d) \boxplus (b \odot c) \boxplus (b\odot d)$ for all $ a,b,c,d \in R$.

A hyperring $ F$ is called a hyperfield if $ 0 \neq 1$ and every non-zero element of $ F$ has a multiplicative inverse.

Partial hyperfields

A partial hyperfield is a pair $ (G,R)$, where $ G$ is a subgroup of the group of units of a hyperdomain $ R$ such that $ -1 \in R$ and $ G$ generates $ R$ as a hyperring.

We set $ P := G \cup \{ 0 \}$, and denote the partial hyperfield $ (G,R)$ simply by $ P$ when no confusion is likely to arise.

Partial hyperfields generalize both hyperfields and partial fields in a natural way.  When $ R$ is a ring, $ P$ is just a partial field, and when $ G = R \backslash \{ 0 \}$ is a group, $ P$ is just a hyperfield.

A partial hyperfield is called doubly distributive if the ambient hyperring $ R$ is doubly distributive.

Tracts

Partial hyperfields are special cases of still more general objects called tracts, which appear to be a natural setting for matroid theory.

We define a tract to be an abelian group $ G$ (written multiplicatively), together with a subset $ N_G$ of the group semiring $ {\mathbb N}[G]$ satisfying:

(T0) The zero element of $ {\mathbb N}[G]$ belongs to $ N_G$.
(T1) The identity element 1 of $ G$ is not in $ N_G$.
(T2) There is a unique element $ \epsilon$ of $ G$ with $ 1 + \epsilon \in N_G$.
(T3) $ N_G$ is closed under the natural action of $ G$ on $ {\mathbb N}[G]$.

We set $ F := G \cup \{ 0 \} \subset {\mathbb N}[G]$, and refer to the tract $ (G,N_G)$ simply as $ F$ when no confusion is likely to arise.  We will also sometimes write $ F^\times$ instead of $ G$, and $ -1$ instead of $ \epsilon$.

One thinks of $ N_G$ as those linear combinations of elements of $ G$ which “sum to zero” (the $ N$ in $ N_G$ stands for “null”).

Tracts from partial hyperfields

We can associate a tract to a partial hyperfield $ (G,R)$ by declaring that a formal sum $ \sum a_i g_i \in {\mathbb N}[G]$ belongs to $ N_G$ if and only if $ 0 \in \boxplus a_i g_i$ in $ R$.

We note, for the experts, that one can associate a tract to any fuzzy ring in the sense of Dress and Dress-Wenzel, and that if $ P$ is a doubly distributive partial hyperfield there is an associated fuzzy ring whose realization as a tract coincides with the realization of $ P$ itself as a tract.

Grassmann-Plücker functions over tracts

Now let $ F$ be a tract.  A function $ \varphi : E^r \to F$ is called a Grassmann-Plücker function if it is nonzero, alternating (meaning that $ \varphi(x_1,\ldots,x_i, \ldots, x_j, \ldots, x_r)= -\varphi(x_1,\ldots,x_j, \ldots, x_i, \ldots, x_r)$ and $ \varphi(x_1,\ldots, x_r) = 0$ if $ x_i = x_j$ for some $ i \neq j$), and it satisfies the following generalization of the classical Grassmann-Plücker relations:

(GP) For any two subsets $ X := \{ x_1,\ldots,x_{r+1} \}$ and $ Y := \{ y_1,\ldots,y_{r-1} \}$ of $ E$,
$ \sum_{k=1}^{r+1}  (-1)^k \varphi(x_1,x_2,\ldots,\hat{x}_k,\ldots,x_{r+1}) \cdot \varphi(x_k,y_1,\ldots,y_{r-1}) \in N_G.$

If $ F=K$ is a field then a projective equivalence class of Grassmann-Plücker functions $ \varphi : E^r \to K$ is the same thing as an $ r$-dimensional subspace of $ K^m$.  This is essentially just the assertion that the usual Grassmannian variety is cut out by the Plücker equations.

On the other hand:

Proposition 1: If $ F = {\mathbb K}$ is the Krasner hyperfield, a projective equivalence class of Grassmann-Plücker functions $ \varphi : E^r \to {\mathbb K}$ is the same thing as a rank $ r$ matroid on $ E$.

Indeed, if $ \varphi : E^r \to {\mathbb K}$ is a nonzero alternating function and $ {\mathbf B}_\varphi$ denotes the set of $ r$-element subsets $ \{ e_1,\ldots, e_r \}$ of $ E$ such that $ \varphi(e_1,\ldots,e_r) \neq 0$, it is easy to see that $ {\mathbf B} := {\mathbf B}_\varphi$ satisfies the Grassmann-Plücker relations (GP) if and only if

(BE) Given $ B,B’ \in {\mathbf B}$ and $ b \in B \backslash B’$, there exists $ b’ \in B’ \backslash B$ such that both $ (B \cup \{ b’ \}) \backslash \{ b \}$ and $ (B’ \cup \{ b \}) \backslash \{ b’ \}$ are in $ {\mathbf B}$.

But condition (BE) is well-known to be equivalent to the usual Basis Exchange property for matroids!  In other words, $ {\mathbf B}_\varphi$ is the set of bases of a rank $ r$ matroid $ M_{\varphi}$ on $ E$.  Conversely, given such a matroid $ M$, we can define $ \varphi_M : E^r \to {\mathbb K}$ by setting $ \varphi_M(e_1,\ldots,e_r) = 1$ if $ \{ e_1,\ldots,e_r \}$ is a basis of $ M$ and $ \varphi_M(e_1,\ldots,e_r) = 0$ if not.  By the exchange property (BE), the function $ \varphi_M(e_1,\ldots,e_r)$ will satisfy (GP).

Motivated by Proposition 1, if $ F$ is a tract we define a strong $ F$-matroid (or strong matroid over $ F$) of rank $ r$ on $ E$ to be a projective equivalence class of Grassmann-Plücker functions $ \varphi : E^r \to F$.  Thus strong matroids over fields are the same as linear subspaces, and strong matroids over the Krasner hyperfield are the same as matroids in the usual sense.   (By a matroid over a partial hyperfield $ F$, we mean a matroid over the corresponding tract.)  One can also show that strong matroids over a partial field $ P$ are the same as matroids representable over $ P$ in the usual sense.

We have the following additional interesting examples of (strong) matroids over tracts:

Proposition 2: If $ F = {\mathbb S}$ is the hyperfield of signs, a matroid over $ {\mathbb S}$ is the same thing as an oriented matroid.

Proposition 3: If $ F = {\mathbb T}$ is the tropical hyperfield, a matroid over $ {\mathbb T}$ is the same thing as a valuated matroid.

Proposition 4: If $ F = {\mathbb U}_0$ is the regular partial field $ (\{ \pm1 \}, {\mathbb Z})$, a matroid over $ {\mathbb U}_0$ is the same thing as a regular matroid.

Weak matroids over tracts

It is also of interest to consider objects which satisfy a weaker version of (GP), where we consider only the three-term Grassmann-Plücker relations. Specifically, a weak $ F$-matroid is a projective equivalence class of nonzero alternating functions $ \varphi : E^r \to F$ such that (a) $ {\mathbf B}_\varphi$ is the set of bases for a (classical) matroid on $ E$, and (b) $ \varphi$ satisfies (GP) for all $ X,Y$ with $ |X \backslash Y| = 3$.

It will turn out that in Propositions 1-4 above, strong and weak $ F$-matroids are the same.

Circuit axioms for matroids over tracts

Let $ {\mathcal C}$ be a collection of pairwise incomparable nonempty subsets of $ E$. We say that $ C_1,C_2 \in {\mathcal C}$ form a modular pair in $ {\mathcal C}$ if $ C_1 \neq C_2$ and $ C_1 \cup C_2$ does not properly contain a union of two distinct elements of $ {\mathcal C}$.

If $ F$ is a tract and $ X \in F^m$, we write $ \underline{X}$ for the support of $ X$, i.e., the set of $ i \in \{ 1,\ldots,m \}$ such that $ X_i \neq 0$. If $ {\mathcal C} \subset F^m$ and $ X,Y \in {\mathcal C}$, we say that $ X,Y$ are a modular pair in $ {\mathcal C}$ if $ \underline{X},\underline{Y}$ are a modular pair in $ \underline{\mathcal C} := \{ \underline{X} \; : \; X \in {\mathcal C} \}.$

Theorem 1: Let $ F$ be a tract and let $ E = \{ 1,\ldots,m \}$. There is a natural bijection between weak $ F$-matroids on $ E$ and collections $ {\mathcal C} \subset F^m$ satisfying:

(C0) $ 0 \not\in {\mathcal C}$.
(C1) If $ X \in {\mathcal C}$ and $ \alpha \in F^\times$, then $ \alpha \cdot X \in {\mathcal C}$.
(C2) [Incomparability] If $ X,Y \in {\mathcal C}$ and $ \underline{X} \subseteq \underline{Y}$, then there exists $ \alpha \in F^\times$ such that $ X = \alpha \cdot Y$.
(C3) [Modular Elimination] If $ X,Y \in {\mathcal C}$ are a modular pair in $ {\mathcal C}$ and $ e \in E$ is such that $ X_e= -Y_e \neq 0$, there exists $ Z \in {\mathcal C}$ such that $ Z_e=0$ and $ X_f + Y_f – Z_f \in N_G$ for all $ f \in E$.

We call $ {\mathcal C}$ the set of $ F$-circuits of the weak $ F$-matroid $ M$.

In [BB], there is also a stronger version of the circuit elimination axiom (C3) which gives a cryptomorphic characterization of strong $ F$-matroids in terms of circuits. Let’s say that a family of atomic elements of a lattice is modular if the height of their join in the lattice is the same as the size of the family. If $ \mathcal C$ is a subset of $ F^m$, a modular family of elements of $ \mathcal C$ is one such that the supports give a modular family of elements in the lattice of unions of supports of elements of $ \mathcal C$.

Then there is a natural bijection between strong $ F$-matroids on $ E$ and collections $ {\mathcal C} \subset F^m$ satisfying (C0),(C1),(C2), and the following stronger version of the modular elimination axiom (C3):

[Strong modular elimination] Suppose $ X_1,\ldots,X_k$ and $ X$ are $ F$-circuits of $ M$ which together form a modular family of size $ k+1$ such that $ \underline X \not \subseteq \bigcup_{1 \leq i \leq k} \underline X_i$, and for $ 1 \leq i \leq k$ let $ e_i \in (X \cap X_i) \setminus \bigcup_{\substack{1 \leq j \leq k \\ j \neq i}} X_j$ be such that $ X(e_i) = -X_i(e_i) \neq 0$. Then there is an $ F$-circuit $ Z$ such that $ Z(e_i) = 0$ for $ 1 \leq i \leq k$ and $ X_1(f) + \cdots + X_k(f) + X(f) – Z(f) \in N_G$ for every $ f \in E$.

Duality

There is a duality theory for matroids over tracts which generalizes the known duality theories for matroids, oriented matroids, valuated matroids, etc., and which corresponds to orthogonal complementation for matroids over fields.

Let $ F$ be a tract. The inner product of two vectors $ X,Y \in F^m$ is $ X \cdot Y := \sum_{i=1}^m X_i \cdot Y_i.$ We call $ X$ and $ Y$ orthogonal, denoted $ X \perp Y$, if $ X \cdot Y \in N_G$. If $ S \subset F^m$, we denote by $ S^\perp$ the orthogonal complement of $ S$, i.e., the set of all $ X \in F^m$ such that $ X \perp Y$ for all $ Y \in S$.

If $ M$ is a (weak or strong) $ F$-matroid on $ E$ whose collection of circuits is denoted $ {\mathcal C}$, then $ \underline{M} := \{ \underline{X} \; : \; X \in {\mathcal C} \}$ is the collection of circuits of a matroid in the usual sense on $ E$, which we call the underlying matroid of $ M$.

Theorem 2: Let $ F$ be a tract, and let $ M$ be a (weak, resp. strong) $ F$-matroid of rank $ r$ on $ E=\{ 1,\ldots,m \}$ with $ F$-circuit set $ {\mathcal C}$ and Grassmann-Plücker function $ \varphi.$
Then there is a (weak, resp. strong) $ F$-matroid $ M^*$ of rank $ m-r$ on $ E$, called the dual $ F$-matroid of $ M$, with the following properties:

1. The $ F$-circuits of $ M^*$ are the elements of $ {\mathcal C}^\perp$ of minimal non-empty support.

2. $ M^*$ has the Grassmann-Plücker function $ \varphi^*(x_1,\ldots,x_{m-r}) = {\rm sign}(x_1,\ldots,x_{m-r},x_1′,\ldots,x_r’) \varphi(x_1′,\ldots,x_r’),$ where $ x_1′,\ldots,x_r’$ is any ordering of $ E \backslash \{ x_1,\ldots,x_{m-r} \}.$

3. The underlying matroid of $ M^*$ is the dual of the underlying matroid of $ M$.

4. $ M^{**} = M$.

The deepest part of Theorem 2 is the fact that the elements of $ {\mathcal C}^\perp$ of minimal non-empty support satisfy the circuit elimination axiom (C3) (or its strong variant).

Dual pair axioms for matroids over hyperfields

One can give another cryptomorphic characterization of $ F$-matroids using the notion of dual pairs. It is perhaps the simplest of all descriptions of matroids over tracts, but it presupposes that one already knows what a (usual) matroid is.

Let $ M$ be a (classical) matroid on $ E$. We call a subset $ {\mathcal C}$ of $ F^m$ an $ F$-signature of $ M$ if it is closed under multiplication by nonzero elements of $ F$ and $ \underline{\mathcal C} := \{ \underline{X} \; : \; X \in {\mathcal C} \}$ is the set of circuits of $ M$.

We call $ ({\mathcal C},{\mathcal D})$ a dual pair of $ F$-signatures of $ M$ if:

(DP1) $ {\mathcal C}$ is an $ F$-signature of $ M$.
(DP2) $ {\mathcal D}$ is an $ F$-signature of the dual matroid $ M^*$.
(DP3) $ {\mathcal C} \perp {\mathcal D}$, meaning that $ X \perp Y$ for all $ X \in {\mathcal C}$ and $ Y \in {\mathcal D}$.

Theorem 3: Let $ F$ be a tract and let $ E = \{ 1,\ldots,m \}$. There is a natural bijection between strong $ F$-matroids on $ E$ and matroids $ M$ on $ E$ together with a dual pair of $ F$-signatures of $ M$.

An analogous theorem holds for weak $ F$-matroids if we only require that (DP3) holds when $ |\underline{X} \cap \underline{Y}| \leq 3$.

Vectors, perfection, and double distributivity

Given a tract $ F$ and a strong $ F$-matroid $ M$ on $ E$ with $ F$-circuit set $ \mathcal C$ and $ F$-cocircuit set $ \mathcal C^*$, a vector of $ M$ is an element of $ F^m$ which is orthogonal to everything in $ \mathcal C^*$. Similarly a covector of $ M$ is an element of $ F^m$ which is orthogonal to everything in $ \mathcal C$. We say that $ F$ is perfect if, for any strong matroid $ M$ over $ F$, all vectors are orthogonal to all covectors.

Theorem 4: Let $ F$ be a tract.

1. If $ F$ is perfect, then the notions of weak and strong $ F$-matroids coincide.

2. Every doubly distributive partial hyperfield is perfect.

As a consequence, we see that the notions of weak and strong $ F$-matroids coincide for doubly distributive partial hyperfields $ F$. This holds, in particular, when $ F=P$ is a partial field or when $ F$ is the Krasner hyperfield, the tropical hyperfield, or the hyperfield of signs.

There are examples in [BB] which show that weak and strong $ F$-matroids do not coincide when $ F$ is either the triangle hyperfield or the phase hyperfield.

Some directions for future research

There are many things one would like to know about matroids over tracts which aren’t yet well-understood. Here are some concrete problems which come to mind:

1. Does the theory developed in [BB] also work for tracts in which multiplication is not assumed to be commutative? It would be nice, for example, if one could fold the theory of representations of matroids over skew partial fields (as developed in this paper by Pendavingh and van Zwam) into our framework.
2. Laura Anderson has developed a theory of vectors and covectors for matroids over hyperfields. It would be interesting to resolve some of the conjectures in her paper, for example the Elimination Conjecture 7.2 or Conjecture 6.4 concerning flats.
3. Can one extend the Lift Theorem from this paper by Pendavingh and van Zwam to matroids over tracts?
4. Can one give an “algebraic” characterization of perfect tracts?

We can make Problem #4 a bit more precise. For any perfect tract, the matroids which are strongly representable over the tract are the same as the weakly representable ones, so they are determined by the set $ N_G^{(3)}$ of elements of $ N_G$ which are sums of at most 3 terms. On the other hand, any set of 3-term relations in $ N_G$ can be extended to a perfect tract by just including everything of size at least 4 in $ N_G$. The problem is that this includes a lot of extra stuff in $ N_G$ which might not be needed for strong representability. This motivates looking at the smallest tract extending $ N_G^{(3)}$ which could possibly be perfect, namely the set of all combinations which appear as sums in the GP relations (or the orthogonality relations) for weak matroids over $ N_G^{(3)}$. Could it be that if this tract is perfect then it must satisfy certain algebraic conditions which are also sufficient to guarantee perfection?