GATE CSE 2004 | Question: 76

Question

In an $M \times N$ matrix all non-zero entries are covered in $a$ rows and $b$ columns. Then the maximum number of non-zero entries, such that no two are on the same row or column, is

• A. $\leq a +b$
• B. $\leq \max(a, b)$
• C. $\leq \min(M-a, N-b)$
• D. $\leq \min(a, b)$

Comments

My Point : if we take identity matrix of 4x4  in which maximum number of non-zero netry =4 .. if we take 2 row and 2 column then according to this answer min (2,2)= 2 is the maximum non zero but the real nonzero entry is 4 ...So option D is also contradicting and seems to false .. plz correct me where I am wrong @Arjun ,

---

@rohitpatel_ro This comment is reallly helpful

---

some results we have to remember i guess

Answer 1

maximum number of non-zero entries, such that no two are on the same row or column

Any entry will be a member of some row and some column. So, with $a$ rows we can have maximum $a$ elements such that no row has a repeated element. Same is applicable for $b$ columns also. So, combining both, answer should be $\leq \min(a,b)$. 

We can also apply pigeonhole principle here. Let $p = \min(a,b)$ be the number of holes. So, we can place up to $p$ non-zero entries (pigeons) and as soon as $(p+1)^{th}$ entry comes it must be making two entries in some column or row. 

Correct Answer: $D$

Comments

how can the values of a and b be different?

they've said "no two are on the same row or column" so each row and column will have only 1 element right?

---

@jinal99

Think of a rectangular matrix

---

Thanks @Ayush Upadhyaya Sir your comment helped a lot

Answer 2

Suppose a < b, for example let a = 3, b= 5, then we can put non-zero entries only in 3 rows and 5 columns. So suppose we put non-zero entries in any 3 rows in 3 different columns. Now we can't put any other non-zero entry anywhere in matrix, because if we put it in some other row, then we will have 4 rows containing non-zeros, if we put it in one of those 3 rows, then we will have more than one non-zero entry in one row, which is not allowed. So we can fill only "a" non-zero entries if a < b, similarly if b < a, we can put only "b" non-zero entries. So answer is ≤min(a,b), because whatever is less between a and b, we can put atmost that many non-zero entries. So option (D) is correct. 

Comments

Refer : https://www.geeksforgeeks.org/gate-gate-cs-2004-question-76/

---

Best explanation for this question.thanku

---

Thank you for simple explanation !

---

https://www.cse.iitd.ac.in/~mittal/gate/gate_math_2004.html

Answer 3

So answer is option (D)

Answer 4

- Question is asking for maximum number of elements which are neither in the same row or same column.

In an ideal case such elements are always present on diagonals i.e. no diagonal elements have same row or same column. ( Different permutations of the same matrix will have different positions in the matrix )

and number of diagonal elements depend upon min (number of rows, number of columns)

so, Answer – D

The best way i think to solve such questions are by assuming a sample matrix.

Answer 5

In a M×N matrix all non zero entries are covered in a rows and b columns , the rest ( M-a rows , N-b columns ) have zero entries. Then the maximum number of non zero entries such that no two are in same row/ column can be found out from the following cases 

Case 1 : a> b . No of non zero rows > non of no zero columns in this case you can have only 1 entry per a no of rows and 1 entry per b number of columns . But since a > b you are bound to have atleast 2 non zero entries in the same column. ( Visualise matrix 3×2 ) . So in this case , one row will become zero . So in this case max entries can be b only 

Case 2 : a<b . For similar reasons as above , opposite variable one column will become zero . So b cannot be greater than a . So in this case max entries can be a only 

Case 3 : a=b . Now this can be easy . Think of simple row echelon form matrix . Now we can say max no of non zero entries can be a/b 

Then max entries <= min(a,b) .  Option D  .we cannot have max entries <=min( M-a , N-b) because it will refer to rows and columns other than a and b which may or may not be equal to a and b  .

Answer 6

See it

https://www.cse.iitd.ac.in/~mittal/gate/gate_math_2004.html