# Greatest elements of the column and the least elements of the row of a Matrix

Let A be a real m×n matrix, with no two entries equal.

Let A(i,j) be the matrix entry obtained by selecting the least entry in each row, and then the greatest of these entries. Let A(u,v) be obtained by selecting the largest entry from each column, and then the least entry from these.

Prove that A(i,j) ≤ A(u,v)

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

A(i,j) = 26
A(u,v) = 32\

EDIT

My effort: I flattened the Matrix and sorted the entries. For both, A(i,j) and A(u,v), there must be at least (m-1) entries less than them, and at least (n-1) entries greater than them. This means that our value lies somewhere between mth and (mn-n+1)th entry (of the flattened/sorted matrix). However, I still can't prove that A(i,j) ≤ A(u,v)

• Welcome to MSE. It will be more likely that you will get an answer if you show us that you made an effort. – José Carlos Santos Feb 13 '18 at 12:08

## 1 Answer

Consider what the definition implies about the relationships between rows and columns.

A(u,v) is the largest in its column by definition. Also, A(i,j) is the smallest in its row by definition. If A(i,j) and A(u,v) are in the same row or column, clearly A(i,j) $\leq$ A(u,v) by definition.

If they are not, then we know that A(u,v) $\geq$ A(i,v) because it's the largest of its column. We also know that A(i,j) $\leq$ A(i,v) by definition. So, A(i,j) $\leq$ A(i,v) $\leq$ A(u,v).