Tag Archives: geometry of cocircuits

The combinatorial derived matroid

Posted on by
Reply

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):

Two possibilities for the derived matroid of $U_{3,6}$

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 Vámos matroid

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.

  1. $\emptyset\notin\mathcal{D}$;
  2. if $D\in\mathcal{D}$ and $D\subseteq D’$ then $D’\in\mathcal{D}$;
  3. 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:

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

The geometry of cocircuits and circuits. A tombeau for Henry Crapo 1933 — 2019

Posted on by
Reply

A guest post by Joseph Kung.


The road less traveled

Henry Howland Crapo died on September 3, 2019, at the age of 86. Henry’s mathematical work has had significant influence in at least three areas: his early results were landmarks in matroid theory, he was one of the creators of structural topology, and he was one of the first to apply exterior or Cayley algebra methods to matroid theory, computational geometry and automatic theorem proving.

Henry’s life did not follow the usual path of an academic mathematician in the second half of the twentieth century. After a short more-or-less conventional academic career, ending as professor at the University of Waterloo, he chose to resign and pursue a peripatetic career in France, taking inappropriately junior positions. This is probably not because he needed a job, as he had private means, but to gain residency in France. He achieved this, eventually retiring to La Vacquerie (Hérault), a small village in the mountains near Montpellier. His beautifully restored house, on the Grand’Rue, was the venue for several private conferences — the Moutons Matheux — first in structural topology and then in matroid theory. Henry was a contrarian, not only in mathematics, but in life. Henry’s politics were to the left (in the French sense), and they were never dogmatic, but infused with a deep humanity. He was fond of conspiracy theories, but as intellectual exercises, so that it was possible to discuss issues like the Kennedy assassination with him, reasonably and humorously. He was constantly exploring the possibilities and improbabilities of the human mind, individual and collective; for example, as the guests and performers of a musical evening at a Moutons Matheux, one found a violist da gamba playing J.S. Bach and Tobias Hume, and a Dervish musician singing traditional melodies, accompanying himself on the Saz.

On a more personal note, my introduction to matroids is through Henry’s book with Rota “On the Foundations of Combinatorial Theory: Combinatorial Geometries”, the flimsy preliminary edition which, to be honest, taught me a minimum about matroids in the technical sense, but a maximum about their deep structures. I also “lifted” much of the chapter on strong maps in the book “Theory of Matroids” from his Bowdoin lecture notes. I should also apologize to Henry for not using the ineffable effable effanineffable name “combinatorial geometry” instead of “matroid”, but the latter name has stuck, and there is no doing anything about it.

I should also mention two expository or survey papers Henry wrote. The first is “Structural topology, or the fine art of rediscovery” (MR1488863) and the second ``Ten abandoned gold mines” (MR1854472). These papers are well-worth reading.

The geometry of circuits

I had intended to write in some detail about Henry’s work, but cold reflection soon indicates that this is a task which will almost certainly exceed my own mortality. One way to remember Henry is to write about one of his idées fixes, the problem of defining a matroid on the set of circuits or the set of cocircuits of a matroid. The program of finding (all) the dependencies on the circuits of a matroid was stated by Gian-Carlo Rota, in the 1960’s, as a part of his vision that matroid theory is an “arithmetical” or discrete counterpart of classical invariant theory. Thus, this program asks an analogue of the algebraic geometry question of “finding the syzygies among the syzygies”. This is an easy task when the matroid comes with a representation over a field, but I believe, impossible in general. Henry’s favorite approach was to build a free exterior algebra with “formal” coordinates from the matroid. One can then perform algebraic or symbolic calculations with formal coordinates as if the matroid were represented in a vector space. The ultimate version of this is the Whitney algebra, which Henry developed in joint work with Bill Schmitt. See the paper “The Whitney algebra of a matroid” (MR1779781). However, I think that there are intrinsic difficulties in this approach because the combinatorial interpretation of one algebraic identity is sufficiently ambiguous that when repeated, as is necessary when an algebraic derivation is performed, the interpretation usually becomes meaningless. However, there are exceptions — the Rota basis conjecture, for example — which show that this approach could be fruitful. Henry wrote an introductory article “The geometry of circuits” (unpublished) about this approach.

The geometry of cocircuits

In the remainder of this note, I will describe what seems to be practical from Henry’s ideas. I begin by describing a way of building a matroid of cocircuits from a given representation of a matroid. Before starting, I should say all this is elementary linear algebra. Some would say, and they would be right, that it is a special case of the theory of chain groups of Tutte.

