How many "$1$" can be selected at most, provided that only one from each row and column of the attached matrix $A$ is selected?(That is, when one "$1$" is selected, no other element can be selected than the row and column where that "$1$" is located.)
$$ A = \begin{bmatrix} 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{bmatrix} $$
Answer: I think $6$ can be chosen. How can I give this answer in connection with graph theory? I think it has to do with the Latin Square(or Rectangle). But I can't connect and explain.
Please help me. I thought a lot, but I could not establish the relationship completely. Thanks...
An $m\times n$ binary matrix can represent a biparite graph on $A\sqcup B$, where $|A|=m$ and $|B|=n$, and a one at entry $(i,j)$ means the $i^{th}$ vertex of $A$ is joined to the $j^{th}$ vertex of $B$. Then, a selection of ones in pairwise different rows and columns corresponds to a matching in that bipartite graph. A matching is a subset of edges where no two edges in the subset have a common endpoint. Therefore, asking the largest number of ones in pairwise different rows and columns is equivalent to asking what is the size of the maximum matching in that graph.
There is a lot of research in the field of maximum matchings, especially for bipartite graphs. There are several algorithms which compute the maximum matching reasonable of a bipartite graph quickly, described in the Wikipedia page for maximum matchings. https://en.wikipedia.org/wiki/Maximum_cardinality_matching