Matroids

Every programmer learns the greedy algorithm: at each step, make the locally best choice and never look back. Sometimes it works brilliantly — Kruskal's algorithm finds the cheapest spanning tree in a graph by always picking the shortest unused edge that doesn't create a cycle. But sometimes greedy fails spectacularly: for the knapsack problem, always grabbing the highest-value item can leave you far from the optimum.

For decades this distinction looked like accident. The truth, discovered by Richard Rado in 1957 and extended by Jack Edmonds in 1971, is deeply structural: there is a precise class of combinatorial objects — matroids — for which the greedy algorithm is always optimal, and for anything outside that class greedy can fail.

A matroid abstracts the key feature of linear independence from vectors: a collection of sets called independent sets, where every subset of an independent set is independent (the hereditary property) and where if you have two independent sets of different sizes you can always extend the smaller one by adding an element from the larger (the augmentation property). Those two rules are exactly what you need for greedy to reach the global best.

The edges of a graph form a graphic matroid: a set of edges is independent if and only if it contains no cycle. Kruskal's algorithm is just the greedy algorithm applied to this matroid — sort all edges by weight, add each one if it doesn't close a cycle.

<p class="hint">{{hint}}</p>
<canvas id="graph" width="480" height="280"></canvas>
<div class="info-row">
  <span id="status" class="status">{{status_initial}}</span>
  <span id="total" class="total"></span>
</div>
<div class="btns">
  <button id="run" type="button">{{btn_run}}</button>
  <button id="shuffle" type="button" class="ghost">{{btn_shuffle}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="edge-list"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { display: block; border: 1px solid #d0d8e0; border-radius: 10px;
         background: #f7f9fb; max-width: 100%; }
.info-row { display: flex; align-items: center; gap: 1rem; margin: .5rem 0 .3rem; min-height: 1.6em; }
.status { font-size: .92rem; font-weight: 600; }
.status.done { color: #0a7d33; }
.status.step { color: #1d3557; }
.total { font-size: .92rem; color: #555; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
#edge-list { font-size: .82rem; color: #444; line-height: 1.7; max-height: 110px; overflow-y: auto; }
#edge-list span { margin-right: .5rem; }
.el-added { color: #0a7d33; font-weight: 700; }
.el-skipped { color: #c92f3c; text-decoration: line-through; }

// Code not found

Press Run greedy to watch Kruskal build the minimum spanning tree one edge at a time. Press Shuffle weights to try a different instance. Notice that greedy never backtracks and always reaches the optimum — the Rado–Edmonds theorem guarantees this for any matroid, not just graphs.

The central theorem, proved by Richard Rado (1957) and given its modern form by Jack Edmonds (1971), is a complete characterization:

Rado–Edmonds theorem: A greedy algorithm that always picks the highest-weight available independent element produces a maximum-weight independent set if and only if the independence system is a matroid.

This is a two-way result — not merely "greedy works on matroids" but "greedy works only on matroids." If your structure fails the augmentation axiom, you can always construct a weight function that makes greedy fail.

The three matroid axioms that guarantee greedy optimality are:

• Non-emptiness: the empty set is independent.
• Hereditary property: every subset of an independent set is independent.
• Augmentation (exchange) property: if A and B are both independent and |B| > |A|, then some element of B \ A can be added to A and the result is still independent.

The augmentation property is the critical one: it means all maximal independent sets (called bases) have the same size, and you can always grow a smaller independent set toward a larger one without getting stuck. This is precisely what lets greedy exchange locally and arrive globally.

Efficiency: on a matroid with ground set of size n, the greedy algorithm runs in O(n log n + n · T) time where T is the cost of a single independence test. For graphic matroids T is nearly O(1) with union-find, giving Kruskal's classical O(n log n) bound. The problem of finding a maximum spanning tree is equally easy — just negate all weights.

Beyond single matroids: matroid intersection (find a common independent set in two matroids of maximum weight) is polynomial but harder; matroid union and three-way intersection can encode NP-complete problems. The greedy paradise has clear borders.

Matroid theory turns up wherever you need a provably efficient algorithm for a combinatorial optimum:

• Network design: minimum spanning trees (graphic matroid), minimum arborescences, and cheapest connected subgraphs are all solved optimally by greedy. Every time an ISP lays cable or a chip designer routes wires at minimum cost, a matroid guarantee is at work.
• Scheduling: the class of problems where you select a subset of jobs to schedule on a single machine to maximize reward — subject to deadlines — admits a matroid structure (a transversal matroid or partition matroid), so greedy scheduling is optimal.
• Coding theory: the columns of a generator matrix form a linear matroid over a finite field. Greedy decoding, minimum-distance codewords, and efficient encoder design all exploit matroid structure.
• Linear algebra and circuits: matroids were invented partly to axiomatize graph theory and linear independence in a common framework. The cycle matroid of a graph and the column matroid of a matrix are the two canonical examples; understanding one illuminates the other.
• Matroid intersection for matchings: a maximum matching in a bipartite graph is the intersection of two partition matroids — so it can be solved in polynomial time, explaining why max-matching is easy while three-dimensional matching is NP-complete.

Matroid theory is also the diagnostic tool for new greedy algorithms: when someone proposes a greedy shortcut, checking whether the feasible sets form a matroid tells you immediately whether the shortcut is guaranteed correct.

The greedy algorithm is one of the oldest ideas in computing, yet for most of its history it looked like a heuristic — something that happens to work in special cases. Matroids changed that. The Rado–Edmonds theorem turns "greedy works here" from an observation into a theorem with a tight characterization: you can trust greedy if and only if your independent sets form a matroid.

That precision has lasting consequences. It tells network engineers why spanning-tree algorithms are reliable, it tells schedulers when deadline-driven greedy is safe, and it draws a clean line between the easy optimization problems and the hard ones. When greedy fails — as it does for knapsack, bin packing, and the rest of the NP-hard world — it is not bad luck. It is the absence of the augmentation axiom, and no amount of cleverness in the greedy order can fix that.

Matroids are, in a precise sense, the mathematical home of trustworthy greediness.