Matroid

A matroid is an independence system in which a smaller admissible selection can always grow using an element of a larger admissible selection. This exchange rule abstracts linear independence of vectors and the selection of edges forming a forest. It forces all matroid bases to have the same cardinality and makes the matroid greedy algorithm correct for maximizing their total weight. The useful surprise is that local choices become globally optimal because of a structural rule about admissible subsets, rather than a special numerical coincidence.

The weighted three-vector matroid below lets us inspect every subset and every possible size comparison. Its three vectors give three two-element matroid bases, yet their total weights differ. The graphic matroid of a graph triangle has exactly the same admissible labels. A pregeometry is a finitary closure-theoretic extension to possibly infinite sets.

For a finite matroid $M=(E,\mathcal{I})$, the convex hull of the indicator vectors of its matroid independent sets is exactly the displayed system, where $x(A)={\sum }_{e\in A}{x}_e$. It is an integral polytope. The equality $x(E)=r_M(E)$ instead gives the face corresponding to matroid bases; independence does not require that equality.

Proof. If $I$ is independent, $|I\cap A|\le r_M(A)$, so every independent indicator and every convex combination of them satisfies the inequalities. For the reverse inclusion, take an arbitrary real objective $c$. List its positive coordinates in nonincreasing order as $c_1\ge \cdots \ge c_k>0$, put $c_{k+1}=0$ and let $S_i$ be the first $i$ elements in this ordering. Run the matroid greedy algorithm on these elements, obtaining an independent set $I$. At every prefix the selected elements are maximal in $S_i$: an earlier rejected element cannot become admissible after further additions, by heredity. The augmentation axiom implies that every maximal independent set in $S_i$ has size $r_M(S_i)$. Hence $|I\cap S_i|=r_M(S_i)$.

For every point satisfying the displayed system, nonnegativity and telescoping giveThus every linear objective is maximized by an independent indicator, with the empty set used if all coefficients are nonpositive. Singleton rank inequalities bound every coordinate between zero and one, making the system compact. If it contained a point outside the compact convex hull of independent indicators, the finite-dimensional separating hyperplane theorem would supply an objective strictly larger at that point than at every independent indicator, a contradiction. This proves equality and integrality without assuming the desired convex-hull description in advance. Negative objective coefficients are discarded explicitly; maximizing over independent sets differs from maximizing over bases when such coefficients occur.

For an undirected finite graph, its forest polytope is the matroid independence polytope of its graphic matroid. It has the exact inequality descriptionsHere $\kappa (V,A)$ counts all connected components of a graph, including isolated vertices, and $E(S)$ denotes the edges internal to $S$. A maximal forest has one fewer edge than vertices in each component, giving the rank $|V|-\kappa (V,A)$. The matroid independence polytope theorem therefore proves the first description. It implies the second since the rank of $E(S)$ is at most $|S|-1$. Conversely, split any $A$ into its vertex components $S_j$; nonnegativity gives $x(A)\le {\sum }_{j}x(E(S_j))\le {\sum }_j(|S_j|-1)=|V|-\kappa (V,A)$. No spanning requirement is imposed, so an optimum with negative edge weights can leave vertices isolated.

On labelled ground sets of sizes $1,2,3$, there are respectively $2,5,16$ matroids, or $2,4,8$ up to matroid isomorphism. At rank of a matroid one, a nonempty subset of nonloops specifies all matroid independent sets of cardinality one. On three labels at rank of a matroid two, the three types are one matroid loop with an independent pair, no matroid loops with one pair of parallel elements of a matroid, and all pairs independent with the triple dependent.

The closure of a matroid obeys the displayed exchange rule. This is the finite pregeometry exchange principle: if adding $x$ newly makes $y$ dependent, then adding $y$ also makes $x$ dependent.

Proof. Write $r=r(A)$. The first hypothesis and the one-element bound on the rank of a matroid give $r(A+y)=r+1$. The second gives $r(A+x+y)=r(A+x)\le r+1$. Inclusion gives $r(A+x+y)\ge r(A+y)$, so equality holds. This is exactly $x\in {\mathrm{cl}}_M(A+y)$.

The closure of a matroid adds all elements that fail to increase its rank of a matroid. It abstracts the linear span in a linear matroid. It is extensive, preserves inclusion, preserves the rank of a matroid, and is an idempotent function:Proof. Extensivity follows from $A+x=A$ when $x\in A$. If $A\subseteq B$ and $x\notin B$, submodularity of matroid rank gives $r(B+x)-r(B)\le r(A+x)-r(A)$. Thus an element in ${\mathrm{cl}}_M(A)$ also lies in ${\mathrm{cl}}_M(B)$; the case $x\in B$ is automatic. Add the finitely many elements of ${\mathrm{cl}}_M(A)\setminus A$ one at a time. Inclusion preservation makes each addition have zero marginal increment of the rank of a matroid, proving rank preservation.

For completeness, nested subsets $A\subseteq B$ of equal rank of a matroid have the same closure of a matroid. If $x\notin B$, apply submodularity of matroid rank to $B$ and $A+x$ to obtain $r(B+x)\le r(A+x)$; monotonicity gives the reverse bound. The defining tests for membership in their closures are therefore equal. If $x\in B$, $r(A)\le r(A+x)\le r(B)=r(A)$, so both closures contain $x$. Apply this equal-rank result to $A\subseteq {\mathrm{cl}}_M(A)$ to prove idempotence. In particular, every maximal matroid independent set of $B$ has the same closure of a matroid as $B$.

For $0\le r\le n$, the uniform matroid $U_{r,n}$ on an $n$-element ground set has as its matroid independent sets exactly the subsets of cardinality at most $r$. Heredity is immediate, and augmentation works because any smaller such subset can acquire an element of a larger one without exceeding $r$. Its rank of a matroid on $A$ is $\min \{|A|,r\}$.

