What is a matroid? Definition, examples, and why greedy works

A matroid is a finite set $E$ together with a family $\mathcal{I}$ of its subsets satisfying three conditions:

The sets in $\mathcal{I}$ are called independent.

The classic example is linearly independent vectors. The empty set of vectors is linearly independent; every subset of a linearly independent set is linearly independent; and if one independent set is smaller than another, some vector of the larger one can be added to it without losing independence.

The word “independent” should not be taken too literally, though. In matroid theory it is a technical term: we decide which subsets count as independent and then check the three axioms above. There is no hidden physical, causal or statistical “dependence” between the elements to look for. The term comes from linear algebra — one of the examples the theory grew out of.

It is axiom (I3), the exchange axiom, that makes matroids interesting. It says: of two independent sets of different sizes, the smaller one can always be grown by at least one element of the larger while staying independent.

Whitney introduced matroids in 1935 to capture the common structure behind linear independence in matrices and acyclicity in graphs. Even the name matroid comes from matrix.

The main practical result is surprisingly strong: on a matroid the simple greedy algorithm is not a heuristic — for additive non-negative weights it is guaranteed to find the optimum.

Definition

Formally, a matroid is a pair $M = (E, \mathcal{I})$, where $E$ is a finite set called the ground set and $\mathcal{I} \subseteq 2^E$ is the family of its independent sets.

Conditions (I1)–(I3) are called the independence axioms.

Axiom (I1) says the empty set is independent.

Axiom (I2) expresses heredity: if a set is independent, so is every subset of it.

It is (I3) that separates a matroid from an arbitrary hereditary system: if an independent set $A$ is smaller than an independent set $B$, then $B$ always holds an element that $A$ can be extended by.

(I1) and (I2) hold for almost any sensible problem: choosing nothing is feasible, and dropping an element from a feasible set never hurts. So in practice the whole check comes down to (I3).

Almost all of the basic vocabulary of matroid theory follows from these three axioms.

A dependent set is a subset of the ground set that is not independent.

A circuit is a minimal dependent set. In other words, it is dependent itself, but removing any one of its elements makes it independent. In a graphic matroid the circuits are exactly the ordinary cycles of the graph.

A loop is a one-element circuit: an element that cannot be part of any independent set. In a graphic matroid an example is an edge from a vertex to itself — it forms a cycle on its own. In a linear matroid the zero vector is a loop.

A basis is a maximal independent set. By the exchange axiom all bases of a matroid have the same size: if there were two bases $A$ and $B$ with $|A| < |B|$, (I3) would let us add an element of $B$ to $A$, so $A$ would not be maximal.

The rank $r(A)$ of a set $A \subseteq E$ is the size of the largest independent subset of $A$. In particular, $r(E)$ is called the rank of the matroid and equals the size of any of its bases.

A coloop (also called an isthmus) is an element contained in every basis. In a graphic matroid these are the bridges of the graph.

The dual matroid $M^*$ has the same ground set $E$, and its bases are the complements of the bases of the original matroid: $B^* = E \setminus B$. Hence $r^*(E) = |E| - r(E)$. The dual of a graphic matroid is called the cographic matroid, or cut matroid.

The direct sum $M_1 \oplus M_2$ of matroids on disjoint ground sets $E_1$ and $E_2$ works like this: a set is independent exactly when its part in $E_1$ is independent in $M_1$ and its part in $E_2$ is independent in $M_2$. Ranks add: $r(M_1 \oplus M_2) = r(M_1) + r(M_2)$.

Deletion of an element $e$, written $M \setminus e$ (also called restriction to $E \setminus \{e\}$), simply keeps the independent sets that do not contain $e$.

Contraction of an element $e$, written $M / e$, is defined for an $e$ that is not a loop: a set $A \subseteq E \setminus \{e\}$ is independent in $M / e$ if $A \cup \{e\}$ is independent in $M$.

Deletions and contractions can be repeated. The matroids obtained this way are called minors of the original matroid.

