可表示拟阵

形式陈述 ​

设 $M=(E,\mathcal{I})$ 是有限拟阵，$F$ 是域。若存在一个列由 $E$ 标号的 $F$ 上矩阵 $A$，使对每个 $X\subseteq E$ 都有

$$X\in \mathcal{I}⟺\{A_e:e\in X\}\text{ 在 }F\text{ 上线性无关},$$

就称 $M$ 可在 $F$ 上表示，并写 $M=M_F[A]$。若它可在某个域上表示，则称 $M$ 为可表示拟阵。

左乘可逆矩阵，也就是对 $A$ 作可逆行变换，不改变列之间的线性依赖；把任一非零列乘以非零标量同样不改变拟阵。零列对应 loop，互为非零标量倍数的两列对应平行元素。这些操作给出同一拟阵的新表示，但并非所有同一拟阵的矩阵表示都必须由一组此类操作互相得到。

直觉 ​

可表示拟阵只保留一组向量“哪些子集线性无关”的骨架，忘掉坐标值和依赖关系中的具体系数。它把线性无关公理库线性无关Linear independence只有全零系数能产生零向量的向量组。的交换性质带入纯组合环境，同时允许不同向量配置在丢弃坐标后成为同一个拟阵。

域是表示数据的一部分。线性方程中的加法与标量会随域的特征变化，同一组组合依赖可能在一个域中实现、在另一个域中不可能实现。因此“可表示”不能在讨论特定表示性质时省略底域。

例子与边界 ​

给图的边任取方向，以顶点–边有向关联矩阵的列标记边；每列在边的起点为 $-1$、终点为 $1$，其余为 $0$。删去每个连通分量的一行后，该矩阵在任意域上表示图拟阵：一组列线性无关，当且仅当对应边集不含圈。因此图拟阵公理库图拟阵Graphic matroid以图边为底集、以无环边集为独立集的拟阵。是可在每个域上表示的 regular matroid。

Fano 拟阵可由 ${\mathbb{F}}_2^3$ 中七个非零向量作为列表示。每条“直线”上的三列满足 $u+v+w=0$，形成三元素回路。它可在且只能在特征 $2$ 的域上表示；若把同一组合依赖强行放到特征不为 $2$ 的域，相关关系会彼此冲突。这是底域不可省略的标准边界。

并非每个拟阵都可表示，Vámos 拟阵就是不能在任何域上表示的例子。即使一个拟阵可表示，不同表示也可能不具有投影等价性；“行变换和列缩放保持拟阵”是充分的不变操作，不是表示唯一性定理。

推论与应用 ​

矩阵表示把拟阵秩变成列秩，把闭包变成线性张成内的已标号列，把回路变成极小线性相关列集。于是秩与闭包公理库拟阵的秩与闭包Matroid rank · Matroid closure · Matroid flat用最大独立子集的大小定义拟阵秩，并以不增加秩的元素定义闭包与平坦。、回路公理库拟阵回路Matroid circuit · Circuit of a matroid拟阵中按包含关系极小的依赖集，是独立性首次失效的局部证书。都可用线性代数计算，同时仍保留图拟阵等组合例子的统一语言。

可表示性还连接编码理论：生成矩阵或校验矩阵的列依赖决定码的最小距离与删缩结构。对表示矩阵的删列对应拟阵删除，对非 loop 元素的收缩可由基变换后删除相应行列实现。底域特征限制则把组合禁形与线性表示理论联系起来。

参考资料

• James Oxley, Matroid Theory, 2nd ed., Oxford University Press, 2011, Chapters 2 and 6.
• Alexander Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003, Volume B, chapters on matroid representations.