Matroids over Hyperfields, Part II

In Part I of this post, we defined hyperrings and hyperfields, gave some key examples, and introduced matroids over (doubly distributive) hyperfields in terms of Grassman-Plücker functions. If $E=\{ 1,\ldots,m \}$ is a finite set and $K$ is a field, we saw that a $K$ -matroid on $E$ is the same thing as a linear subspace of $K^m$ , and if ${\mathbb K}$ is the Krasner hyperfield then a ${\mathbb K}$ -matroid on $E$ is the same thing as a matroid in the usual sense. Matroids over the hyperfield ${\mathbb S}$ of signs are the same thing as oriented matroids, and matroids over the tropical hyperfield ${\mathbb T}$ are the same thing as valuated matroids. In this post we will give some “cryptomorphic” axiomatizations of matroids over hyperfields, discuss duality theory, and then discuss the category of hyperrings in a bit more detail.

Elementary vectors of a subspace

Let $K$ be a field. One canonical way to encode a linear subspace of $K^m$ with a finite amount of data is via the Plücker vector of $W$ , or equivalently the Grassmann-Plücker function $\varphi_W$ defined in our previous post. Another way is through the elementary vectors of $W$ , which we now define.

The support of a vector $v \in K^m$ is the set $\underline{v}$ of $i \in \{ 1,\ldots,m\}$ such that $v_i \neq 0$ . If $W \subset K^m$ is a linear subspace, the elementary vectors of $W$ are the support-minimal elements of $W \backslash \{ 0 \}$ . It is a pleasant exercise in linear algebra to show that the set of projective equivalence classes of elementary vectors of $W$ (i.e., elementary vectors up to scalar multiplication) is finite, and the elementary vectors of $W$ span $W$ (and in particular uniquely determine $W$ ).

For example, if $W$ is the span in ${\mathbb R}^3$ of $(1,2,1)$ and $(0,1,1)$ , the elementary vectors of $W$ are all scalar multiples of $(1,1,0), (0,1,1)$ , and $(1,0,-1)$ .

In the language of matroids, the supports of elementary vectors of $W$ are the circuits of the linear matroid associated to $W$ . In terms of circuits of $F$ -matroids, which we will define in a moment, the elementary vectors themselves will be the circuits of $W$ considered as a matroid over $K$ . With this in mind, we note that the set ${\mathcal E}$ of elementary vectors of $W$ has the following properties:

(E0) $0 \not\in {\mathcal E}$ .
(E1) If $v \in {\mathcal E}$ and $\alpha \in K^\times$ , then $\alpha v \in {\mathcal E}$ .
(E2) If $v,v' \in {\mathcal E}$ and $\underline{v} \subseteq \underline{v'}$ , then there exists $\alpha \in K^\times$ such that $v = \alpha v'$ .
(E3) If $v,v' \in {\mathcal E}$ , $v_i=-v'_i \neq 0$ , and $v \neq -v'$ , then there exists $v'' \in {\mathcal E}$ with $\underline{v''} \subseteq \underline{v} \cup \underline{v'}$ such that $v''_i=0$ . Moreover, if $\underline{v} \cup \underline{v'}$ does not properly contain any union $\underline{w} \cup \underline{w'}$ with $w,w' \in {\mathcal E}$ , $w \neq w'$ , then we may take $v'' = v + v'$ .

Property (E3) follows from the fact (which we leave as an exercise) that every vector $w \in W$ can be written as a sum of elementary vectors whose supports are contained in the support of $w$ . (For the second part of (E3), note that the condition on $\underline{v} \cup \underline{v'}$ implies that $v+v'$ must be an elementary vector.)

Circuit axioms for matroids over hyperfields

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}$ .

The top left and top right cycles form a non-modular pair in the collection of simple cycles of the graph

If $F$ is a hyperfield 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 doubly distributive hyperfield and let $E = \{ 1,\ldots,m \}$ . There is a natural bijection between $F$ -matroids on $E$ (defined in terms of projective equivalence classes of Grassman-Plücker functions) 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 \odot 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 \odot Y$ .
(C3) [Elimination] If $X,Y \in {\mathcal C}$ with $X \neq -Y$ and $e \in E$ is such that $X_e=-Y_e \neq 0$ , then there exists $Z \in {\mathcal C}$ such that $\underline{Z} \subseteq (\underline{X} \cup \underline{Y}) \backslash \{ e \}.$ Moreover, if $X,Y \in {\mathcal C}$ are a modular pair in ${\mathcal C}$ then we may choose $Z \in {\mathcal C}$ such that $Z_e=0$ and $Z_f \in X_f \boxplus Y_f$ for all $f \in E$ .

We call ${\mathcal C}$ the set of circuits of the $F$ -matroid $M$ . The restriction to modular pairs in the second part of axiom (C3) is necessary by an example due to Anderson and Delucchi.