Two matroids are isomorphic if there is a bijection between their ground sets that preserves independence.

Example 1: graphic matroid

Take a graph $G = (V, E)$.

Use its edge set $E$ as the ground set and call a set of edges independent if it contains no cycle. In other words, the independent sets are the forests.

This is the graphic, or cycle, matroid of the graph.

The bases of a connected graphic matroid are its spanning trees. The circuits of the matroid are the cycles of the graph. Its loops are the self-loop edges. Its coloops are the bridges, since every bridge must belong to every spanning tree.

If a connected graph has $n$ vertices, then $r(E) = n - 1$. This is not a separate fact about trees that happens to agree with matroid theory. It follows directly from the exchange axiom: all bases have the same size, and the bases of the graphic matroid are exactly the spanning trees.

Click edges to build a set; the panel finds the cycle if there is one and reports the rank. “Run greedy” sorts the edges by weight and applies Kruskal’s algorithm; “step” takes one edge at a time and says whether it was taken or would have closed a cycle.

Now give every edge a weight.

If we sort the edges by increasing weight and add each edge exactly when it does not close a cycle, we get Kruskal’s algorithm for the minimum spanning tree.

Kruskal does not work because of some special trick about graphs. It is a special case of the general greedy algorithm on a matroid.

Example 2: linear matroid

Let the ground set be the columns of a matrix over a field $F$.

Call a set of columns independent exactly when the corresponding vectors are linearly independent.

The resulting structure is called a linear matroid. If a matroid can be obtained this way from some matrix over $F$, it is said to be representable over $F$.

This is one of the original examples of matroid theory.

The graphic matroid is representable over every field. For a directed graph, take its vertex–edge incidence matrix, where each edge is a column with $+1$ at one end and $-1$ at the other. Over $\mathrm{GF}(2)$, where $1 = -1$, both non-zero entries equal one.

A set of such columns is linearly independent exactly when the corresponding edges contain no cycle.

A matroid representable over every field is called regular. So graphic $\subsetneq$ regular $\subsetneq$ representable, and both inclusions are strict.

Loops and circuits are especially visible in a linear matroid. The zero vector is a loop. Two non-zero proportional vectors form a two-element circuit. In the plane, any minimally dependent set of three pairwise non-proportional vectors is a three-element circuit.

Example 3: uniform matroid U(k,n)

The uniform matroid $U_{k,n}$ has $n$ elements, and its independent sets are exactly the subsets of size at most $k$:

Its bases are all $k$-element subsets. Its circuits are all $(k+1)$-element subsets. Its rank is $k$.

For example, in $U_{1,n}$ you can choose at most one element. Any two elements already form a circuit.

In $U_{n,n}$ every subset is independent. This matroid is called free.

$U_{2,4}$ matters most. It has four elements; any one or two of them are independent, and any three-element set is dependent. It is the simplest matroid that is not representable over $\mathrm{GF}(2)$.

A famous theorem of Tutte says: a matroid is representable over $\mathrm{GF}(2)$ — that is, binary — if and only if it has no $U_{2,4}$ minor.

Example 4: partition matroid — the customs desk

Imagine you are going through customs.

All items are split into categories: say, alcohol, cigarettes, electronics and cheese. The rule is: you may carry at most one item of each category.

Every item has some value, and you want a permitted set of maximum total value.

Why is this a matroid?

An empty bag is permitted — (I1) holds.

Take anything out of a permitted bag and it is still permitted — (I2) holds.

Now take two permitted bags $A$ and $B$ with $|A| < |B|$. Since each category holds at most one item, bag $B$ covers more distinct categories than $A$. So some category is present in $B$ and missing from $A$.

That item can be moved from $B$ into $A$ without breaking the rule. So (I3) holds too.

This is a partition matroid.

In general the ground set can be split into blocks $E = E_1 \sqcup E_2 \sqcup \cdots \sqcup E_m$ with a capacity $k_i$ for each block. The independent sets are then the sets $A$ with $|A \cap E_i| \le k_i$ for every $i$.

