Prove that optimal set is unique

Question

Prove that there is a unique optimal set in a weighted matroid M = (S, I, w), with distinct weights on elements from S.

Answer 1

If you have a weighted matroid, the greedy algorithm always returns the maximum weight base.

Consider how the greedy algorithm works: at each step, you select the remaining maximally weighted element of the base, which is unique because the weights are unique. So when the greedy algorithm terminates, you have selected a maximally weighted base, and each choice you made was unique, so there can only be one.

I find it much easier to think about a particular example to see the logic when it comes to matroids in general. Consider any set of workers of size $I$ and a set of jobs of size $J$. Take an $I \times J$ matrix $A$ where $a_{ij}\ge 0 $ is the benefit of assigning worker $i$ to job $j$. Only a single worker can be assigned to any job. The greedy algorithm is, "Find the maximum $a_{ij}$, remove $i$ and $j$ from consideration; continue until $ \min \{I,J\} $ jobs and workers are assigned." If the $a_{ij}$ are all unique, you never run into indifferences, and there will be a unique optimal assignment.