全幺模矩阵与整数顶点

一个顶点由若干线性无关的紧约束钉住。抽出 $n$ 条独立紧约束，得到 $Bx=b_B$。Cramer 法则给

其中 $B_j$ 是把第 $j$ 列换成整数右端的矩阵。分子为整数；TU 加上 $B$ 可逆，迫使分母只有 $1$ 或 $-1$，于是每个坐标都是整数。

这个证明不能只检查原矩阵整个行列式。LP 顶点会选择不同约束作为基，真正需要的是所有可能基的分母都受控。即使原矩阵恰好是方阵且行列式为一，它内部的小子式仍可能产生分数顶点。

若可行域含直线而没有顶点，可以用整数盒子截断来完成一般证明。任取 $x\in P$，选足够大的整数 $M$ 使其在 $[-M,M{]}^n$ 中；加入这些单位行仍为 TU，截断后是顶点全整数的有界多胞形，所以 $x$ 是其中整数点的凸组合。让盒子覆盖任意 $x$，便得到 $P=P_I$，没有把无顶点情形遗漏掉。

网络关联矩阵的直接证明 ​

对一个有限有向图公理库有向图Directed graph · Digraph以顶点有序对为弧、能够保留连接方向的有限简单图结构。，每条弧对应一列：尾顶点行贡献 $-1$，头顶点行贡献 $+1$，其他行记零。若允许自环，两项在同一行相抵，得到零列；平行弧保留各自的列。取弧 $0\to 1,1\to 2,2\to 3,3\to 0,0\to 2$，矩阵为

任取一个方形子矩阵 $B$，对阶数归纳。若某列全零，行列式为零；若某列只剩一个非零，它必为 $\pm 1$，沿该列展开，降到小一阶。剩下的情况是每列都有两个非零，且一正一负，于是全部行相加为零，行线性相关，行列式仍为零。三个分支覆盖所有子矩阵，TU 得证。

对二分图的无向点边关联矩阵，每列原来有两个 $+1$。把某一侧顶点对应的所有行乘 $-1$，就变成上述有向关联结构。因此二分图关联矩阵也 TU，进而解释匹配度约束的整数性。

奇圈在哪里制造分母 ​

无向三角形的点边关联矩阵可写成

方程 $Bx=\mathbf{1}$ 的解是每条边 $1/2$。这也是非负度约束 $Bx\le \mathbf{1}$ 的一个分数顶点：三条紧约束独立，解被唯一钉住。奇圈使行符号无法同时把每条边改成一正一负，分母二正是这个障碍的代数表现。

另一个较小的提醒是

它的整个行列式为 $1$，是方阵意义下的幺模矩阵，却不是 TU，因为元素 $2$ 已经是非法的 $1\times 1$ 子式。“幺模”和“全幺模”不能省略一个字混用。

在LP公理库线性规划Linear programming · LP在线性等式和不等式约束下优化线性目标函数的问题。中，TU 是关于矩阵的统一保证：保持这个矩阵及合法单位界结构，任意整数右端都不会制造分数顶点。反过来，某个具体右端下得到整数多面体，并不证明矩阵 TU；分数危险可能只在其他右端出现。

整数右端同样不可省略。单行矩阵 $A=(1)$ 已经 TU，但 $x\le 1/2$ 的端点仍是分数。也不要随意把某行乘二以后继续宣称矩阵 TU：可行域可能没变，矩阵证书却变了。

网络流、带整数容量与供需的流平衡，以及二分图匹配多胞形公理库二分图匹配多胞形Bipartite matching polytope证明二分图的非负边变量与顶点度上界已给出匹配凸包，并用交替扰动区分分数可行点和分数顶点。都能用这套分母控制解释整数性。不过通用检查“所有子式”有指数多候选；定义本身不是一个高效识别算法。对网络矩阵使用上面的结构归纳，比穷举子式更适合证明任意规模输入。

下载核验只在一个四行五列实例上逐一检查全部方形子式，并检查三角形的行列式二；这些计算帮助核对例子，普遍结论来自归纳证明。一般 TU 识别还有更深的结构算法，不应从小矩阵枚举的运行时间外推。