This post is co-authored by Ragnar Freij-Hollanti.
As has been mentioned on this blog before, an idée fixe of the late Henry Crapo was to naturally define a matroid $\delta M$ whose ground set is the collection $\mathcal{C}(M)$ of circuits (or the collection $\mathcal{C}(M^*)$ of cocircuits) of an underlying matroid $M$. Similar questions have also been asked by Gian-Carlo Rota. We will call such a construction a derived matroid of $M$, partly in analogy with the construction of derived codes in coding theory. Throughout this blogpost, $n$ will denote the size and $k$ will denote the rank of $M$.
The derived matroid could be seen as a combinatorialization of the notion of syzygies and resolutions in commutative algebra, regarding circuits as combinatorial “relations”, which generate a space in which we can again study “relations”, and so on. From this viewpoint, it is natural to try to define a matroid structure on the set of circuits. On the other hand, it seems like a desirable feature that the nullity of $M$ would give, or at least bound, the number of “independent” circuits (i.e. relations) in $M$, or in other words that the number of independent cocircuits would equal (or be bounded by) the nullity of $M^*$, which is the rank of $M$. In this light studying the sequence of repeated derivations of a matroids $M$ would be more natural if $\delta M$ had as its ground set the cocircuits of $M$. Since the cocircuits are in natural bijection with the hyperplanes of $M$, a derived matroid with ground set $\mathcal{C}(M^*)$ would model the hyperplane arrangement described by the point set in the representable case. There are thus good arguments both in favour of grounding the derived matroid on $\mathcal{C}(M)$ and on $\mathcal{C}(M^*)$. In our paper, we choose the first alternative, but the last word has hardly been said in this debate, and of course, one definition can be obtained from the other by dualizing.
Let us first consider the case for represented matroids, and let $G$ be a $k\times n$ matrix of full rank representing $M$ over a field $\mathbb{F}$. Then, every circuit $C\in\mathcal{C}(M)$ is the inclusion-minimal support of a vector $q_C\in\mathbb{F}^n$ such that $G q_C=\mathbf{0}$, and this vector is unique up to scalar multiple. The collection of vectors $\{q_C\}_{C\in\mathcal{C}(M)}$ represent some matroid with ground set $\mathcal{C}(M)$, and we will denote this matroid by $\delta_{OW}(G)$, where the subscript refers to the authors Oxley and Wang, who studied this construction [OW19].
It is not difficult to see that $\delta_{OW}(G)$ has rank $n-k$, because the circuit vectors together generate the null space of the matrix $G$. While this is certainly a desirable feature, it is an unfortunate fact that the construction $\delta_{OW}$ depends on $G$ rather than only on $M$. The geometrically easiest illustration of this feature may be when $M$ is the uniform matroid $U_{3,6}$, represented by a configuration $P$ of six points in general position in the projective plane. Then, the hyperplane arrangement of the $\binom{6}{2}=15$ lines (through pairs of $P$) can be of two different kinds, as shown in the picture below (not all lines are drawn):
Indeed, in addition the five lines intersecting in each point of $P$, it will generically be the case that all other intersections of lines are distinct. However, it is also possible that three of the lines, that do not share a point in $P$, might meet in a point in the projective plane. In this latter case, the cocircuits corresponding to the three lines will be “dependent”; in the former case they will be “independent” in $\delta_{OW}(Q^*)$.
It is fair to say that the dependence between the three lines in the previous example is “accidental”, in that it is not forced by the matroid structure of $U_{3,6}$ itself. If we are to define “the” derived matroid of the matroid $U_{3,6}$ combinatorially, we in particular want the complements of these lines to be independent. Following this line of thought, we consider independence to be the generic state of things, while dependence is forced by constraints coming from the underlying matroid. Our construction of $\delta M$ is thus twofold. First we identify which collections of circuits “have to” be dependent in any “reasonably defined” derived matroid of $M$. After this, we add just enough other dependent sets, to guarantee that $\delta M$ is indeed a matroid, and we do it in such a way as to not introduce unnecessary dependent sets, and in particular not in low rank.
Let us illustrate this procedure with the infamously non-representable Vámos matroid $M$. All sets of three or fewer elements are independent and among the sets of four elements only the five depicted as grey rectangles in the figure are circuits. All sets of five or more elements are dependent.
The ground set of the derived matroid $\delta M$ has 41 elements, the circuits of $M$. If we consider the three planes $abcd$, $adef$ and $bcef$, we intuitively want this to be a dependent set in $\delta M$, because it “looks like” these planes make a “circuit”. To make this mathematically more precise, we can say that this set of circuits is dependent because its size (3) is larger than the nullity in $M$ of the union of all its elements (these six elements have nullity 2 in $M$). That is to say, we want that a set of circuits is dependent in $M$ if it belongs to the family
$$\mathcal{A}_0:=\{A\subseteq\mathcal{C}:|A|>n(\cup_{C\in A}C)\}.$$
It is readily checked that in the previous example of $U_{6,3}$, the three discussed lines are not in this family, because $3\not>3$.
The above family $\mathcal{A}_0$ gives us a precise description of which collections of circuits “have to” be dependent in $\delta M$. Note that this is a combinatorial description: it does not depend on a representation of the matroid. What we want to do now, is make sure that we find all dependent sets of the derived matroid. To see how to get to this, consider the axioms for the collection $\mathcal{D}$ of dependent sets of a matroid.
- $\emptyset\notin\mathcal{D}$;
- if $D\in\mathcal{D}$ and $D\subseteq D’$ then $D’\in\mathcal{D}$;
- if $D_1,D_2\in\mathcal{D}$ and $D_1\cap D_2\notin\mathcal{D}$, then $(D_1\cup D_2)\setminus\{e\}\in\mathcal{D}$ for all $e\in D_1\cap D_2$.
Our collection $\mathcal{A}_0$ satisfies the first two axioms, but in general, it does not satisfy the third. So we want to add extra elements in order to get a collection that does satisfy (D3). There are two ways to do this, as we see from a logical rewriting of the axiom:
- If $D_1, D_2\in\mathcal{D}$, then $D_1\cap D_2\in\mathcal{D}$ or $(D_1\cup D_2)\setminus\{e\}\in\mathcal{D}$ for all $e\in D_1\cap D_2$.
This means that for any $A_1,A_2\in\mathcal{A}_0$, we can either decide that $A_1\cap A_2$ is dependent, or that $(A_1\cup A_2)\setminus{C}$ is dependent for all $C\in A_1\cap A_2$ (or both). If we decide on the first, we will get a lot of small dependent sets, and often this leads to a derived matroid of rank 0. We therefore decide to define the following operations.
Definition. Let $\mathcal{C}$ be the set of circuits of some matroid, and let $\mathcal{A}\subseteq \mathcal{C}$. Then we define the collections
$$\epsilon(\mathcal{A})=\mathcal{A}\cup\left\{(A_1 \cup A_2) \setminus {C} : A_1, A_2\in \mathcal{A}, A_1\cap A_2\not\in\mathcal{A}, C\in A_1\cap A_2\right\}$$ and $${\uparrow}\mathcal{A}=\{A\subseteq \mathcal{C}: \exists A’\in\mathcal{A}: A’\subseteq A\}.$$
Observe that, by definition, $\mathcal{A}\subseteq {{\uparrow} \mathcal{A}}$ and $\mathcal{A}\subseteq \epsilon(\mathcal{A})$ for every $\mathcal{A}\subseteq2^\mathcal{C}$. The operations ${\uparrow}$ and $\epsilon$ are designed to guarantee properties (D2) and (D3) in the matroid axioms.
Definition. Let $M$ be a matroid, and $\mathcal{C}=\mathcal{C}(M)$ its collection of circuits. Define the collection
$$ \mathcal{A}_0:=\{A \subseteq \mathcal{C}: |A|> n(\cup_{C\in A} C)\}. $$
Inductively, we let $\mathcal{A}_{i+1}={\uparrow}\epsilon(\mathcal{A}_i)$ for $i\geq 1$, and
$$\mathcal{A}=\bigcup_{i\geq 0} \mathcal{A}_i.$$
Note that the sequence $\mathcal{A}_i$ is both increasing and contained in the finite set $2^\mathcal{C}$. Hence, we have that $\mathcal{A}_0\subseteq\mathcal{A}$ and $\mathcal{A}=\mathcal{A}_n$ for some $n\geq 0$.
Definition (combinatorial derived matroid). Let $M$ be a matroid with circuits $\mathcal{C}$. Then the combinatorial derived matroid $\delta M$ is a matroid with ground set $\mathcal{C}(M)$ and dependent sets $\mathcal{A}$.
By carefully checking the dependent axioms, we can prove that this definition gives indeed a matroid. In fact, we can prove two more ways to construct this derived matroid, by means of its circuits: we refer the interested reader to the full paper [FJK23].
Theorem. For any matroid $M=(E,\mathcal{C})$ the collection $\mathcal{A}$ is the collection of dependent sets of some matroid with ground set $\mathcal{C}$.
This is good news! We now have a definition of a derived matroid that is purely combinatorial: it does not depend on a representation, and hence it exists for any matroid. As far as we know, this is the first definition of this kind. We also managed to show that there is more good news: this definition behaves well with connectedness. That is, the derived matroid of a direct sum is the direct sum of the derived matroids of the connected components.
Unfortunately, it is not all good news. It is not difficult to show that the rank of $\delta M$ is bounded by $n-k$, as desired, but equality does not always hold. Computer calculations by Knutsen [Knu23] show that the rank of the derived Vámos matroid is 3, and not 4. However, this news is not as bad as it sounds, since the Vámos matroid was shown to not have an adjoint by Cheung [Che74]. The construction of the adjoint of a matroid is, in some sense, the dual of that of the derived matroid: it has the set of cocircuits of $M$ as its ground set.
Many questions are still open regarding this construction of $\delta M$. Most prominently: how does this construction relate to earlier constructions of the derived matroid? In particularly, that of Oxley and Wang, but also to the adjoint of a matroid. For more questions, we refer to the full paper [FJK23]. We hope this post inspired you to think more about derived matroids!
References
[Che74] Cheung, A.L.C. (1974). Adjoints of a geometry. Canadian Mathematical Bulletin, 17(3), 363-365.
[FJK23] Freij-Hollanti, R. & Jurrius, R.P.M.J. & Kuznetsova, O. (2023). Combinatorial Derived Matroids. Electronic Journal of Combinatorics, 30(2), P2.8.
[Knu23] Knutsen, T.D. (2023). Codes, matroids and derived matroids. Master thesis, UiT Arctic University of Norway.
[OW19] Oxley, J & Wang, S. (2019). Dependencies among dependencies in matroids. Electronic Journal of Combinatorics, 26(3), P3.46.
