Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
See Hall’s marriage theorem. –  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
add comment

1 Answer

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.