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.