2.5.30 #

解答 #

不妨按照升序排序，$x_{ij}$ 代表第 $i$ 行第 $j$ 列的元素。

首先保证每列都是有序的。

对第一行排序，对于第一行的元素 $x_{1i}$ ，排序结果无非两种。

要么 $x_{1i}$ 不改变，要么和更小的元素进行交换。

显然，无论哪种情况，第 $i$ 列都是有序的。

因此对第一行排序之后，第一行有序，每一列都分别有序。

之后我们对第二行排序，考虑元素 $x_{11}$。

此时 $x_{11}$ 小于第一列的所有其他元素，也小于第一行的所有其他元素。

又每一列都分别有序，因此 $x_{11}$ 是整个矩阵的最小值，第二行不存在比它小的元素。

考虑使用选择排序，我们把第二行的最小值和 $x_{21}$ 交换，第一列仍然有序。

现在去掉第一列，对剩下的矩阵做一样的操作，可以将第二行依次排序。

同时保证第二行的元素都小于同列的第一行元素。

接下来的行都可以依次类推，最终将整个矩阵的所有行排序，定理得证。