全单调矩阵与行极小值

全单调性保存的不是数值大小，而是候选之间的胜负方向。在两列之间，越往下走，右边候选可以从落后变成领先；一旦严格领先，就不能重新落后或打平到让最左规则偏向左边。

为什么只看 $2\times 2$ 就足够？若某个子矩阵的上行选了右列 $\ell$、下行却选更左的 $j$，上行最左最小的定义给出 $A_{ij}>A_{i\ell }$。严格蕴含迫使下行也有 $A_{kj}>A_{k\ell }$，下行就不可能选 $j$。反过来，若严格蕴含失败，上行在这两列中选右边，下行因为左边更小或平局而选左边，这个 $2\times 2$ 子矩阵已经是反例。

定义中的“所有子矩阵”听来庞大，二列胜负规则却把它变成局部逻辑。也正因为删列以后仍然成立，递归搜索才有稳定的前提。

原表单调，子表不单调 ​

取

两行最左极小列都是 $0$，所以原表的极小列序列 $(0,0)$ 非降。但删掉第零列后，剩下

上行选右列，下行选左列，次序逆转。严格比较也直接揭示失败：$3>1$ 成立，而下行对应的 $1>3$ 不成立。一个只在原表上抽查极小列是否非降的程序，无法认证全单调性。

全单调也不要求四点和满足 Monge ​

考虑

两行都偏好左列。上行“右列严格更好”的前提不成立，故唯一的 $2\times 2$ 条件成立；任何更小子矩阵也平凡成立，$B$ 全单调。但 $0+4>2+1$，所以它不是Monge 数组公理库Monge 数组与交叉交换不等式Monge array · Monge matrix用任意四个有序格子的交换不等式控制行极小值的位置，并把平方分段费用转化成可证明的候选单调性。。

Monge 推出全单调，是因为四点不等式保证 $A_{ij}-A_{i\ell }\le A_{kj}-A_{k\ell }$；全单调只保留差值是否为正的方向信息，舍弃了差值具体增加多少。少要求一些数值结构，就能覆盖更多可搜索的成本表。

一个等号为什么会改变正确性 ​

再看

按最左规则，两行都选第一列，$C$ 全单调。如果误用 $A_{ij}\ge A_{i\ell }\Rightarrow A_{kj}\ge A_{k\ell }$，上行的 $0\ge 0$ 会要求下行 $0\ge 1$，反而把这个合法矩阵排除。平局规则与逻辑刻画必须一同确定。

在全零矩阵里，每行可以随意选一个最小位置，但这样记录出的答案可能倒退；这不反驳矩阵的全单调性，只说明选点规则没有遵守定义。实现中保存并比较二元组“数值、原列号”，是让最左规则贯穿所有递归层的直接办法。

全单调性对保序删行、删列封闭，因而适合“删除不可能赢的列，再递归求部分行”的搜索。SMAWK 算法公理库SMAWK 全单调矩阵搜索SMAWK algorithm交替执行列淘汰、奇数行递归与有界插值，在线性求值次数内找出全单调矩阵的每行最左极小值。正是利用这一点，把一个 $m\times n$ 隐式矩阵的全部行极小值化成 $O(m+n)$ 次表项求值。若只知道当前表的极小列单调，通常仍可做分治扫描，但不能直接引用 SMAWK 的列淘汰证明。

有些 DP 表只定义在阶梯形可行域上，例如候选切点必须满足 $k<j$。为其余格子补 $+\mathrm{\infty }$ 后，应重新验证严格比较刻画。对于非负前缀和平方费用，若上行右列严格胜出，它必为有限的合法项；其左列也合法，下一行又保留这两个候选，此时可用有限区域的 Monge 性完成证明。这个论证依赖可行域向下扩张；任意缺项位置补无穷不自动保持全单调。

实际使用有三层不同的检查：先由模型证明全单调性，再用小规模穷举验证平局和边界实现，最后才使用快速搜索。随机测试没有发现逆序，不能代替第一层证明；但它很擅长发现把严格比较写成非严格比较、把原列号换成局部列号等实现失误。