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

@Arjun Sir : are u putting entries this way. Then according to this min of a and b will be answer. Is it correct ?

---

yes. Thats correct.

---

@Arjun Sir , I am unable to understand this question . as it is saying no two non zero entry come in same row or column . so each entry telling that corresponding row and column will not contain any other non zero entry .

and by this value of a and b will be equal . because each entry is corresponding to one row and one column .

as in above given comment diagram . first element a is corresponding to first row and first column . and like wise other elements too . There total 4 rows and 4 columns and each column and each row is having different element .

For me what i am undersatnding is that value of a and b will be same bcoz each element corresponds to one row and column and no other elemnt can come in that row and column .

and if they are same then many option will be correct ..
correct me sir .

---

@amit pal

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

---

@Arjun sir, which one is correct meaning of a rows and b columns contain non-zero elements.

Let a=3 and b=2.

0	0	1	1	0	0
0	0	1	1	0	0
1	1	1	1	1	1
1	1	1	1	1	1
1	1	1	1	1	1
0	0	1	1	0	0

or 

0	0	0	0	0	0
0	0	0	0	0	0
0	0	1	1	0	0
0	0	1	1	0	0
0	0	1	1	0	0
0	0	0	0	0	0

If first one is correct - then ans should be option B.

And 2nd one is correct then option D is fine.

---

@Vijay. WHy you have taken multiple non-zero entries in same row/column? They have said dont take.

---

@vijay @Amit

No

read the line " such that no two are on the same row or column "

So, 1st put a non zero entry.

then make that row and column empty.

Put the next element next empty row or column.

See the pic of Gate Brahmachari .

How he put the elements.

---

^ I  just want to tell the meaning of the first  line (In an M××N matrix all non-zero entries are covered in aa rows and bb columns.) by those table.

That is not final ans..

---

My ans should be like this --
@Srestha, now tell where is fault in the below table...  check marked non-zero elements ..can't they be ans acc. to the given condition ??

0	0	1	1	0	0
0	0	1	1	0	0
1	1	1	1	1	1
1	1	1	1	1	1
1	1	1	1	1	1
0	0	1	1	0	0

---

@vijay both tables give 0 as answer rt?

---

ohh, sorry , Actually I mis-understood the question .. some days ago I solved this with right approach ,, but I got confused today ... ohh my dear mind don't confuse like this for atleast those 3 life changing  hrs.. thanks all :)

---

@Vijay. Haha. Stay calm. Dont do anything hurriedly. I am also doing similar mistakes right now.

---

Dont't it should be min(M, N)?

---

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.