# Marriage Problem

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 A_{i}. 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 A_{1}, ..., A_{n} be subsets of an n-set M. The family of sets
_{1}, ..., A_{n}*system of distinct representatives* (SDR) iff there exist
distinct elements _{1}, ..., x_{n},_{i} is in A_{i}, for each

Let A_{1}, ..., A_{n} be subsets of an n-set M. The family of sets _{1}, ..., A_{n}*marriage condition* iff the union of any k of the sets contains at least k elements, for all

### MARRIAGE THEOREM

A family A_{1}, ..., A_{n} of sets has a system of distinct representatives iff the family satisfies the marriage condition.

### Remark

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.

### Proof

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 _{ij})_{1}, ..., A_{n}_{i}'s). For each _{ij} = 1 ^{th} element of M is in A_{j} and set _{ij} = 0

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.

### GREEDY PHASE:

|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 a_{ij} = 1 in block C and a_{jk} = 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.

### LABEL PHASE:

|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 a_{ij} = 1 in F and a_{jk} = 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 k^{th} and i^{th} 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 E_{1} be the nonzero columns of F and let G_{1} be the rows of G corresponding to the columns of E_{1} (if column i meets E_{1}, then row i meets G_{1}.) If G_{1} has a 1, then we can interchange a column of G_{1} with a column of E_{1} 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 F_{1} be the submatrix of A consisting of the columns left of E_{1} and whose rows are the rows of G_{1}. If F_{1} has only zeros, then, as with F, the marriage condition is violated. Otherwise, let E_{2} be the nonzero columns of F_{1} and let G_{2} be the rows of G corresponding to the columns of F_{2}. If G_{2} 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 F_{i}'s and G_{i}'s until some G_{i} 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.

**Example**:

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.

### Corollary

If a family A_{1}, ..., A_{n} of sets has the property that _{i}| = k,_{i} occurs in at most k of the A_{i}, then the family has a system of distinct representatives.

### Proof

We show that the family satisfies the marriage condition. For any s, _{i}. Since each A_{i} has k elements, there are exactly ks occurences of elements in the s sets A_{i}. Since each element can occur
in at most k sets, there are at most kt occurences of elements in the s sets A_{i}. Hence ks≤kt, whence s≤t. Thus the family _{1}, ..., A_{n}

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.

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny