A Celebration of Spans

Nine years ago, I wrote a July 4th blog post about matroids called A Celebration of Independence. Today, I’d like to talk about independence’s lesser-known sibling. In particular, I want to describe a characterization of matroids due to Paul Vaderlind that I feel ought to be better known.

In most books and articles on matroid theory, the notion of “spanning set” plays a subordinate role to “independent set”, even though they are dual concepts (a subset of a matroid is independent iff its complement is spanning in the dual matroid). While this doesn’t particularly bother me, I do feel like it’s the interplay between the notions of “linear independence” and “span” which is the secret sauce of linear algebra, but somehow this tends to be obscured in matroid theory, which is supposed to be a combinatorial avatar of linear algebra.

In particular, a result which one might call the “fundamental theorem of linear algebra” is that a maximal independent set is the same thing as a minimal spanning set. In matroid theory, this is sometimes presented as tautological, since some authors define a set to be spanning if it contains a basis, whereas an independent set is one that is contained in a basis. What I’d like to discuss here is the fact that, with a suitable definition of “span”, matroids can be completely characterized by the fact that a maximal independent set is the same thing as a minimal spanning set. In the lingo of the biz, we say that this gives a “cryptomorphic” characterization of matroids.

What does it mean to span?

Before making things precise, let’s think a bit about the relationship between independence and spanning in linear algebra. Given a set of vectors v_1,\ldots,v_n in {\mathbb R}^m, we say they are linearly independent if c_1 v_1 + \ldots + c_nv_n = 0 with c_1,\ldots,c_n \in {\mathbb R} implies c_1 = \cdots = c_n = 0, and linearly dependent otherwise. And we say that v_1,\ldots,v_n is spanning if for every v \in {\mathbb R}^m there exist c_1,\ldots,c_n \in {\mathbb R} such that v = c_1 v_1 + \ldots + c_n v_n.

Notice that we can actually define “spanning” in terms of independence: v_1,\ldots,v_n is spanning iff for every v \in {\mathbb R}^m, there is an independent subset I of \{ v_1,\ldots,v_n \} such that I \cup \{ v \} is dependent.

We can make a similar definition in matroid theory: if M is a matroid on the finite set E, given by specifying either its independent subsets or circuits (which are the minimal dependent sets), a subset X of E is spanning iff for every e \in E, there is an independent subset I of E such that I \cup \{ e \} is dependent. Equivalently, X is spanning iff for every e \in E, there is a circuit C with e \in C \subseteq X \cup \{ e \}.

This definition works well, and is equivalent (by a non-trivial argument) to the characterizations given above: X is spanning iff it contains a basis of M iff E - X is independent in M^*. This is all well-known, and easy to find in references such as Oxley’s book “Matroid Theory”.

However, if we wish to characterize matroids in terms of a “max independent = min spanning” axiom, it turns out that we need to make a slight tweak to the definition of “spanning”. To understand the subtlety, consider the following simple result of linear algebra:

Lemma: If v is in the span of \{ v_1,\ldots,v_n \} and v' is in the span of \{ v, v_1,\ldots,v_n \}, then v' is in the span of \{ v_1,\ldots,v_n \}.

The proof is evident: if v = c_1 v_1 + \ldots + c_n v_n and v' = d v + d_1 v_1 + \cdots + d_n v_n, then v' = (dc_1 + d_1)v_1 + \cdots + (dc_n + d_n) v_n.

The issue is that in the purely combinatorial setting of matroids, we don’t have a notion of “addition”, so it’s difficult to mimic this argument. One can use the (strong) circuit elimination axiom for matroids to accomplish something similar, but if we’re trying to characterize matroids in terms of some abstract notions of “independent” and “spanning”, we don’t have that tool available either. So it’s best to just buckle down and take the “transitive closure” of the above definition. Here’s what I mean…

Clutters, circuits, and spans

