betaFeedback

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 BB, the analog of a linear space is a BB-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 BB does not yield an element of BB. We overcome this by introducing an Eckmann-Hilton operator ⊕\oplus in § 2, which should be thought of as “generic evaluation” of the formal sum over BB, 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 BB to have an Eckmann-Hilton operator ⊕\oplus and to be tolerant. Moreover, we denote the additive inverse of 11 in BB by ε\varepsilon.

Theorem 1. Let BB be a tolerant band with an Eckmann-Hilton operator ⊕\oplus, and let μ\mu and ν\nu be two BB-matroids of rank rr and ss over a ground set EE, such that r+s≤∣E∣r+s\leq|E|. Then, the matroid union μ∪ν\mu\cup\nu, defined coordinate-wise on Z∈(Er+s)Z\in\binom{E}{r+s} as

\mu\cup\nu(Z)=\bigoplus_{X\mathbin{\mathaccent\cdot\cup}Y=Z}\epsilon^{|\{y<x\mid x\in X,\ y\in Y\}|}\mu(X)\nu(Y)

is either identically zero or a BB-matroid of rank r+sr+s on EE. If ⊕\oplus 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 BB-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 n×nn\times n matrices, we consider a BB-matroid of rank nn on [2n][2n] with a fixed basis [n][n]. We call such a matroid a BB-bimatroid. Unlike BB-matroids or BB-matrices, these have a well-defined and well-behaved multiplication. We call the set of full-rank n×nn\times n BB-bimatroids the general linear monoid GLB(n)\mathrm{GL}_{B}(n).

Theorem 2. Let BB be a tolerant band with an Eckmann-Hilton operator, and let M\mathrm{M} and N\mathrm{N} be full-rank n×nn\times n-BB-bimatroids, then the product M⋅N\mathrm{M}\cdot\mathrm{N} is a full-rank n×nn\times n-BB-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, GLB(n)\mathrm{GL}_{B}(n) 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 BB-matroid stable intersection μ∩ν\mu\cap\nu (see Def. 11) is dual to the matroid union of the dual matroids μ⊥∪ν⊥\mu^{\perp}\cup\nu^{\perp}. Using the Eckmann–Hilton operator and Baker-Bowler’s cocircuits C∗C^{*} [2], we define the BB-linear space W∗W^{*} (see Def. 13), which is cryptomorphic to a BB-matroid for any band BB in which all nonzero elements are units. Such bands are called idylls in [3].

Theorem 3. Let BB be a tolerant idyll with an Eckmann-Hilton operator. Let μ\mu and ν\nu be BB-matroids with nonzero matroid stable intersection μ∩ν\mu\cap\nu. Then, the BB-linear space of μ∩ν\mu\cap\nu is contained in the set-theoretic intersection of BB-linear spaces for μ\mu and ν\nu, i.e.,

W∗μ∩ν⊂W∗μ∩W∗ν,W^{*\mu\cap\nu}\subset W^{*\mu}\cap W^{*\nu},

with equality under additional assumptions on the transversality of the intersection, convexity of the linear spaces, and fusion property of the band BB.

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 BB is a commutative monoid (B,⋅,1)(B,\cdot,1), together with a set NBN_B, called the null set, consisting of formal sums ∑ai\sum a_i of elements ai∈Ba_i \in B, such that

(Zero element) there exists an element 0∈B0 \in B that satisfies a⋅0=0a \cdot0 = 0 for all a∈Ba \in B;

(Null ideal) we have 0∈NB0 \in N_B, a⋅x∈NBa \cdot x \in N_B, and x+y∈NBx+y \in N_B for all a∈Ba \in B and x,y∈NBx,y \in N_B; and

(Additive inverse) for every a∈Ba \in B, there exists a unique b∈Bb \in B with a+b∈NBa+b \in N_B.

In every band, there exists a distinguished element ϵ\epsilon such that 1+ϵ∈NB1+\epsilon\in N_B.

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 RR is a band, where NR={∑ai∣∑ai=0 evaluated in R}N_R = \{\sum a_i \mid\sum a_i = 0\text{ evaluated in }R\}. The Krasner band K={0,1}\mathbb{K} = \{0,1\} is defined with NK={∑i=1k1∣k≥2}∪{0}N_{\mathbb{K}} = \{\sum_{i=1}^{k}1 \mid k \ge2\} \cup\{0\}. The tropical band T=R≥0\mathbb{T} = \mathbb{R}_{\ge0} is defined with the null set consisting of 00 and all formal sums that attain the maximum of their summands at least twice. The sign band S={0,1,ϵ}\mathbb{S} = \{0,1,\epsilon\} is defined with the null set consisting of 00 and formal sums that contain at least one 11 and one ϵ\epsilon.

