全幺模矩阵

全幺模矩阵（totally unimodular matrix，TU矩阵）是每个方形子矩阵的行列式都属于 $\{0,1,-1\}$ 的矩阵。它的重要性来自一个结构性结论：在适当的线性约束形式下，如果系数矩阵全幺模、右端数据为整数，线性规划的顶点自动是整数。此时某些看似必须用整数规划处理的网络模型，可以直接从线性规划得到整数最优解。

定义检查的不只是整个矩阵的行列式，而是任意大小、任意选取行与列形成的方形子矩阵，包括一阶子矩阵。因此全幺模矩阵的每个元素必为零或正负一；反过来，仅有这种元素取值远远不够。

有向网络的关联矩阵

三座节点有三条弧 $1\to 2$、$2\to 3$、$1\to 3$。规定弧离开节点记负一、进入节点记正一，按此顺序写列，得到节点—弧关联矩阵 $$B=\left(\begin{array}{ccc}-1& 0& -1\\ 1& -1& 0\\ 0& 1& 1\end{array}\right).$$ 它的每一列至多有一个正一、一个负一。下面证明任何无自环有向图的这种关联矩阵都全幺模，而非只检查这个三阶例子。

取其任意 $k\times k$ 子矩阵 $C$，对阶数归纳。一阶结论明显。若某列全零，行列式为零；若某列恰有一个非零元素，沿该列展开，行列式等于正负一个低一阶子式，归纳得到零或正负一。剩下的情形是每列都有两个非零元素；它们必是一正一负，故各行之和为零向量，行线性相关，行列式为零。三种情形已覆盖所有方形子矩阵，证明完毕。

顶点整性的证明

设 $A$ 是 $m\times n$ 全幺模矩阵，$b\in {\mathbb{Z}}^m$，考虑 $$P=\{x\in {ℝ}^n:x\ge 0,Ax\le b\}.$$ 在 $A$ 下方添加 $-I$ 得矩阵 $\tilde{A}$，它仍全幺模：任何含单位行的子式可沿该行展开，直到归结为 $A$ 的子式或零。

若 $x^{\ast }$ 是 $P$ 的顶点，其活动约束中必能选出 $n$ 个线性独立的约束。否则存在非零方向同时正交于所有活动行，沿此方向足够小的正、负移动仍可行，便能把该点写成两个不同可行点的中点，与顶点定义矛盾。将所选活动行组成方阵 $C$，相应整数右端组成 $d$，有 $$C{x}^{\ast }=d,detC\in \{1,-1\}.$$ 克拉默法则给出每个坐标为整数行列式除以正负一，因而全为整数。这证明了所有顶点的整性。特别地，非空有界的 $P$ 上任意线性目标都有整数顶点最优解；不能把结论说成每个最优解都为整数，因为两整数最优顶点之间也可能有分数最优点。

等式约束可拆成两个不等式，整数量的上下界也可加单位行；相应的正负行复制与单位行扩充保持全幺模。故同一原理适用于具有整数供需和整数容量的最小费用网络流模型。

一次完整网络流计算

仍用上面三条弧，从节点一向节点三输送两件货，节点二只负责中转。设流量为 $f_{12},f_{23},f_{13}\ge 0$，弧上单位费用分别为一、一、三元，没有其他容量上限。平衡式为 $Bf=(-2,0,2{)}^T$。令 $t=f_{12}$，中转与供需守恒给出 $$\begin{array}{cc}{f}_{23}& =t,f_{13}=2-t,0\le t\le 2,\\ c^{T}f& =t+t+3(2-t)=6-t.\end{array}$$ 所以 $t=2$，最优流为 $(2,2,0)$，费用四元。即使求解时允许流量为实数，这个最优顶点也是整数；代入每个节点的流入流出可以逐一核对守恒。

弧标为“流量；单位费用”。绿色两段各运两件，金色直达弧最优流量为零。这里画的是网络连接关系，不代表地理距离。

非全幺模与非整数右端

矩阵 $$H=\left(\begin{array}{ccc}1& 1& 0\\ 1& 0& 1\\ 0& 1& 1\end{array}\right)$$ 只含零一，但 $detH=-2$，所以不是全幺模。多面体 $\{x\ge 0:Hx\le \mathrm{𝟏}\}$ 有顶点 $(1/2,1/2,1/2)$：三个不等式均取等，系数矩阵可逆，唯一确定该分数点。目标最大化坐标和时，这个点值为二分之三；整数可行点最多只有一个一，最优值为一。

变式。 若前述运输量改为半件，关联矩阵仍全幺模，但右端变为 $(-1/2,0,1/2{)}^T$，最优流为 $(1/2,1/2,0)$，费用一元。此时没有违反定理，因为整数右端这一条件已经不满足。模型中货物是否可分，也必须由实际任务决定。

小矩阵的精确检查

以下代码枚举全部方形子矩阵，用有理数消元计算行列式。若失败，返回一个具体反例子式；若通过，返回空证据。它适合小例验证，不是大规模全幺模识别算法。

Python 3

from fractions import Fraction
from itertools import combinations

def determinant(a):
    b = [list(map(Fraction,row)) for row in a]
    n, value = len(b), Fraction(1)
    for k in range(n):
        pivot = next((i for i in range(k,n) if b[i][k]), None)
        if pivot is None:
            return Fraction(0)
        if pivot != k:
            b[k], b[pivot] = b[pivot], b[k]
            value = -value
        v = b[k][k]
        value *= v
        for i in range(k+1,n):
            factor = b[i][k]/v
            for j in range(k+1,n):
                b[i][j] -= factor*b[k][j]
            b[i][k] = 0
    return value

def check_tu(matrix):
    a = tuple(tuple(row) for row in matrix)
    n = len(a[0]) if a else 0
    if any(len(row) != n for row in a):
        raise ValueError("rectangular matrix required")
    if any(type(x) is not int for row in a for x in row):
        raise ValueError("integer entries required")
    for k in range(1,min(len(a),n)+1):
        for rows in combinations(range(len(a)),k):
            for cols in combinations(range(n),k):
                d = determinant([[a[i][j] for j in cols] for i in rows])
                if d not in (-1,0,1):
                    return False, (rows,cols,d)
    return True, None

print(check_tu([[-1,0,-1],[1,-1,0],[0,1,1]]))
print(check_tu([[1,1,0],[1,0,1],[0,1,1]]))
# (True, None)
# (False, ((0, 1, 2), (0, 1, 2), Fraction(-2, 1)))

消元的每次行变换不改变行列式或显式记录其符号，因此乘积给出精确结果；枚举覆盖了定义要求的全部子式。对 $m\times n$ 矩阵，算术操作数上界可写为 $$O\left(\sum _{k=1}^{min(m,n)}(\genfrac{}{}{0ex}{}{m}{k})(\genfrac{}{}{0ex}{}{n}{k})k^3\right).$$ 额外工作空间为 $O(mn+min(m,n{)}^2)$，有理数位复杂度另计。空矩阵按没有非空反例子式处理。大矩阵应利用网络结构或专门的识别方法，而非穷举定义。