The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+12 votes
1.6k views

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

  1. $\leq a +b$
  2. $\leq \max(a, b)$
  3. $\leq \min(M-a, N-b)$
  4. $\leq \min(a, b)$
asked in Linear Algebra by Veteran (69k points)
edited by | 1.6k views

2 Answers

+16 votes
Best answer

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. 

 

answered by Veteran (346k points)
selected by

@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 .

@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)?
+3 votes

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. 

answered by Boss (8.3k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,593 questions
40,128 answers
114,021 comments
38,389 users