When studying linear algebra over bands, an immediate problem is that formal sums of elements of BB are not elements of BB. This is problematic when considering matrix multiplication. To this end, we consider bands with an additional structure:

Definition 2. Let BB be a band. An Eckmann-Hilton (EH) operator is an associative binary operation ⊕:B×B→B\oplus: B \times B \to B that satisfies

(EH1) that the zero-element of BB is the additive identity, $0 \oplus x = x \oplus 0 = x$ for all x∈Bx \in B;

(EH2) double distributivity, that is, (a⊕b)(c⊕d)=ac⊕bc⊕ad⊕bd(a \oplus b)(c \oplus d) = ac \oplus bc \oplus ad \oplus bd for all a,b,c,d∈Ba,b,c,d \in B;

(EH3) for all a,b∈Bma,b \in B^m that if ∑i=1mai∈NB\sum_{i=1}^{m} a_i \in N_B and ∑i=1mbi∈NB\sum_{i=1}^{m} b_i \in N_B, then ∑i=1m(ai⊕bi)∈NB\sum_{i=1}^{m}(a_i \oplus b_i) \in N_B.

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 ⊕\oplus 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 KK, the EH operator is the evaluation of the sum using standard addition of KK.

  • The EH operator over the Krasner band KK is induced by 1⊕1=11\oplus1=1.

  • The EH operator over the tropical band T\mathbb{T} is the standard tropical addition, given by a⊕b=max⁡(a,b)a\oplus b=\max(a,b) for all a,b∈Ta,b\in\mathbb{T}. 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 SS there are two EH operators, which we denote by ⊕>\oplus_> and ⊕<\oplus_<. They are induced by 1⊕>ε=11\oplus_>\varepsilon=1, and ε⊕>1=ε\varepsilon\oplus_>1=\varepsilon, and respectively by 1⊕<ε=ε1\oplus_<\varepsilon=\varepsilon, and ε⊕<1=1\varepsilon\oplus_<1=1. 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 BB-matroid of rank rr on a totally ordered ground set EE is an equivalence class of functions μ:(Er)→B\mu:\binom{E}{r}\to B, such that μ(I)∈B×\mu(I)\in B^{\times} for some I∈(Er)I\in\binom{E}{r}, and the following Grassmann–Plücker relations are satisfied for any I∈(Er−1)I\in\binom{E}{r-1} and J∈(Er+1)J\in\binom{E}{r+1},

∑k=0rε∣{e∈I∪J∣e<ik}∣μ(I∖{ik})μ(J∪{ik})∈NB.(1)\sum_{k=0}^{r}\varepsilon^{|\{e\in I\cup J\mid e<i_k\}|}\mu(I\setminus\{i_k\})\mu(J\cup\{i_k\})\in N_B. \tag*{(1)}

We consider μ\mu up to projective equivalence, i.e., with μ∼a⋅μ\mu\sim a\cdot\mu for all a∈B×a\in B^{\times}.

Many familiar classes of matroids can be recovered as BB-matroids. For a field KK, a KK-matroid of rank rr on [n][n] is an rr-dimensional subspace of KnK^n. Classical matroids are precisely matroids over KK, oriented matroids are SS-matroids, and valuated matroids are T\mathbb{T}-matroids.

Definition 4. A band BB with EH operator ⊕\oplus is tolerant if any ai,bi,ci,di,S∈Ba_i,b_i,c_i,d_i,S\in B such that

∑i=1naici∈NB,S+∑i=1nbici∈NB,εS+∑i=1naidi∈NB,and∑i=1nbidi∈NB,\sum_{i=1}^{n}a_ic_i\in N_B,\qquad S+\sum_{i=1}^{n}b_ic_i\in N_B,\qquad\varepsilon S+\sum_{i=1}^{n}a_id_i\in N_B,\qquad\text{and}\qquad\sum_{i=1}^{n}b_id_i\in N_B,

also satisfy that

∑i=1n(ai⊕bi)(ci⊕di)∈NB.\sum_{i=1}^{n}(a_i\oplus b_i)(c_i\oplus d_i)\in N_B.

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 T2\mathbb{T}_2 where ⊕\oplus is addition is not tolerant. For example,

(1⊕1)(1⊕1)+(1⊕1)(1⊕1)+(1⊕2)(2⊕1)∉NB(1 \oplus1)(1 \oplus1) + (1 \oplus1)(1 \oplus1) + (1 \oplus2)(2 \oplus1) \notin N_{B}

