# There are some $1$ in the$n\times n$ grid such that the number of $1$ in each row and each column is $K (K<n).$

Prove that I can choose exactly one $\mathbf{1}$ from each row such that for every two of them,they are not in the same column.

-
– Brian M. Scott Sep 26 '12 at 6:37
Please edit the question so the question is in the body, not just in the title. – Gerry Myerson Sep 27 '12 at 6:53

Brian M. Scott's hint about Hall's Marriage Theorem is spot on.

Let $[n]=\{1,2,\ldots,n\}$. Let $\mathcal{S}=\{S_i\}_{i \in [n]}$ be a collection of sets.

• Definition: A system of distinct representatives of $\mathcal{S}$ is a set $\{s_i\}_{i \in [n]}$ such that $s_i \in S_i$ and $s_i \neq s_j$ whenever $i \neq j$.

• Definition: We say $\mathcal{S}$ satisfies the marriage condition if, for each $W \subseteq \mathcal{S}$, we have $$|W| \leq \left| \bigcup_{A \in W} A \right|.$$

• Hall's Marriage Theorem: $\mathcal{S}$ has a system of distinct representatives if and only if it satisfies the marriage condition.

So, we will now turn the $(0,1)$-matrix problem into a problem about a family of sets.

Let $M$ be a $n \times n$ $(0,1)$-matrix with $k$ copies of the symbol $1$ in each row and each column, where $1 \leq k \leq n$. Assume the rows and columns of $M$ are labelled by $[n]$.

Define $\mathcal{S}=\{S_i\}_{i \in [n]}$ by $$S_i=\{j \in [n]:m_{ij}=1\},$$ for all $i \in [n]$. That is, $S_i$ is the set of indices $j$ for which row $i$ contains a $1$ in the $j$-th cell $j$. Note that $|S_i|=k$ for all $i \in [n]$.

So we can restate the goal as follows: For each $i \in [n]$, choose $s_i \in S_i$ such that $s_i \neq s_j$ whenever $i \neq j$. That is, we are after a system of distinct representatives from $\mathcal{S}$.

Let $W \subseteq \mathcal{S}$. There are $|W|$ sets in $W$, each of size $k$. Each element in $[n]$ can appear in at most $k$ sets (otherwise we violate the condition that exactly $k$ copies of $1$ appear in some column of $M$).

Hence there are at least $\frac{k|W|}{k}=|W|$ distinct symbols in $\bigcup_{A \in W} A$. That is, the marriage condition is satisfied. Thus $\mathcal{S}$ contains a system of distinct representatives, and thus we can indeed choose $n$ $1$'s with one representative from each row and each column of $M$.

• The above proof shows that the permanent of $M$ is non-zero.
• The above proof shows that a $(n-k) \times n$ Latin rectangle $L$ (with $1 \leq k \leq n$) admits a completion to a $(n-k+1) \times n$ Latin rectangle, and thus, by induction, a Latin square. (Define the matrix $M=(m_{ij})$ by $m_{ij}=0$ if symbol $i$ does not occur in column $j$.)