Htykuut

The task is the following,

Let $M$ be a matrix. Show that the minimal number of rows and columns that together contain all $1$’s of $M$ equals the size of the largest set of $1$’s in $M$, such that no two are in the same row or column.

How can I proof this?

Let $$R: ={text{set of rows and columns that together contain all 1’s of M}}$$Let $$S: = {text{largest set of 1’s in M, such that no two are in the same row or column}}$$We need at least a row or column to cover each of the $1$'s in $S$ (as each of them is in a different row and column), so $$|R| geq |S|$$

Claim: There is a combination of rows and columns created by assigning either a row or a column to each $1$ in $S$ (for eg. first $1$ in $S$ is contained in a row of $R$; second in a column of $R$; etc.) that contains each of the $1$'s in $M$

Suppose there doesn't exist any, then there is some $1$ left out in the matrix from all the row and column indices of any combination of rows and columns in $R$. This $1$ is not in $S$ since we covered all of them by assigning either a row or column containing it. This is a contradiction to the size of $S$ since we chose it to be the largest set of $1$'s with different row and column index than all others.

I edited my answer to make it more informative

Here is a somewhat unsatisfactory proof as it reduces this theorem to another one about bipartite graphs without telling you anything about why that theorem is true. (But I'll provide a link where you can look it up.)

Make a bipartite graph: one set of vertices are the rows, one set of vertices are the columns and we draw an edge from vertex 'row i' to vertex 'column j' if and only there is a 1 in entry (i, j) of $M$.

Now 1's correspond to edges in the graph, and a collection of $1$'s with no common rows or columns correspond to a set of edges with no common vertices. Such a collection of edges is called a matching.

A set of rows and columns that together 'see' all 1's corresponds to a collection of vertices that together see all edges. Such a set of vertices is called a vertex cover.

In every graph we have (for obvious reasons) that the size of the biggest matching is less than or equal to the size of the smallest vertex cover. However, in bipartite graphs (of which the graph we constructed from our matrix $M$ is an example) we have the highly non-obvious fact that these sizes are actually equal. (This is called Konig's matching theorem and the proof can be found on page 41 in these lecture notes by Lex Schrijver: https://homepages.cwi.nl/~lex/files/dict.pdf.

The equality given by Konigs theorem for the very particular graph coming from our matrix $M$ is exactly the equality you were asking about.