The circuits of a matroid (which determine the independent sets and vice-versa) are non-empty and pairwise incomparable – a collection {\mathcal C} of subsets of a set E with these properties is called a clutter. Formally, {\mathcal C} is a clutter if every element of {\mathcal C} is non-empty and whenever C,C' \in {\mathcal C} satisfy C \subseteq C' we have C = C'.

Given a clutter {\mathcal C} on a finite set E, we define a set X \subseteq E to be independent with respect to {\mathcal C} if X does not contain any element of {\mathcal C}. The span of X \subseteq E with respect to {\mathcal C}, which I will denote by {\rm span}_{\mathcal C}(X), consists of X together with all elements e \not\in X such that there is a sequence e_1,\ldots,e_k = e and C_1,\ldots,C_k \in {\mathcal C} such that e_j \in C_j \subseteq X \cup \{ e_1,\ldots,e_j \} for all j=1\ldots,k. And we say that X is spanning if {\rm span}_{\mathcal C}(X) = E. (This is just “iterating” our previous notion of what it means for a set to be spanning.)

If we really want to avoid iteration, there is a trick we can use. Define a subset F of E to be a flat (with respect to the clutter {\mathcal C}) if there do not exist an element e \in E - F and a “circuit” C \in {\mathcal C} such that e \in C \subset F \cup \{ e \}. (This is the combinatorial analogue of being a linear subspace.) Now define the span of X to be the smallest flat containing X (this is well-defined because E itself is clearly a flat and the intersection of two flats is also a flat), and say that X is spanning if this smallest flat is E itself. It is not hard to see that these definitions agree with the previous ones.

The main theorem of this post is the following:

Theorem (Vaderlind): A clutter {\mathcal C} on the finite set E is the collection of circuits of a matroid M if and only if the maximal independent sets of E coincide with the minimal spanning sets of E.

I will not give a full proof of the theorem, as it’s a bit tedious to give all the details; for that, I refer to Vaderlind’s paper. (Note, however, that there is a typo in the statement of his Proposition 1.2: it should say \widetilde{I(M)}, not I(M).) I will instead give a brief outline of the proof, along with some interesting consequences.

Idea of the proof

Vaderlind’s proof combines three different assertions, each interesting in their own right. As one might expect, the proof is closely related to matroid duality, so we will need to introduce a suitable notion of “orthogonality” in the context of clutters. (I will use my own notation and terminology rather than Vaderlind’s, and I will refer to elements of {\mathcal C} as “circuits”, even though {\mathcal C} is just an abstract clutter and not necessarily a matroid.)

First of all, to any collection {\mathcal S} of subsets of E, there is a canonically associated clutter c({\mathcal S}) given by taking the minimal non-empty elements of {\mathcal S} with respect to inclusion.

Now, given a clutter {\mathcal C}, we define its orthogonal complement {\mathcal C}^\perp to consist of all subsets D of E with |C \cap D| \neq 1 for all C \in {\mathcal C}. We call {\mathcal C}^* = c({\mathcal C}^\perp) the dual clutter, and we refer to elements of {\mathcal C}^* as cocircuits. This mimics a familiar characterization of cocircuits in matroid theory (they are characterized by the fact that a circuit and a cocircuit cannot intersect in a single element), which in turn reflects the trivial observation in linear algebra that if the dot product of two vectors is zero, there cannot be just a single index for which both vectors have nonzero coordinates.

The first two results we need, which are purely about clutters and have nothing specific to do with matroids, are the following.

Proposition 1 (Proposition 1.1 in Vaderlind, due to Edmonds and Fulkerson): Given a clutter {\mathcal C}, let {\mathcal C}^\dagger consist of all subsets X of E meeting every element of {\mathcal C}, and let {\mathcal C}^\circ = c({\mathcal C}^\dagger). Then {\mathcal C}^{\circ\circ} = {\mathcal C}.

