There is a quiet mystery at the heart of combinatorial optimisation. Why does the same naive algorithm — sort by weight, take what you can, skip what breaks the rules — solve apparently unrelated problems? It finds a maximum-weight spanning tree. It finds a minimum-weight basis of a vector configuration. It schedules jobs, assigns colours, packs schedules. The problems look different. The procedure is always the same, and it always works.
The answer, found by Hassler Whitney in 1935 and refined over the following decades, is that all these problems share a hidden skeleton. That skeleton is the matroid.
The tempting but incomplete picture
Start with the most familiar independence notion: linear independence of vectors. Given a finite set of vectors, some subsets are independent and some are not. Independence has a clear shape:
- the empty set is independent;
- a subset of an independent set is independent;
- if two independent sets have different sizes, the smaller one can be extended by borrowing something from the larger one without breaking independence.
Now look at a graph. Call a set of edges independent when it forms a forest, that is, when it contains no cycle. Independence has exactly the same shape:
- the empty edge set is acyclic;
- a subgraph of a forest is a forest;
- if two forests have different sizes, the smaller one can be extended by some edge of the larger one without creating a cycle.
Two worlds, one shape. Vectors in a vector space. Edges in a graph. The objects are different. The independence notion is different. But the combinatorial structure of which subsets count as independent is the same.
The tempting picture is that matroid are “just like linear independence, but abstract.” That is true, but it undersells the idea. The real question is sharper: what is the minimal combinatorial structure that makes greedy optimisation work? Matroids are the answer to that question, not merely a generalisation of vectors.
Why the axioms are forced
The three matroid axioms are not arbitrary. Each one is exactly the ingredient that a greedy algorithm needs, and removing any one of them breaks it.
Begin with a ground set and a family of subsets we want to call independent. We want greedy to be able to build a maximal independent set by taking elements one at a time.
The first requirement is that there is somewhere to start. This is non-emptiness:
Without it, greedy has no initial independent set to grow from. The family could be empty, and the algorithm would never begin.
The second requirement is that independence survives taking subsets. If a collection is independent, then any sub-collection of it — obtained by dropping some elements — is still independent. This is heredity:
It says: if a collection is acceptable, then any sub-collection is acceptable. This is what lets greedy discard elements freely. If the current set is independent and we drop something, we are still safe. Without heredity, dropping an element could land us in a dependent set, and greedy would have no stable way to backtrack.
The first two axioms together say is a downward-closed family containing the empty set. That is already a meaningful structure, called an independence system. But greedy does not yet work on every independence system. Something is missing.
The third requirement is that independent sets grow in a balanced way. This is exchangeability:
It says: a smaller independent set can always borrow something from a larger one and stay independent. This is the axiom that prevents greedy from getting stuck. If greedy has built a small independent set and a larger one exists, exchangeability guarantees that some still-available element can extend it. Without exchange, greedy could paint itself into a corner: a small independent set that cannot grow, even though a larger one exists elsewhere.
The striking fact is that these three axioms are not just sufficient for greedy to work. They are necessary. If an independence system violates any one of them, there is some weight assignment for which greedy returns a suboptimal basis. Matroids are the exact frontier where naive greedy is correct.
Why matroids arose
Whitney introduced matroids in 1935 to answer a specific question: what is the abstract structure shared by linear independence and graph acyclicity? He noticed that the key theorems about bases — all bases have the same size, exchange works, rank is well-defined — did not need vectors or graphs. They only needed the three axioms.
The name “matroid” was deliberately playful: a “matrix” plus the “-oid” suffix, suggesting something matrix-like without being a matrix. The idea was to isolate the combinatorial skeleton and throw away the surrounding material.
Later, Jack Edmonds in the 1960s gave the picture its optimisation meaning. He proved that matroids are exactly the structures on which the greedy algorithm is optimal. This turned matroids from a tidy abstraction into a tool: to understand why an algorithm works, check whether the underlying independence structure is a matroid.
Where the abstraction lives
Once the axioms are isolated, the same shape surfaces in many settings.
- Vector matroids take to be a set of vectors and independence to be linear independence. Bases are bases of the spanned subspace; rank is dimension.
- Graphic matroids take to be the edge set of a graph and independence to be acyclicity. Bases are spanning forests; rank is .
- Uniform matroids take independence to be “size at most “. This is the purest case, with no internal structure beyond a global cap.
- Partition matroids split the ground set into blocks and cap each block separately. Independence is a collection of local caps.
The comfort is that one no longer has to prove the same theorem four times. Prove it for matroids, and it holds for vectors, graphs, uniform caps, and partition caps at once.
The conceptual landing
A matroid is not a generalisation for its own sake. It is the minimal structure that makes a naive greedy procedure optimal. The three axioms are exactly the three things greedy needs: a place to start, safety when dropping elements, and a guarantee that a smaller independent set can always grow toward a larger one.
That is why matroids arose, and why they remain interesting. They name the exact combinatorial shape behind a family of algorithms that would otherwise look like a collection of lucky coincidences.