Recall that a cocircuit is the complement of a copoint. (A copoint is also known as a hyperplane.) Let $M^{(0)}$ be a matroid of rank $r$ with a specific representation as a multiset $S$ of vectors in $\mathbb{K}^r$, where $\mathbb{K}$ is a field. For each cocircuit $D$, the copoint $S \backslash D$ spans a unique (linear) hyperplane in $\mathbb{K}^r$ and hence, each cocircuit $D$ defines a linear functional $\alpha_D$, unique up to a non-zero multiplicative factor, whose value on a vector $x$ we denote by
\[
\langle \alpha_D | x \rangle.
\]
For each vector $x$ in $S$, $\langle \alpha_D | x \rangle \neq 0$ if and only if $x$ is in the cocircuit $D$. It is easy to check that the cocircuit matrix, with columns indexed by $S$ and rows by the set $\mathcal{D}$ of cocircuits, with the $D,x$-entry equal to $\langle \alpha_D | x \rangle$, is a representation of $M^{(0)}$. Transposing the matrix, one obtains a matroid $M^{(1)}$ on the set $\mathcal{D}$ of cocircuits, This matroid is the cocircuit matroid of $M^{(0)}$. It has the same rank $r$ as $M^{(0)}$. Among the copoints of $M^{(1)}$ are the sets $E_a,$ where $a$ is a vector in $S$ and
\[
E_a = \{D: a \in D\},
\]
the set of all copoints containing the vector $a$. If $M^{(0)}$ is simple, the map $a \mapsto E_a$ embeds $S$ injectively into $\mathcal{D}$.

Deleting rows from the transpose of the cocircuit matrix so that there remains a matrix having $r$ rows and rank $r$, one obtains a representation of $M^{(1)}$ on which one can repeat the construction. Iterating, one constructs a sequence — I will call it the Crapo sequence —
\[
M^{(0)}, M^{(1)}, M^{(2)}, M^{(3)}, \,\,\ldots
\]
with $M^{(i)}$ embedded naturally in $M^{(i+2)},$ so that there are two non-decreasing sequences of matroids, all having the same rank $r$ as the original matroid $M^{(0)}$, one starting with the matroid and the other starting with the cocircuit matroid.

It is not easy to describe the Crapo sequence given $M^{(0)}$, but an example might clarify the situation. Let $M^{(0)} = M(K_4)$, the cycle matroid of the complete graph on $4$ vertices, or as Henry would have preferred, the complete quadrilateral, with the specific representation $e_1,e_2,e_3,e_1-e_2, e_1-e_3,e_2 – e_3$. The matroid $M(K_4)$ has $7$ copoints (four $3$-point lines and three $2$-point lines), so if one takes the representation over $\mathrm{GF}(2),$ then $M^{(1)}$ is the Fano plane $F_7$ and the Crapo sequence stabilizes, with $M^{(i)}= F_7$ for $i \geq 2$. On the other hand, if one takes the representation over $\mathrm{GF}(3)$, then $M^{(1)}$ is the non-Fano configuration $F_7^-$. The non-Fano configuration has $9$ copoints ($6$ are $3$-point lines and $3$ are $2$-point lines) with $4$ points on (exactly) $3$ lines, and $3$ points on $4$-lines. From this, one sees that $M^{(2)}$ has nine points, three $4$-point lines, four $3$-point lines, and perhaps more lines. One concludes that $M^{(2)}$ is the rank-$3$ Dowling matroid $Q_3$ on the group $\{+1,-1\}$. The matroid $Q_3$ has six additional $2$-point lines, making a total of thirteen lines. Thus, $M^{(3)}$ is the ternary projective plane $\mathrm{PG}(2,3)$. The Crapo sequence now stabilizes and $M^{(i)} = \mathrm{PG}(2,3)$ forever after. Over $\mathrm{GF}(5)$ and larger fields, the situation is much more complicated and I do not know simple descriptions, although as will be shown shortly, the Crapo sequence of $M(K_4)$ eventually stabilizes over any finite field. I might note that since $M(K_n)$ has $2^{n-1}-1$ copoints, its Crapo sequence stabilizes at $i=1$ over $\mathrm{GF}(2)$.

I should make two remarks at this point. The first is that the construction of $M^{(1)}$ from $M^{(0)}$ may change if one chose inequivalent representations. An example is $U_{6,3}$ and its two inequivalent representations. The second is that it is possible to define a looser structure, that of $2$- or line-closure, on the set of cocircuits; the closed sets in this structure are the linear subclasses of Tutte. Being the closed sets of a closure, the linear subclasses form a lattice, with the points (that is, the elements covering the minimum, in this case the empty set) being the one-element linear subclasses consisting of one copoint. Henry discussed this theory in his papers “Single-element extensions of matroids” (MR0190045) and “Erecting geometries” (MR0272655, 0277407).