Such a matroid is the direct sum of uniform matroids $U_{k_i,|E_i|}$. In our customs example $k_i = 1$ for every category.

Greedy really is obvious here: when the categories do not constrain one another, it is enough to take the most valuable permitted item from each category.

Now change just one rule: the total weight of your luggage must not exceed 23 kg.

Let $A = \{$one 20 kg item$\}$ and $B = \{$two 10 kg items$\}$. Then $|A| < |B|$. Yet no element of $B$ can be added to $A$: that would make 30 kg.

So the exchange axiom fails. This is no longer a matroid but a knapsack constraint.

Values can be assigned so that greedy first grabs an attractive 20 kg item and then can no longer take the two 10 kg items, although together they are worth more.

One bag, two rules that look almost the same — and completely different mathematics.

“At most one item of each category” forms a matroid.

“At most 23 kg in total” does not.

It is the exchange axiom that shows the difference before the algorithm ever runs.

Points and lines: a rank-3 matroid

Matroids can be built from more than vectors or edges.

Take a finite set of points in the plane and call a set of points independent in the sense of affine independence.

One point is independent. Any two distinct points are independent. Three points are independent exactly when they do not lie on one line. Four points in the plane are always affinely dependent.

So this matroid has rank at most 3.

If three points lie on one line and no proper part of them is dependent, the triple is a circuit of the matroid.

Moving the points changes the matroid itself: a new collinear triple creates a new circuit. Drag the points and watch the count of lines.

Not every rank-3 matroid, however, can be realised by points of the ordinary real plane.

The classic example is the Fano matroid. It has seven elements with seven special three-element circuits and is linearly representable only over fields of characteristic 2. In particular, it cannot be represented over $\mathbb{R}$.

The exchange axiom in action

Now it is clear why (I3) is central.

First of all, it immediately proves that all bases of a matroid have the same size.

Suppose $A$ and $B$ are two maximal independent sets with $|A| < |B|$. By (I3) there is an element $e \in B \setminus A$ for which $A \cup \{e\}$ stays independent. But then $A$ was not maximal. Contradiction.

So greedy can never end up “stuck” in a small maximal independent set while a larger one exists somewhere.

Build two independent sets $A$ and $B$ on the graph. Whenever $|A| < |B|$, the panel searches $B \setminus A$ for an edge that can join $A$ without closing a cycle — the axiom promises one always exists.

What is more, a failure of (I3) directly gives an example on which greedy loses.

Suppose there are independent sets $A$ and $B$ with $|A| < |B|$, but no element of $B \setminus A$ can be added to $A$.

Give every element of $A$ weight $1 + \varepsilon$, every element of $B \setminus A$ weight $1$, and every other element weight $0$.

Greedy prefers the elements of $A$ first. Once it has collected $A$, no new element of $B \setminus A$ can be added. It ends with weight $|A|(1+\varepsilon)$.

Meanwhile $B$ weighs at least $|B| \ge |A| + 1$. Choosing $0 < \varepsilon < 1/|A|$ gives

So $B$ beats the greedy solution. Breaking a single axiom has automatically produced a counterexample for greedy.

Why Kruskal works: the greedy algorithm and matroids

Consider the general problem.

Every element of a finite set has a non-negative weight. We want an independent set of maximum total weight.

The most natural algorithm is very simple: sort the elements by decreasing weight, then go through them in that order and add an element whenever the set stays independent with it.

No search. No backtracking. No dynamic programming.

When is this procedure guaranteed to find the optimum?

The Rado–Edmonds theorem answers that.

Rado–Edmonds theorem. Let $\mathcal{I}$ be a non-empty family of subsets of a finite set $E$ that is closed under taking subsets. Then greedy finds an independent set of maximum weight for every assignment of non-negative weights if and only if $(E, \mathcal{I})$ is a matroid.

Left: forests, which form a matroid. Right: matchings, which do not. “Step” advances both sides one element at a time.

This is a very strong statement.