Proposition 2 (Proposition 2.6 in Vaderlind): Let {\mathcal C} be a clutter. Then X \subseteq E is a minimal spanning set with respect to {\mathcal C} if and only if the complement of X is a maximal independent set with respect to {\mathcal C}^*.

(It is here that one must be careful to distinguish between the “naive span” and “transitive span”.)

The proofs are not difficult, but it’s a moderate bookkeeping challenge to keep track of all the minima and maxima involved.

To state the other result we need, which does involve matroids, define an I-basis of a clutter {\mathcal C} to be a maximal independent set and an S-basis of {\mathcal C} to be a minimal spanning set. It is easy to see that B \subseteq E is an I-basis with respect to {\mathcal C} if and only if its complement \tilde{B} is a minimal non-empty set meeting every circuit, i.e., \tilde{B} \in {\mathcal C}^\circ.

Let B_I({\mathcal C}) denote the set of I-bases of {\mathcal C}, and let B_S({\mathcal C}) denote the set of S-bases of {\mathcal C}.

With this terminology, Proposition 2 says that the complement of B_I({\mathcal C}^*) is B_S({\mathcal C}), and the observation in the previous paragraph (applied to the clutter {\mathcal C}^*) says that the complement of B_I({\mathcal C}^*) is equal to ({\mathcal C}^*)^\circ. Thus B_S({\mathcal C}) = ({\mathcal C}^*)^\circ.

Proposition 3 (Proposition 2.3 in Vaderlind): A clutter {\mathcal C} is the collection of circuits of a matroid if and only if {\mathcal C}^* = B_I({\mathcal C})^\circ, i.e., the cocircuits of {\mathcal C} are the minimal non-empty sets meeting every I-basis.

Proof: The fact that the cocircuits of a matroid have this property is well-known. For the other direction, we need to prove that {\mathcal C} has the circuit elimination property: if C_1, C_2 \in {\mathcal C} are distinct and e \in C_1 \cap C_2, then there exists C_3 \in {\mathcal C} such that C_3 \subseteq C_1 \cup C_2 - \{ e \}.

Given such circuits C_1 and C_2 containing e, if C_1 \cup C_2 - \{ e \} does not contain any circuit then C_1 \cup C_2 - \{ e \} is independent, and so is contained in a maximal independent set B. The complement \tilde{B} of B is a minimal non-empty set meeting every circuit. Since C_i \cap \tilde{B} \neq\emptyset and C_1 \cup C_2 - \{ e \} \subseteq B, we must have C_i \cap \tilde{B} = \{ e \} for i=1,2. Let f \in C_1, f \neq e. Then f \in B, and since \tilde{B} meets every I-basis except for B, \tilde{B} \cup \{ f \} meets every I-basis. So, by hypothesis, there exists a cocircuit D \in {\mathcal C}^* such that D \subseteq \tilde{B} \cup \{ f \}. Moreover, we must have f \in D, since otherwise D would not meet B. It follows that f \in C_1 \cap D. As |C_1 \cap D| \neq 1, we must have e \in D also. This implies that e \in D \cap C_2, and since |C_2 \cap D| \neq 1, we must have f \in C_2. As this holds for all f \neq e in C_1, and e \in C_1 \cap C_2, we conclude that C_1 \subseteq C_2, contradicting the fact that {\mathcal C} is a clutter. Q.E.D.

Combining Proposition 3 and Proposition 1, we obtain:

Corollary 1: A clutter {\mathcal C} is the collection of circuits of a matroid if and only if ({\mathcal C}^*)^\circ = B_I({\mathcal C}).

And combining this with our previous observation that B_S({\mathcal C}) = ({\mathcal C}^*)^\circ gives Vaderlind’s theorem:

Theorem 1: A clutter {\mathcal C} is the collection of circuits of a matroid if and only if B_I({\mathcal C})= B_S({\mathcal C}).

A self-dual cryptomorphism

