Latin squares could be used by dating services to organize meetings between a number n of girls and the same number n of boys. Having met all the boys, each girl comes up with a list of boys she would not mind marrying. The dating service is faced now with the task of arranging marriages so as to satisfy each girl preferences. Call the set of boys listed by the i-th girl Ai. The problem is then to pick boys, one from each list, without selecting the same boy more than once. An abstract formulation of this problem and its constructive solution by W. McWorter, Jr. is given below.
Let A1, ..., An be subsets of an n-set M. The family of sets
A family A1, ..., An of sets has a system of distinct representatives iff the family satisfies the marriage condition.
Strictly speaking, the proof below does not require the sets of boys and girls to be equipotent. However, this is a sensible assumption. For, if there are fewer boys the marriage condition fails. On the other hand, if there are fewer girls, the difference can be made up by "desperate" girls willing to marry any boy without disturbing the truth or falsity of the marriage condition.
I will prove this theorem by describing a procedure for constructing a system of distinct representatives which succeeds iff the marriage condition is satisfied. Another elegant, though less procedural, proof illuminates various phases of the algorithm. It is convenient for me to describe everything in terms of zero-one matrices. Let
Then the family has a SDR iff the matrix A has a transversal of 1's. Here is the procedure together with a proof that it constructs a transversal of 1's iff the family satisfies the marriage condition. Assume matrix A is in the form below, where, at the beginning, the upper left block with 1's on the diagonal may or may not be empty. Successive steps of the algorithm are designed to increase the size of the block.
|1 | | | 1 | | | . | | | . | | | 1| | | --------|--------| | | | | | B | | | |
If block B is empty (0×0), then we are done, the family has a SDR. If B contains a 1, interchange rows and columns (without disturbing the diagonal of ones in the upper left corner block) to put a 1 in the upper left corner of B, replace B with that obtained by using all but the first row and first column of B, and resume the greedy phase.
Otherwise, we proceed to the LABEL PHASE.
B HAS ONLY ZEROS:
|1 | | | 1 | | | . | | | . | D | | 1| | | --------|--------| | | | | C | 0 | | | |
If block C has only zeros, we are done; the family has no SDR because the sets associated with the columns of C together with a set associated with a column of B violate the marriage condition; that is, the union of these sets contains one fewer elements than the number of sets.
If aij = 1 in block C and ajk = 1 in block D, then interchange columns j and k of A and resume the greedy phase with B the lower right corner block which now contains a 1.
|1 | | | | . | | G | | 1| | | ------------------------ | |1 | | | | . | | | F | . | 0 | | | 1| | |-----|-------|--------| | | | | | 0 | E | 0 | | | | | A
Having reached here, for every 1 in C there are only zeros in the corresponding row of D. We can re-arrange the columns of C so that all its zero columns are left of all its nonzero columns as follows. If column i of A meets C in a nonzero column of C, and column
If the block F contains only zeros, then we are done; the family has no SDR because the sets corresponding to the columns of F and one set corresponding to a column of G violates the marriage condition.
If aij = 1 in F and ajk = 1 in G, for some k, then swap columns j and k of A. This puts a 1 in the zero block just below G. Now we can swap the kth and ith columns of A, putting a 1 in the lower right corner zero block. Resume the greedy phase.
Otherwise, if for every nonzero column of F, the corresponding row of G has only zeros, then let E1 be the nonzero columns of F and let G1 be the rows of G corresponding to the columns of E1 (if column i meets E1, then row i meets G1.) If G1 has a 1, then we can interchange a column of G1 with a column of E1 to put a 1 in a row that corresponds to a column of E; whence we can do another interchange to put a 1 into the lower right block of A and resume the GREEDY PHASE. Otherwise, let F1 be the submatrix of A consisting of the columns left of E1 and whose rows are the rows of G1. If F1 has only zeros, then, as with F, the marriage condition is violated. Otherwise, let E2 be the nonzero columns of F1 and let G2 be the rows of G corresponding to the columns of F2. If G2 contains a 1, we can do a series of column swaps to put a 1 to the right of E and resume the GREEDY PHASE. Otherwise, we continue the construction of Fi's and Gi's until some Gi has a nonzero entry unless G has all entries zero, a violation of the marriage condition (if a column of G is zero, then the union of one set has no elements, a violation of the marriage condition). Thus, either the marriage condition is violated or we can do a series of swaps that puts a 1 to the right of E so we can resume the GREEDY PHASE.
1 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0
A series of 4 swaps needed to put a 1 in the lower right corner.
Thus the family has an SDR iff the marriage condition is satisfied.
If a family A1, ..., An of sets has the property that
We show that the family satisfies the marriage condition. For any s,
This corollary is used to show that every latin rectangle can be completed to a latin square, and that every attempt to construct a latin square by transversals, i.e., place the 1's, then place the 2's, etc., can succeed.