Symptom

You have a selection problem. Pick a set of items, each with a value, subject to some rule about which sets are allowed, and maximise total value.

You write the greedy solution in ten minutes: sort by value descending, take each item if it keeps the set legal. You test it on every case you can think of and on a thousand random instances, and it is correct every time. You ship it.

Four months later a customer reports a case where the answer is 12% worse than an alternative they computed by hand. Greedy was wrong all along, and your thousand random tests never generated the structure that breaks it.

The uncomfortable part is that you had no way to know. Greedy is correct for minimum spanning trees and wrong for knapsack, correct for interval scheduling by end-time and wrong for interval scheduling by length, and nothing about the problem statements makes the difference visible. There is a condition that decides it exactly, and testing is not it.

Statement

Matroid. A matroid is a pair $M = (E, \mathcal{I})$ where $E$ is a finite ground set and $\mathcal{I} \subseteq 2^E$ is a family of independent sets satisfying:

  1. (Non-triviality) $\emptyset \in \mathcal{I}$.
  2. (Hereditary) If $B \in \mathcal{I}$ and $A \subseteq B$ then $A \in \mathcal{I}$.
  3. (Exchange) If $A, B \in \mathcal{I}$ and $|A| < |B|$, then there exists $x \in B \setminus A$ with $A \cup {x} \in \mathcal{I}$.

Axiom 3 is the content. It says a smaller independent set can always be grown using an element from any larger one, which forbids the situation where an early choice paints you into a corner.

Rado–Edmonds theorem (1957, 1971). Let $(E, \mathcal{I})$ be hereditary and non-trivial. Then the greedy algorithm — sort $E$ by weight descending, add each element whose addition keeps the set independent — finds a maximum-weight independent set for every weight function $w : E \to \mathbb{R}_{\ge 0}$ if and only if $(E, \mathcal{I})$ is a matroid.

An if-and-only-if. Greedy is not merely sufficient for matroids; matroids are exactly the structures on which greedy always works. If greedy is correct for all weightings, you were working on a matroid whether you knew it or not.

Argument

The full proof of both directions is longer than this post has room for, so here is the load-bearing sketch, and the Read next carries the rest.

Proof sketch.

(Matroid $\Rightarrow$ greedy optimal.) Let $G = {g_1, \dots, g_k}$ be greedy’s output in the order chosen, so $w(g_1) \ge \cdots \ge w(g_k)$, and let $O$ be an optimal independent set, ordered likewise. First, $|G| = |O|$: if $|G| < |O|$, exchange gives an element of $O$ extending $G$, and greedy would have taken it. Then show $w(g_i) \ge w(o_i)$ for every $i$ by induction. Suppose not, and let $i$ be least with $w(g_i) < w(o_i)$. Apply exchange to $A = {g_1,\dots,g_{i-1}}$ and $B = {o_1,\dots,o_i}$, with $|A| < |B|$: some $o_j \in B \setminus A$ extends $A$ independently, and $w(o_j) \ge w(o_i) > w(g_i)$. But greedy, having built $A$, considers $o_j$ before $g_i$ and would have taken it. Contradiction. Summing termwise gives $w(G) \ge w(O)$.

(Greedy optimal $\Rightarrow$ matroid.) Contrapositive. If exchange fails for some $A, B$ with $|A| = a < b = |B|$, choose weights $w = 1 + 1/a$ on $A$’s elements, $1$ on $B \setminus A$, and $0$ elsewhere. Greedy takes all of $A$ first, then can add nothing from $B$, ending at $a + 1$. Taking $B$ gives $b > a+1$ when $b > a+1$; tuning the constants covers $b = a+1$. So a weight function exists on which greedy loses.

The exchange axiom is the whole story. Read it as: no greedy choice can be regretted. Whatever you have taken so far, if a better solution is larger, you can always continue toward it. Failure of greedy always looks like an early choice that blocks a set of later ones, and axiom 3 is exactly the statement that this cannot happen.

Instances, so the abstraction has referents.

  • Graphic matroid. $E$ = edges of a graph, independent = acyclic. Greedy is Kruskal’s algorithm, and the Rado–Edmonds theorem is why Kruskal is correct. The MST proof you learned separately is this theorem specialised.
  • Uniform matroid. Independent = any set of size $\le k$. Greedy is “take the $k$ largest”, which is obviously right, and this is the matroid that makes it so.
  • Linear matroid. $E$ = vectors, independent = linearly independent. This is where the vocabulary — independent, rank, basis, span — comes from, and the axioms are exactly the properties of linear independence that survive abstraction.
  • Partition matroid. $E$ partitioned into groups with quotas $k_i$; independent = at most $k_i$ from group $i$. This is the one that fits real selection problems: “at most 3 from each team”, “at most 2 per availability zone”. Greedy is provably optimal here, which is worth knowing because the constraint looks complicated enough to reach for a solver.
  • Transversal matroid. Independent = sets of left vertices matchable into the right side of a bipartite graph. Assignment problems with one-sided preferences land here.

