Numbers in boxes | dr. ada morse

Algebra and combinatorics are different viewpoints on how to put structure on a set of things. An algebraist looks at a set and sees a bunch of things she can smash together to produce other things (e.g. numbers can be added, cake ingredients can be mixed, delicious avocados can be bred.) A combinatorialist* looks at a set and sees a bunch of things xe can group together (“combine” if you will) in different ways (e.g. categories can be Venn diagrammed, cake ingredients separated into dry/wet/nonbinary sections, delicious avocados will be eaten too quickly to be combined with anything if your combinatorialist is anything like this humble author.)

Algebraists get extremely pumped about linear algebra. Anytime you see a group of algebraists (as in murder of crows) hanging out, you can be damn sure one of them is just itching to use some linear algebra. And it was just such a group that, long ago, was infiltrated by a collection of combinatorialists who perpetrated the greatest heist of mathematical history: the theft of linear algebra itself.

The story goes like this. Let $V$ be a finite-dimensional vector space, and let’s think about the collection $\mathcal{I}$ of all linearly independent sets of vectors in $V$ . This collection has certain structural properties as a collection of sets: (1) if $A \in \mathcal{I}$ and $B \subseteq A$ , then $B \in \mathcal{I}$ , (2) the empty set is always independent, and (3) if $A$ and $B$ are both in $\mathcal{I}$ and $|A| < |B|$ , then there is some $v \in B$ such that $A \cup v \in \mathcal{I}$ . These properties are all proven in linear algebra using the operations defining a vector space, but they are purely combinatorial properties when $\mathcal{I}$ is thought of as simply a list of ways to group together elements of $V$ (what fancy-pants mathematicians call a set system). So instead of starting with algebraic operations, as an algebraist might, and deriving this structure, our combinatorial heisters decided to take these properties as axioms…

That is, let’s define a matroid to be a pair $M = (E,\mathcal{F})$ where $E$ is a finite set, and $\mathcal{F}$ is a nonempty collection of subsets of $E$ such that

(hereditary property) if $A \in \mathcal{F}$ and $B \subseteq A$ , then $B \in \mathcal{F}$ ; and,
(augmentation property) if $A$ and $B$ are both in $\mathcal{F}$ and $|A| < |B|$ , then there some $v \in B \setminus A$ such that $A \cup v \in \mathcal{F}$

It turns out that this is enough to recover many of the theorems we expect to be true of a collection of linearly independent sets. For example, suppose $A$ and $B$ are both maximal independent sets (with respect to inclusion) in a matroid $M = (E,\mathcal{F})$ . By augmentation, if $|B| > |A|$ then there is some $v \in B \setminus A$ such that $A \cup v$ is independent. But this contradicts maximality of $A$ . By playing the same game with roles reversed, we can’t have $|A| > |B|$ either. So all the maximal independent sets of $M$ have the same size (and are usually called bases — cause yeah, we stole the lingo too.)

Okay, you say, so this is a fun game, but what’s the point? Stay tuned…

*some combinatorist is getting really pissed off at me right now.

dr. ada morse

musician, mathematician, quasibee

Category Archives: Numbers in boxes

Linear Algebra (algebra not included)