Title

考虑一个 $m \times n$ 的矩阵，其元素是互不相同的实数，且每一行内的元素按照从小到大的顺序重新排列. 现在把排列后的矩阵中每一列内的元素按照从小到大的顺序排列. 试证：重新排列后的矩阵中，每一行的元素仍按照从小到大的顺序排序.

Proof

不妨记原矩阵为 $A$，经过重排得到的矩阵为 $A'$.

考虑矩阵 $A$ 的每一行上第 $j$ , $j+1$ 列的元素，都有 $a_{ij} < a_{i(j+1)}$ （其中 $1 \leq i \leq m$ 为任意选取）.

固定指标 $j$ , $j+1$ .

考虑重排后第 $k$ 行上的元素，$a'_{kj}$ 和 $a'_{k(j+1)}$ ，由于指标 $j$ 和 $k$ 的选取都是任意的，因此现在我们只需证明 $a'_{kj} < a'_{k(j+1)}$ 即可.

注意到，在 $A'$ 中第 $j+1$ 列中，比 $a'_{k(j+1)}$ 小的元素有 $k-1$ 个：

由于矩阵 $A'$，是在 $A$ 的基础上对每一列进行重排——因此， $A'$ 中第 $j$ , $j+1$ 列上的元素仍分别是 $A$ 中第 $j$ , $j+1$ 列上的元素. 于是 $a'_{1(j+1)},\ a'_{2(j+1)},\ \dots ,\ a'_{(k-1)(j+1)}$ 这 $k-1$ 个 元素连同 $a'_{k(j+1)}$ 一齐，在矩阵 $A$ 中都各自有一个比它们小的元素位于第 $j$ 列中.

另一方面，由于 $a'_{k(j+1)}$ 比 $a'_{1(j+1)},\ a'_{2(j+1)},\ \dots ,\ a'_{(k-1)(j+1)}$ 这 $k-1$ 个元素都大，所以，在第 $j$ 列中，至少有 $k$ 个元素小于 $a'_{k(j+1)}$ .

注意到 $a'_{kj}$ 在第 $j$ 列中按从小到大的顺序排在第 $k$ 位，即该列恰有 $k-1$ 个元素比它小；所以，倘若 $a'_{kj} \geq a'_{k(j+1)}$ ，则说明在 $j$ 列中至多只有 $k-1$ 个元素比 $a'_{k(j+1)}$ 小，这与上面的推论矛盾. 于是 $a'_{kj} < a'_{k(j+1)}$ 成立.

命题得证.

Q.E.D.

Note

这个命题涉及到了矩阵，但实际上它和矩阵的性质应该没有什么直接的联系；笔者是在一本科普性质的数学趣题集上看到的，作者曾形容这个命题 “介乎于微妙与显然之间” ，笔者也深以为然.