And the non-matroids, which is where the failures come from.

  • Knapsack. Independent = sets fitting in the capacity. Hereditary, yes. But exchange fails: ${$item of weight 6$}$ and ${$two items of weight 4$}$ in a capacity-8 knapsack — the smaller set cannot be extended by either member of the larger. Greedy by value, or by value density, is not optimal, and knapsack is NP-hard.
  • Vertex cover, set cover, TSP. All fail exchange, all have greedy heuristics with approximation ratios rather than optimality.
  • Interval scheduling. Sets of pairwise-disjoint intervals do not form a matroid — exchange fails — and yet greedy by earliest end time is optimal. This is the important caveat: the theorem says matroids are exactly where greedy works for every weight function, and a specific weighting can still admit greedy on a non-matroid. Interval scheduling by count works; by weight, greedy fails and you need dynamic programming.

What to do when it is not a matroid. The structure degrades gracefully, which is the useful part.

Matroid intersection. Sets independent in two matroids simultaneously. Greedy fails, but the problem is still solvable in polynomial time — bipartite matching is the intersection of two partition matroids. Three matroids is NP-hard.

Submodular maximisation. If the objective has diminishing returns ($f(A \cup {x}) - f(A) \ge f(B \cup {x}) - f(B)$ for $A \subseteq B$) and the constraint is a matroid, greedy gives a $(1 - 1/e) \approx 0.63$ approximation, and that constant is optimal unless P = NP. Most real “pick a diverse set” problems — sensor placement, feature selection, document summarisation — are here, and the honest engineering position is a proved 63% rather than a hoped 100%.

Matroid basics as a modelling check. Before writing greedy, test exchange on two small independent sets of different sizes. It takes ten minutes and it is a proof rather than a thousand random trials.

Forbids

Concluding greedy is optimal because it passed testing. Test cases sample the input space; the matroid condition characterises it. Random instances rarely contain the blocking structure, which is exactly why the counterexample arrived from a customer and not from CI.

Greedy optimality for knapsack, set cover, or weighted interval scheduling. Exchange fails in each. There is no ordering, no tie-break, no clever value-density metric that repairs it, because the theorem’s “only if” rules the whole family out at once.

Expecting a greedy algorithm proved for one weighting to survive reweighting. Interval scheduling is the cautionary case: correct by count, incorrect by weight, same constraint family.

Does not forbid

It does not say greedy is useless off matroids, and the over-correction here is as costly as the original error. Greedy on submodular objectives under a matroid constraint is $(1-1/e)$-optimal and cannot be beaten in polynomial time. Greedy set cover is $\ln n$-optimal and is likewise optimal under standard assumptions. These are the best known algorithms, not fallbacks, and reading this theorem as “avoid greedy unless matroid” discards them.

It does not require you to identify the matroid explicitly. Kruskal was correct for fourteen years before Rado–Edmonds explained why. The theorem is a tool for deciding new cases, not a licence you must obtain first.

It does not mean non-matroid problems are intractable. Matroid intersection, weighted interval scheduling, and knapsack with integer weights are all polynomial; they simply need a different algorithm than greedy. The theorem is about greedy, not about hardness, and treating “not a matroid” as “NP-hard” is a common and wrong leap.

It does not require weights to be non-negative in every variant. The statement above uses $w \ge 0$ for cleanliness; the negative-weight case is handled by discarding negatives, since the hereditary property makes dropping them safe.

Boundary

  • Weighted maximisation only. The theorem is about maximising a linear weight over independent sets. Non-linear objectives are the submodular story above, with its different guarantee.
  • The independence oracle must be cheap. Greedy calls it once per element; if testing independence is itself expensive, the algorithm’s cost is dominated by the oracle, and for some matroids the oracle is the hard part.
  • Greedoids relax the hereditary axiom and cover cases like Dijkstra and breadth-first search, where the structure is ordered rather than downward closed.
  • Two matroids is easy, three is hard. Matroid intersection is polynomial; three-matroid intersection is NP-hard, and 3-dimensional matching is the standard witness.
  • Representability is subtle. Not every matroid comes from a matrix over a given field, and the ones that do not are where the deep theory lives — none of which affects the greedy result, which needs only the axioms.

The check to internalise: before trusting greedy, try to break exchange on two small sets. Passing tests tells you about the tests; the exchange property tells you about the problem.