monotone minima
minima 是名词 minimum 的复数形式。
monotone minima 说的是矩阵的一种性质。若一个矩阵的每一行的最小值（若有多个取最左边那一个）所在的列的编号从上到下是单调不降的，就说这个矩阵是 monotone 的。若一个矩阵的每个子矩阵都是 monotone 的，就说这个矩阵是 totally monotone 的。
子矩阵（英语：submatrix）是在矩阵选取部分行、列所组成的新矩阵。
试证明：
矩阵 $A$ 是 totally monotone 的 $\iff$ $A$ 的每个 2x2 子矩阵都是 monotone 的。
例题
坐标平面上有 $N$ 个房屋和 $M$ 个商店。第 $i$ 个房屋的坐标是 $(p_i, 0)$。第 $j$ 个商店的坐标是 $(x_j, y_j)$。满足
- $p_1 < p_2 < \dots < p_N$
- $x_1 \le x_2 \le \dots \le x_M$
考虑矩阵 $D_{N\times M}$， $D_{i,j}$ 是第 $i$ 个房屋到第 $j$ 个商店的距离。证明 $D$ 是 totally monotone 的。
monotone minima
minima 是名词 minimum 的复数形式。
monotone minima 说的是矩阵的一种性质。若一个矩阵的每一行的最小值（若有多个取最左边那一个）所在的列的编号从上到下是单调不降的，就说这个矩阵是 monotone 的。若一个矩阵的每个子矩阵都是 monotone 的，就说这个矩阵是 totally monotone 的。
子矩阵（英语：submatrix）是在矩阵选取部分行、列所组成的新矩阵。
试证明：$A$ 是 totally monotone 的 $\iff$ $A$ 的每个 2x2 子矩阵都是 monotone 的。
矩阵
例题
坐标平面上有$N$ 个房屋和 $M$ 个商店。第 $i$ 个房屋的坐标是 $(p_i, 0)$ 。第 $j$ 个商店的坐标是 $(x_j, y_j)$ 。满足
考虑矩阵$D_{N\times M}$ ， $D_{i,j}$ 是第 $i$ 个房屋到第 $j$ 个商店的距离。证明 $D$ 是 totally monotone 的。