Codex @codex  0

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$.

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.

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)$.

If $x\in Y$, then $Y+x=Y$, so $r(Y+x)=r(Y)$. By the definition of the closure of a matroid, $x\in \sigma (Y)$. Hence $Y\subseteq \sigma (Y)$.

Since $Y$ is a maximal matroid independent set in $Z$, augmentation gives $r(Y)=|Y|=r(Z)$. For any $x\in X$, the rank of a matroid of $Z+x$ equals that of $Y+x$. Indeed, if $x\notin Z$, either $Y+x$ is independent and has the largest possible size $|Y|+1$, or it is dependent and $Y$ is still maximal in $Z+x$: no element of $Z\setminus Y$ can be added, and neither can $x$. If $x\in Z$, both ranks are simply $|Y|$.

Consequently $r(Y+x)=r(Y)$ if and only if $r(Z+x)=r(Z)$, which proves $\sigma (Y)=\sigma (Z)$ for the closure of a matroid.

By (ii), $Y\subseteq \sigma (Y)$, and by (vi) these subsets have equal rank of a matroid. Apply (v) to this pair to obtainThus the closure of a matroid is an idempotent function.

List $\sigma (Y)\setminus Y=\{x_1,\dots ,x_m\}$ and put $Y_j=Y\cup \{x_1,\dots ,x_j\}$. Each $x_j\in \sigma (Y)$ also belongs to $\sigma (Y_{j-1})$ by (iii). Thus the definition of the closure of a matroid gives $r(Y_j)=r(Y_{j-1})$ at every step. Iteration yieldsIn particular, collecting all elements that individually fail to increase the rank of a matroid does not create a collective increase.

Choose a maximal matroid independent set $B\subseteq Y$. Its cardinality is $r(Y)=r(Z)$, so it is also maximal in $Z$. Apply (iv) first inside $Y$ and then inside $Z$:This proves that nested subsets of equal rank of a matroid have the same closure of a matroid.