2.1k 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)$
edited | 2.1k views

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.

selected
+11

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

0
yes. Thats correct.
0
@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 .
+4
0

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

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

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

0

^ 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
0
@vijay both tables give 0 as answer rt?
0
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 :)
+1
@Vijay. Haha. Stay calm. Dont do anything hurriedly. I am also doing similar mistakes right now.
0
Dont't it should be min(M, N)?
+3
Basically, they are asking what is the maximum rank of an mxn matrix.

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

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.

0

1
2