In an M x N matrix, all non-zero entries are covered by a rows and b columns.…
2004
In an M x N matrix, all non-zero entries are covered by 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.
≤ max {a, b}
- C.
≤ min {M-a, N-b}
- D.
≤ min {a, b}
Attempted by 7 students.
Show answer & explanation
Correct answer: A
View the M x N matrix as a bipartite graph: rows are vertices on one side, columns are vertices on the other side, and each non-zero entry is an edge between its row and column. A set of non-zero entries with no two in the same row or column is a matching. The given a rows and b columns cover every non-zero entry, so they form a vertex cover of size a + b. Every edge in any matching must touch this cover, and because matching edges do not share endpoints, at most one matched edge can be assigned to each covering row or column. Hence the maximum possible number of such non-zero entries is at most a + b.