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)

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

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


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)

  • $\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$ – José Carlos Santos Feb 13 '18 at 12:08

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.