Matroids & Exchange Arguments

Across this module we have watched greedy algorithms win (activity selection, Huffman codes, Kruskal's and Prim's spanning trees) and watched greedy lose, on the 0/1 knapsack. Each victory came with a proof: a guarantee that taking the locally best option never forecloses the global optimum. This lesson is about the proofs themselves. First we distill the two arguments every greedy correctness proof is built from. Then we ask the deeper question: is there a structural property that predicts when greedy will work, before we attempt the proof? The answer is yes, and its name is the matroid. The matroid theory makes precise the boundary we kept bumping into, why Kruskal is correct and 0/1 knapsack is not, and reduces is greedy optimal here? to is this structure a matroid?

Two templates for proving greedy optimal

Every greedy correctness proof in this module is an instance of one of two patterns. They are interchangeable in power but feel different to wield.

This is the activity-selection argument: greedy's $k$ -th activity finishes no later than the $k$ -th activity of any valid schedule, so greedy always has at least as much room left for future activities and ends up with at least as many.

This is the one you reach for: it proves the greedy-choice property by showing that whatever an optimal solution does first, we may exchange it for greedy's first choice without harm.¹ The two templates differ in direction: stays-ahead pushes greedy forward and shows it never falls behind; exchange pulls an optimum toward greedy and shows the pull never hurts. The exchange argument is the one that generalizes into a theory, because its swap step is literally an axiom of the structure we are about to define.

Matroids

A matroid abstracts the notion of independence: linear independence of vectors, acyclicity of edges, freedom to add one more element without breaking a rule.

The first axiom is mild; most natural notions of independence are closed under taking subsets. The exchange property is the engine: a smaller independent set can always be grown by stealing some element from any larger one. It forbids the situation where you get stuck early with a maximal-but-small independent set while a much larger one exists.

A first consequence of the exchange property is that all bases have the same size: if two bases $A, B$ had $∣ A ∣ < ∣ B ∣$ , the exchange property would let us add an element of $B$ to $A$ , contradicting that $A$ is maximal. So rank is well-defined: every base has exactly $r (M)$ elements, exactly as every basis of a vector space has the same dimension. (Indeed, the columns of a matrix, with $I$ the linearly independent subsets, form the linear matroid; this is where the vocabulary comes from.)

The exchange property — any smaller independent set

A

can absorb some

x \in B ∖ A

from a larger one

Because $∣ A ∣ < ∣ B ∣$ , some $x \in B ∖ A$ (here $c$ ) joins $A$ keeping it independent, so no maximal independent set is left stranded below the rank.

The matroid–greedy theorem

A weighted matroid attaches a positive weight $w (x) > 0$ to each element $x \in S$ , with $w (A) = \sum_{x \in A} w (x)$ . The natural optimization problem: find a maximum-weight independent set. Since weights are positive and $I$ is hereditary, a maximum-weight independent set is always a base. The greedy algorithm is the obvious one: sort by weight descending, add each element if it keeps the set independent.

Algorithm:

\textsc{Greedy}(M=(S,\mathcal I),\, w)

— maximum-weight independent set

1
$A \gets \varnothing$
2
sort $S$ into nonincreasing order by weight $w$
3
for each $x \in S$ in sorted order do
4
if $A \cup \{x\} \in \mathcal{I}$ then
independence test
5
$A \gets A \cup \{x\}$
6
return $A$

The forward direction is a clean exchange argument; it is worth seeing in full, because it is the abstract skeleton of every concrete greedy proof in this module.

Proof (greedy is optimal on a matroid). Let $g_{1}, g_{2}, \dots, g_{r}$ be greedy's picks in the order chosen, so $w (g_{1}) \geq w (g_{2}) \geq \dots \geq w (g_{r})$ , and let $G = {g_{1}, \dots, g_{r}}$ . Suppose for contradiction some base $O$ has $w (O) > w (G)$ . List $O$ 's elements in nonincreasing weight order as $o_{1}, \dots, o_{r}$ (both bases have size $r = r (M)$ ). Let $k$ be the first index where $w (g_{k}) < w (o_{k})$ ; such a $k$ exists, else $w (g_{i}) \geq w (o_{i})$ for all $i$ and $w (G) \geq w (O)$ .

Consider $A = {g_{1}, \dots, g_{k - 1}}$ and $B = {o_{1}, \dots, o_{k}}$ , both independent (subsets of independent sets, by the hereditary axiom). Since $∣ A ∣ = k - 1 < k = ∣ B ∣$ , the exchange property gives an element $o_{j} \in B ∖ A$ with $A \cup {o_{j}} \in I$ . Each $o_{i} \in B$ has $w (o_{i}) \geq w (o_{k}) > w (g_{k})$ , so $w (o_{j}) > w (g_{k})$ .

But when greedy considered the elements in weight order, at the moment it chose $g_{k}$ the set $A = {g_{1}, \dots, g_{k - 1}}$ was already in hand, and $A \cup {o_{j}}$ is independent with $w (o_{j}) > w (g_{k})$ . Greedy scans in nonincreasing weight, so it would have reached and accepted $o_{j}$ before $g_{k}$ , a contradiction. Hence no such $O$ exists and $G$ is maximum-weight. $□$

Laid out side by side, greedy's picks and the optimum's, both sorted by weight, make the contradiction visible. They agree on weight up to the first index $k$ where greedy falls behind ( $w (g_{k}) < w (o_{k})$ ). The prefix $A = {g_{1}, \dots, g_{k - 1}}$ is smaller than $B = {o_{1}, \dots, o_{k}}$ , so the exchange property hands us an element $o_{j} \in B$ that keeps $A$ independent and is heavier than $g_{k}$ — which greedy, scanning in weight order, must have reached and accepted before $g_{k}$ . That is the contradiction.

The Rado–Edmonds exchange step. Greedy's picks

g_{i}

and an allegedly better base's picks

o_{i}

, both in nonincreasing weight, agree until index

k

where

w (g_{k}) < w (o_{k})

(red). The exchange property on

A = {g_{1} \dots g_{k - 1}}

and

B = {o_{1} \dots o_{k}}

yields a heavier independent extension greedy would have taken first.

The single step that does all the work is the exchange property gives an element $o_{j}$ . That is the matroid axiom standing in for the ad-hoc swap we constructed by hand for activity selection. The converse, that a non-matroid hereditary structure has a weight function defeating greedy, is what makes the matroid the exact characterization, not merely a sufficient condition: if the exchange property fails for some $A, B$ , one can place weights that lure greedy into the stranded maximal set $A$ and away from the heavier $B$ .

Examples that are matroids

The graphic matroid. Let $G = (V, E)$ be a graph. Take $S = E$ and let $I$ be the acyclic edge sets, the forests of $G$ . This is a matroid: a subset of a forest is a forest (hereditary), and if forests $A, B$ have $∣ A ∣ < ∣ B ∣$ , then $B$ touches more components, so some edge of $B$ joins two trees of $A$ without creating a cycle (exchange property). The bases are the spanning forests; for a connected graph, the spanning trees, all of size $∣ V ∣ - 1 = r (M)$ .

Now run $Greedy$ on the graphic matroid with negated edge weights (maximum-weight independent set becomes minimum-weight spanning tree): sort edges, add each edge that does not form a cycle. That is Kruskal's algorithm, exactly: the independence test $A \cup {e}$ stays acyclic is the union-find cycle check from the minimum spanning trees lesson. So Kruskal's correctness is not a special miracle; it is the Rado–Edmonds theorem instantiated on the graphic matroid.

Acyclic edge sets form a matroid — Kruskal is matroid-greedy, taking edges by weight and rejecting any that close a cycle

Edges $1, 2, 3$ are accepted in weight order (blue); edge $4$ is rejected because $r$ and $s$ are already connected, so adding it would close the cycle $p q s r$ , leaving $I$ . The accepted set is a base: a spanning tree.

The uniform / partition matroid. Even simpler: fix $k$ and let $I = {A \subseteq S : ∣ A ∣ \leq k}$ , so every set of size at most $k$ is independent. This uniform matroid $U_{k, n}$ is plainly hereditary, and the exchange property is trivial (any larger set has a spare element). Greedy reduces to pick the $k$ heaviest elements, which is obviously optimal; the matroid machinery confirms the trivial.

The uniform matroid

U_{3, 6}

: independent means

∣ A ∣ \leq 3

. Greedy sorts by weight descending and takes the first