It is almost true that if one takes a matroid with a specific representation over a finite field $\mathrm{GF}(q)$, then the Crapo sequence $M^{(i)}$ eventually stabilizes at $\mathrm{PG}(r-1,q^{\prime})$, where $q^{\prime}$ divides $q$. It is clear that if the sequence reaches a projective geometry, then the sequence stabilizes. For a sequence to stabilize at $M^{(i)}$, the number of points and the number of copoints must be the same, and a theorem (discovered many times) says that $M^{(i)}$ must be modular, and by a theorem of G. Birkhoff, a direct sum of projective geometries. Thus, the assertion is true except when $M^{(0)} = U_{r,r}$. In particular, with one exception, if one starts with a representation of $M^{(0)}$ over a finite field $\mathbb{K}$ and $r \geq 3,$ then from the projective geometry in the Crapo sequence, one can recover a subfield of $\mathbb{K}$. When one takes a representation over a field of characteristic $0$ (and $M^{(0)} \neq U_{r,r}$), then the Crapo sequence cannot stabilize at a finite index $i$, but one should be able to take an infinite limit to get a geometric structure in which points are in bijection with copoints.

The matroid of circuits of a matroid $M$ with a representation as a multiset of vectors can be defined as the cocircuit matroid of the dual $M^{\perp}$ with an orthogonal dual of the given representation. If the original matroid has size $n$ and rank $r$, the circuit matroid has rank $n-r$ and iterating this construction usually gives a sequence which blows up. See the papers of Longyear (MR566870) and Oxley and Wang (MR4014616). There are specific problems about circuit matroids which are interesting. For example, one can ask whether there is a matroid of circuits of a transversal matroid which is a gammoid. (The orthogonal dual of a transversal matroid is a gammoid, and the transpose of a circuit matrix gives a representation of the dual, so the answer is probably affirmative.) Or, one can ask for a construction (which has to be combinatorial) of a circuit matroid of a paving matroid (if one exists).

Adjoints

The adjoint is an attempt at constructing the cocircuit matroid without using a representation. I will work with geometric lattices rather than matroids. The opposite $P^{\mathrm{opp}}$ of a partial order $P$ is the partial order obtained by reversing the order relation. An adjoint $\mathrm{Adj}(L)$ of a geometric lattice $L$ is a geometric lattice of the same rank as $L$ such that there is a one-to-one order-preserving function mapping points of $L^{\mathrm{opp}}$ (which are copoints of $L$) into the points of $\mathrm{Adj}(L)$.

Alan Cheung (MR0373976) showed that the lattice of flats of the Vamós matroid (or the “twisted cube”) does not have an adjoint. Alan proved this using the lattice of linear subclasses. The Vamós matroid is the smallest rank-$4$ paving matroid which is not representable over any field as it is a relaxation of the configuration given by the bundle theorem in projective geometry. It might be worthwhile to look at bigger rank-$4$ paving matroids: do the non-representable ones also not have adjoints? The Vamós matroid is self-dual. A natural question is whether the existence of an adjoint for the lattice of flats of a matroid implies the existence of an adjoint for the lattice of flats of its dual.

The question now arises of what happens in rank $3$. In rank $3$ or the plane, if two lines do not intersect at a point, then it is always possible to add that point of intersection. Thus adjoints exist at rank $3$. When one iterates taking adjoints, the Crapo sequence does not necessarily stabilize at a finite projective plane, but it is possible to construct the infinite limit. This limit is the free closure of D.R. Hughes; see his book “Projective Planes”, written with Piper (MR0333959). It might be of interest to extend the Hughes construction for rank $4.$

I end with matroids which can be said to be hiding in plain sight. Henry was the first to look at what are now called paving matroids. He and Rota called them Hartmanis partitions, which is correct, but hardly “catchy”. (Incidentally, Hartmanis’ papers (MR0098358, 0086045) are well worth studying.) In his work with Blackburn and Higgs (MR0419270) on cataloging all simple matroids having at most $8$ elements, a remarkably far-sighted effort for its time, it was observed that paving matroids seem to “predominate”, an observation which has now been formalized as a conjecture. However, while much work is done on asymptotic predomination, the matroids themselves have hardly been studied. One way to study paving matroids in detail (suggested by Cheung’s work), is to look at the lattice of linear subclasses, which should answer questions such as representability or the existence of adjoints.