The forward direction says: if the feasible sets form a matroid, there is no need to prove greedy correct again for every new set of weights. The structure of the problem already guarantees optimality.

The reverse direction says no less: if the family is not a matroid, there is some assignment of weights on which this greedy algorithm fails.

So a matroid is not just one of the classes of problems where greedy sometimes works. Among hereditary systems, it is the exact structural boundary of universal correctness for this greedy algorithm.

For problems on bases the same statement holds with arbitrary real weights: all bases have the same size, so adding the same constant to every weight does not change which basis is optimal.

Kruskal’s algorithm is exactly this principle applied to the graphic matroid, except that to find a minimum the edges are sorted by increasing weight.

Proof of the Rado–Edmonds theorem

We have in effect already proved the reverse direction.

If the exchange axiom fails, there are $A$ and $B$ with $|A| < |B|$ such that no element of $B \setminus A$ can be added to $A$. The weights $1 + \varepsilon$ on $A$ and $1$ on $B \setminus A$ make greedy choose $A$, although $B$ has larger total weight.

It remains to prove the forward direction.

Let greedy choose the elements $g_1, g_2, \ldots, g_r$ in that order, so that $w(g_1) \ge w(g_2) \ge \cdots \ge w(g_r)$. Call the resulting basis $G = \{g_1, \ldots, g_r\}$.

Let $O = \{o_1, \ldots, o_r\}$ be an optimal basis, its elements also sorted by non-increasing weight: $w(o_1) \ge w(o_2) \ge \cdots \ge w(o_r)$.

The sizes agree. Greedy stops only at a maximal independent set, that is, at a basis; with non-negative weights the optimum can be taken to be a basis too, because extending it by zero-weight elements does not lower its weight; and by the exchange axiom all bases have the same size.

We show that $w(g_i) \ge w(o_i)$ for every $i$.

Suppose not, and take the first index $i$ with $w(g_i) < w(o_i)$.

Consider $A = \{g_1, \ldots, g_{i-1}\}$ and $B = \{o_1, \ldots, o_i\}$.

Both sets are independent: the first is part of the greedy basis, the second part of the optimal one. Moreover, $|A| = i - 1 < i = |B|$.

By the exchange axiom there is $o_j \in B \setminus A$ such that $A \cup \{o_j\}$ is independent.

Since $j \le i$, we have $w(o_j) \ge w(o_i) > w(g_i)$. So greedy examined $o_j$ before $g_i$.

At that moment the elements already chosen formed some subset of $A$. Since $A \cup \{o_j\}$ is independent, by heredity that earlier subset together with $o_j$ is independent too.

So the algorithm must have accepted $o_j$. Then by the time $g_i$ was chosen, $o_j$ would already belong to $A$. But we chose $o_j \in B \setminus A$. Contradiction.

Hence $w(g_i) \ge w(o_i)$ for every $i$, and therefore $w(G) \ge w(O)$.

The greedy solution is optimal. $\blacksquare$

The whole proof rests on essentially one application of the exchange axiom.

That is the precise mathematical meaning of the phrase: a matroid is the structure on which greedy works universally.

Other classes of matroids

Transversal matroid. Take a bipartite graph between the elements of the ground set $E$ and some set of “slots”. A subset $A \subseteq E$ is independent if its elements can be matched to distinct slots. These partial transversals form a matroid (Edmonds and Fulkerson, 1965).

It is important not to mix up two statements. The subsets of vertices that can be matched to distinct vertices of the other side form a matroid. The matchings themselves, taken as sets of edges of an arbitrary graph, are in general not a matroid — which is exactly what the panel with the three-edge path above shows.

Algebraic matroid. Let $K \supseteq F$ be a field extension and $E$ a finite set of elements of $K$. A subset of $E$ is independent if its elements are algebraically independent over $F$. Linear matroids are a special case of algebraic ones, but there are algebraic matroids with no linear representation over any field.

