拟阵的秩与闭包

秩只数能保留多少份独立信息；闭包收集已经被这些信息决定的已标号元素。在线性情形，它就是“矩阵的哪些列已落在当前张成空间内”。闭包的底集仍是 $E$，不是把整个向量空间中的点都添加进来。

子模性说明，已有信息越多，新元素还能贡献的秩越少。拟阵比一般子模函数更特殊：每次只增加 $0$ 或 $1$。这种离散增量与交换性质相互约束，最终让秩、独立集与闭包描述同一结构。

四列矩阵贯穿秩、贪心和对偶 ​

在 $\mathbb{Q}$ 上取列标号为 $E=\{a,b,c,d\}$ 的矩阵

这是一个线性表示理路可表示拟阵Representable matroid · Linear matroid能由某个域上矩阵列向量的线性无关关系实现的拟阵。。所有单列均非零，六个二阶行列式依次为

因此全部基为

这里 $ab$ 表示标号子集 $\{a,b\}$，其他简写同理。任意含至少三个元素的集合秩均为二，唯一秩一的二元集是 $cd$。

表列出了全部可能情况。平坦恰为 $\varnothing ,a,b,cd,E$，其中 $cd$ 的两个标号保留为不同元素，不能因向量平行就合并成一个标号。

上方连线表示平坦之间的包含关系，竖直层级为秩；蓝色节点仍是包含两个标号的集合。下方方框单独画基与补基，它们本身不是此例的平坦，不能混入上方的包含图。对偶的具体矩阵与最小权解释见对偶页。

取 $X=ac,Y=bc$，式 (2) 为 $2+2\ge 2+1$，严格不等号来自交集 $c$ 只有秩一。闭包交换则可取 $X=a,x=b,y=c$：$c\notin \mathrm{cl}(a)$，但 $c\in \mathrm{cl}(ab)=E$，于是 $b\in \mathrm{cl}(ac)=E$。

同一矩阵在贪心页理路拟阵贪心定理Matroid greedy theorem完整证明有限独立系统的贪心双向刻画，区分任意实权重的基优化与非负权重的独立集优化，并在四列矩阵上核对每次接受、拒绝及最优值。配上权重 $(4,3,6,5)$，再在对偶页理路拟阵对偶Matroid duality从秩公理证明基的补集确实定义对偶拟阵，推导对偶秩公式，并以四列矩阵及其正交核给出所有子集上的可复算证书。求正交核矩阵。这里明确使用 $\mathbb{Q}$；若把数值原样降到特征二的域，$d$ 会变成零列，依赖结构随之改变。

图拟阵与拓扑闭包的边界 ​

在图拟阵中，若 $X$ 为边集，则

其中 $c(V,X)$ 是生成子图的连通分量数。证明是：每个分量的生成树有“顶点数减一”条边，任何森林又至多有这么多边。加入一条连接不同分量的边会使秩增一；端点已在同一分量的边则位于闭包。

拟阵闭包不是拓扑闭包。均匀拟阵 $U_{2,3}$ 中两个不同单点分别是平坦，其并的秩已达二，闭包却是整个底集。因此平坦不必对有限并封闭。

从独立集增广证明子模性 ​

先在 $X\cap Y$ 中取一组基 $J$，把它扩充为 $X$ 中的基 $B_X$，再扩充为 $X\cup Y$ 中的基 $B$。这些扩充都可逐次应用增广公理完成，得到

不能有 $e\in (B_X\cap Y)\setminus J$，否则 $J+e$ 是 $X\cap Y$ 中更大的独立集；同样不能有 $e\in (B\cap X)\setminus B_X$。因此

从而 $B\cap Y$ 是大小为 $|J|+|B|-|B_X|$ 的独立集。于是

正是式 (2)。式 (1) 则直接来自最大独立子集的定义。

由秩公理重新得到拟阵 ​

现在只假设 $r$ 为满足式 (1)、(2) 的整数值函数。首先 $r(\varnothing )=0$。对 $e\notin S$，把式 (2) 用于 $S$ 与 $\{e\}$，得

故每个单元素增量是 $0$ 或 $1$。子模性还给出边际递减：

按式 (3) 定义独立集，空集独立。若 $J\subseteq I$ 且 $r(I)=|I|$，逐元素应用式 (7) 得

两端相等，强制 $r(J)=|J|$，故遗传性成立。

设 $I,J$ 独立且 $|I|<|J|$。若每个 $e\in J\setminus I$ 都不增加 $r(I)$，式 (8) 说明把这些元素逐个加入以后，每一步仍不增加秩。因此

违反单调性。故至少有一个元素增量为一，使 $I+e$ 独立，增广公理成立。

还要验证所构造拟阵的秩真的等于给定 $r$。任意独立 $I\subseteq S$ 有 $|I|=r(I)\le r(S)$。反之，从空集开始，只要当前独立 $I\subseteq S$ 满足 $r(I)<r(S)$，同样的边际递减论证保证存在 $e\in S\setminus I$ 增加秩。有限次后得到大小为 $r(S)$ 的独立集。两边界相等，完成重建；唯一性来自式 (3)。

闭包为何是幂等且允许交换 ​

广延性由式 (4) 立即成立。若 $X\subseteq Y$ 且 $e\in \mathrm{cl}(X)$，则当 $e\notin Y$ 时，式 (8) 把在 $Y$ 上的增量压到零；当 $e\in Y$ 时结论显然。因此闭包单调。

把 $\mathrm{cl}(X)\setminus X$ 的元素逐个加入，每个在 $X$ 上的增量都为零，式 (8) 保证后续增量也为零，所以

若 $e\notin \mathrm{cl}(X)$，则

故 $e$ 也不属于 $\mathrm{cl}(\mathrm{cl}(X))$。结合广延性，得到幂等性。

最后证明式 (5)。记 $r(X)=k$。其第一条假设给 $r(X+y)=k+1$，第二条给

由单调性及单元素上界，

故全为等号，特别是 $r(X+x+y)=r(X+y)$，这正是 $x\in \mathrm{cl}(X+y)$。

数值语言如何进入优化 ​

集合 $I$ 独立等价于 $r(I)=|I|$；它为基还需 $r(I)=r(E)$。加入元素被拒绝，便可表达为该元素已在当前集合的闭包里。贪心的双向刻画理路拟阵贪心定理Matroid greedy theorem完整证明有限独立系统的贪心双向刻画，区分任意实权重的基优化与非负权重的独立集优化，并在四列矩阵上核对每次接受、拒绝及最优值。利用增广性证明任意权重下的正确性；对偶秩公式理路拟阵对偶Matroid duality从秩公理证明基的补集确实定义对偶拟阵，推导对偶秩公式，并以四列矩阵及其正交核给出所有子集上的可复算证书。则使用本页的逆向重建确认“基取补集”仍形成拟阵。

拟阵交定理理路拟阵交定理Matroid intersection theorem · Edmonds matroid intersection theorem两个有限拟阵的最大共同独立集大小，等于一次底集切分上的两侧秩之和的最小值。把两侧的秩组合成最优性上界。这里的秩公理证明支持那套证书，却不声称两拟阵的共同独立集仍满足单拟阵增广公理。