130. Rows and Columns


把一个矩阵的每一行各自从左到右排成不减的次序,然后把每一列各自从上到下排成不减的次序。证明:排完列之后,每一行仍然不减。(以从小到大为例;从大到小完全同理。)

结论成立,整个证明只有一个数个数的动作。

把各行排好后的矩阵记为\(A=(a_{ij})\),再逐列排序得\(B\)。各列互不相干,所以\(B\)的第\(j\)列就是把\(A\)的第\(j\)列单独排好,\(b_{ij}\)恰是第\(j\)列的第\(i\)小元素。于是要证的只是:第\(j\)列的第\(i\)小元素不超过第\(j+1\)列的第\(i\)小元素。

道理就一句话:对任何阈值\(x\),第\(j+1\)列里不超过\(x\)的元素各住在某行\(r\),而该行满足\(a_{r,j}\le a_{r,j+1}\le x\),同行第\(j\)列的元素也不超过\(x\)。所以不论\(x\)取什么值,第\(j+1\)列中不超过\(x\)的元素总不多于第\(j\)列的。取\(x\)为第\(j+1\)列的第\(i\)小元素:它下面至少压着\(i\)个元素,于是第\(j\)列也压着至少\(i\)个,其第\(i\)小元素自然不超过\(x\)。这对一切\(i,j\)成立,故\(B\)的每一行仍不减。

排完列,列本就有序,行又仍不减,矩阵已双向单调。元素相等、或改成从大到小排序,论证原样成立。

Previous