Distinct nonloops $x,y$ are parallel elements of a matroid when their pair is dependent. Declaring each nonloop parallel to itself makes parallelism an equivalence relation on the nonloops. Transitivity follows directly from augmentation: if $\{a,b\}$ and $\{b,c\}$ are dependent but $\{a,c\}$ independent, the independent singleton $\{b\}$ could not be augmented from the independent pair $\{a,c\}$, contradicting the matroid independence axioms. In a linear matroid, nonzero proportional vectors give parallel elements of a matroid.

A matroid dependent set is a subset of the ground set that is not a matroid independent set. By heredity, every subset containing a matroid dependent set is also dependent. Distinct nonloops are parallel elements of a matroid exactly when their pair is a matroid dependent set.

A nonloop is an element whose singleton is a matroid independent set. It is precisely an element that is not a loop of a matroid, and its singleton has rank of a matroid one.

An element $x$ is a loop of a matroid when its singleton is not a matroid independent set. By heredity, no matroid independent set contains it. Equivalently its singleton has rank of a matroid zero, or it belongs to the closure of a matroid of the empty set. In a graphic matroid, a self-loop is a loop of a matroid.

A matroid isomorphism between $(E,\mathcal{I})$ and $(E^{\prime },{\mathcal{I}}^{\prime })$ is a bijection $\varphi$ such that $I\in \mathcal{I}$ if and only if $\varphi (I)\in {\mathcal{I}}^{\prime }$. It relabels the ground set without changing independence. The number of labelled matroids therefore differs from the number of types up to matroid isomorphism.

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]

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.

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.

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.

On a finite ground set $E$, a submodular rank function is a normalised set function $r$ with $r(\varnothing )=0$, a monotone set function, and a submodular set function, such that $r(A\cup \{e\})-r(A)\in \{0,1\}$ for $e\notin A$. Equivalently, require nonnegative integer values, monotonicity, submodularity and $r(\{e\})\le 1$. The diminishing returns characterization of submodularity bounds each marginal by its singleton value. Thus $0\le r(A)\le |A|$.

These functions are precisely the rank functions of matroids. To see the converse direction, define $\mathcal{I}=\{A:r(A)=|A|\}$. It contains the empty set. If $B\subseteq A\in \mathcal{I}$, the unit marginal bounds give $|A|=r(A)\le r(B)+|A\setminus B|$, so $r(B)=|B|$ and heredity holds. For augmentation, suppose $A,B\in \mathcal{I}$ with $|A|<|B|$. If every $e\in B\setminus A$ had zero marginal over $A$, diminishing returns would keep each marginal zero as they are added successively. This would give $r(A\cup B)=r(A)=|A|<|B|=r(B)$, contradicting monotonicity. Some marginal is therefore one, giving an independent augmentation.

Finally any inclusion-maximal $I\subseteq A$ in this independence family has $r(I\cup \{e\})=r(I)$ for every remaining $e\in A\setminus I$. Successively adding them and using diminishing returns shows $r(A)=r(I)=|I|$, so the resulting matroid really has rank $r$. The forward direction is submodularity of matroid rank. These integer increment conditions distinguish matroid ranks from arbitrary real-valued submodular functions.

The rank of a matroid is a normalised set function, a monotone set function, and a submodular set function. Adding one element increases it by at most one.

Proof of submodularity. Choose a maximal matroid independent set $I_0$ in $A\cap B$, extend it to a maximal matroid independent set $I_A$ in $A$, then extend it to one $I_U$ in $A\cup B$. The matroid independence axioms make their sizes $r(A\cap B)$, $r(A)$ and $r(A\cup B)$. Every element of $I_U\setminus I_A$ lies outside $A$, since otherwise it could be added to $I_A$ inside $A$. Hence $I_0\cup (I_U\setminus I_A)$ is an independent subset of $B$, so its size $r(A\cap B)+r(A\cup B)-r(A)$ is at most $r(B)$.

The remaining assertions follow from the definition of the rank of a matroid. The empty set has maximum independent size zero, increasing the available subset cannot reduce that maximum, and deleting a newly added element from an independent subset decreases its size by at most one.

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.

Take labels $E=\{a,b,c\}$ and vectors in the real vector space ${\mathbb{R}}^2$:Here is the complete independence check for all eight subsets. The empty set is independent. Each of $\{a\},\{b\},\{c\}$ is independent because its vector is nonzero. Every pair is independent: the determinants of the two-column matrices $[v_a{v}_b]$, $[v_a{v}_c]$, and $[v_b{v}_c]$ are respectively $1$, $1$, and $-1$. The triple is dependent because $v_c-v_a-v_b=0$. ThereforeDeleting elements from any listed subset stays in this list, verifying heredity. Every exchange comparison has sizes $(0,1)$, $(0,2)$, or $(1,2)$. From the empty set, any element of the larger matroid independent set works: this covers three singleton targets and three pair targets. From any singleton to any pair, every element of the pair outside the singleton works, since every resulting pair is independent. This covers all nine singleton-pair comparisons, including disjoint ones. There are no other comparisons: all fifteen ordered size-increasing pairs satisfy exchange.

The three matroid bases are $\{a,b\}$, $\{a,c\}$, and $\{b,c\}$, all of cardinality two, with weights $13$, $14$, and $11$. The matroid greedy algorithm considers $a$, then $c$, then $b$: it admits $a$, admits $c$ because their determinant is nonzero, and rejects $b$ because the triple is dependent. The resulting matroid basis $\{a,c\}$ has weight $8+6=14$, the largest of the three totals. Every singleton can grow, so none is maximal; the three pairs are both maximal and maximum in cardinality.

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.

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.