拟阵对偶

原拟阵选择一组足够独立的元素作为基，对偶记录哪些元素可以同时留下不用。对偶独立集 $I^{\ast }$ 是某个补基的子集，这等价于原侧的 $E\setminus I^{\ast }$ 仍含有一组基。因此，“对偶独立”对应“原侧剩余元素足够生成”，并不是把原独立性逐集合取反。

对任意 $X$，其对偶秩衡量最多能从 $X$ 中舍弃多少元素，同时让剩余底集仍生成原拟阵。外部 $E\setminus X$ 已提供 $r(E\setminus X)$ 份秩，还必须从 $X$ 留下 $r(E)-r(E\setminus X)$ 份，这正好解释式 (2)。

同一四列矩阵的补基 ​

沿用秩与闭包页理路拟阵的秩与闭包Matroid rank · Matroid closure · Matroid flat证明有限拟阵秩的子模性及秩公理的逆向重建，由此推出闭包交换，并用同一个四列矩阵计算秩、平坦与依赖证书。在 $\mathbb{Q}$ 上的矩阵

原秩为二，全部原基与补基为：

因此对偶的所有二元集都是基，唯独 $ab$ 除外。原侧的平行对是 $cd$，对偶侧的平行对为 $ab$；取对偶并非保留每个子集的秩。

用式 (2) 核对，

用正交核实际构造对偶表示 ​

解 $Az=0$，可写

因此核的一组基作为行组成

仍按相同次序标记列 $a,b,c,d$。$A^{\ast }$ 的前两列相等且非零，后两列为标准基，直接算得其基恰为上表右列。这是一个完整矩阵证书，而不仅是抽象补集记号。

其回路为 $ab,acd,bcd$，故它们是原拟阵的余圈。原拟阵的回路则为 $cd,abc,abd$。这两个列表可以通过逐子集检验线性相关并排除更小相关子集得到。

图、均匀拟阵与权重 ​

均匀拟阵满足 $U_{r,n}^{\ast }=U_{n-r,n}$，因为任意 $r$ 元基的补集恰为任意 $(n-r)$ 元集。

若 $G$ 是连通平面图，在固定平面嵌入下，$M(G{)}^{\ast }$ 是平面对偶图 $G^{\ast }$ 的图拟阵。平面三角形的生成树含两条边，补集只有一条；对偶图为两个顶点间的三条平行边，任一单边正是生成树。原图的桥变为对偶自环，原图的圈对应对偶的极小割。此平面图解释需要嵌入，抽象拟阵对偶本身不需要；非平面图的对偶拟阵也未必是图拟阵。

对给定权重，总有 $w(E\setminus B)=w(E)-w(B)$。因此最大权原基对应同一权重下的最小权对偶基。四列贪心例理路拟阵贪心定理Matroid greedy theorem完整证明有限独立系统的贪心双向刻画，区分任意实权重的基优化与非负权重的独立集优化，并在四列矩阵上核对每次接受、拒绝及最优值。中 $w(E)=18$，原最优基 $ac$ 权重 $10$，补基 $bd$ 的权重为 $8$，且是全部对偶基中的最小值。

验证候选对偶秩的全部公理 ​

令

它整数值且 $q(\varnothing )=0$。对 $e\notin X$，记 $Y=E\setminus X$，由原秩的单元素增量为 $0$ 或 $1$，

从空集逐元素加入，便得 $0\le q(X)\le |X|$ 及单调性。

再用集合大小的容斥等式，以及补集把并、交互换，

最后一步是原秩的子模性。由秩公理的逆向重建理路拟阵的秩与闭包Matroid rank · Matroid closure · Matroid flat证明有限拟阵秩的子模性及秩公理的逆向重建，由此推出闭包交换，并用同一个四列矩阵计算秩、平坦与依赖证书。，$q$ 确实是某个拟阵的秩。

现在识别它的基。$B^{\ast }$ 为这个新拟阵的基，当且仅当

第一等式等价于 $r(E\setminus B^{\ast })=r(E)$；第二等式等价于 $|E\setminus B^{\ast }|=r(E)$。两者合起来说明 $E\setminus B^{\ast }$ 是一个大小等于秩的生成集，因而是原基。反向也立即成立。这证明了式 (1)、(2) 以及对偶的存在性。

从补基直接读出式 (2) 的数值 ​

式 (2) 也能通过一个达到下界的选择看见。对任何原基 $B$，

因此

在 $E\setminus X$ 中先选一组基，再扩充为整个 $E$ 的基，便使等号成立：后续无法再加入外部元素，否则外部原先那组基并非极大。于是

第一等式使用“任意对偶独立集可扩充为对偶基”，其正确性已经由上面的构造证明。

正交核为什么对每个子集都给出对偶秩 ​

对一般域 $F$ 上的满行秩 $r\times n$ 矩阵 $A$，令 $B$ 的行是一组 $\ker A$ 的基，故 $B$ 有 $n-r$ 行。对标号子集 $X$，把核向量投影到 $X$ 坐标，记投影为 ${\pi }_X$。因为 $B$ 的行张成整个核，

投影核是在 $X$ 上坐标为零的 $\ker A$ 元素；删去这些零坐标后，它自然同构于外部列矩阵 $A_{E\setminus X}$ 的零空间，维数为

由秩—零化度定理理路秩–零化度定理Rank–nullity theorem有限维线性映射的定义域维数等于核维数与像维数之和。，

这正是式 (2)，因此核矩阵在所有子集上都表示对偶拟阵。这里的“正交”是代数双线性配对 $Az=0$，无须实内积或复共轭；式 (3) 是该一般论证在四列例子中的实际结果。这也说明可表示性理路可表示拟阵Representable matroid · Linear matroid能由某个域上矩阵列向量的线性无关关系实现的拟阵。在同一域上的对偶下保持。

删除、收缩与 loop 的交换 ​

删除 $e$ 只移去该标号，所以对 $X\subseteq E-e$，

若 $e$ 非 loop，收缩的独立集是满足 $I+e$ 在 $M$ 中独立的 $I\subseteq E-e$。遗传性直接成立；对 $I+e,J+e$ 应用原增广公理，增加的元素在 $J\setminus I$ 中，故收缩也满足增广公理。若 $e$ 为 loop，则定义收缩等于删除。两种情况的秩统一为

对非 loop，从独立单元素 $e$ 扩充到 $X+e$ 内的基，删去 $e$ 后得到达到右侧的收缩独立集；反方向由把 $e$ 加回来得到上界。对 loop，加入它不增秩，式 (7) 同样成立。

将式 (7) 代入对偶秩公式，得

故 $(M/e{)}^{\ast }=M^{\ast }\setminus e$；取两次对偶，也得 $(M\setminus e{)}^{\ast }=M^{\ast }/e$。这里 $r_M(e)$ 简写 $r_M(\{e\})$。

由 $r^{\ast }(\{e\})=1-r(E)+r(E-e)$，原侧的 coloop，即每个基都必须包含的元素，恰好在对偶侧变为 loop；再取对偶就得到反向对应。回路理路拟阵回路Matroid circuit · Circuit of a matroid拟阵中按包含关系极小的依赖集，是独立性首次失效的局部证书。、余圈及删缩关系由此使用同一套秩公式连接起来。