since there is no triangle with side lengths 4, 4, and 9. However, with S=2.5S=2.5, we have

1⋅1+1⋅1+1⋅2∈NBS+1⋅1+1⋅1+2⋅2∈NB1 \cdot1 + 1 \cdot1 + 1 \cdot2 \in N_{B} \qquad S + 1 \cdot1 + 1 \cdot1 + 2 \cdot2 \in N_{B}
S+1⋅1+1⋅1+1⋅1∈NB1⋅1+1⋅1+2⋅1∈NB.S + 1 \cdot1 + 1 \cdot1 + 1 \cdot1 \in N_{B} \qquad1 \cdot1 + 1 \cdot1 + 2 \cdot1 \in N_{B}.

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 BB-matroids.

Definition 5. Let BB be a band. Let μ\mu be a matroid of rank rr on a ground set EE, and let ν\nu be a matroid of rank ss on a ground set FF. Then, their direct sum μ⊕^ν\mu\widehat{\oplus}\nu is the map

μ⊕^ν:(E⊔Fr+s)→B;Z↦μ(Z∩E)ν(Z∩F).\mu\widehat{\oplus}\nu:\binom{E\sqcup F}{r+s}\to B;\quad Z\mapsto\mu(Z\cap E)\nu(Z\cap F).

For the ground set E⊔FE\sqcup F of μ⊕^ν\mu\widehat{\oplus}\nu, we fix the order e<fe<f for any e∈Ee\in E and f∈Ff\in F, and inherit the order on EE and FF otherwise.

By a direct computation, it can be shown that the direct sum μ⊕^ν\mu\widehat{\oplus}\nu is a BB-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 BB be a band. For a BB-matroid μ:(Er)→B\mu:\binom{E}{r}\to B and two consecutive elements a<b∈Ea<b\in E, we define a reordering of μ\mu to be the new function

