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

Here is one approach we can also look for.

Note: The matrix I framed is of M x N and I have written N x N.

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

Basically, they are asking what is the maximum rank of an mxn matrix.

which is $Rank(a)\leq min\{m,n\}$

---

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

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.