First, Let's Formalize the Definitions #

Let’s start by clarifying exactly what we’re working with to avoid confusion:

• For our m×n matrix ( A ) (with distinct real elements):
  • ( A(i,j) ) (let’s call this the row-max-min): First find the smallest element in each row, then take the maximum of these minima.
  • ( A(u,v) ) (let’s call this the col-min-max): First find the largest element in each column, then take the minimum of these maxima.

Example to Ground the Idea #

Take the given matrix as a concrete case:

A = \begin{pmatrix} 3 & 52 & 32 \\ 34 & 66 & 26 \end{pmatrix}

• Row minima: 3 (from row 1), 26 (from row 2) → ( A(i,j) = \max(3,26) = 26 )
• Column maxima: 34 (column 1), 66 (column 2), 32 (column 3) → ( A(u,v) = \min(34,66,32) = 32 )
  As we can see, 26 ≤ 32 — this aligns with the claim we need to prove.

The General Proof #

Let’s use formal notation to prove this holds for any m×n matrix ( A ) with distinct real elements:

1. Let ( r^* = \max_{1 \leq i \leq m} \left( \min_{1 \leq j \leq n} A_{i,j} \right) ) — this is our ( A(i,j) ). By definition, ( r^* ) is the minimum element of some specific row ( k ), so ( r^* = \min_{1 \leq j \leq n} A_{k,j} ). This means for every column ( j ), ( r^ \leq A_{k,j} )* (since it’s the smallest element in row ( k )).

2. Now let ( c^* = \min_{1 \leq j \leq n} \left( \max_{1 \leq i \leq m} A_{i,j} \right) ) — this is our ( A(u,v) ). For each column ( j ), ( \max_{1 \leq i \leq m} A_{i,j} ) is the largest element in that column, so for every row ( i ), ( A_{i,j} \leq \max_{1 \leq i \leq m} A_{i,j} ).

3. Combine these two observations: For every column ( j ), ( r^* \leq A_{k,j} \leq \max_{1 \leq i \leq m} A_{i,j} ). Since this inequality holds for all columns, when we take the minimum of all column maxima (which is ( c^* )), ( r^* ) must be less than or equal to that minimum. In mathematical terms:
   [
   r^* \leq \min_{1 \leq j \leq n} \left( \max_{1 \leq i \leq m} A_{i,j} \right) = c^*
   ]
   This directly proves ( A(i,j) \leq A(u,v) ).

Intuitive Breakdown #

If you want to think about it in plain terms:

• The row-max-min is the "best worst-case" element: you pick a row, take its smallest value, and choose the row where this smallest value is as large as possible.
• The col-min-max is the "worst best-case" element: you pick a column, take its largest value, and choose the column where this largest value is as small as possible.
  Naturally, the best of the worst cases can’t outperform the worst of the best cases — you can’t get a higher value by prioritizing rows (and taking minima) than you can by prioritizing columns (and taking maxima).

内容的提问来源于stack exchange，提问作者AliF