拟阵的秩与闭包

形式陈述 ​

设 $M=(E,\mathcal{I})$ 是有限拟阵公理库拟阵Matroid用遗传性和交换公理抽象线性无关集与森林结构的组合系统。。子集 $X\subseteq E$ 的秩定义为

$$r_M(X)=max\{|I|:I\subseteq X,I\in \mathcal{I}\}.$$

秩函数满足

$$0\le r(X)\le |X|,X\subseteq Y\Rightarrow r(X)\le r(Y),$$

以及次模不等式

$$r(X)+r(Y)\ge r(X\cup Y)+r(X\cap Y).$$

反过来，有限集上的整数值函数只要满足这三类秩公理，就可由 $\mathcal{I}=\{I:r(I)=|I|\}$ 恢复唯一拟阵。$X$ 的闭包定义为

$${\mathrm{cl}}_M(X)=\{e\in E:r(X\cup \{e\})=r(X)\}.$$

它满足广延性 $X\subseteq \mathrm{cl}(X)$、单调性和幂等性。满足 $\mathrm{cl}(F)=F$ 的集合称为平坦。若 $r(\{e\})=0$，则 $e$ 是 loop；两个不同非 loop 元素 $e,f$ 若 $r(\{e,f\})=1$，则称它们平行。

直觉 ​

秩不数集合里有多少元素，而数其中能保留多少份互不冗余的信息。闭包则收集所有已经被 $X$ 强制决定的元素：加入它们不会再增加一份独立信息。这个视角把线性张成从向量空间抽离出来，只保留“加入后维数是否增长”的判断。

平坦是信息已经封闭的集合。若一个集合还漏掉某个不增秩元素，它就没有完整表示自己所决定的内容；补齐全部这类元素后得到闭包。秩与闭包因此是同一依赖结构的数值语言和算子语言。

例子与边界 ​

在线性拟阵中，$E$ 是一族向量，$r(X)$ 是 $X$ 所张成空间的维数，而 $\mathrm{cl}(X)$ 是 $E$ 中落在 $\mathrm{span}(X)$ 内的全部向量。零向量是 loop，互为非零标量倍数的两个向量是平行元素。

在图拟阵中，$X$ 是图的一组边，

$$r(X)=|V|-c(V,X),$$

其中 $c(V,X)$ 是生成子图 $(V,X)$ 的连通分量数。$\mathrm{cl}(X)$ 恰由那些端点已经在 $(V,X)$ 同一连通分量中的边组成，因为加入这种边只会形成圈而不会减少分量数。

拟阵闭包不是拓扑闭包。以均匀拟阵 $U_{2,3}$ 为例，两个不同单点各自都是闭集，但它们的并含两个元素、秩已达到 $2$，其闭包是整个三元素底集；因此有限并不必保持闭。秩也不是普通集合大小：平行元素可以增加元素数却不增加秩。

推论与应用 ​

集合 $I$ 独立当且仅当 $r(I)=|I|$；$B$ 是基当且仅当它独立且 $r(B)=r(E)$。闭包还满足交换性质：若 $y\notin \mathrm{cl}(X)$ 且 $y\in \mathrm{cl}(X\cup \{x\})$，则 $x\in \mathrm{cl}(X\cup \{y\})$。这正是线性代数中交换引理的组合版本。

秩的子模性公理库子模函数Submodular function定义在有限集合幂集上的边际收益递减函数。为拟阵优化提供数值工具。拟阵贪心定理公理库拟阵贪心定理Matroid greedy theorem有限独立系统中，按非增权重加入可行元素对每个非负权重都产生最大权独立集，当且仅当该系统是拟阵。用独立集语言构造最大权基，拟阵交则用秩刻画两个独立性系统能够共同容纳多大的集合。图拟阵公理库图拟阵Graphic matroid以图边为底集、以无环边集为独立集的拟阵。中，秩公式把森林、连通分量和生成树统一起来；在拟阵对偶公理库拟阵对偶Matroid duality以基的补集为基定义的对偶拟阵构造。中，秩进一步给出对偶秩公式与割结构。

参考资料

• James Oxley, Matroid Theory, 2nd ed., Oxford University Press, 2011, Chapters 1–2.
• Michel X. Goemans, Lecture Notes on Matroid Optimization, MIT, sections on rank functions and closure.