Chapter 32: Matroid Theory

Exactly which independence systems make greedy choice optimal?

Selecting the most valuable available item looks sensible until it blocks two items whose combined value is larger. What structural condition makes such local choices reliable for every assignment of weights? Matroids answer that question by abstracting the exchange behavior shared by forests, independent vectors, and certain matching systems.

For the foundation, an independence system is a finite set $E$ together with a nonempty family $\mathcal I$ closed under taking subsets. Its members are feasible sets. It is a matroid when it also satisfies augmentation: if $I,J\in\mathcal I$ and $\lvert I\rvert\lt\lvert J\rvert$, some $e\in J\setminus I$ makes $I\cup\{e\}$ independent. A basis is a maximal independent set; in a matroid all bases have the same size, the rank. Greedy processes elements by decreasing weight and accepts an element when independence is preserved.

The foundation tools are these established facts: greedy maximizes the weight of an independent set for every nonnegative weighting exactly for matroid independence systems; complements of bases define the dual matroid; and a matrix represents a matroid when its independent column subsets are precisely the independent sets. Field choice matters. The optional sections develop proofs, algorithms, and extensions; their graduate arguments are not required to complete the final foundation investigation.

32.1 Independence axioms and examples

Optional extension; not required to complete the chapter foundation. Independence is a property of labeled subsets, not a geometric picture. The same abstract matroid can have several different realizations.

A finite matroid $M=(E,\mathcal I)$ satisfies:

1. $\varnothing\in\mathcal I$.
2. If $J\subseteq I\in\mathcal I$, then $J\in\mathcal I$.
3. If $I,J\in\mathcal I$ and $\lvert I\rvert\lt\lvert J\rvert$, some $e\in J\setminus I$ satisfies $I\cup\{e\}\in\mathcal I$.

The third condition is augmentation. It implies that all maximal independent subsets of any fixed $S\subseteq E$ have equal size: otherwise the smaller could be augmented by the larger. This local equal-size statement is stronger than merely saying that maximal sets in the whole ground set have equal size.

Solved examples. The uniform matroid $U_{r,n}$ on an $n$-element set has all subsets of size at most $r$ independent, where $0\leq r\leq n$. Heredity is immediate, and any element of $J\setminus I$ augments a smaller independent $I$, since $\lvert I\rvert+1\leq\lvert J\rvert\leq r$.

For a matrix over a field, let $E$ label its columns and declare independent subsets to be linearly independent. If every column of $J$ lay in the span of $I$, then $\dim\operatorname{span}(J)\leq\lvert I\rvert$, contradicting $\lvert J\rvert\gt\lvert I\rvert$. Thus at least one column augments $I$. Zero columns are allowed and correspond to loops.

For a partition matroid, partition $E$ into blocks $P_1,\ldots,P_t$ with capacities $q_i\geq0$, and require $\lvert I\cap P_i\rvert\leq q_i$. If $\lvert J\rvert\gt\lvert I\rvert$, some block has more elements of $J$ than of $I$. Adding an element from that block respects its capacity. These examples illustrate that augmentation can arise from dimension, cardinality, or resource capacities.

A forest matroid is explained in 32.3. Its ground elements are edges, not vertices. Similarly, a transversal matroid uses a fixed set of items matched into auxiliary slots; it is different from declaring arbitrary edge sets to be matchings.

Exercise. Let $E=\{a,b,c,d\}$, blocks $\{a,b\},\{c,d\}$, and capacity one in each. List the bases and augment $I=\{a\}$ using $J=\{b,c\}$. Hint: Compare the block occupancies. Solution: The bases are $\{a,c\},\{a,d\},\{b,c\},\{b,d\}$. Adding $b$ to $I$ violates the first capacity, but adding $c$ is valid. Augmentation requires some valid element, not every candidate.

32.2 Bases, circuits, and rank functions

Optional extension; not required to complete the chapter foundation. Bases describe maximal freedom, circuits describe minimal obstructions, and rank measures the amount of independence available inside a subset.

A circuit is a minimal dependent set. A loop is an element whose singleton is a circuit; a coloop belongs to every basis. Distinct nonloop elements are parallel when their pair is a circuit. Bases satisfy the exchange property: for bases $B_1,B_2$ and $e\in B_1\setminus B_2$, some $f\in B_2\setminus B_1$ makes $(B_1\setminus\{e\})\cup\{f\}$ a basis. Apply augmentation to the independent $(\lvert B_1\rvert-1)$-set and $B_2$; the augmenting element must lie outside $B_1$.

