= Closure of a matroid
{title2=$\operatorname{cl}_M(A)=\{x:r(A\cup\{x\})=r(A)\}$}
= Matroid closure
{synonym}
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>:
$$
A\subseteq\operatorname{cl}_M(A),\qquad
A\subseteq B\Rightarrow\operatorname{cl}_M(A)\subseteq\operatorname{cl}_M(B),\qquad
r(\operatorname{cl}_M(A))=r(A),\qquad
\operatorname{cl}_M(\operatorname{cl}_M(A))=\operatorname{cl}_M(A).
$$
\b[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)\leq r(A+x)-r(A)$. Thus an element in $\operatorname{cl}_M(A)$ also lies in $\operatorname{cl}_M(B)$; the case $x\in B$ is automatic. Add the finitely many elements of $\operatorname{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)\leq 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)\leq r(A+x)\leq r(B)=r(A)$, so both closures contain $x$. Apply this equal-rank result to $A\subseteq\operatorname{cl}_M(A)$ to prove idempotence. In particular, every maximal <matroid independent set> of $B$ has the same <closure of a matroid> as $B$.
Back to article page
