0
$\begingroup$

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.

  • 0
    Please edit the question so the question is in the body, not just in the title.2012-09-27

1 Answers 1

1

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$.


Comments:

  • Hall's Marriage Theorem is non-constructive; it doesn't tell you how to find such a selection. (But it definitely exists.)

  • 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$.)