When $F = {\mathbb K}$ is the Krasner hyperfield, we may identify elements of ${\mathbb K}^m$ with subsets of $E$ and axiom (C3) is equivalent to a well-known strong version of the circuit elimination axiom in matroid theory.

One can show that the second part of (C3) implies the first, and thus (C3) can be replaced by:

(C3′) [Modular Elimination] If $X,Y \in {\mathcal C}$ are a modular pair and $e \in E$ is such that $X_e=-Y_e \neq 0$ , then there exists $Z \in {\mathcal C}$ such that $Z_e=0$ and $Z_f \in X_f \boxplus Y_f$ for all $f \in E$ .

It is not difficult to check that if $M$ is an $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$ .

Duality theory

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

Let $F$ be a hyperfield. The inner product of two vectors $X,Y \in F^m$ is $X \odot Y := \boxplus_{i=1}^m X_i \odot Y_i.$ We call $X$ and $Y$ orthogonal, denoted $X \perp Y$ , if $0 \in X \odot Y$ . 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$ .

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

1. The 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).

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 hyperfields, 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^E$ 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 doubly distributive hyperfield and let $E = \{ 1,\ldots,m \}$ . There is a natural bijection between $F$ -matroids on $E$ and matroids $M$ on $E$ together with a dual pair of $F$ -signatures of $M$ .

Homomorphisms of hyperrings and push-forwards

The passage from an $F$ -matroid $M$ to its underlying matroid $\underline{M}$ can be viewed as a special case of a general push-forward operation for matroids over hyperfields. In order to explain this, we need to first define homomorphisms of hyperrings.

A hyperring homomorphism is a map $f : R \to S$ such that $f(0)=0, f(1)=1$ ,
$f(x \odot y)=f(x) \odot f(y)$ , and $f(x \boxplus y) \subseteq f(x) \boxplus f(y)$ for $x,y \in R$ .

Lemma: Let $F,F'$ be doubly distributive hyperfields. If $f : F \to F'$ is a hyperring homomorphism and $M$ is an $F$ -matroid on $E$ with Grassmann-Plücker function $\varphi$ and collection of circuits ${\mathcal C}$ , there is an $F'$ -matroid $f_*(M)$ on $E$ , called the push-forward of $M$ , whose Grassmann-Plücker function is $(f_* \varphi)(e_1,\ldots,e_r) = f(\varphi(e_1,\ldots,e_r))$ and whose collection of circuits is $f_*({\mathcal C}) := \{ c' f_*(X) \; : \; c' \in F', \; X \in {\mathcal C} \}.$

If $F$ is a hyperfield, there is a canonical homomorphism $\psi : F \to {\mathbb K}$ sending $0$ to $0$ and all non-zero elements of $F$ to $1$ . If $F$ is doubly distributive and $M$ is an $F$ -matroid, the push-forward $\psi_*(M)$ coincides with the underlying matroid $\underline{M}$ .

A matroid $M'$ on $E$ is realizable over a field $K$ , in the usual sense of matroid theory, if and only if there is a $K$ -matroid $M'$ on $E$ such that $M' = \psi_*(M)$ , where $\psi : K \to {\mathbb K}$ is the canonical map.

Examples of hyperring homomorphisms

Homomorphisms of hyperrings are interesting in their own right, irrespective of the connection with matroid theory. Here are a few intriguing examples. Let $R$ be a commutative ring with $1$ .

Example 1: A hyperring homomorphism from $R$ to the Krasner hyperfield ${\mathbb K}$ is the same thing as a prime ideal of $R$ , via the correspondence $f \leftrightarrow {\rm ker}(f)$ , where the kernel of $f$ is ${\rm ker}(f) := \{ x \in R \; : \; f(x)=0 \}.$ (Colloquially speaking, this means that ${\mathbb K}$ represents the functor Spec on commutative rings.)

Example 2: A hyperring homomorphism from $R$ to the tropical hyperfield ${\mathbb T}$ is the same thing as a prime ideal ${\mathfrak p}$ of $R$ together with a real valuation on the residue field of ${\mathfrak p}$ (i.e., the fraction field of $R/{\mathfrak p}$ ). In particular, a hyperring homomorphism from a field $K$ to ${\mathbb T}$ is the same thing as a real valuation on $K$ . (This illustrates a close connection between ${\mathbb T}$ and the Berkovich spectrum of $R$ .)

Example 3: A hyperring homomorphism from $R$ to the hyperfield of signs ${\mathbb S}$ is the same thing as prime ideal ${\mathfrak p}$ together with an ordering (in the sense of ordered fields) on the residue field of ${\mathfrak p}$ . In particular, a hyperring homomorphism from a field $K$ to ${\mathbb S}$ is the same thing as an ordering on $K$ . (This illustrates a close connection between ${\mathbb S}$ and the real spectrum of $R$ .)

Matt Baker's Math Blog

Thoughts on number theory, graphs, dynamical systems, tropical geometry, pedagogy, puzzles, and the p-adics

Matroids over Hyperfields, Part II

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply