0
$\begingroup$

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)

$\endgroup$
1
  • $\begingroup$ Welcome to MSE. It will be more likely that you will get an answer if you show us that you made an effort. $\endgroup$ Feb 13, 2018 at 12:08

1 Answer 1

0
$\begingroup$

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).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .