Try
You can choose at most two instruments from four labeled a, b, c and d. A partial choice is independent when it respects that capacity. Starting with a, you can add any one other instrument. Starting with a and b, you cannot add another. Before continuing, list every choice that cannot be extended.
Those six pairs are maximal by inclusion: no further element can be added. This does not yet mean “best by weight.” If a is worth 9 and b is worth −1, the pair is worth 8 while a alone is worth 9. First settle the structural question: when do all maximal choices have the same size?
Predict
Change the rule: permit exactly the subsets of either {a} or {b,c}. Both a alone and b with c are maximal. Which has maximum cardinality, meaning largest number of elements? Explain why the smaller choice cannot be extended even though a larger permitted choice exists. This is a failure of augmentation, not of the rule that deleting an element remains permitted.
Experiment
Return to the four-instrument, capacity-two rule. Imagine a comparison basis B containing a and b, and a retained prefix A containing just a. You now want to accept c. Cross out one element of B to fit c while preserving every element of A.
The second row answers the actual question. A valid exchange that destroys an earlier choice is insufficient for a greedy proof. Repeat with A empty: both deletions now preserve the prefix. Try B containing a and d, with the same retained a and incoming c.
Understand
Let E be a finite ground set, the collection of available elements. Let I be a nonempty family of subsets of E called independent sets. A finite matroid satisfies two rules:
- Heredity: every subset of an independent set is independent. In particular the empty set is independent.
- Augmentation: if independent sets A and B satisfy |A| < |B|, some element b in B but outside A makes A together with b independent. Vertical bars denote the number of elements, not weight.
A basis is an independent set that is maximal by inclusion. The empty family of choices is not allowed, but a family consisting only of the empty set is allowed. Its elements are all loops: none can be chosen independently. No graph is needed for this definition.
Extension and equal basis size
Starting with an independent set, keep adding a feasible element until none remains. Each addition increases its size by one, and E is finite, so the process stops at a basis. If bases B and C had |B| < |C|, augmentation would add an element to B. That contradicts maximality. Interchanging B and C excludes the opposite inequality. All bases therefore have the same size r, called the rank. Rank zero is valid: the unique basis is empty.
An independent set of size r must be a basis. Otherwise it could extend to a larger independent set and then to a basis larger than r, a contradiction. This little fact is needed in both exchange arguments below.
Ordinary basis exchange: be careful about the quantifiers
Take bases B and C and specify one element e in B outside C. Deleting e leaves an independent set of size r−1. Augment it against C, obtaining an element f in C outside B: e is not in C, so f cannot merely be the deleted e. The new independent set has size r and is a basis. For each specified e, there exists an f. This does not say that every possible f works.
The preserved-prefix lemma
Suppose A is contained in a basis B, g is outside B, and A together with g is independent. We want a basis containing A and g while changing B as little as possible.
Start from A together with g. While its size is below r, augment it against B. Each step adds an element from B; no previous element is deleted. After finitely many steps, the set reaches size r and is a basis. It lies inside B together with g, a set of size r+1, so it omits exactly one element b. Because g and every element of A were retained, b belongs to B outside A. Thus the new basis is B plus g minus b, and all earlier choices survive.
The assumption that A with g is independent implies its size is at most r. If its size already equals r, no additions are needed. This includes the smallest boundary case of the construction. When g is already in B, simply retain B; the exchange lemma is unnecessary.
Two families you can verify without a graph
Uniform family: for a finite E with a capacity r between zero and |E|, allow every subset of size at most r. Deletion preserves the size bound. If |A| < |B| ≤ r, an element of B outside A fits into A. The four-instrument example is called U₂,₄: rank two on four elements.
Partition family: split the six labels into disjoint groups a,b,c and d,e,f, with capacities one and two. Deletion preserves both capacities. If B has more elements in total than A, some group has more B-elements than A-elements. That group has spare capacity in A and an element of B outside A; adding it proves augmentation. The rank is three, attained by a,d,e.
Optional column representation: the field matters
Over the real numbers take columns a=(1,0), b=(0,1), c=(1,1) and d=(1,2). The determinants of pairs ab, ac, ad, bc, bd, cd are 1, 1, 2, −1, −1, 1. Thus every pair is independent, while every triple is dependent in dimension two. This represents U₂,₄.
For a general finite family of columns, deleting columns preserves independence. If independent B has more columns than independent A, not all B-columns can lie in the span of A: their independent span would have dimension |B| greater than |A|. One column outside that span extends A independently. This proves augmentation.
Changing the field changes the question. Modulo two, d becomes (1,0), equal to a, so the pair ad is dependent. The real determinant 2 is nonzero over the reals and zero modulo two. Return to linear independence for span and dependence before attempting this optional route.
Apply
Write the preserved-prefix proof without using “exchange repeatedly” as a substitute for an argument. Identify the independent set at every stage, the basis used for augmentation, the stopping size, and the one element that can be omitted. Then return to the failed two-choice family from Predict and locate exactly where this construction becomes impossible.
Continue
Continue to weighted greedy and failure to turn this feasibility lemma into an optimality proof. Return to graphic exchange for the original tree example. Neither route requires earlier completion.
Primary comparison: Michel Goemans, MIT 18.433, Matroid Optimization, Handout 9 (16 March 2011), consulted 28 October 2026. This lesson proves the finite statements used here; matroid intersection, infinite matroids and general oracle complexity are outside its scope.
