Solution to sort each column, algorithm puzzle

[This is a solution to the sort each column, algorithm puzzle posted earlier]

A brief description of the problem:

Given a matrix of integers, by permuting each row separately (with possibly different permutations), can each column of the matrix be sorted (in ascending order, with smallest in row one)? Give a polynomial time algorithm for it.

Solution

---

Consider the case of a $2\times n$ matrix, which has two rows and $n$ columns.

Suppose it was possible to sort the columns by permuting the rows.

The claim is that, the columns remain sorted, even after we sort the rows!

For example, this is a matrix in which the columns are sorted:

$\begin{bmatrix}4&7&8&6\\5&100&200&10\end{bmatrix}$

Now, if we sort each row individually we get

$\begin{bmatrix}4&6&7&8\\5&10&100&200\end{bmatrix}$

The columns are still sorted!

The proof is actually not difficult:

Suppose $a \le b$ and $c \le d$, then we have that:

$\min\{a,c\} \le \min\{b,d\}$ and $\max\{a,c\} \le \max\{b,d\}$.

Thus
$\begin{bmatrix}\dots&a&\dots&c&\dots\\\dots&b&\dots&d&\dots\end{bmatrix}$

can be replaced by

 $\begin{bmatrix}\dots&\min\{a,c\}&\dots&\max\{a,c\}&\dots\\\dots&\min\{b,d\}&\dots&\max\{b,d\}&\dots\end{bmatrix}$

and still have the columns sorted.

Thus if the columns are sortable, they are sortable by sorting the individual rows (and vice-versa).

So the algorithm is simple: sort each row, and then check if the columns are sorted.