k = 3

(blue), which is trivially the maximum-weight base; the exchange property holds because any larger set always has a spare element.

The partition matroid generalizes it: partition $S$ into groups and allow at most $k_{i}$ elements from group $i$ ; independence is within every group's cap. Scheduling and assignment constraints of the form no more than $c$ of this kind are partition-matroid constraints, which is why greedy solves so many of them.

Beyond greedy: matroid intersection. A single matroid yields to greedy; the common independent sets of two matroids over the same ground set do not, in general. Still, matroid intersection solves the maximum-weight common independent set in polynomial time by augmenting-path methods (bipartite matching is a special case). The intersection of three matroids is already NP-hard. So the matroid is the precise frontier of greedy works; one step beyond it you need heavier machinery.

Why 0/1 knapsack and TSP are not matroids

The theorem cuts both ways, and it explains the failures we have already seen.

0/1 knapsack. Recall from the greedy method lesson that greedy fails on the 0/1 knapsack, and from the knapsack DP lesson that it needs dynamic programming. The reason, in matroid language: let $S$ be the items and call a set independent if its total weight fits in capacity $W$ . This is hereditary: drop items and it still fits. But the exchange property fails. Take capacity $W = 8$ and item sizes giving the independent sets ${7}$ and ${4, 4}$ . Both fit, and $∣ {4, 4} ∣ = 2 > 1 = ∣ {7} ∣$ , yet no element of ${4, 4}$ can join ${7}$ , since $7 + 4 = 11 > 8$ . The smaller independent set is stranded: it cannot grow toward the larger one, which is the exact pattern the exchange property forbids.

0/1 knapsack is not a matroid (

W = 8

). The independent set

{7}

and the larger

{4, 4}

both fit, yet adding either

4

{7}

gives

11 > 8

. No element of the larger set can grow the smaller, so the exchange property fails.

The exchange property is violated; the structure is not a matroid; and by Rado–Edmonds some weighting must defeat greedy, which is exactly the value/density counterexample from the greedy-method lesson.

Traveling salesman. For the TSP, let $I$ be the edge sets that extend to a Hamiltonian tour (or the partial-tour fragments greedy builds). This is not even reliably hereditary, and the exchange property collapses badly: a cheap partial path can be a dead end that no edge of a longer, valid fragment can rescue without revisiting a vertex or exceeding degree $2$ . There is no matroid, so no weighting guarantee, and indeed nearest-neighbor greedy can be made arbitrarily bad. TSP's hardness is not an accident of greed; the independence structure simply isn't a matroid (and TSP is NP-hard regardless).

The pattern is uniform. When greedy is provably optimal, you can almost always exhibit a matroid behind it. When greedy fails, the exchange property is the axiom that breaks.

Takeaways

Every greedy correctness proof is a greedy-stays-ahead induction (greedy's $k$ -th partial solution is never behind any rival's) or an exchange argument (transform any optimum into the greedy solution without loss). They are equivalent in power; exchange is the one that abstracts into a theory.
A matroid $M = (S, I)$ is a ground set plus a hereditary family of independent sets satisfying the exchange property: any smaller independent set can absorb some element of any larger one. Maximal independent sets are bases; they all share size $r (M)$ , the rank.
Rado–Edmonds theorem: on a weighted matroid, sorting by weight and greedily keeping independence yields a maximum-weight base, and greedy is optimal on a hereditary structure iff it is a matroid. The proof's one nontrivial step is precisely the exchange axiom.
The graphic matroid (acyclic edge sets) makes Kruskal's MST an exact instance of matroid-greedy; the uniform / partition matroid captures at most $k$ of each kind constraints. Matroid intersection is the polynomial-time frontier just beyond single-matroid greedy.
0/1 knapsack and TSP are not matroids (the exchange property fails), which is the structural reason greedy fails on them and dynamic programming or exact search is required instead.

CLRS, Ch. 16 — Greedy Algorithms (§16.2): the greedy-choice property and optimal substructure, proved by exchanging an optimal solution's first choice for greedy's. ↩
CLRS, Ch. 16 — Greedy Algorithms (§16.4): the Rado–Edmonds theorem — greedy returns a maximum-weight independent set exactly when the structure is a matroid; the proof rests on the exchange property. ↩