To conclude this post, we note that by Proposition 2, for any clutter {\mathcal C} we have B \in B_I({\mathcal C}) iff \tilde{B} \in B_S({\mathcal C}^*). So by Theorem 1, {\mathcal C} is the collection of circuits of a matroid if and only if B_I({\mathcal C}) is the complement of B_I({\mathcal C}^*).

The proof of Proposition 3 shows that, in fact, the following mild generalization of this statement holds:

Theorem 2: Clutters {\mathcal C} and {\mathcal D} on E are the circuits and cocircuits, respectively, of a matroid M if and only if:

(1) {\mathcal C} and {\mathcal D} are orthogonal, meaning that |C \cap D| \neq 1 for all C \in {\mathcal C} and D \in {\mathcal D}; and

(2) B_I({\mathcal C}) is the complement of B_I({\mathcal D}).

I have not ever seen this result written down before, although I imagine it is known to some experts (and perhaps one of the readers of this blog can provide a reference!).

What’s interesting about this result is that it is “self-dual”, treating circuits and cocircuits in a symmetric way.

Here’s another cryptomorphism which is easily seen to be equivalent to Theorem 1. For the statement, define a basis (with no modifier) of a clutter {\mathcal C} to be a set which is both independent and spanning.

Theorem 3: A clutter {\mathcal C} is the collection of circuits of a matroid if and only if:

(1) The bases of {\mathcal C} are pairwise incomparable under inclusion, i.e., B_1 \subseteq B_2 implies B_1 = B_2.

(2) For every independent set I and every spanning set S, there exists a basis B with I \subseteq B \subseteq S.

Again, this is not something I’ve ever seen written down, although (1) and (2) are of course well-known properties of matroid bases.

Concluding remarks

1) If M is a matroid, M^{**} = M. For a general clutter {\mathcal C}, the condition {\mathcal C}^{**} = {\mathcal C} defines what Vaderlind calls a semimatroid.

2) If M is a matroid, then the “naive span” and “transitive span” of a set X coincide. In other words, {\rm span}_{\mathcal C}(X) consists of X together with all elements e \not\in X such that there is a circuit C \in {\mathcal C} with e \in C \subseteq X \cup \{ e \}. To see this, recall from Oxley Proposition 4.1.12 that matroids satisfy the following strong circuit elimination axiom: if C_1,C_2 are circuits, e \in C_1 \cap C_2, f \in C_1 - C_2, then there exists a circuit C_3 \subseteq C_1 \cup C_2 with f \in C_3. This implies, by a straightforward argument, that if there are circuits C_1,C_2 and a set X with e \in C_1 \subseteq X \cup \{ e \} and f \in C_2 \subseteq X \cup \{ e,f \}, then there is a circuit C_3 with f \in C_3 \subseteq X \cup \{ f \}. By induction, it follows that the naive span and transitive span of X coincide.

3) I don’t actually have an explicit example showing that the naive span is insufficient in Theorem 1. I leave this as a problem for readers of this blog: find a clutter {\mathcal C} which is not a matroid but has the property that maximal independent sets and minimal spanning sets coincide, where “spanning” is defined as in Remark 2.

4) The only other matroid cryptomorphism I know of which is “self-dual” is the following criterion due to Minty. A painting of a set E is a partition of E into three disjoint subsets, which (in honor of Independence Day) we’ll call red, white, and blue, such that there is a unique element painted white. With this terminology, Minty’s criterion is that clutters {\mathcal C} and {\mathcal D} on E are the circuits and cocircuits, respectively, of a matroid M if and only if for every painting of E, precisely one of the following holds: (1) there is a blue-white member of {\mathcal C} containing the white element; or (2) there is a red-white member of {\mathcal D} containing the white element.

5) In 2015, Paul Vaderlind gave a wonderful TedX talk entitled “Do the math, change the world” about the challenges faced by STEM students in the developing world. You can watch it here.

This entry was posted in Combinatorics, Oldies but goodies and tagged , . Bookmark the permalink.

Leave a comment