A Celebration of Independence

Yesterday marked the second anniversary of my blog, and today is the 239th birthday of the U.S. In celebration of Independence Day, I want to explain what matroids are. Matroids were invented by Hassler Whitney (and independently by Takeo Nakasawa) to abstract the notion of linear independence from vector spaces to a much more general setting that includes acyclicity in graphs. Other pioneering early work on matroids was done by Garrett Birkhoff and Saunders MacLane. Matroid theory is a rich subject about which we will only scratch the surface here. In particular, there are many different (“cryptomorphic“) ways to present the matroid axioms which all turn out to be (non-obviously) equivalent to one another. We will focus on just a couple of ways of looking at matroids, emphasizing their connections to tropical geometry.

We begin with the independence point of view, which in many ways is the most intuitive one (not to mention the most appropriate for the Fourth of July).

A matroid ${M}$ is a finite set ${E}$ (called the ground set of ${M}$ ) together with a collection ${{\mathcal I}}$ of subsets of ${E}$ , called independent sets of ${M}$ , such that:

• (I1) The empty set is independent.
• (I2) Every subset of an independent set is independent.
• (I3) (Augmentation axiom) If ${I,J}$ are independent sets with ${\# I < \# J}$ , then there exists ${y \in J \backslash I}$ such that ${I \cup \{ y \}}$ is independent.

A maximal independent set is called a basis. The augmentation axiom implies that any two bases of ${M}$ have the same cardinality; we define the rank of ${M}$ to be this common cardinality.

A subset of ${E}$ which is not independent is called dependent. A circuit in a matroid ${M}$ is a minimal dependent set. The collection of circuits in a matroid satisfies the following axioms, which can in fact be taken as an alternate definition of a matroid:

• (C1) Every circuit is non-empty.
• (C2) No proper subset of a circuit is a circuit.
• (C3) (Circuit Elimination Axiom) If ${C_1,C_2}$ are distinct circuits and ${e \in C_1 \cap C_2}$ , then ${(C_1 \cup C_2) \backslash \{ e \}}$ contains a circuit.

It is often convenient to replace (C3) by the a priori stronger but equivalent axiom

• (C3′) (Strong Circuit Elimination Axiom) If ${C_1,C_2}$ are distinct circuits, ${e \in C_1 \cap C_2}$ , and $f \in C_1 \backslash C_2$ , there is a circuit containing $f$ and contained in ${(C_1 \cup C_2) \backslash \{ e \}}$ .

Examples

Here are some key examples of matroids:

Example 1 (Linear matroids): Let ${V}$ be a vector space over a field ${k}$ , let ${E}$ be a finite subset of ${V}$ , and let ${{\mathcal I}}$ be the collection of all linearly independent subsets of ${E}$ . Then ${(E,{\mathcal I})}$ is a matroid. A matroid of this form is said to be representable over ${k}$ . If we write the elements of ${E}$ as the columns of an ${m \times n}$ matrix ${A}$ (with respect to some ordered basis of ${V}$ ), then a subset of ${E}$ is independent iff the corresponding columns of ${A}$ are linearly independent over ${k}$ . We denote this matroid by ${M(A)}$ .

Example 2 (Graphic matroids): Let ${G}$ be a connected finite graph, let ${E}$ be the set of edges of ${E}$ , and let ${{\mathcal I}}$ be the collection of all subsets of ${E}$ which do not contain a cycle. Then ${M(G) := (E,{\mathcal I})}$ is a matroid which is representable over every field ${k}$ . (Matroids with this latter property are called regular.) A basis of ${M(G)}$ is just a spanning tree of ${G}$ . An amazing theorem of Whitney says that if ${G}$ is ${3}$ -connected then ${M(G)}$ determines ${G}$ up to isomorphism.

Example 3 (Fano matroid): Let ${E}$ be the projective plane over ${{\mathbf F}_2}$ (the seven elements of ${E}$ can be identified with the dots in the picture below). A subset ${S \subseteq E}$ is dependent if and only if ${\# S \geq 4}$ or ${\# S = 3}$ and ${S}$ is one of the 7 lines in the picture (6 straight and one curved). This notion of dependency gives rise to a rank 3 matroid, the Fano matroid, which is representable over ${{\mathbf F}_2}$ but not over any field of characteristic different from 2. In particular, the Fano matroid is not graphic.

Example 4 (Algebraic matroids): Let ${E = \{ 1,\ldots,n \}}$ , let ${R = k[x_1,\ldots,x_n]}$ be the polynomial ring in ${n}$ variables over a field ${k}$ , and let ${P}$ be a prime ideal of ${R}$ . Let ${{\mathcal I}}$ be the collection of all ${I \subset E}$ such that ${P \cap k[x_i \; : \; i \in I] = (0)}$ . Then ${M(P,R) := (E,{\mathcal I})}$ is a matroid. A matroid of this form is said to be algebraic over ${k}$ . (This is not the usual definition, but is equivalent to it.) All representable matroids over ${k}$ are algebraic.

Example 5 (Vamos matroid): Let ${E}$ be the 8 vertices of the cuboid shown in the following picture. A subset ${S \subseteq E}$ is dependent if and only if ${\# S \geq 5}$ or ${\# S = 4}$ and ${S}$ is one of the 5 square faces in the picture. This notion of dependency gives rise to a rank 4 matroid, the Vamos matroid, which is not algebraic, so in particular not representable, over any field.

Duality

If ${M = (E,{\mathcal I})}$ is a matroid, let ${{\mathcal I}^*}$ be the collection of subsets ${S\subseteq E}$ such that ${E \backslash S}$ contains a basis ${B}$ for ${M}$ . It turns out that ${{\mathcal I}^*}$ satisfies axioms (I1),(I2), and (I3) and thus ${M^* = (E,{\mathcal I}^*)}$ is a matroid, called the dual matroid of ${M}$ .

If ${M=M(G)}$ is the matroid associated to a planar graph ${G}$ , then ${M^*}$ is the matroid associated to the planar dual of ${G}$ . Another amazing theorem of Whitney says that, conversely, if ${G}$ is a connected graph for which the dual matroid ${M(G)^*}$ is graphic, then ${G}$ is planar.

It is an open problem whether or not the dual of an algebraic matroid is always algebraic.

Connection to tropical geometry

Let ${M}$ be a matroid with ground set ${E}$ . We define ${{\rm trop}(M)}$ to be the set of vectors ${w = (w_e)_{e \in E} \in {\mathbf R}^E}$ such that for any circuit ${C}$ of ${M}$ , the minimum is achieved twice in ${\max_{e \in C} w_e}$ . A matroid fan is a subset of ${{\mathbf R}^E}$ of the form ${{\rm trop}(M)}$ for some matroid ${M}$ on ${E}$ . There is a close connection between matroid fans and tropicalizations of linear spaces over trivially valued fields, as we will now describe.

Let ${K}$ be a field equipped with a valuation, i.e., a map ${v : K \rightarrow {\mathbf R} \cup \{ \infty \}}$ satisfying ${v(x)=\infty}$ iff ${x=0}$ , ${v(1)=0}$ , ${v(xy)=v(x)+v(y)}$ , and ${v(x+y) \geq {\min}(v(x),v(y))}$ for all ${x,y \in K}$ .

A valued field extension of ${K}$ is a pair ${(L,v_L)}$ consisting of a field extension ${L/K}$ together with a valuation ${v_L}$ on ${L}$ extending the given valuation on ${K}$ . We denote by ${{\rm val}_K}$ the set of valued field extensions of ${K}$ .

If ${V \subseteq (K^\times)^n}$ is an algebraic subvariety, we define the tropicalization of ${V}$ to be
$\displaystyle {\rm trop}(V) := \bigcup_{L \in {\rm val}_K} \{ ({\rm val}_L(x_1),\ldots,{\rm val}_L(x_n)) \; | \; (x_1,\ldots,x_n) \in V_L(L) \},$
where ${V_L = V \times_K L}$ is the base-change of ${V}$ to ${L}$ .

One can show that ${{\rm trop}(V)}$ is the topological closure of
$\displaystyle \{ ({\rm val}_L(x_1),\ldots,{\rm val}_L(x_n)) \; | \; (x_1,\ldots,x_n) \in V_L(L) \}$
for any ${L \in {\rm val}_K}$ such that ${v_L(L^\times)}$ is dense in ${{\mathbf R}}$ , and such a valued field $L$ always exists.

By the Bieri-Groves theorem, if ${V}$ is an algebraic subvariety of ${(K^\times)^n}$ of pure dimension ${d}$ , then ${{\rm trop}(V)}$ is the support of a rational polyhedral complex of pure dimension ${d}$ . Moreover, if ${V}$ is connected then so is ${{\rm trop}(V)}$ . If the valuation on ${k}$ is trivial (meaning that ${v(x) = 0}$ for ${x \in k^\times}$ ), then ${{\rm trop}(V)}$ is the support of a rational polyhedral fan.

Let ${k}$ be a field. We call a subspace ${W}$ of ${k^n}$ non-degenerate if it is not contained in any coordinate hyperplane ${H_i}$ , ${i \in E := \{ 1,\ldots,n \}}$ . If ${W}$ is a non-degenerate ${d}$ -dimensional subspace of ${k^n}$ , one can define an associated rank ${d}$ matroid ${M_W}$ by declaring that a subset ${I \subseteq E}$ is independent if and only if
$\displaystyle \left( \bigcap_{i \in I} H_i \right) \cap W = (0).$

The following theorem is a consequence of results of Kapranov and Sturmfels:

Theorem 1: If ${W}$ is a non-degenerate subspace of ${k^n}$ then (with respect to the trivial valuation on ${k}$ )
$\displaystyle {\rm trop}(W \cap (k^\times)^n) = {\rm trop}(M_W).$

This shows, in particular, that the tropicalization of ${W}$ depends only on the matroid ${M_W}$ .

A natural way to put a fan structure on ${{\rm trop}(M)}$ is as follows. For ${w \in {\mathbf R}^E}$ , we define the initial matroid ${M_w}$ to be the matroid on ${E}$ whose circuits are the minimal sets among
$\displaystyle \{ f \in C \; : \; w_f = \max_{e \in C} w_e \}.$

Note that, by definition, ${{\rm trop}(M)}$ is equal to the set of ${w}$ such that ${M_w}$ has no loops. (A loop is a circuit with one element.) It turns out that the cones ${{\rm trop}(M_w)}$ associated to the various distinct initial matroids ${M_w}$ form a $d$ -dimensional rational polyhedral fan, called the Bergman fan of ${M}$ , whose support is ${{\rm trop}(M)}$ . This fan is balanced, meaning that for each $(d-1)$ -dimensional cone $\tau$ , the sum of the ray generators of the $d$ -dimensional cones that contain $\tau$ belongs to $\tau$ .

The relationship between matroids and tropical geometry is even closer than Theorem 1 would indicate. To state the result, we define a tropical linear fan of dimension ${d}$ to be the support of a balanced rational polyhedral fan of pure dimension ${d}$ .

Theorem 2: One can recover a matroid ${M}$ on ${E=\{1,\ldots,n\}}$ from the tropical linear fan ${{\rm trop}(M) \subset {\mathbf R}^n}$ . Moreover, every tropical linear fan is the support of ${{\rm trop}(M)}$ for some matroid ${M}$ . Thus the association ${M \rightsquigarrow {\rm trop}(M)}$ gives a natural bijection between rank ${d}$ matroids on ${E}$ and tropical linear fans of dimension ${d}$ in ${{\mathbf R}^n}$ . A matroid ${M}$ is representable over ${k}$ iff ${{\rm trop}(M) = {\rm trop}(W \cap (k^\times)^n)}$ for some non-degenerate linear subspace ${W \subset k^n}$ .

Motivated by Rota’s conjecture that the coefficients of the characteristic polynomial of a matroid form a log-concave sequence, June Huh has asked (see e.g. Section 4.3 of his thesis) whether, given a matroid ${M}$ on $E=\{ 1,\ldots, n\}$ and an algebraically closed field ${k}$ , there always exists an algebraic variety ${V \subset k^n}$ (not necessarily a linear space!) such that ${{\rm trop}(V) = {\rm trop}(M)}$ (as sets). My Georgia Tech colleague Josephine Yu recently proved that the answer is no; more precisely, she shows in this beautiful short paper if ${M}$ is not algebraic then there is no such variety ${V}$ . So, for example, the Bergman fan of the Vamos matroid is not the set-theoretic tropicalization of any algebraic variety.

Valuated matroids and general tropical linear spaces

So far we have been working over a trivially valued field ${k}$ . There is an analogous story which works for arbitrary non-archimedean fields ${K}$ in which we replace matroids by valuated matroids. The circuit-based definition (due to Murota and Tamura) is as follows.

Let ${{\mathbf T} = {\mathbf R} \cup \{ \infty \}}$ , and define the support of a vector ${x \in {\mathbf T}^E}$ to be
$\displaystyle \underline{x} = \{ e \in E \; : \; x_e \neq \infty \}.$

A valuated matroid on ${E}$ is a collection ${C \subset T^E}$ of (valuated) circuits satisfying:

(VC0) ${(\infty,\infty,\ldots,\infty) \not\in C}$ .
(VC1) If ${x \in C}$ and ${\alpha \in {\mathbf R}}$ then ${x + \alpha \cdot {\mathbf 1} \in C}$ .
(VC2) If ${x,y \in C}$ with ${\underline{x} \neq \underline{y}}$ then ${\underline{x} \not\subset \underline{y}}$ .
(VC3) (Valuated Strong Circuit Elimination) If ${x,y \in C}$ and ${u,v \in E}$ with ${x_u = y_u \neq \infty}$ and ${x_v < y_v}$ , then there exists ${z \in C}$ such that ${z_u = \infty}$ , ${z_v = x_v}$ , and ${z \geq \min (x,y )}$ .

It follows from the axioms that a circuit is determined, up to a scalar multiple of ${{\mathbf 1}}$ , by its support. In particular, the set of circuits mod ${{\mathbf 1}}$ in a valuated matroid is finite.

Every matroid can be enhanced to a valuated matroid, but possibly in many different ways. This is analogous to the fact that every field ${k}$ can be regarded as a valued field by putting the trivial absolute value on it, but in general there are many different valued field structures on ${k}$ .

We denote by ${{\rm supp}(M)}$ the underlying matroid of a valuated matroid ${M}$ : a subset ${C}$ of ${E}$ is a circuit of ${{\rm supp}(M)}$ if and only if it is the support of a circuit of ${M}$ .

Like ordinary matroids, valuated matroids have duals. We say that two vectors $v=(v_1,\ldots,v_n)$ and $w=(w_1,\ldots,w_n)$ in ${\mathbf T}^E$ are orthogonal, written $v \perp w$ , if the minimum is achieved twice in the “tropical dot product” ${\rm min} (v_1 + w_1, \ldots, v_n + w_n)$ . The vectors of minimal support in $C^\perp$ satisfy the axioms (VC0)-(VC3) and therefore form the circuits of a valuated matroid called the dual valuated matroid $M^*$ . The underlying matroid of $M^*$ is the dual of the underlying matroid of $M$ .

Let ${M}$ be a valuated matroid. We define the tropical linear space associated to ${M}$ , denoted ${{\rm trop}(M)}$ , to be the tropical convex hull of the circuits of ${M^*}$ , i.e. the set of all ${x \in {\mathbf T}^E}$ such that ${x = \min \{ a_1 + x_1,\ldots, a_m + x_m \}}$ for ${a_1,\ldots,a_m \in {\mathbf T}}$ and ${x_1,\ldots,x_m \in C^*}$ .
A tropical linear space is a subspace of ${{\mathbf T}^E}$ of the form ${{\rm trop}(M)}$ for a valuated matroid ${M}$ . It can be given the structure of a polyhedral complex whose recession fan is ${{\rm trop}({\rm supp}(M))}$ . One can check that a tropical linear fan, as previously defined, is in particular a tropical linear space (modulo the fact that for technical reasons we are now working in ${\mathbf T}^n$ rather than ${\mathbf R}^n$ ).

As in the trivially valued case, there is a close relationship between this definition and the tropicalization of linear spaces. If ${K}$ is a non-archimedean field and ${W}$ is a ${d}$ -dimensional ${K}$ -linear subspace of ${{\mathbf R}^E}$ , we can define an associated valuated matroid ${M_W}$ whose circuits are the minimal (in the sense of inclusion of supports) elements of
$\displaystyle \{ ({\rm val}(\lambda_1),\ldots,{\rm val}(\lambda_m)) \; : \; \lambda_1 e_1 + \cdots + \lambda_m e_m \in W \backslash \{ 0 \} \}.$

Theorem 3: $\displaystyle {\rm trop}(W) = {\rm trop}(M_W).$

The fact that ${M_W}$ satisfies (VC0)-(VC3) is one justification for the definition of a valuated matroid. There are lots of other good justifications. For example, Alex Fink proved the folklore fact that a tropical linear space is the same thing as a balanced polyhedral complex whose recession fan is a tropical linear fan, which is the same as a “tropical cycle of degree 1”. As another example of why valuated matroids are nice, there is an equivalent definition using tropical Plücker vectors reflecting the fact that, just as linear spaces can be thought of as vectors satisfying the Plücker relations, a valuated matroid can be thought of as a tropical vector satisfying the tropicalization of the Plücker relations.

Concluding remarks:

1. A good reference for tropical geometry and its relation to matroid theory is the recently published book Introduction to Tropical Geometry by Maclagan and Sturmfels. For an introduction to matroids targeted to algebraic geometers, I recommend Eric Katz’s survey paper. For the combinatorially minded, there are many good introductions including this survey paper by Oxley.

2. Simon Hampe has recently shown that a tropical linear fan (resp. tropical linear space) is the same thing as a pure-dimensional balanced rational polyhedral fan (resp. polyhedral complex) which is tropically convex. This gives a purely geometric characterization of matroids (resp. valuated matroids).

3. June Huh and Eric Katz use Bergman fans of matroids in order to prove Rota’s conjecture for matroids representable over some field in this paper. Note that what they call the Bergman fan is a subdivision of what we have called the Bergman fan. See Section 4.2 of the Maclagan-Sturmfels book for descriptions of both of these fan structures on ${{\rm trop}(M)}$ .

4. Bergman fans of matroids are examples of strongly extremal tropical varieties, i.e., pure-dimensional rational polyhedral complexes admitting a unique (up to scalar multiple) set of weights which make them balanced. Strongly extremal tropical varieties play a central role in this paper by Farhad Babaee and June Huh giving a counterexample to the strongly positive Hodge conjecture of Demailly.

5. Maclagan and Rincon use tropical linear spaces and valuated matroids to prove some new results about the Giansiricusas’ notion of tropical scheme theory in their recent paper “Tropical schemes, tropical cycles, and valuated matroids”.

6. Just as a smooth manifold is a space which is locally a linear space, it is natural in tropical geometry to define a tropical variety to be smooth if the star of every point is a tropical linear fan (i.e., the Bergman fan of a matroid). This point of view leads, for example, to a tropical analogue of Hodge theory via the Orlik-Solomon algebra of a matroid (see, e.g., Chapter 2 of Kristin Shaw’s thesis).

5 thoughts on “A Celebration of Independence”

Pingback: Hodge Theory in Combinatorics | Matt Baker's Math Blog
Pingback: Matroids over Hyperfields, Part I | Matt Baker's Math Blog
Tyler says:

April 7, 2017 at 5:14 pm

In the discussion of duality, it says: “If $M=M(A)$ is the linear matroid associated to a matrix $A$, then $M^{*}$ is the linear matroid associated to the transpose of $A$.” According to the definition of $M^{\ast}$, both $M$ and $M^{\ast}$ have the same underlying set $E$. On the other hand, in Example 1, linear matroids are defined so that the cardinality of $E$ is the number of columns of $A$. If $A$ is an $m\times n$-matrix, then we should have $\# E=n$, whereas $M(A^{\text{t}})$ should have an underlying set of size $m$. …Maybe I misunderstand.

- Matt Baker says:
  
  April 10, 2017 at 1:43 pm
  
  You are correct Tyler, thanks. What I had written is true if one first puts A in a suitable normal form, but that is probably not worth explaining in the post (as it’s not needed), so I’ve simply deleted the incorrect remark.
  
Pingback: Lorentzian Polynomials II: Applications | Matt Baker's Math Blog

Matt Baker's Math Blog

Thoughts on number theory, graphs, dynamical systems, tropical geometry, pedagogy, puzzles, and the p-adics

A Celebration of Independence

5 thoughts on “A Celebration of Independence”

Leave a Reply Cancel reply

Share this:

Like this:

Related

5 thoughts on “A Celebration of Independence”

Leave a Reply Cancel reply