WorksMathematics
Linear Algebra over Bands
Abstract
We introduce Eckmann-Hilton operators on bands, which allow for a suite of matroidal constructions, in particular, matroid unions and matroid stable intersections. This enables the construction of general linear monoids over bands. Geometrically, we show that matroid stable intersection extends the transverse intersection of linear spaces over fields and the stable intersection of tropical linear spaces, lending new insight into intersection theory on bands.
Introduction
Methods from linear algebra are universally useful in all areas of mathematics. Bands, introduced by Baker-Jin-Lorscheid [3], are a generalization of rings that can be used to describe many settings in algebraic combinatorics, in particular, oriented matroids and tropical linear spaces as in [4]. Their work builds on earlier studies of matroids with coefficients, developed by Baker-Bowler in [2] and originating in work of Dress-Wenzel [5]. Beyond matroid theory, bands provide a unified framework to study algebraic geometry in these settings. For this, methods in linear algebra are useful to define and study universal notions of tangent spaces and vector bundles, as well as many more.
Over a band , the analog of a linear space is a -matroid, introduced in [4]. This leads to challenges in constructing linear maps, as they need to be simultaneously general enough to be useful, and defined matroid theoretically. In this extended abstract, we develop a matroidal analog of matrices, allowing us to model linear maps.
The first obstruction is that formal addition over a band does not yield an element of . We overcome this by introducing an Eckmann-Hilton operator in § 2, which should be thought of as “generic evaluation” of the formal sum over , see Def. 2. Past its existence, most of our constructions require an additional compatibility assumption of the formal sum and the Eckmann-Hilton operator, which we call tolerant, see Def. 4. In the following, we require every band to have an Eckmann-Hilton operator and to be tolerant. Moreover, we denote the additive inverse of in by .
Theorem 1. Let be a tolerant band with an Eckmann-Hilton operator , and let and be two -matroids of rank and over a ground set , such that . Then, the matroid union , defined coordinate-wise on as
is either identically zero or a -matroid of rank on . If is not commutative, the sum is taken in lexicographical order (in the sense of Example 4).
To prove this result, we define several additional matroidal constructions. We show that direct sums (see Def. 5), reorderings (see Def. 6), and contractions along equivalent elements (see Def. 7) of -matroids still satisfy the Grassmann–Plücker relations.
Using these matroidal methods allows us to give a well-defined notion of linear algebra over bands in Section 3. As a stand-in for matrices, we consider a -matroid of rank on with a fixed basis . We call such a matroid a -bimatroid. Unlike -matroids or -matrices, these have a well-defined and well-behaved multiplication. We call the set of full-rank -bimatroids the general linear monoid .
Theorem 2. Let be a tolerant band with an Eckmann-Hilton operator, and let and be full-rank --bimatroids, then the product is a full-rank --bimatroid. Further, the bimatroid product is associative; and the unit bimatroid induced by the identity matrix is a unit of this product. In other words, is a monoid.
In Section 4, we shift to a geometric perspective. In tropical geometry, many statements on valuated matroids can be rewritten as statements about tropical linear spaces. These reformulations often allow for the proof of further statements on bands using geometric intuition.
We first show that the -matroid stable intersection (see Def. 11) is dual to the matroid union of the dual matroids . Using the Eckmann–Hilton operator and Baker-Bowler’s cocircuits [2], we define the -linear space (see Def. 13), which is cryptomorphic to a -matroid for any band in which all nonzero elements are units. Such bands are called idylls in [3].
Theorem 3. Let be a tolerant idyll with an Eckmann-Hilton operator. Let and be -matroids with nonzero matroid stable intersection . Then, the -linear space of is contained in the set-theoretic intersection of -linear spaces for and , i.e.,
with equality under additional assumptions on the transversality of the intersection, convexity of the linear spaces, and fusion property of the band .
In particular, for tropical geometers, Theorems 1 and 3 provide alternative proofs to results on stable sums and stable intersections of valuated matroids in [7, 14]. For oriented matroid theorists, we fill in a missing step in the existing proof of oriented matroid union in [9] in Theorem 1, and introduce new concepts in Theorem 2.
Matroid unions over bands
In this section, we study matroids over bands with Eckmann-Hilton operators. We begin by recalling the theory of bands and introduce the Eckmann-Hilton operator, an additional formal structure on bands that can be interpreted as a generic evaluation map. We then use this structure to generalize matroid union.
Tolerant bands with Eckmann-Hilton operators
In this section we recall bands, which were introduced in [3], and then proceed to define the Eckmann-Hilton operator and what it means for bands to be tolerant.
Definition 1. A band is a commutative monoid , together with a set , called the null set, consisting of formal sums of elements , such that
(Zero element) there exists an element that satisfies for all ;
(Null ideal) we have , , and for all and ; and
(Additive inverse) for every , there exists a unique with .
In every band, there exists a distinguished element such that .
Bands form a well-defined and reasonable category, as elaborated on in [3]. Furthermore, many structures of interest that arise in combinatorial algebraic geometry can be described as structures over bands.
Example 1. Every ring is a band, where . The Krasner band is defined with . The tropical band is defined with the null set consisting of and all formal sums that attain the maximum of their summands at least twice. The sign band is defined with the null set consisting of and formal sums that contain at least one and one .
When studying linear algebra over bands, an immediate problem is that formal sums of elements of are not elements of . This is problematic when considering matrix multiplication. To this end, we consider bands with an additional structure:
Definition 2. Let be a band. An Eckmann-Hilton (EH) operator is an associative binary operation that satisfies
(EH1) that the zero-element of is the additive identity, $0 \oplus x = x \oplus 0 = x$ for all ;
(EH2) double distributivity, that is, for all ;
(EH3) for all that if and , then .
An EH operator should be thought of as “choosing a generic representative” to evaluate the formal sum. The axiom (EH3) should be thought of as allowing to “commute” with the formal sum. In particular, this partially satisfies the hypothesis of the topological Eckmann–Hilton argument, which this definition is named after.
Example 2. Most bands of interest have EH operators.
For a field , the EH operator is the evaluation of the sum using standard addition of .
The EH operator over the Krasner band is induced by .
The EH operator over the tropical band is the standard tropical addition, given by for all . This can be generalized for a broader class of bands that includes the tropical real hyperfield, tropical complex hyperfield, and tropical phase hyperfield in the sense of [1].
Over the band of signs there are two EH operators, which we denote by and . They are induced by , and , and respectively by , and . Note that this is an example of a non-commutative EH operator. This can also be generalized for all fusion idylls with the inflation property, as defined in [3 Def. 1.9] and [1 Def. 6.9].
Bands allow for a unified study of matroids, defined by Grassmann–Plücker relations.
Definition 3 (see [3]). A -matroid of rank on a totally ordered ground set is an equivalence class of functions , such that for some , and the following Grassmann–Plücker relations are satisfied for any and ,
We consider up to projective equivalence, i.e., with for all .
Many familiar classes of matroids can be recovered as -matroids. For a field , a -matroid of rank on is an -dimensional subspace of . Classical matroids are precisely matroids over , oriented matroids are -matroids, and valuated matroids are -matroids.
Definition 4. A band with EH operator is tolerant if any such that
also satisfy that
All bands we discussed in Example 2 are tolerant with the EH operators given thereafter. However, there are also well-known examples which are not tolerant with respect to their canonical EH operator, one being the classical triangular hyperfield:
Example 3. The triangular hyperfield where is addition is not tolerant. For example,
since there is no triangle with side lengths 4, 4, and 9. However, with , we have
Matroid unions over tolerant bands with EH operators
The main goal of this section is to give a sketch of the proof of Theorem 1, which uses an inductive technique inspired by [9]. The full proof is long and technical, and exceeds the scope of this extended abstract. Instead, we outline the main steps, which involve showing that several matroidal constructions are again -matroids.
Definition 5. Let be a band. Let be a matroid of rank on a ground set , and let be a matroid of rank on a ground set . Then, their direct sum is the map
For the ground set of , we fix the order for any and , and inherit the order on and otherwise.
By a direct computation, it can be shown that the direct sum is a -matroid. Note that the direct sum with a uniform matroid is a natural generalization of elongation of valuated matroids as defined in [7 Sec. 5.3].
Since the EH operator is not necessarily commutative, it is sometimes necessary to reorder elements of the ground set, flipping signs.
Definition 6. Let be a band. For a -matroid and two consecutive elements , we define a reordering of to be the new function
where as a set, with identical ordering, except for the order of and switched.
As before, it can be shown by a computation that is a -matroid.
Definition 7. Let be a -matroid, and let be two distinct ground set elements, adjacent in the total order of . Consider , and set in . The order on is inherited from the order on by setting if and only if . We define the contraction of identifying and as
Theorem 4. Suppose is tolerant band with EH operator . Let be a -matroid, let be adjacent terms in the total order of , and let be the contraction of identifying and as defined above. Then satisfies the Grassmann-Plücker relations.
Proof sketch. The proof is lengthy and proceeds along a careful case-by-case analysis, distinguished by whether the exchanged element is contained in a set with . The most challenging case is when is contained in both and in the Grassmann-Plücker relation of given in (1). In this case, we utilizes the four Plücker relations of involving , with , . Unlike the direct sum in Definition 5, this case utilizes the assumption that the band is tolerant. □
It is possible that the contraction of a -matroid identifying and is identically zero. In this case, there exists a -matroid of smaller rank that can take its place. It is defined as
We are now ready to give a proof of Theorem 1, showing that the matroid union satisfies the Plücker relations, that is, is either identically zero or a -matroid.
Proof of Theorem 1. Consider the direct sum on the disjoint union of ground sets . It can be shown that this function satisfies the Plücker relations. To distinguish between the two copies of , denote elements of the first copy by and elements of second copy by . Consider a reordering of arising by sequentially reordering from to . This is still a -matroid by the discussion after Definition 6.
Starting with , we sequentially apply matroid contraction by identifying with for in decreasing order in . Denote the resulting function after contracting up to by . All still satisfy the Plücker relations by Theorem 4.
We verify that is equal to : For any , let be the two copies of in before the contractions. We write elements of the set in strictly ascending order. Inductively writing in terms of , we obtain
Thus, satisfies the Plücker relations. This means that the matroid union is either identically zero or a -matroid itself.
In the case that is identically zero, there may be a -matroid of a smaller rank that can be constructed by using the lower rank contraction in Equation (3), whenever contracting by identifying results in a zero function. When is or , this -matroid of a potentially smaller rank respectively coincides with the usual notion of (oriented) matroid union.
If the EH operator is commutative, i.e., the semiring arising from the EH operator is idempotent, then since
Example 4. Let be a -matroid of rank 1 on where , and let be a -matroid of rank 2 on given by
Then, the matroid union is the rank 3 matroid on with
and similarly $\mu\cup\nu(134)=\mu\cup\nu(124)=\mu\cup\nu(123)=1.
Bimatroid products over bands
For a band , we now construct the matroidal analog of matrices. Although the -matroid defined by taking the maximal minors of a matrix with entries in using the EH operator can yield a first approximation, the data contained therein is not sufficient for many constructions. Thus, we define a larger -matroid that captures the information of all minors of the matrix, rather than just the maximal ones.
Definition 8. A bimatroid over a band on rows and columns is a -matroid where . In shorthand, we say that is an -bimatroid.
Equivalently, we express as a bivalued map , defined for all with .
K-bimatroids are precisely the bimatroids introduced by Kung and Schrijver [8, 13], i.e. matchings on bipartite graphs. Over , we recover valuated bimatroids, introduced by Murota [11].
A natural example, and the motivation of the definition of bimatroids, is that minors of -matrices induce -bimatroids. Assume and consider a matrix . Appending an identity matrix yields a matrix. Taking the maximal minors (with respect to the EH operator) of this matrix yields a bimatroid. The fact that this is a matroid is not straightforward, and can be proven using matroid union.
Definition 9. Let be an -bimatroid and be an -bimatroid over a band . Their product is defined by
for and any , where is summed in lexicographical order.
When are given by all minors of matrices over a field, the bimatroid product coincides with all minors of the matrix product , due to the Cauchy–Binet formula. Over , Definition 9 recovers “composition” as defined in [6 Pg. 107].
Example 5. Let be a -bimatroid on row and columns given by
and let be a -bimatroid of on rows and column given by
Then, the bimatroid product is given by
and similarly .
To show that the bimatroid product is still a bimatroid over bands, we need two auxiliary matroid constructions.
Definition 10. Let be a -matroid, a finite set, and with .
Its loop extension by is defined to be if and otherwise, for any .
Its generic contraction by is defined to be for any .
Theorem 5. Let be a tolerant band with an EH operator. Let be an -bimatroid and be an -bimatroid over . Their product is a -bimatroid, that is, -bimatroid multiplication is well-defined.
Proof sketch. First, show that both constructions in Definition 10 yield a -matroid. Now, note that the bimatroid product can be written as
Since the result of every one of these constructions satisfy the Plücker relations, so does the bimatroid product. The condition on the first coordinate follows from the fact that .
We say that an bimatroid is of full rank if , as is the analog of the -minor. Then, products of full rank -bimatroids are again full rank, as , and associativity of the bimatroid product follows from the associativity of the EH operator. Combined, we obtain Theorem 2.
Example 6. We demonstrate Equation (4) on the bimatroid product from Example 5. We have that and for and as given in Example 4. We observe that the map is given by and . This is precisely the matroid form of .
Intersections of linear spaces over bands
We first formally define matroid stable intersection over bands, then relate this construction to both -matroid union and intersections of -linear spaces.
Definition 11. Let be a band with EH operator . For two -matroids of rank and of rank on with , we define the matroid stable intersection to be the map
where the sum is taken in reverse lexicographical ordering on .
To link stable intersection to matroid union, we recall from [4] that the dual of a -matroid is the -matroid given by .
Example 7. We now consider the dual -matroids of the matroids in Example 4. The -matroid has rank on and is given by
and the T-matroid has rank 2 on , given as
Their matroid stable intersection is given by
and similarly , which is the dual matroid of .
Theorem 6. Let and denote the dual of matroids and over a band with an EH operator. Then,
Moreover, if is tolerant, then is either identically zero or a -matroid.
The expression follows by algebraic manipulation, and the last statement follows from Theorem 1. Over , combining Theorems 1 and 6 yields an alternative proof for [14 Prop. 3.1].
We now shift to a geometric perspective. For fields, matroid stable intersection yields the shuffle formula for vector space intersection in [15]. In tropical geometry, matroid stable intersection can be seen as the stable intersection of tropical linear spaces in [14]. We generalize this idea to bands.
When is an idyll, -matroids can be equivalently defined using the cryptomorphism with cocircuits, which allow us to view -matroids as linear spaces over .
Definition 12 ([2 Def. 4.6]). For a -matroid over , the set of cocircuits is , where is given as
Extending the tropical setting, we define -linear spaces as the span of cocircuits using the Eckmann-Hilton operator.
Definition 13. We say that is in the convex span of a set of vectors , denoted by , if there exist such that
For a -matroid of rank over , the -linear space is the convex span of its cocircuits,
We say that a -linear space is convex if the -linear space defined as above coincides with the set of covectors as defined in [1 Def. 2.15]. We say that the band itself is convex if every -linear space is convex. Many key examples of bands are convex – due to [12 Thm. 3.8], and both and because of how their null sets are defined.
Proof sketch of Theorem 3. We first express the cocircuits of the matroid stable intersection in terms of the cocircuits of the constituent matroids.
Lemma 1. The cocircuit of associated with can be expressed as
To prove that is in the convex span of cocircuits of (or respectively), we show that the coefficient of each in the linear expression is independent of . The inclusion then follows from the fact that -linear spaces are closed under the EH operator . Under an additional transversality condition, the reverse inclusion can be shown for convex -linear spaces over fusion band by manipulating relations on covectors of imposed by circuits of and . □
In general, the additional condition needed for can be seen as requiring the intersection to be “transversal”. Over , this coincides with transverse matroids in [14]. Over , it corresponds to transverse intersections of tropical linear spaces in [10 Def. 3.4.9], thus providing an alternative proof for [14 Prop. 3.4].
Example 8. The -linear spaces of and defined in Example 7 can be described as
and
with set-theoretic intersection
which indeed equals .
Acknowledgements
We thank Matt Baker, Melody Chan, Alex Fink, Jeff Giansiracusa, Felipe Rincón, and Martin Ulirsch for helpful conversations. We particularly thank Chayim Lowen for pointing us to Eckmann-Hilton operators over hyperfields. Parts of this paper were written while V.S. was a Member at the Institute for Advanced Study, Princeton, and funded by the Charles Simonyi Endowment.
AI disclosure
AI has not been used in the development of this manuscript at any stage.
References
- [1]L. Anderson. “Vectors of matroids over tracts”. J. Combin. Theory Ser. A 161 (2019), pp. 236–270. DOI.arxiv.org/abs/1607.04868
- [2]M. Baker and N. Bowler. “Matroids over partial hyperstructures”. Adv. Math. 343 (2019), pp. 821–863. DOI.arxiv.org/abs/1709.09707
- [3]M. Baker, T. Jin, and O. Lorscheid. “New building blocks for F₁-geometry: bands and band schemes”. J. Lond. Math. Soc. (2) 111.4 (2025), Paper No. e70125, 62. DOI.DOI
- [4]M. Baker and O. Lorscheid. “The moduli space of matroids”. Adv. Math. 390 (2021), Paper No. 107883, 118. DOI.arxiv.org/abs/1809.03542
- [5]A. W. M. Dress and W. Wenzel. “Valuated matroids”. Adv. Math. 93.2 (1992), pp. 214–250. DOI.DOI
- [6]B. Frenk. Tropical varieties, maps and gossip. Ph.D. thesis. Eindhoven University of Technology, 2013.DOI
- [7]J. Giansiracusa and N. Giansiracusa. “A Grassmann algebra for matroids”. Manuscripta Math. 156.1-2 (2018), pp. 187–213. DOI.arxiv.org/abs/1510.04584
- [8]J. P. S. Kung. “Bimatroids and invariants”. Adv. in Math. 30.3 (1978), pp. 238–249. DOI.DOI
- [9]J. Lawrence and L. Weinberg. “Unions of oriented matroids”. Linear Algebra and its Applications 41 (1981), pp. 183–200. DOI.
- [10]D. Maclagan and B. Sturmfels. Introduction to Tropical Geometry. Vol. 161. Graduate Studies in Mathematics. Providence, RI: American Mathematical Society, 2015, pp. xiv+363. Link.
- [11]K. Murota. “Finding optimal minors of valuated bimatroids”. Applied Mathematics Letters 8.4 (1995), pp. 37–41. DOI.DOI
- [12]K. Murota and A. Tamura. “On Circuit Valuation of Matroids”. Advances in Applied Mathematics 26.3 (2001), pp. 192–225. DOI.DOI
- [13]A. Schrijver. “Matroids and linking systems”. J. Combin. Theory Ser. B 26.3 (1979), pp. 349–369. DOI.
- [14]D. E. Speyer. “Tropical linear spaces”. SIAM J. Discrete Math. 22.4 (2008), pp. 1527–1558. DOI.DOI
- [15]K. Wohlhart. “The intersection of vector spaces: An engineering approach to the shuffle formula”. Mechanism and Machine Theory 63 (2013), pp. 59–72. DOI.DOI