Direct sum. Matroids on disjoint ground sets can be combined independently of each other. Ranks add. A matroid that cannot be written non-trivially as a direct sum is called connected. Every finite matroid decomposes uniquely into connected components.

Matroid union. Let $M_1, \ldots, M_k$ be matroids on the same ground set. A set is independent in their union if it can be split into parts so that the $i$-th part is independent in $M_i$. The matroid union theorem says the result is again a matroid.

This construction is what lies behind questions like “can the edge set be split into $k$ forests?” — Nash-Williams gave the exact answer.

The cographic matroid, or cut matroid, is dual to the graphic one. For a connected graph its independent sets can be read as the edge sets whose removal does not disconnect the graph. Its circuits are the minimal cuts of the graph.

The cographic matroid of a graph is itself graphic if and only if the graph is planar (Whitney); in that case it is the graphic matroid of the planar dual.

A binary matroid is a matroid representable over the field $\mathrm{GF}(2)$.

A regular matroid is a matroid representable over every field; equivalently, by a totally unimodular matrix. Every graphic and every cographic matroid is regular.

Tutte’s theorems give especially elegant characterisations by excluded minors. A matroid is binary if and only if it has no $U_{2,4}$ minor. A regular matroid must in addition contain neither the Fano matroid $F_7$ nor its dual $F_7^*$.

Short answers

What is a matroid in one sentence?

A matroid is a finite set with a chosen notion of independence that is hereditary and satisfies the exchange axiom.

Why is the exchange axiom needed?

It guarantees that a smaller independent set can always be extended by elements of a larger one and, in particular, that all bases have the same size. That property is what makes the greedy algorithm correct.

Where do matroids show up?

In linear algebra, spanning trees of graphs, transversal and assignment problems, error-correcting codes, combinatorial optimisation, and many problems whose constraints allow elements to be exchanged without losing feasibility.

What is the rank of a matroid?

The size of any of its bases. More locally, r(A) is the largest size of an independent subset of A. For a connected graph on n vertices the rank of its graphic matroid is n − 1.

Is every problem where greedy works a matroid?

No. Greedy can happen to give the right answer on one particular set of weights, in a problem that has nothing to do with matroids. The Rado–Edmonds theorem says something much stronger: for a hereditary family, greedy is optimal for every assignment of non-negative weights if and only if the family is a matroid.

How does a matroid differ from a greedoid?

A greedoid is a more general structure. In a matroid any set of elements can be removed from a feasible set and what remains is still feasible. A greedoid drops that full heredity and only asks that some element can always be removed, so the greedy theorem for matroids does not carry over to arbitrary greedoids without extra conditions.

Matroid vs. knapsack?

An ordinary knapsack constraint violates the exchange axiom in general. One heavy element can fill the whole budget while another feasible set holds several lighter ones; the second set is larger, yet none of its elements can be added to the first. So a knapsack is not a matroid, and the standard greedy algorithm gets no matroid guarantee of optimality.

Further reading

• J. G. Oxley, Matroid Theory, 2nd ed., Oxford University Press, 2011. The main modern reference on matroid theory; chapters 1–2 cover everything on this page.
• G. Gordon, J. McNulty, Matroids: A Geometric Introduction, Cambridge University Press, 2012. A geometric introduction well suited to a first encounter.
• D. J. A. Welsh, Matroid Theory, Academic Press, 1976; Dover reprint, 2010. The classic monograph.
• A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003, vol. B, chapters 39–40. Matroids, greedy algorithms, matroid intersection and union.
• J. G. Oxley, “What is a matroid?”, Cubo 5 (2003), 179–218. A survey introduction by the author of the main textbook, freely available from the author’s page at LSU.
• M. L. Fisher, G. L. Nemhauser, L. A. Wolsey, “An analysis of approximations for maximizing submodular set functions — II”, Mathematical Programming Study 8 (1978), 73–87. The classic result on greedy maximisation of submodular functions under matroid constraints.

Nikolay Eremeev, Senior Data Infrastructure Engineer. Writes about what he builds in production. CV ·hi@nikolay-eremeev.com