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 is a finite set and is a field, we saw that a -matroid on is the same thing as a linear subspace of , and if is the Krasner hyperfield then a -matroid on is the same thing as a matroid in the usual sense. Matroids over the hyperfield of signs are the same thing as oriented matroids, and matroids over the tropical hyperfield 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 be a field. One canonical way to encode a linear subspace of with a finite amount of data is via the Plücker vector of , or equivalently the Grassmann-Plücker function defined in our previous post. Another way is through the elementary vectors of , which we now define.
The support of a vector is the set of such that . If is a linear subspace, the elementary vectors of are the support-minimal elements of . It is a pleasant exercise in linear algebra to show that the set of projective equivalence classes of elementary vectors of (i.e., elementary vectors up to scalar multiplication) is finite, and the elementary vectors of span (and in particular uniquely determine ).
For example, if is the span in of and , the elementary vectors of are all scalar multiples of , and .
In the language of matroids, the supports of elementary vectors of are the circuits of the linear matroid associated to . In terms of circuits of -matroids, which we will define in a moment, the elementary vectors themselves will be the circuits of considered as a matroid over . With this in mind, we note that the set of elementary vectors of has the following properties:
(E1) If and , then .
(E2) If and , then there exists such that .
(E3) If , , and , then there exists with such that . Moreover, if does not properly contain any union with , , then we may take .
Property (E3) follows from the fact (which we leave as an exercise) that every vector can be written as a sum of elementary vectors whose supports are contained in the support of . (For the second part of (E3), note that the condition on implies that must be an elementary vector.)
Circuit axioms for matroids over hyperfields
Let be a collection of pairwise incomparable nonempty subsets of . We say that form a modular pair in if and does not properly contain a union of two distinct elements of .
If is a hyperfield and , we write for the support of , i.e., the set of such that . If and , we say that are a modular pair in if are a modular pair in
Theorem 1: Let be a doubly distributive hyperfield and let . There is a natural bijection between -matroids on (defined in terms of projective equivalence classes of Grassman-Plücker functions) and collections satisfying:
(C1) If and , then .
(C2) [Incomparability] If and , then there exists such that .
(C3) [Elimination] If with and is such that , then there exists such that Moreover, if are a modular pair in then we may choose such that and for all .
We call the set of circuits of the -matroid . The restriction to modular pairs in the second part of axiom (C3) is necessary by an example due to Anderson and Delucchi.
When is the Krasner hyperfield, we may identify elements of with subsets of 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 are a modular pair and is such that , then there exists such that and for all .
It is not difficult to check that if is an -matroid on whose collection of circuits is denoted , then is the collection of circuits of a matroid in the usual sense on , which we call the underlying matroid of .
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 be a hyperfield. The inner product of two vectors is We call and orthogonal, denoted , if . If , we denote by the orthogonal complement of , i.e., the set of all such that for all .
Theorem 2: Let be a doubly distributive hyperfield, and let be an -matroid of rank on with circuit set and Grassmann-Plücker function
Then there is an -matroid of rank on , called the dual -matroid of , with the following properties:
1. The circuits of are the elements of of minimal non-empty support.
2. has the Grassmann-Plücker function where is any ordering of
3. The underlying matroid of is the dual of the underlying matroid of .
The deepest part of Theorem 2 is the fact that the elements of 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 -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 be a (classical) matroid on . We call a subset of an -signature of if it is closed under multiplication by nonzero elements of and is the set of circuits of .
We call a dual pair of -signatures of if:
(DP1) is an -signature of .
(DP2) is an -signature of the dual matroid .
(DP3) , meaning that for all and .
Theorem 3: Let be a doubly distributive hyperfield and let . There is a natural bijection between -matroids on and matroids on together with a dual pair of -signatures of .
Homomorphisms of hyperrings and push-forwards
The passage from an -matroid to its underlying matroid 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 such that ,
, and for .
Lemma: Let be doubly distributive hyperfields. If is a hyperring homomorphism and is an -matroid on with Grassmann-Plücker function and collection of circuits , there is an -matroid on , called the push-forward of , whose Grassmann-Plücker function is and whose collection of circuits is
If is a hyperfield, there is a canonical homomorphism sending to and all non-zero elements of to . If is doubly distributive and is an -matroid, the push-forward coincides with the underlying matroid .
A matroid on is realizable over a field , in the usual sense of matroid theory, if and only if there is a -matroid on such that , where 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 be a commutative ring with .
Example 1: A hyperring homomorphism from to the Krasner hyperfield is the same thing as a prime ideal of , via the correspondence , where the kernel of is (Colloquially speaking, this means that represents the functor Spec on commutative rings.)
Example 2: A hyperring homomorphism from to the tropical hyperfield is the same thing as a prime ideal of together with a real valuation on the residue field of (i.e., the fraction field of ). In particular, a hyperring homomorphism from a field to is the same thing as a real valuation on . (This illustrates a close connection between and the Berkovich spectrum of .)
Example 3: A hyperring homomorphism from to the hyperfield of signs is the same thing as prime ideal together with an ordering (in the sense of ordered fields) on the residue field of . In particular, a hyperring homomorphism from a field to is the same thing as an ordering on . (This illustrates a close connection between and the real spectrum of .)