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!
 A: Notice that you can start from after the first step. Specifically, you only need to prove that, given an arbitrary matrix where each row is already in ascending order, sorting each column in ascending order keeps each row sorted. Here is a very neat trick to do this.
Let $m$ be the number of columns. For each $k$ from $1$ to $m$, sort the rows of the subarray from column $k$ to column $m$ in increasing order of the element in column $k$. (Each row of the subarray stays together.) We do this sorting by bubble sort. We maintain the invariant that the elements in each row stays sorted. This invariant is trivially true when $k = 1$. When $k > 1$, and we perform a swap involving rows $p$ and $(p+1)$, consider the elements in those rows and in the columns $(k-1)$ and $k$:

$\cdots \quad a \quad d \quad \cdots_1$
$\cdots \quad b \quad c \quad \cdots_2$

By the invariance we have $a \le b \le c$ and the swap is only done because $c \le d$. After the swap we have:

$\cdots \quad a \quad c \quad \cdots_2$
$\cdots \quad b \quad d \quad \cdots_1$

And the invariance is preserved since $a \le c$ and $b \le d$. Look! No index chasing!
A: 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}
