Sorting rows then sorting columns preserves the sorting of rows From Peter Winkler's book:

Given a matrix, prove that after first sorting each row, then sorting each column, each row remains sorted.

For example: starting with
$$\begin{bmatrix}
1 & -3 & 2 \\
0 & 1 & -5 \\
4 & -1 & 1
\end{bmatrix}$$
Sorting each row individually and in ascending order gives
$$\begin{bmatrix}
-3 & 1 & 2 \\
-5 & 0 & 1 \\
-1 & 1 & 4
\end{bmatrix}$$
Then sorting each column individually in ascending order gives
$$\begin{bmatrix}
-5 & 0 & 1 \\
-3 & 1 & 2 \\
-1 & 1 & 4
\end{bmatrix}$$
And notice the rows are still individually sorted, in ascending order.
I was trying to find a 'nice'  proof that does not involve messy index comparisons... but I cannot find one!

Let's say after sorting, the new matrix is $A$ with m rows and n columns. We have to prove that
\begin{equation}
A_{ij}\leq A_{ik},\, \forall j  \leq k
\end{equation}
where  $A_{xy}$ is element at $x_{th}$ row and $y_{th}$ column.
Here we know that there are at least $i$ elements (including $A_{ik}$) in column $k$ which are less than or equal to $A_{ik}$ and corresponding to their initial positions we have $i$ elements in column $j$ which are at most those elements therefore at least $i$ elements exist in column $j$ which are less than or equal to $A_{ik}$, Hence when column j is sorted
\begin{equation}
A_{ij} \leq A_{ik}
\end{equation}
