Assign each element of the finite ground set a real number $w(e)$. The matroid greedy algorithm sorts elements by nonincreasing weight, starts with the empty set, and admits an element exactly when the enlarged selection is a matroid independent set. Ties can be resolved arbitrarily. After all elements have been considered, the result is a matroid basis of maximum total weight among all matroid bases. This holds even with negative weights: the task is to produce a full matroid basis. ^[ref]

Maximizing weight over all matroid independent sets is a different task when weights can be negative. For that task, skip negative elements; zero-weight additions are optional. With weights $w(a)=8$, $w(c)=-1$, $w(b)=-2$ in the weighted three-vector matroid, the heaviest matroid basis is $\{a,c\}$ with weight $7$, while the heaviest matroid independent set is $\{a\}$ with weight $8$. For nonnegative weights, every matroid independent set can be extended to a matroid basis without reducing weight, so the optimum values coincide.

Proof outline. Let $g_1,\dots ,g_r$ be the admitted elements in order, and order any competing matroid basis $b_1,\dots ,b_r$ by nonincreasing weight. If $w(b_k)>w(g_k)$, exchange would let one of $b_1,\dots ,b_k$ augment $\{g_1,\dots ,g_{k-1}\}$. That element was considered before $g_k$ and, by heredity, was admissible even at that earlier stage, a contradiction. Hence $w(g_k)\ge w(b_k)$ for every $k$, and summing proves optimality. Rejected elements remain inadmissible as the selection grows, by heredity, so the final selection is maximal. The guarantee depends on the matroid independence axioms and on weights adding independently across elements; interactions between chosen elements are a different objective.

For a finite undirected graph, the graphic matroid has its edges as the ground set. A subset is a matroid independent set when its edges form a forest on the original vertices, including isolated vertices. Its matroid bases give a spanning tree in each connected component of a graph; for a connected graph, each matroid basis is a spanning tree.

For a graph triangle on vertices $P,Q,R$, label the edges $a=PQ$, $b=QR$, and $c=PR$, with weights $8,5,6$. The empty set, all singletons, and all pairs are forests; the triple contains the graph cycle $P,Q,R,P$. Thus its eight subsets have exactly the independence pattern checked in the weighted three-vector matroid, and the same fifteen exchange comparisons pass. The matroid greedy algorithm chooses $PQ$, chooses $PR$, and rejects $QR$, producing the heaviest spanning tree, of weight $14$.

Exchange outline. Deleting edges cannot create a graph cycle. If forests $I,J$ have $|I|<|J|$, some edge of $J$ joins different connected components of a graph of $I$: otherwise, within each such component, $J$ would have at most its number of vertices minus one edges, giving $|J|\le |I|$. Adding that edge keeps a forest. This is the matroid independence axioms expressed through connectivity.

A linear matroid has a finite ground set indexing a family of vectors in a vector space over a specified field. A subset of labels is a matroid independent set precisely when its vectors are linearly independent. Labels distinguish repeated vectors; the ground set is not required to consist of distinct numerical vectors. The matroid bases correspond to bases for the linear span of all the supplied vectors.

Exchange outline. The linear span of $|I|$ linearly independent vectors has dimension $|I|$. If $|J|>|I|$, not all the linearly independent vectors indexed by $J$ can lie in that linear span. A vector outside it can be added to $I$. Heredity follows because a linear dependence in a subset would also be a linear dependence in the full selection.

For a subset $A$ of the ground set, the rank of a matroid on $A$ is the maximum cardinality of a matroid independent set contained in $A$:Thus $r_M(E)$ is the common size of the matroid bases, and $r_M(\varnothing )=0$. The weighted three-vector matroid has $r_M(E)=2$, even though its ground set has three labels.

A matroid basis is a matroid independent set that is a maximal element under inclusion of subsets: no additional element of the ground set can be admitted. Maximum cardinality means having the largest size among all matroid independent sets. Maximality tests whether this particular selection can grow; maximum size compares it with every selection. In a matroid the two conditions coincide, so all matroid bases have a common size. They need not have equal weight. ^[ref]

Proof outline. If a maximal matroid independent set $B$ were smaller than another matroid independent set $J$, the matroid independence axioms would admit an element of $J\setminus B$, contradicting maximality. Finiteness allows every matroid independent set to grow to a matroid basis by successive admissible additions. In a general independence system, maximal selections can have different sizes, as in the hereditary nonmatroid greedy obstruction.

A matroid independent set is a subset belonging to the family $\mathcal{I}$. Independence refers to the chosen matroid: for a linear matroid it means linear independence, and for a graphic matroid it means that the chosen edges contain no graph cycle. It is different from an independent set, which selects vertices with no edge between them.

Let $E$ be a finite set and $\mathcal{I}\subseteq \mathcal{P}(E)$ a family of subsets, where $\mathcal{P}(E)$ is the power set. The matroid independence axioms areThe second condition is heredity; the third is exchange, also called augmentation. The set difference $J\setminus I$ matters: the new element must actually increase the cardinality of $I$. Exchange adds one element without requiring any deletion from $I$. Nonemptiness together with heredity is equivalent to the first condition. ^[ref]

The cover of the 2021 Chemical Demonstrations Booklet credits Magdalena Wajrak and Tim Harrison as its preparers.