拟阵对偶

把拟阵的每个基取补集,得到对偶拟阵;对偶的基与原拟阵的基互为补集,秩函数有 r*(A)=|A|-r(E)+r(E-A)。

标签 数学 / 拟阵 / 对偶 / 基

定义

设 𝑀=(𝐸,ℐ︀) 是拟阵,ℬ︀(𝑀) 为其基族。定义

ℬ︀∗={𝐸∖𝐵:𝐵∈ℬ︀(𝑀)}.

以 ℬ︀∗ 为基族的拟阵称为 𝑀 的对偶,记作 𝑀∗=(𝐸,ℐ︀∗)。

等价地,𝐼∈ℐ︀∗ 当且仅当 𝐸∖𝐼 包含 𝑀 的一个基;也就是 𝐸∖𝐼 是 𝑀 的生成集。

基本性质

由 拟阵基定理 的基交换可以直接验证:ℬ︀∗ 满足基交换公理,因此确实定义一个拟阵。

对偶的基与原拟阵的基互为补集:

𝐵∗∈ℬ︀(𝑀∗)⇔𝐸∖𝐵∗∈ℬ︀(𝑀).

因此 (𝑀∗)∗=𝑀。

若 𝑟 是 𝑀 的秩函数,𝑟∗ 是 𝑀∗ 的秩函数,则

𝑟∗(𝐴)=|𝐴|−𝑟(𝐸)+𝑟(𝐸∖𝐴).

图拟阵的对偶是余图拟阵:连通图 𝐺 的图拟阵 𝑀(𝐺) 的对偶 𝑀∗(𝐺) 的基,是生成树的补,即余树。详见 拟阵实例。

源码位置