Define

$$ r(S)=\max\{\lvert I\rvert:I\subseteq S,\ I\in\mathcal I\},\qquad \operatorname{cl}(S)=\{e\in E:r(S\cup\{e\})=r(S)\}. $$

Rank satisfies $0\leq r(S)\leq\lvert S\rvert$, monotonicity, and submodularity:

$$ r(S)+r(T)\geq r(S\cup T)+r(S\cap T). $$

Proof of submodularity. Choose a basis of $S\cap T$, extend it to a basis $J$ of $S$, then extend $J$ to a basis $K$ of $S\cup T$. The new elements $K\setminus J$ lie in $T\setminus S$, because $J$ was already maximal in $S$. Together with the chosen intersection basis they form an independent subset of $T$, so $r(T)\geq r(S\cap T)+r(S\cup T)-r(S)$.

Conversely, an integer-valued function satisfying these rank axioms determines a matroid by $I\in\mathcal I$ exactly when $r(I)=\lvert I\rvert$. This is a standard equivalent axiom system; deriving augmentation from submodularity is the omitted direction of that equivalence.

Circuits satisfy elimination: if distinct circuits $C_1,C_2$ share $e$, their union minus $e$ contains a circuit. Indeed their intersection is independent, and rank submodularity gives $r(C_1\cup C_2)\leq\lvert C_1\cup C_2\rvert-2$. If the union minus $e$ were independent, its size would force rank at least $\lvert C_1\cup C_2\rvert-1$, a contradiction. Any dependent finite set contains a minimal dependent subset.

Exercise. Find all circuits and closures of singletons in $U_{2,4}$. Hint: Every pair is independent and every triple is dependent. Solution: The four triples are exactly the circuits. Each singleton has rank one and closure equal to itself. Every two-element set has rank two and closure equal to the whole ground set. This matroid is simple: it has no loops or parallel pairs.

32.3 Graphic, cographic, linear, and transversal matroids

Optional extension; not required to complete the chapter foundation. These constructions produce matroids from networks, matrices, and assignments. Their ground sets must remain explicit to avoid confusing different kinds of independence.

The graphic matroid $M(G)$ has ground set $E(G)$ and independent sets the forests. For a spanning subgraph $(V,F)$, its rank is $\lvert V\rvert-c(F)$, where $c(F)$ includes isolated vertices. To prove augmentation, suppose no edge of a larger forest $J$ could be added to a smaller forest $I$. Then every edge of $J$ lies within one component of $I$. Inside each such component, a forest has at most its number of vertices minus one edges; summing gives $\lvert J\rvert\leq\lvert I\rvert$, a contradiction. Graph loops are matroid loops; parallel graph edges form two-element circuits.

The cographic matroid is $M(G)^{\ast}$, defined by complementary bases as in 32.5. For connected $G$, its bases are complements of spanning trees, and its circuits are bonds, the minimal nonempty edge cuts. A set is cographically independent exactly when removing it leaves the graph connected: the remaining edges then contain a spanning tree. This construction applies without requiring a planar drawing.

A linear matroid is given by independent columns over a specified field. Graphic matroids are linear over every field: oriented incidence columns represent them, with one redundant row per component removable. In characteristic two the signs coincide, but forest columns remain independent. Graphical cut and cycle structures explain why these particular representations work uniformly across fields.

A transversal matroid has left vertices $E$ and auxiliary right-hand slots $R$ in a bipartite graph. A subset of $E$ is independent if a matching assigns all its elements to different slots. Heredity is immediate. For augmentation, compare matchings saturating $I$ and a larger $J$; their alternating union contains an augmenting component that covers an additional left element while preserving coverage of $I$. This proves exchange, with the standard alternating-path lemma as the matching prerequisite.

Solved example. A triangle with edge labels $a,b,c$ gives $U_{2,3}$. It is represented over every field by columns $(1,0),(0,1),(1,1)$. It also arises as a transversal matroid when each of $a,b,c$ can use either of two slots: exactly the subsets of size at most two can be matched. Its cographic dual is $U_{1,3}$, with singleton bases and two-element circuits. Different constructions can agree as matroids while the graph, matrix, and bipartite objects themselves differ.

The figure shows the common independent pair $\{a,c\}$ in the three models. The triangle edges form a tree, the highlighted columns have determinant one, and the highlighted assignment uses distinct slots. All six allowable assignment edges are drawn; only two belong to the displayed matching.

Exercise. For left elements $a,b,c$ and slots $1,2$, take neighborhoods $N(a)=\{1\}$, $N(b)=\{1\}$, $N(c)=\{1,2\}$. Find the bases and a circuit. Hint: The first two elements compete for a single slot. Solution: The bases are $\{a,c\}$ and $\{b,c\}$, and $\{a,b\}$ is the unique circuit. The element $c$ is a coloop. This transversal matroid has rank two but is not $U_{2,3}$, because one pair is forbidden.

32.4 Greedy algorithm characterization

Optional extension; not required to complete the chapter foundation. The theorem concerns all weights, not the success of one run. Assume a finite nonempty hereditary independence system and nonnegative element weights.

Order $E=\{e_1,\ldots,e_n\}$ so $w_1\geq\cdots\geq w_n\geq0$. Scan in that order, accepting $e_i$ exactly when the current set remains independent. Ties may be broken arbitrarily. For a matroid, greedy produces a maximum-weight independent set.

Proof of sufficiency. Let $E_i=\{e_1,\ldots,e_i\}$. The accepted elements in this prefix form a maximal independent subset of $E_i$: a rejected element cannot become feasible after more elements are accepted, by heredity. Augmentation then makes its size $r(E_i)$. Any independent $J$ satisfies $\lvert J\cap E_i\rvert\leq r(E_i)$. With $w_{n+1}=0$, summation by parts gives

$$ w(J)=\sum_{i=1}^n(w_i-w_{i+1})\lvert J\cap E_i\rvert. $$

Every coefficient is nonnegative, and greedy attains the largest possible prefix count at every $i$, so its total weight is at least $w(J)$.

Proof of necessity. Suppose augmentation fails for independent $I,J$ with $\lvert I\rvert\lt\lvert J\rvert$. Then $I$ is nonempty. Choose $0\lt\varepsilon\lt1/\lvert I\rvert$, assign weight $1+\varepsilon$ to elements of $I$, weight one to $J\setminus I$, and zero elsewhere. Greedy first accepts all of $I$, then none of $J\setminus I$. Its weight is $(1+\varepsilon)\lvert I\rvert$. But $w(J)=\lvert J\rvert+\varepsilon\lvert I\cap J\rvert$ is larger, since $\lvert J\rvert-\lvert I\rvert\geq1\gt\varepsilon\lvert I\setminus J\rvert$. Thus universal greedy correctness forces augmentation. Together, the two proofs characterize matroids.

Solved trace. In the triangle matroid, give $a,b,c$ weights $5,3,4$. The order is $a,c,b$. Greedy accepts $a$, accepts $c$, and rejects $b$ because the triple is a circuit. The three basis weights are $8,9,7$ for $ab,ac,bc$, so the returned basis $ac$ has optimal weight nine.

Sorting costs $O(n\log n)$ comparisons, followed by at most $n$ independence-oracle calls. If a call costs $T$, the total is $O(n\log n+nT)$. In graphic matroids, a disjoint-set structure tests whether an edge joins different components; sorting plus union–find yields Kruskal's algorithm. For minimum spanning bases, sort increasing costs. This is basis optimization, not unrestricted independent-set optimization.

For arbitrary real weights, greedy still optimizes among bases: adding a common constant to every weight makes them nonnegative and preserves comparisons between equal-sized bases. For maximum-weight independent sets, skip negative-weight elements. Blindly forcing a basis could lower the objective.

Exercise. On $U_{2,3}$, give weights $5,-1,-2$. Compare maximum independent-set and maximum basis objectives. Hint: Feasible sets have different sizes. Solution: The best independent set is the singleton of weight five. The best basis contains weights five and minus one, totaling four. Greedy with negative-weight rejection solves the first problem; greedy continued to full rank solves the second.

32.5 Matroid duality

Optional extension; not required to complete the chapter foundation. Duality exchanges what must be selected with what can be omitted. It acts on the same labeled ground set, not on a complementary graph vertex set.

For $M=(E,\mathcal I)$, define the bases of $M^{\ast}$ by

$$ \mathcal B(M^{\ast})=\{E\setminus B:B\in\mathcal B(M)\}. $$

These are the bases of a matroid, and applying the operation twice recovers $M$. The dual rank formula is

$$ r^{\ast}(S)=\lvert S\rvert-r(E)+r(E\setminus S). $$

To derive it, maximize $\lvert S\cap(E\setminus B)\rvert$ over primal bases. Minimizing $\lvert S\cap B\rvert$ is equivalent to maximizing $\lvert B\cap(E\setminus S)\rvert$, which equals $r(E\setminus S)$ because a basis of that restriction extends to a primal basis. The formula satisfies the rank axioms: single-element rank increments lie between zero and one, and submodularity follows by applying primal submodularity to complements. Thus it also verifies that complementary bases define a matroid.

Duality exchanges loops and coloops, and circuits of $M^{\ast}$ are cocircuits of $M$. A circuit and cocircuit cannot meet in exactly one element. For representable matroids this follows from orthogonality of a dependence vector and a row-space vector; the general statement follows from basis exchange. Its general proof is omitted.

Solved examples. The triangle $U_{2,3}$ has dual $U_{1,3}$. Its spanning-tree bases are pairs, so complementary bases are single edges. The triangle-plus-bridge matroid in 32.2 has dual bases $\{a\},\{b\},\{c\}$; the bridge $d$ becomes a loop. Its rank is one, confirmed by $r^{\ast}(E)=4-3=1$. Meanwhile $U_{2,4}^{\ast}=U_{2,4}$, since complements of all pairs are all pairs. Self-duality here is an exact equality on the chosen labels.

If a full-row-rank matrix $V$ represents $M$, a matrix whose rows form a basis of $\ker V$ represents $M^{\ast}$. This linear-duality theorem identifies complementary nonsingular column minors; its general determinant argument is omitted. It also shows representability over a fixed field is preserved by duality.

Exercise. Compute the dual rank of $\{d\}$ and $\{a,b\}$ in the triangle-plus-bridge example. Hint: Use $r(E)=3$. Solution: $r^{\ast}(\{d\})=1-3+r(\{a,b,c\})=0$, so $d$ is a loop. Also $r^{\ast}(\{a,b\})=2-3+r(\{c,d\})=1$, so the pair is dependent in the rank-one dual.

32.6 Matroid intersection and union

Optional extension; not required to complete the chapter foundation. Two valid matroid constraints can have an intersection that fails to be a matroid. Nevertheless, two-matroid intersection admits a powerful optimization theorem.

Let $M_1,M_2$ have the same ground set $E$ and ranks $r_1,r_2$. A common independent set belongs to $\mathcal I_1\cap\mathcal I_2$. The matroid intersection theorem states

$$ \max_{I\in\mathcal I_1\cap\mathcal I_2}\lvert I\rvert =\min_{S\subseteq E}\bigl(r_1(S)+r_2(E\setminus S)\bigr). $$

The upper-bound direction is immediate: split any common independent $I$ between $S$ and its complement and apply the two rank bounds. Attainment uses exchange paths. For a common independent $I$, sources are elements outside $I$ addable in $M_1$, and sinks are those addable in $M_2$. Put an arc $x\to y$ for $x\notin I,y\in I$ when $I-y+x$ is independent in $M_2$, and $y\to x$ when it is independent in $M_1$. A shortest source-to-sink path permits an augmentation by symmetric difference. When none exists, reachability yields a rank certificate of optimality. Proving the shortest-path exchange lemma and the certificate is omitted; arbitrary alternating paths are not automatically safe.

Solved example. Let $a=(u_1,v_1)$, $b=(u_1,v_2)$, $c=(u_2,v_1)$ be bipartite edges. One partition matroid enforces at most one edge per left endpoint; the other does the same for right endpoints. Their common independent sets are exactly $\varnothing,a,b,c,bc$, reproducing the nonmatroid system in the opening card. Starting from $I=\{a\}$, the source is $c$, the sink is $b$, and the exchange path is $c\to a\to b$. Flipping it gives $\{b,c\}$, increasing cardinality to two. The choice $S=E$ gives the upper certificate $r_1(E)+r_2(\varnothing)=2$, so the optimum is exactly two.

The union of matroids $M_1,\ldots,M_k$ on $E$ declares a set independent if it can be partitioned as $I_1\sqcup\cdots\sqcup I_k$ with $I_j$ independent in $M_j$. Unlike intersection, this is always a matroid. Its rank is

$$ r_{\vee}(X)=\min_{S\subseteq X}\left(\lvert X\setminus S\rvert+\sum_{j=1}^k r_j(S)\right). $$

The easy direction bounds the assigned elements inside $S$ by the rank sum and those outside by their number. The equality and augmentation theorem are established matroid-union results; see Edmonds' original partition paper for the foundational partition setting.

Two copies of the triangle's graphic matroid cover all three edges: assign $\{a,b\}$ to one forest and $\{c\}$ to the other. The union therefore has rank three, even though each original rank is two. Constraints satisfied simultaneously and elements assigned between alternatives are different operations.

Exercise. Determine the union of two copies of $U_{1,3}$. Hint: Each copy can receive at most one element. Solution: Its independent sets are exactly those of size at most two, so the union is $U_{2,3}$. On the whole three-element set, the rank formula gives minimum two, attained at $S=E$; the empty choice gives three and is not minimizing.

32.7 Representability over finite fields

Optional extension; not required to complete the chapter foundation. A representation certifies dependence by linear algebra over a specified field. The same array of numbers can describe different dependence relations after reduction modulo a prime.

A matroid is $\mathbb F_q$-representable if a matrix over that field has exactly its independent column subsets. Row operations and multiplication of individual columns by nonzero scalars preserve the represented matroid. A zero column represents a loop, and proportional nonzero columns form a parallel pair. A binary matroid is representable over $\mathbb F_2$.

Solved obstruction. The simple rank-two matroid $U_{2,4}$ cannot be binary. A rank-two representation can be reduced to two independent rows without changing column dependence. There are only three nonzero vectors in $\mathbb F_2^2$: $(1,0),(0,1),(1,1)$. Four nonloop columns must repeat a direction, creating a dependent pair, contrary to the independence of every pair in $U_{2,4}$.

More generally, a two-dimensional space over $\mathbb F_q$ has $(q^2-1)/(q-1)=q+1$ one-dimensional subspaces. Thus $U_{2,n}$, for $n\geq2$, is $\mathbb F_q$-representable exactly when $n\leq q+1$: necessity counts distinct nonzero directions; sufficiency chooses that many different directions, so every pair is independent and every triple dependent.

Over $\mathbb F_3$, the four columns

$$ V=\begin{pmatrix}1&0&1&1\\0&1&1&2\end{pmatrix} $$

represent $U_{2,4}$. In column order $a,b,c,d$, the six pair determinants $ab,ac,ad,bc,bd,cd$ are $1,1,2,2,2,1$ modulo three, all nonzero. This proves the claim exactly; real-valued numerical rank tests would not be an acceptable finite-field check.

A kernel-basis matrix is

$$ W=\begin{pmatrix}2&2&1&0\\2&1&0&1\end{pmatrix}\quad\text{over }\mathbb F_3. $$

Direct multiplication gives $VW^{\mathsf T}=0$, and its rows are independent. Its four column directions are also distinct, so it represents the same $U_{2,4}$, illustrating self-duality. The displayed matrix $V$ over $\mathbb R$ also represents $U_{2,4}$, but finite-field representations generally need not transfer to characteristic zero.

Exercise. Reduce $V$ modulo two and identify the defect. Hint: Its fourth column becomes $(1,0)$. Solution: Columns $a,d$ become parallel, so $\{a,d\}$ is dependent. This proves that this particular reduction fails; the direction-count argument above is what rules out every possible binary representation.

32.8 Matroid minors and structural theory

Optional extension; not required to complete the chapter foundation. Deletion removes elements from consideration; contraction treats their available rank as already used. Minors expose smaller obstructions while preserving many structural classes.

For $X\subseteq E$, deletion $M\setminus X$ restricts independence to $E\setminus X$, so $r_{M\setminus X}(S)=r_M(S)$. Contraction has rank

$$ r_{M/X}(S)=r_M(S\cup X)-r_M(X),\qquad S\subseteq E\setminus X. $$

Equivalently $M/X=(M^{\ast}\setminus X)^{\ast}$. For a nonloop element $e$, a set $I$ is independent in $M/e$ exactly when $I\cup\{e\}$ is independent in $M$. That simple description needs adjustment for a loop: contracting a loop equals deleting it. A minor is obtained by successive deletions and contractions; operations on disjoint deleted and contracted sets commute.

In a linear representation, delete columns for deletion. For contraction, pass to the quotient of the column space by the span of the contracted columns. This proves that representability over a fixed field is minor-closed. Graphic minors correspond to graph edge deletion and contraction, retaining any resulting loops and parallel edges; those features must not be silently discarded.

Solved example. Delete $a$ from $U_{2,4}$ to obtain $U_{2,3}$, binary via the three distinct nonzero directions of $\mathbb F_2^2$. Contract $a$ to obtain $U_{1,3}$, binary via a row of three ones. Every smaller proper minor is a minor of one of these two, hence binary. Therefore $U_{2,4}$ is an excluded minor for binary representability: it is not binary, but every proper minor is. Any matroid containing it as a minor is nonbinary. This argument proves a concrete obstruction; a complete characterization of a representability class is a stronger structural theorem.

Structural theory organizes classes using excluded minors and decomposition operations. Finding one obstruction is a sufficient certificate of nonmembership. Failing to find that obstruction is not generally a certificate of membership unless a complete excluded-minor theorem has been established. The distinction matters when interpreting finite searches.

Exercise. Delete and contract the bridge $d$ in the triangle-plus-bridge matroid. Hint: It is a coloop. Solution: Both operations leave $U_{2,3}$ on $a,b,c$, although their general definitions differ. Its primal rank drops from three to two in both cases. In the dual, $d$ is a loop, so contraction and deletion again agree. This checks the dual deletion/contraction identity in a boundary case.

32.9 Matroid polytopes and the Tutte polynomial

Optional extension; not required to complete the chapter foundation. Section 36.1 is recommended later background for convexity and polyhedral optimization, not an entry requirement. The bridge is simple: a polytope is the convex hull of finitely many vectors, and maximizing a linear function over it has an optimum at a vertex. For the full matroid-polytope treatment, see Edmonds' primary polyhedral paper, reprinted here.

The basis polytope is $P(M)=\operatorname{conv}\{\mathbf1_B:B\in\mathcal B(M)\}$. Its exact inequality description is

$$ P(M)=\{x\in\mathbb R_{\geq0}^E:x(E)=r(E),\ x(S)\leq r(S)\text{ for every }S\subseteq E\}, $$

where $x(S)=\sum_{e\in S}x_e$. Basis indicators clearly satisfy the inequalities. The converse and integrality are the matroid-polytope theorem; their full proof is omitted. Greedy's prefix-rank proof shows directly how linear optimization over its basis vertices exploits the same inequalities.

Solved example. For $U_{2,4}$, the polytope is the hypersimplex $\{x\in[0,1]^4:\sum_i x_i=2\}$, with six pair-indicator vertices. To prove this description without the general theorem, observe that a feasible point with a fractional coordinate must have at least two fractional coordinates. Moving a small amount from one to the other preserves the sum and box constraints in both directions, so that point cannot be a vertex. Every vertex is therefore a zero-one vector with two ones. The point $(1/2,1/2,1/2,1/2)$ is feasible but is not a basis; it is an average of basis indicators.

The Tutte polynomial records ranks of all subsets:

$$ T_M(x,y)=\sum_{S\subseteq E}(x-1)^{r(E)-r(S)}(y-1)^{\lvert S\rvert-r(S)}. $$

For an element that is neither a loop nor a coloop, $T_M=T_{M\setminus e}+T_{M/e}$. A loop contributes a factor $y$ and a coloop a factor $x$; the empty matroid has polynomial one. These formulas follow by splitting subsets according to whether they contain $e$, using the appropriate rank changes. Duality gives $T_{M^{\ast}}(x,y)=T_M(y,x)$ by complementing subsets and substituting the dual rank formula.

For $U_{2,4}$, grouping by subset size gives

$$ T=(x-1)^2+4(x-1)+6+4(y-1)+(y-1)^2 =x^2+2x+2y+y^2. $$

Thus $T(1,1)=6$ counts bases, $T(2,1)=11$ counts independent sets, and $T(1,2)=11$ counts spanning sets. The symmetry in $x,y$ agrees with self-duality. For a loopless matroid, $\chi_M(t)=(-1)^{r(E)}T_M(1-t,0)$ is its characteristic polynomial; here it is $t^2-4t+3$.

Exercise. Find the Tutte polynomial of the triangle-plus-bridge matroid. Hint: The triangle has polynomial $x^2+x+y$, and the bridge is a coloop. Solution: It is $x(x^2+x+y)$. Evaluation at $(1,1)$ gives three bases, while dual variable exchange gives $y(y^2+y+x)$, consistent with the bridge becoming a loop.

32.10 Oriented matroids and Lorentzian polynomial connections

Optional research specialization; not required to complete the chapter foundation. Sections 44.8 and 44.9 are recommended later background for signed geometry and log-concavity; they are not entry requirements. The bridge below supplies signs of real linear forms and Hessians of homogeneous polynomials. Full treatments are linked to primary literature. These are two distinct enrichments of matroid theory: orientation adds sign information, while the Lorentzian theorem applies even to matroids without a real realization.

For real columns $v_e\in\mathbb R^r$, a covector records the signs of $u\cdot v_e$ as $u$ ranges over $\mathbb R^r$. Abstractly an oriented matroid can be specified by a family $\mathcal L\subseteq\{-,0,+\}^E$. Define composition by $(X\circ Y)_e=X_e$ if $X_e\neq0$, and $Y_e$ otherwise; define the separation set $S(X,Y)=\{e:X_e=-Y_e\neq0\}$. The covector axioms require the zero sign vector, closure under negation and composition, and elimination: for every $e\in S(X,Y)$ there is $Z\in\mathcal L$ with $Z_e=0$ and $Z_f=(X\circ Y)_f$ for every $f\notin S(X,Y)$.

Real linear forms satisfy these axioms: composition comes from $u+\varepsilon v$ for sufficiently small positive $\varepsilon$; elimination uses a positive linear combination making the selected opposite-sign coordinate vanish. Not all oriented matroids are realizable by real columns. For a primary treatment using these axioms, see Novik–Postnikov–Sturmfels, §2. The existence and geometry of nonrealizable examples are omitted prerequisites.

Solved signed example. Use the columns of $V$ from 32.7 over $\mathbb R$. For $u=(1,-1)$ their signs are $X=(+,-,0,-)$; for $v=(1,1)$ they are $Y=(+,+,+,+)$. The separation set is $\{b,d\}$. To eliminate $b$, take $u+v=(2,0)$, obtaining $Z=(+,0,+,+)$. Outside the separation set, coordinates $a,c$ agree with $X\circ Y$, as required. Also the real minimal dependence $a+b-c=0$ has signed circuit $(+,+,-,0)$, together with its opposite. The unsigned support remembers the ordinary circuit; the signs remember its geometric direction. A finite field such as $\mathbb F_3$ has no compatible real ordering, so one cannot assign these signs just by treating residues as positive or negative integers.

For a rank-$r$ matroid define its homogeneous, multiaffine basis-generating polynomial

$$ f_M(z)=\sum_{B\in\mathcal B(M)}\prod_{e\in B}z_e. $$

For degree at least two, a nonnegative homogeneous polynomial is Lorentzian exactly when its exponent support is $\mathrm M$-convex and every derivative of total order degree minus two has a Hessian with at most one positive eigenvalue. Here $\mathrm M$-convex means that for support vectors $\alpha,\beta$ and $i$ with $\alpha_i\gt\beta_i$, some $j$ with $\alpha_j\lt\beta_j$ allows both exchanged vectors $\alpha-e_i+e_j$ and $\beta-e_j+e_i$ to remain in the support. For zero-one basis indicators this is symmetric basis exchange, a theorem following from matroid axioms. Nonnegative constants and linear polynomials are the low-degree cases.

Established theorem. Every matroid's $f_M$ is Lorentzian. The characterization and this matroid theorem are proved in Brändén–Huh. Their general derivative and discrete-convexity arguments are omitted; checking one Hessian at one point would not prove the higher-degree property. Arbitrarily reweighting individual bases is not covered by the displayed unweighted theorem.

