edited by
9,522 views
35 votes
35 votes

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 by

4 Answers

Best answer
29 votes
29 votes

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$

edited by
25 votes
25 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. 

2 votes
2 votes
- 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:

Related questions

35 votes
35 votes
4 answers
1
Kathleen asked Sep 18, 2014
9,987 views
Let $A, B, C, D$ be $n \times n$ matrices, each with non-zero determinant. If $ABCD = I$, then $B^{-1}$ is $D^{-1}C^{-1}A^{-1}$ $CDA$ $ADC$ Does not necessarily e...
28 votes
28 votes
4 answers
3
Kathleen asked Sep 18, 2014
8,291 views
How many solutions does the following system of linear equations have?$-x + 5y = -1$$x - y = 2$$x + 3y = 3$infinitely manytwo distinct solutionsuniquenone