μb<a:(E′r)→B,μb<a(Z)={εμ(Z)if a,b∈Z,μ(Z)otherwise,\mu_{b<a}:\binom{E'}{r}\to B,\qquad\mu_{b<a}(Z)= \begin{cases} \varepsilon\mu(Z) & \text{if }a,b\in Z,\\ \mu(Z) & \text{otherwise}, \end{cases}

where E′=EE'=E as a set, with identical ordering, except for the order of aa and bb switched.

As before, it can be shown by a computation that μb<a\mu_{b<a} is a BB-matroid.

Definition 7. Let μ:(Er)→B\mu: \binom{E}{r} \to B be a BB-matroid, and let u<v∈Eu < v \in E be two distinct ground set elements, adjacent in the total order of EE. Consider E′:=E/(u∼v)E' := E/(u \sim v), and set w:=[u]=[v]w := [u] = [v] in E′E'. The order on E′E' is inherited from the order on EE by setting x<E′wx <_{E'} w if and only if x<Eux <_{E} u. We define the contraction of μ\mu identifying uu and vv as

ξ:(E′r)→B,ξ(Z)={μ(Z)if w∉Z,μ((Z∖w)∪u)⊕μ((Z∖w)∪v)if w∈Z.(2)\xi: \binom{E'}{r} \to B,\qquad\xi(Z) = \begin{cases} \mu(Z) & \text{if } w \notin Z,\\ \mu((Z \setminus w) \cup u) \oplus\mu((Z \setminus w) \cup v) & \text{if } w \in Z. \end{cases} \tag*{(2)}

Theorem 4. Suppose BB is tolerant band with EH operator ⊕\oplus. Let μ:(Er)→B\mu: \binom{E}{r} \to B be a BB-matroid, let u≠v∈Eu \ne v \in E be adjacent terms in the total order of EE, and let ξ\xi be the contraction of μ\mu identifying uu and vv as defined above. Then ξ\xi 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 ww. The most challenging case is when ww is contained in both II and JJ in the Grassmann-Plücker relation of ξ\xi given in (1). In this case, we utilizes the four Plücker relations of μ\mu involving I∖w∪uI \setminus w \cup u, I∖w∪vI \setminus w \cup v with J∖w∪uJ \setminus w \cup u, J∖w∪vJ \setminus w \cup v. 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 BB-matroid μ\mu identifying uu and vv is identically zero. In this case, there exists a BB-matroid ξ\xi of smaller rank that can take its place. It is defined as

ξ:(E′r−1)→B,ξ(U)={μ(U∪v)if w∉U,μ((U∖w)∪{u,v})if w∈U.(3)\xi: \binom{E'}{r-1} \to B,\qquad\xi(U) = \begin{cases} \mu(U \cup v) & \text{if } w \notin U,\\ \mu((U \setminus w) \cup\{u,v\}) & \text{if } w \in U. \end{cases} \tag*{(3)}

We are now ready to give a proof of Theorem 1, showing that the matroid union μ∪ν\mu\cup\nu satisfies the Plücker relations, that is, is either identically zero or a BB-matroid.

Proof of Theorem 1. Consider the direct sum μ⊞ν\mu\boxplus\nu on the disjoint union of ground sets E⊔EE \sqcup E. It can be shown that this function satisfies the Plücker relations. To distinguish between the two copies of EE, denote elements of the first copy by 1,…,l1,\ldots,l and elements of second copy by 1′,…,l′1',\ldots,l'. Consider a reordering (μ⊞ν)lex(\mu\boxplus\nu)_{\mathrm{lex}} of μ⊞ν\mu\boxplus\nu arising by sequentially reordering E⊔EE \sqcup E from 1<…<l<1′<…<l′1 < \ldots< l < 1' < \ldots< l' to 1<1′<2<2′<⋯<l<l′1 < 1' < 2 < 2' < \cdots< l < l'. This is still a BB-matroid by the discussion after Definition 6.

Starting with (μ⊞ν)lex(\mu\boxplus\nu)_{\mathrm{lex}}, we sequentially apply matroid contraction by identifying ii with i′i' for i=l,l−1,…,1i = l,l-1,\ldots,1 in decreasing order in EE. Denote the resulting function after contracting up to jj by ξj\xi_j. All ξj\xi_j still satisfy the Plücker relations by Theorem 4.

We verify that ξ1\xi_1 is equal to μ∪ν\mu\cup\nu: For any Z={z1<⋯<zr+s}∈(Er+s)Z = \{z_1 < \cdots< z_{r+s}\} \in\binom{E}{r+s}, let ui,viu_i,v_i be the two copies of ziz_i in E⊔EE \sqcup E before the contractions. We write elements of the set in strictly ascending order. Inductively writing ξzi\xi_{z_i} in terms of ξzi+1\xi_{z_{i+1}}, we obtain

ξ1(z1,⋯ ,zr+s)=ξz2(u1,⋯ ,zr+s)⊕ξz2(v1,⋯ ,zr+s)\xi_1(z_1,\cdots,z_{r+s})=\xi_{z_2}(u_1,\cdots,z_{r+s})\oplus\xi_{z_2}(v_1,\cdots,z_{r+s})
=(Ind.)μ⊕^νlex(u1,u2,⋯ ,ur+s)⊕⋯⊕μ⊕^νlex(v1,v2,⋯ ,vr+s)=⨁X∪˙Y=Zlex.ϵ∣{y≤x∣x∈X,y∈Y}∣μ(X)ν(Y)=μ∪ν(Z).\begin{aligned} \overset{(\mathrm{Ind.})}{=}\mu\widehat{\oplus}\nu_{\mathrm{lex}}(u_1,u_2,\cdots,u_{r+s})\oplus\cdots\oplus\mu\widehat{\oplus}\nu_{\mathrm{lex}}(v_1,v_2,\cdots,v_{r+s}) \\ &=\bigoplus_{\substack{X\mathbin{\dot\cup}Y=Z\\\mathrm{lex.}}}\epsilon^{|\{y\le x\mid x\in X,y\in Y\}|}\mu(X)\nu(Y) \\ &=\mu\cup\nu(Z). \end{aligned}

Thus, μ∪ν\mu\cup\nu satisfies the Plücker relations. This means that the matroid union is either identically zero or a BB-matroid itself.

In the case that μ∪ν\mu\cup\nu is identically zero, there may be a BB-matroid of a smaller rank that can be constructed by using the lower rank contraction in Equation (3), whenever contracting by identifying i∼i′i\sim i' results in a zero function. When BB is K\mathbb{K} or S\mathbb{S}, this BB-matroid of a potentially smaller rank respectively coincides with the usual notion of (oriented) matroid union.

If the EH operator ⊕\oplus is commutative, i.e., the semiring arising from the EH operator is idempotent, then μ∪ν=ϵrsν∪μ∼ν∪μ\mu\cup\nu=\epsilon^{rs}\nu\cup\mu\sim\nu\cup\mu since

∣{y<x∣x∈X,y∈Y}∣=∣X∣∣Y∣−∣{x<y∣x∈X,y∈Y}∣.|\{y<x\mid x\in X,y\in Y\}|=|X||Y|-|\{x<y\mid x\in X,y\in Y\}|.

Example 4. Let μ\mu be a T\mathbb{T}-matroid of rank 1 on [4][4] where μ(1)=μ(3)=1,μ(2)=2,μ(4)=0\mu(1)=\mu(3)=1,\mu(2)=2,\mu(4)=0, and let ν\nu be a T\mathbb{T}-matroid of rank 2 on [4][4] given by

ν(23)=ν(24)=ν(34)=1,ν(12)=ν(13)=ν(14)=0.\nu(23)=\nu(24)=\nu(34)=1,\nu(12)=\nu(13)=\nu(14)=0.

Then, the matroid union μ∪ν\mu\cup\nu is the rank 3 matroid on [4][4] with

μ∪ν(234)=μ(2)ν(34)⊕μ(3)ν(24)⊕μ(4)ν(23)=max⁡{2,1,0}=2,\mu\cup\nu(234)=\mu(2)\nu(34)\oplus\mu(3)\nu(24)\oplus\mu(4)\nu(23)=\max\{2,1,0\}=2,

and similarly $\mu\cup\nu(134)=\mu\cup\nu(124)=\mu\cup\nu(123)=1.

Bimatroid products over bands

For a band BB, we now construct the matroidal analog of matrices. Although the BB-matroid defined by taking the maximal minors of a matrix with entries in BB using the EH operator can yield a first approximation, the data contained therein is not sufficient for many constructions. Thus, we define a larger BB-matroid that captures the information of all minors of the matrix, rather than just the maximal ones.

Definition 8. A bimatroid MM over a band BB on rows EE and columns FF is a BB-matroid M:(E∪F∣E∣)→BM:\binom{E\cup F}{|E|}\to B where M(E)=1M(E)=1. In shorthand, we say that MM is an ∣E∣×∣F∣|E|\times|F|-bimatroid.

Equivalently, we express MM as a bivalued map M(R,C):=M((E−R)∪C)M(R,C):=M((E-R)\cup C), defined for all R⊂E,C⊂FR\subset E,C\subset F with ∣R∣=∣C∣|R|=|C|.

K-bimatroids are precisely the bimatroids introduced by Kung and Schrijver [8, 13], i.e. matchings on bipartite graphs. Over T\mathbb{T}, we recover valuated bimatroids, introduced by Murota [11].

A natural example, and the motivation of the definition of bimatroids, is that minors of BB-matrices induce BB-bimatroids. Assume m≥nm \ge n and consider a matrix A∈Bn×mA \in B^{n \times m}. Appending an n×nn \times n identity matrix (I∣A)(I \mid A) yields a n×(n+m)n \times(n+m) 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 MM be an n×mn \times m-bimatroid and NN be an m×lm \times l-bimatroid over a band BB. Their product M⋅NM \mathbin{\cdot} N is defined by

M⋅N(I,K)=⨁J∈([m]d)ϵ∣{y<x∣x∈I,y∈[m]−J}∣M(I,J)N(J,K)M \mathbin{\cdot} N(I,K)=\bigoplus_{J\in\binom{[m]}{d}}\epsilon^{\lvert\{y<x\mid x\in I,y\in[m]-J\}\rvert}M(I,J)N(J,K)

for (I,K)∈([n]d)×([l]d)(I,K)\in\binom{[n]}{d}\times\binom{[l]}{d} and any 0≤d≤min⁡(n,l)0\le d\le\min(n,l), where JJ is summed in lexicographical order.

When M,NM,N are given by all minors of matrices A,A′A,A' over a field, the bimatroid product M⋅NM \mathbin{\cdot} N coincides with all minors of the matrix product AA′AA', due to the Cauchy–Binet formula. Over T\mathbb{T}, Definition 9 recovers “composition” as defined in [6 Pg. 107].

Example 5. Let MM be a T\mathbb{T}-bimatroid on row {1}\{1\} and columns {2,3}\{2,3\} given by

M(∅,∅)=M(1,3)=1, M(1,2)=2,M(\varnothing,\varnothing)=M(1,3)=1,\ M(1,2)=2,

and let NN be a T\mathbb{T}-bimatroid of on rows {2,3}\{2,3\} and column {4}\{4\} given by

N(∅,∅)=N(2,4)=N(3,4)=1.N(\varnothing,\varnothing)=N(2,4)=N(3,4)=1.

Then, the bimatroid product M⋅NM \mathbin{\cdot} N is given by

M⋅N(1,4)=M(1,2)N(2,4)⊕M(1,3)N(3,4)=max⁡{2,1}=2,M \mathbin{\cdot} N(1,4)=M(1,2)N(2,4)\mathbin{\oplus}M(1,3)N(3,4)=\max\{2,1\}=2,

and similarly M⋅N(∅,∅)=1M \mathbin{\cdot} N(\varnothing,\varnothing)=1.

To show that the bimatroid product is still a bimatroid over bands, we need two auxiliary matroid constructions.

Definition 10. Let μ:(Er)→B\mu:\binom{E}{r}\to B be a BB-matroid, SS a finite set, and T⊂ET\subset E with ∣T∣<r\lvert T\rvert<r.

  1. Its loop extension by SS is defined to be μ⊕S(X):=μ(X)\mu\oplus S(X):=\mu(X) if X⊂EX\subset E and μ⊕S(X):=0\mu\oplus S(X):=0 otherwise, for any X∈(E∪Sr)X\in\binom{E\cup S}{r}.

  1. Its generic contraction by TT is defined to be μ/T(X):=μ(X∪T)\mu/T(X):=\mu(X\cup T) for any X∈(E∖Tr−∣T∣)X\in\binom{E\setminus T}{r-\lvert T\rvert}.

Theorem 5. Let BB be a tolerant band with an EH operator. Let MM be an n×mn \times m-bimatroid and NN be an m×lm \times l-bimatroid over BB. Their product M⋅NM \cdot N is a BB-bimatroid, that is, BB-bimatroid multiplication is well-defined.

Proof sketch. First, show that both constructions in Definition 10 yield a BB-matroid. Now, note that the bimatroid product M⋅NM \cdot N can be written as

M⋅N=((M⊕[l])∪([n]⊕N))/[m].(4)M \cdot N = ((M \oplus[l]) \cup([n] \oplus N)) / [m]. \tag*{(4)}

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 M⋅N(∅,∅)=M(∅,∅)N(∅,∅)=1M \cdot N(\varnothing, \varnothing) = M(\varnothing, \varnothing)N(\varnothing, \varnothing) = 1.

We say that an n×nn \times n bimatroid MM is of full rank if M([n],[n])∈B×M([n],[n]) \in B^{\times}, as M([n],[n])M([n],[n]) is the analog of the n×nn \times n-minor. Then, products of full rank n×nn \times n-bimatroids are again full rank, as M⋅N([n],[n])=M([n],[n])N([n],[n])∈B×M \cdot N([n],[n]) = M([n],[n])N([n],[n]) \in B^{\times}, 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 M⋅NM \cdot N from Example 5. We have that M⊕{4}=μM \oplus\{4\} = \mu and {1}⊕N=ν\{1\} \oplus N = \nu for μ\mu and ν\nu as given in Example 4. We observe that the map (μ∪ν)/{2,3}(\mu\cup\nu)/\{2,3\} is given by ((μ∪ν)/{2,3})(1)=1((\mu\cup\nu)/\{2,3\})(1) = 1 and ((μ∪ν)/{2,3})(4)=2((\mu\cup\nu)/\{2,3\})(4) = 2. This is precisely the matroid form of M⋅NM \cdot N.

Intersections of linear spaces over bands

We first formally define matroid stable intersection over bands, then relate this construction to both BB-matroid union and intersections of BB-linear spaces.

Definition 11. Let BB be a band with EH operator ⊕\oplus. For two BB-matroids μ\mu of rank rr and ν\nu of rank ss on EE with r+s≥∣E∣r+s \geq|E|, we define the matroid stable intersection μ∩ν\mu\cap\nu to be the map

μ∩ν:(Er+s−∣E∣)→B;Z↦⨁X∩Y=Zϵ∣{x<y∣x∈X−Z, y∈Y−Z}∣μ(X)ν(Y)\mu\cap\nu: \binom{E}{r+s-|E|} \to B;\qquad Z \mapsto\bigoplus_{X\cap Y=Z} \epsilon^{|\{x<y \mid x\in X-Z,\ y\in Y-Z\}|}\mu(X)\nu(Y)

where the sum is taken in reverse lexicographical ordering on E−ZE-Z.

To link stable intersection to matroid union, we recall from [4] that the dual of a BB-matroid μ:(Er)→B\mu: \binom{E}{r} \to B is the BB-matroid μ⊥:(E∣E∣−r)→B\mu^{\perp} : \binom{E}{|E|-r} \to B given by μ⊥(Z)=μ(E∖Z)\mu^{\perp}(Z) = \mu(E \setminus Z).

Example 7. We now consider the dual T\mathbb{T}-matroids of the matroids in Example 4. The T\mathbb{T}-matroid μ⊥\mu^{\perp} has rank 33 on [4][4] and is given by

μ⊥(234)=μ⊥(124)=1, μ⊥(134)=2,andμ⊥(123)=0.\mu^{\perp}(234) = \mu^{\perp}(124) = 1,\ \mu^{\perp}(134) = 2,\quad\text{and}\quad\mu^{\perp}(123) = 0.

and the T-matroid ν⊥\nu^\perp has rank 2 on [4][4], given as

ν⊥(14)=ν⊥(13)=ν⊥(12)=1,andν⊥(34)=ν⊥(24)=ν⊥(23)=0.\nu^\perp(14)=\nu^\perp(13)=\nu^\perp(12)=1,\quad\text{and}\quad\nu^\perp(34)=\nu^\perp(24)=\nu^\perp(23)=0.

Their matroid stable intersection μ⊥∩ν⊥\mu^\perp\cap\nu^\perp is given by

μ⊥∩ν⊥(1)=μ(134)ν(12)⊕μ(124)ν(13)⊕μ(123)ν(14)=max⁡{2,1,0}=2,\mu^\perp\cap\nu^\perp(1)=\mu(134)\nu(12)\oplus\mu(124)\nu(13)\oplus\mu(123)\nu(14)=\max\{2,1,0\}=2,

and similarly μ⊥∩ν⊥(2)=μ⊥∩ν⊥(3)=μ⊥∩ν⊥(4)=1\mu^\perp\cap\nu^\perp(2)=\mu^\perp\cap\nu^\perp(3)=\mu^\perp\cap\nu^\perp(4)=1, which is the dual matroid of μ∪ν\mu\cup\nu.

Theorem 6. Let μ⊥\mu^\perp and ν⊥\nu^\perp denote the dual of matroids μ\mu and ν\nu over a band BB with an EH operator. Then,

μ∩ν=(μ⊥∪ν⊥)⊥.\mu\cap\nu=(\mu^\perp\cup\nu^\perp)^\perp.

Moreover, if BB is tolerant, then μ∩ν\mu\cap\nu is either identically zero or a BB-matroid.

The expression follows by algebraic manipulation, and the last statement follows from Theorem 1. Over T\mathbb{T}, 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 BB is an idyll, BB-matroids can be equivalently defined using the cryptomorphism with cocircuits, which allow us to view BB-matroids as linear spaces over BB.

Definition 12 ([2 Def. 4.6]). For a BB-matroid μ:(Er)→B\mu:\binom{E}{r}\to B over E=[n]E=[n], the set of cocircuits is C∗μ={αCS∗μ∣S∈(Er−1), α∈B×}∖{(0,…,0)}\mathcal{C}^{*\mu}=\{\alpha C^{*\mu}_S\mid S\in\binom{E}{r-1},\ \alpha\in B^\times\}\setminus\{(0,\ldots,0)\}, where CS∗μ∈BnC^{*\mu}_S\in B^n is given as

CS∗μ(i)={0i∈S,e∣{j>i∣j∈S}∣μ(S∪i)i∉S.C^{*\mu}_S(i)= \begin{cases} 0 & i\in S,\\ e^{|\{j>i\mid j\in S\}|}\mu(S\cup i) & i\notin S. \end{cases}

Extending the tropical setting, we define BB-linear spaces as the span of cocircuits using the Eckmann-Hilton operator.

Definition 13. We say that X∈BnX\in B^n is in the convex span of a set of vectors S={Yk∈Bn∣k∈[l]}S=\{Y_k\in B^n\mid k\in[l]\}, denoted by cspan⁡(S)\operatorname{cspan}(S), if there exist b1,…,bl∈Bb_1,\ldots,b_l\in B such that

X(i)=⨁k=1lbkYk(i)for all i∈[n].X(i)=\bigoplus_{k=1}^{l} b_kY_k(i)\quad\text{for all }i\in[n].

For a BB-matroid μ\mu of rank rr over [n][n], the BB-linear space is the convex span of its cocircuits,

Wμ∗:=cspan⁡(C∗μ).\mathcal{W}^{\mu*}:=\operatorname{cspan}(\mathcal{C}^{*\mu}).

We say that a BB-linear space is convex if the BB-linear space defined as above coincides with the set of covectors as defined in [1 Def. 2.15]. We say that the band BB itself is convex if every BB-linear space is convex. Many key examples of bands are convex – T\mathbb{T} due to [12 Thm. 3.8], and both K\mathbb{K} and S\mathbb{S} 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 μ∩ν\mu\cap\nu associated with SS can be expressed as

CS∗μ∩ν(i)=⨁X∩Y=S,X∪Y=E−iϵ∣{x<y∣x∈X−S, y∈Y−S}∣+∣{(i<x∣x∈E)}∣CX∗μ(i)CY∗ν(i)C_{S}^{*\mu\cap\nu}(i)=\bigoplus_{\substack{X\cap Y=S,\,X\cup Y=E-i}}\epsilon^{|\{x<y\mid x\in X-S,\,y\in Y-S\}|+|\{(i<x\mid x\in E)\}|}C_{X}^{*\mu}(i)C_{Y}^{*\nu}(i)

To prove that CS∗μ∩νC_{S}^{*\mu\cap\nu} is in the convex span of cocircuits of μ\mu (or ν\nu respectively), we show that the coefficient of each CX∗μC_{X}^{*\mu} in the linear expression is independent of ii. The inclusion W∗μ∩ν⊂W∗μ∩W∗νW^{*\mu\cap\nu}\subset W^{*\mu}\cap W^{*\nu} then follows from the fact that BB-linear spaces are closed under the EH operator ⊕\oplus. Under an additional transversality condition, the reverse inclusion can be shown for convex BB-linear spaces over fusion band BB by manipulating relations on covectors of imposed by circuits of μ\mu and ν\nu. □

In general, the additional condition needed for W∗μ∩ν=W∗μ∩W∗νW^{*\mu\cap\nu}=W^{*\mu}\cap W^{*\nu} can be seen as requiring the intersection to be “transversal”. Over K\mathbb{K}, this coincides with transverse matroids in [14]. Over T\mathbb{T}, 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 T\mathbb{T}-linear spaces of μ⊥\mu^\perp and ν⊥\nu^\perp defined in Example 7 can be described as

W∗μ⊥={v∈B4∣v1=v3≥2v2 or v1=2v2≥v3 or 2v2=v3≥v1},W^{*\mu^\perp}=\{v\in B^4\mid v_1=v_3\ge2v_2\text{ or }v_1=2v_2\ge v_3\text{ or }2v_2=v_3\ge v_1\},

and

W∗ν⊥={v∈B4∣v2=v3=v4},W^{*\nu^\perp}=\{v\in B^4\mid v_2=v_3=v_4\},

with set-theoretic intersection

W∗μ⊥∩W∗ν⊥={v∈B4∣v1=2v2=2v3=2v4},W^{*\mu^\perp}\cap W^{*\nu^\perp}=\{v\in B^4\mid v_1=2v_2=2v_3=2v_4\},

which indeed equals W∗(μ∩ν)⊥W^{*(\mu\cap\nu)^\perp}.

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. [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. [2]M. Baker and N. Bowler. “Matroids over partial hyperstructures”. Adv. Math. 343 (2019), pp. 821–863. DOI.arxiv.org/abs/1709.09707
  3. [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. [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. [5]A. W. M. Dress and W. Wenzel. “Valuated matroids”. Adv. Math. 93.2 (1992), pp. 214–250. DOI.DOI
  6. [6]B. Frenk. Tropical varieties, maps and gossip. Ph.D. thesis. Eindhoven University of Technology, 2013.DOI
  7. [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. [8]J. P. S. Kung. “Bimatroids and invariants”. Adv. in Math. 30.3 (1978), pp. 238–249. DOI.DOI
  9. [9]J. Lawrence and L. Weinberg. “Unions of oriented matroids”. Linear Algebra and its Applications 41 (1981), pp. 183–200. DOI.
  10. [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. [11]K. Murota. “Finding optimal minors of valuated bimatroids”. Applied Mathematics Letters 8.4 (1995), pp. 37–41. DOI.DOI
  12. [12]K. Murota and A. Tamura. “On Circuit Valuation of Matroids”. Advances in Applied Mathematics 26.3 (2001), pp. 192–225. DOI.DOI
  13. [13]A. Schrijver. “Matroids and linking systems”. J. Combin. Theory Ser. B 26.3 (1979), pp. 349–369. DOI.
  14. [14]D. E. Speyer. “Tropical linear spaces”. SIAM J. Discrete Math. 22.4 (2008), pp. 1527–1558. DOI.DOI
  15. [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

Paper details

vlnc:W_nfpxf3fr
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

None listed by the authors

View statement
Looking for related papers…
Contents