In an M x N matrix all non-zero entries are covered in 'a' rows and 'b' columns. Then the maximum number of non-zero ent...

Question

In an M x 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. a <= b
B. <= min(a,b)
C. <= a + b
D. <= min(M-a, N-b)

Accepted Answer

The maximum number is <= min(M-a, N-b). Answer: D. All non-zero entries lie within a rows and b columns. We want to select non-zero entries with no two sharing a row or column (a matching). The non-zero entries are confined to the intersection of those a rows and b columns. Outside these rows and columns all entries are zero. A matching in this a x b submatrix can have at most min(a,b) elements, but we must also consider the positions not covered — the (M-a) uncovered rows and (N-b) uncovered columns contain only zeros, so no entries can be chosen from there. The answer is min(M-a, N-b) which reflects the maximum matching bounded by the uncovered rows and columns.

In an M x 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. a <= b B. <= min(a,b) C. <= a + b D. <= min(M-a, N-b)