Matrix Saddle Points
Source: Algo Muse, CSE, IIT Bombay
Problem:
An entry aij in a matrix is called a saddle point if it is strictly greater than all the entries in the ith row and strictly lesser than all entries in the jth column or vice-versa. For example, the matrix shown below has two saddle points.
What is the maximum number of saddle points an nxn matrix can have?
Update (December 14, 2011):
Due to some reason I do not know of, the problem is not there on the Algo Muse website anymore. :P
Solution posted by Panna, Gold and Iron (Nikhil Pandey, CSE IITB 2009 Alumnus), Prasham Rambhia (Aero IITB Fifth Year Undergraduate Student, To be Morgan Stanley Quant) and Insomniac in comments!
Problem:
An entry aij in a matrix is called a saddle point if it is strictly greater than all the entries in the ith row and strictly lesser than all entries in the jth column or vice-versa. For example, the matrix shown below has two saddle points.
What is the maximum number of saddle points an nxn matrix can have?
Update (December 14, 2011):
Due to some reason I do not know of, the problem is not there on the Algo Muse website anymore. :P
Solution posted by Panna, Gold and Iron (Nikhil Pandey, CSE IITB 2009 Alumnus), Prasham Rambhia (Aero IITB Fifth Year Undergraduate Student, To be Morgan Stanley Quant) and Insomniac in comments!
Is it that simple? Or I am making mistake somewhere.
ReplyDeleteAnyways my answer 2.
We can not have two saddle points which are simultaneoualy max in row and min in column or opposite.
So one from rowmax and one from column max.
2 kinds of siddle.
ReplyDeleterow elements < siddle < column element
column element < siddle < row elements
Every row/column can have only one maximum element. Now, [assuming row maximum], one of these n points is a possible siddle [of the first kind].
Let it be a[i][j]....let there be another siddle a[k][l].
So we have
a[k][j] > a[i][j] > a[i][l]
a[i][l] > a[k][l] > a[k][j].
Not possible.
so only one siddle point of type 1, and similarly one of type 2.
So maximum 2 [also since you have given an example of a matrix with 2 siddle points, I dont have to prove the feasibility of their existence]
The maximum number of saddle points any nxn matrix can have is 2!
ReplyDeleteFirstly, note that the following operations do not change the number of saddle points:
1. Interchanging rows
2. Interchanging columns
3. Taking transpose of the matrix
Hence, without loss of generality, we can assume the following:
a. The largest of the saddle points, say x, is at the position (1,1). (If not already the case, this can be ensured by atmost one operation each of 1 & 2.)
b. All entries of the first row, other than x, are smaller than x; all entries of the first column, other than x, are larger than x. (If not already the case, this can be ensure by operation 3.)
Having done this, assume that there are two more saddle points, say y at position (i,j) and z at position (k,l). Obviously, j and l cannot be equal to 1.
In view of (b), both y and z are the smallest elements of their row (because a(i,1)>x>=y; similarly, for z). This also implies that y and z are in different rows, i.e. i is not equal to k.
As they are saddle points, they need to be the largest entry in their columns. As such, they need to be in different columns too, i.e. j is not equal to l.
Hence, we have y = a(i,j) < a(i,l) < a(k,l) = z.
Also, y = a(i,j) > a(k,j) > a(k,l) = z.
Obviously, this is a contradiction as y cannot be both greater than and less than z.
Thus, there cannot be more than two saddle points.
That there can possibly be two saddle points is exemplified in the problem itself. This settles our problem! :)
2.
ReplyDeleteWe can divide the saddle points in two categories - C1 and C2. C1 being the description given in the problem. C2 being the "vice-versa".
Claim: There can't be more than one saddle points of type C1.
Proof: Any permutation of the rows or columns doesn't affect the saddle points. So, WLOG, assume a saddle point at (1,1). Let it be of type C1. If another saddle point at (i,j) is of type C1, then
Aij > Ai1 > A11
Aij < A1j < A11
hence, (i,j)=(1,1).
Similarly, it can be proved that there can't be more than one C2 saddle points.
Trivially, both C1 and C2 points can exist (the example given in the question has C1 and C2 saddle points)
Hence, answer is 2.
Yes, the solutions by all of you are correct! Thanks
ReplyDeleteHow about this matrix? which has 4 saddle points (2,2), (2,4), (4,2), (4,4)
Delete{{4,3,5,1,2},
{-1,0,-2,0,-1},
{-4,1,4,3,5},
{-3,0,-1,0,-2},
{3,2,-7,3,8}}