Let M be a (0, 1) matrix; that is, a matrix where each of whose entries is either a 0 or a 1. A line in M is either a row or a column of M. Use Dilworth's theroem to prove that the minimum number of lines containing all the 1's of M is equal to the maximum number of 1's, no two of which are in the same line.
I realize this is the Konig's theorem basically. I started the proof out by:
Let G be a bipartite graph with vertex bipartition {X, Y} , such that A is an adjacency matrix of graph G, where X is a set of vertices corresponding to the rows of matrix A, and Y is the vertex set corresponding to the columns.
Any hint after this would be great! I know we have to introduce the concept of chains and antichains, but how do we connect that with the matrix entries?