This is not really a new answer, but places the question in a somewhat broader perspective. Note that the given answers really only consider one pair of adjacent columns at a time, the fact that these are inside a rectangle doesn't really matter. Also one could allow the columns to be of different length, provided that an empty place is considered smaller than any person. The fundamental result is the following.
Define a partial order on the set $A^*$ of words over some ordered alphabet $A$, by comparing corresponding partitions: $(a_1a_2\dots a_n)\geq(b_1b_2\ldots,b_m)$ whenever $n\geq m$ and $a_i\geq b_i$ for all $i\leq m$. Each word determines a multiset of letters (by forgetting the order), and any multiset is represented by a unique word in which the letters are weakly decreasing; this defines a natural "sorting" map $\phi: A^*\to A^*$ whose image is the set of weakly decreasing words. Then $\phi$ is a morphism of paritally ordered sets: for $v,w\in A^*$ one has $v\leq w\implies \phi(v)\leq\phi(w)$. Clearly this applies in particular to sorting two adjacent columns in the matrix of the question. The proof is the one given in the other answers: if letter $k$ of $\phi(v)$ is $a$, then at least $k$ letters of $\phi(v)$, and therefore of $v$, are${}\geq a$, and so by $v\leq w$ at least $k$ letters of $w$ are${}\geq a$, and in particular letter $k$ of $\phi(w)$ is.
The given statement can be made slightly stronger by replacing '$\leq$' by '$<$'; the proof then requires in addition a not-quite-so-easy argument showing that two different permutations of the same multiset of letters cannot be comparable by '$<$'. One way to proceed is to compare for a hypothetical counterexample the sets of positions occupied by the greatest letter; if these sets differ, then both words have some position where they contain the greatest letter and the other word does not, which contradicts them being comparable; if the sets coincide then one can remove all letters in these positions from both words and conclude using induction on the value of the greatest letter.