For $U_{2,4}$ the polynomial is the sum of all six products $z_i z_j$, $i\lt j$. Its support is all pair indicators, which satisfy symmetric exchange directly. Its constant Hessian is $J_4-I_4$, with eigenvalues $3,-1,-1,-1$. Because degree is two, this exact Hessian and the support check prove the Lorentzian property completely for this example.

Historical log-concavity conjectures now have established solutions: Adiprasito–Huh–Katz prove log-concavity of absolute characteristic-polynomial coefficients for arbitrary matroids; the strongest Mason inequality, including binomial normalization of independent-set counts, is proved by the Lorentzian framework above. These results are not being presented as open. Chow rings, Hodge–Riemann relations, and the general homogenized polynomial argument are omitted prerequisites. No unverified current conjecture is needed for the investigation.

Exercise. For $U_{2,4}$, compare the characteristic coefficient sequence and independent-set count sequence. Hint: The counts are $1,4,6,0,0$. Solution: The absolute characteristic coefficients are $1,4,3$, with $4^2\geq1\cdot3$. The normalized independent counts $I_k/\binom4k$ are $1,1,1,0,0$; they are log-concave with no internal zeros. This verifies a small instance, not the general theorems. Its orientation supplies extra signed data, while its Lorentzian property follows from the unsigned matroid alone.

Verify matroid axioms and investigate a dual or representability obstruction

The investigation starts from a complete list of feasible subsets and ends with a certificate whose scope is explicit. Use exact finite sets and finite-field arithmetic; optional signed and polynomial explorations connect these elementary checks to the research extension.

Worked solutions. There are $1+4+6=11$ independent sets: the empty set, four singletons, and six pairs. Heredity holds because subsets of sets of size at most two have size at most two. If $\lvert I\rvert\lt\lvert J\rvert\leq2$, then $J\setminus I$ is nonempty and any of its elements augments $I$. All pairs are bases, and the circuits are $abc,abd,acd,bcd$. Complementation sends each pair to another pair, so the dual is exactly $U_{2,4}$.

The weighted trace accepts $a$ of weight eight, accepts $b$ of weight six, rejects $c$ because the triple would be dependent, and likewise rejects $d$. The optimum weight is fourteen. In the comparison system, greedy accepts $a$ of weight three, rejects both remaining elements, and loses to $bc$ of weight four. The pair $I=a,J=bc$ is the exact failed augmentation witness.

The pair determinant list in 32.7 verifies all six bases over $\mathbb F_3$; nonzero columns verify the singletons, and a two-row matrix has no independent triple. Thus the representation matches every subset, not only the bases. Over $\mathbb F_2$, four nonzero rank-two column directions cannot be distinct because only three exist. If a proposed binary representation has more rows, restrict coordinates to its two-dimensional column span; the same counting obstruction still applies.

The exhaustive rank table groups as follows:

It yields $T=x^2+2x+2y+y^2$, with six bases and eleven independent sets. For the dual matrix, $VW^{\mathsf T}=0$ over $\mathbb F_3$, and every pair of columns of $W$ is independent. The dual rank formula also reduces to $r^{\ast}(S)=\min(2,\lvert S\rvert)$, supplying an independent combinatorial check.

For the optional signed example, $u=(1,-1)$ and $v=(1,1)$ give the covectors and elimination calculated in 32.10. The quadratic polynomial has six monomials and Hessian $J_4-I_4$. Its one positive eigenvalue and three negative ones verify the analytic certificate, while the pair-indicator support verifies discrete exchange. These two checks explain the connection from the original independence axioms to Lorentzian structure. They also show why orientability and Lorentzianity are different claims: real signs were obtained from a real representation, whereas the polynomial theorem uses matroid exchange without that assumption. For $U_{2,5}$, the direction criterion excludes $\mathbb F_2$ and $\mathbb F_3$ and allows $\mathbb F_4$.

An application is selecting a minimum-cost cycle-free network connecting all terminals. Its feasible edge sets form a graphic matroid, so Kruskal's greedy basis algorithm has the exchange justification proved here. If an additional independent resource-capacity constraint is imposed by a partition matroid, the feasible family becomes a matroid intersection; the one-matroid greedy guarantee no longer automatically applies. The matching example supplies a concrete failure and an exchange-path repair. Matroid language therefore distinguishes when a local choice is provably optimal, when another algorithm is required, and when a finite obstruction rules out a proposed linear model.