This is a TIL post. The problem was disguised as a simple inequality exercise in Norman L Biggs' Discrete Mathematics book.

So here's the deal:

Problem: Prove that in a square matrix, the least of the greatest valued members of each row is greater or equal to greatest of the least value members of a each column. (For convenience, I have assumed the matrix consists of only natural numbers)

With some help from math.stackexchange.com, I was able to formalize this as:

Prove that Min

Let's break it down. From general definitions of Min and Max, we know that:

So, it simply boils down to proving the statement:

Let x

Let y

From

What we just proved is that there exists a f(x

Hence, we can claim using axioms of inequality and natural numbers that:

or in other words,

which can further be extended to

using the reasoning in

Although it took me a while to understand this problem, it took me much lesser time to identify the

Another take-away realization from today: there is a lot of meaning in "break down problems before you try to solve them". This is just a simple example.

So here's the deal:

Problem: Prove that in a square matrix, the least of the greatest valued members of each row is greater or equal to greatest of the least value members of a each column. (For convenience, I have assumed the matrix consists of only natural numbers)

**Formalizing:**With some help from math.stackexchange.com, I was able to formalize this as:

Prove that Min

_{y}(Max_{x}f(x,y)) >= Max_{x}(Min_{y}f(x,y)) where f(x,y) is basically any value in the matrix and x and y refers to the row and column respectively.**Proof:**Let's break it down. From general definitions of Min and Max, we know that:

f(x,y) >= Min(f(x,y))

and

Max(x,y) >= f(x,y)

**- (I)**So, it simply boils down to proving the statement:

Max

_{x}f(x, y) >= Min_{y}f(x, y)Let x

_{o}be a row at which the value Max_{x}f(x, y) is found. As a result, f(x_{o}, y) would be the greatest possible value__for any y__in the x_{o}row -**(II)**Let y

_{o}be a column at which the value Min_{y}f(x, y) is found. As a result, f(x, y_{o}) would be the lowest possible value__for any x__in the y_{o}column. -**(III)**From

**(II)**,
f(x

And from _{o}, y) >= f(x_{o}, y_{o})**(III)**,
f(x

_{o}, y_{o})>= f(x, y_{o})What we just proved is that there exists a f(x

_{o}, y_{o}) that belongs to N, such that
f(x

_{o}, y) >= f(x_{o}, y_{o}) and f(x_{o}, y_{o})>= f(x, y_{o}).Hence, we can claim using axioms of inequality and natural numbers that:

f(x

_{o}, y) >= f(x, y_{o})or in other words,

Max

_{x}f(x, y) >= Min_{y}f(x, y)which can further be extended to

Min

_{y}(Max_{x}f(x,y)) >= Max_{x}(Min_{y}f(x,y))using the reasoning in

**(I)****Summary**Although it took me a while to understand this problem, it took me much lesser time to identify the

*mental route*to understanding this problem (commonly conveyed as "connecting the dots") once it was formalized and expressed as a statement. So the formalization process was worth it because, it helped me clearly understand the problem I was trying to solve. I have not quite been the fan of formal mathematical representation in the past, but I guess that just might change in the future :)Another take-away realization from today: there is a lot of meaning in "break down problems before you try to solve them". This is just a simple example.

Oh I get it now. You just cleared the problem I was facing so quickly. Thank you for doing such an amazing job by posting such content on your blog.

ReplyDelete