In an M x N matrix, all non-zero entries are covered by a rows and b columns.…

Concept: Model any 0/1 (non-zero) incidence pattern between two finite sets as a bipartite graph: put one side of vertices for rows and the other side for columns, and draw an edge for every place a non-zero value occurs. A selection of edges with no two sharing an endpoint is a matching; a set of vertices that touches every edge is a vertex cover. For any graph, a matching can never contain more edges than a given vertex cover has vertices - every matching edge must be touched by the cover, and since matching edges never share a vertex, no single cover vertex can be the touching point for more than one matching edge.

Application: Map this matrix onto that picture, then count.

1. Represent the M x N matrix as a bipartite graph: each row is a vertex on one side, each column is a vertex on the other side, and each non-zero entry at (row i, column j) is an edge joining row i to column j.

2. The given a rows and b columns cover every non-zero entry, so together they form a vertex cover of this graph with a + b vertices (a row-vertices plus b column-vertices).

3. Any set of non-zero entries with no two sharing a row or a column is, in graph terms, exactly a matching - a set of edges with no shared endpoint.

4. Because the a + b covering vertices touch every edge, and matching edges never share a vertex, each of the a + b covering vertices can be the touching point for at most one matching edge.

5. Summing over all a + b covering vertices, the matching can therefore contain at most a + b edges - that is, at most a + b non-zero entries can be chosen with no two sharing a row or column.

Cross-check: A small concrete example confirms the bound is attainable and shows how the other formulas behave on the same data.

• Example: take M = N = 2, with the cover chosen as row 1 (so a = 1) and column 2 (so b = 1); the non-zero entries sit at (1,1), (1,2) and (2,2), all covered by row 1 or column 2.

• Choosing the entries (1,1) and (2,2) gives two non-zero entries in different rows and different columns; here a + b = 1 + 1 = 2, so this selection attains the a + b bound exactly.

• On this same example, max{a, b} = 1, min{a, b} = 1, and min{M-a, N-b} = min{1, 1} = 1 - each of these three expressions evaluates smaller than the 2 entries that were actually selected.

So the general, tight bound - matching the size of the a-row/b-column vertex cover - is a + b non-zero entries with no two on the same row or column.