# Marriage Theorem

The marriage problem requires us to match n girls with the set of n boys. Each girl (after a long and no doubt exhausting deliberation) submits a list of boys she likes. We also make an assumption that being of noble character no boy will break a heart of a girl who likes him by turning her down. So, although, girls appear to seize the initiative by advertising their preferences, the situation is quite symmetric and is best represented by a zero-one matrix. An element a_{ij} in row i and column j is 1 iff the marriage between the girl #i and the boy number #j is feasible. a_{ij} is 0, otherwise. Sometimes all the girls can be given away, sometimes no *complete match* is possible.

The *marriage condition* can be formulated in several equivalent ways:

**Every set of r girls, 1 ≤ r ≤ n likes at least r boys.**Pick up any s columns. Concentrate on rows that have at least one 1 in the selected columns. The number of such rows must not be less than s.

**Every set of s boys, 1 ≤ s ≤ n likes at least s girls.**Pick up any r rows. Concentrate on columns that have at least one 1 in the selected rows. The number of such columns must not be less than r.

**No zero r by s submatrix may satisfy r + s > n.**If such a matrix exists then some r girls can marry only (n - s) boys outside the submatrix. Since r > n - s, there are just too few boys to satisfy all r girls.

The *marriage condition* and the *Marriage theorem* are due to the English
mathematician Philip Hall (1935.)

## Marriage Theorem

Hall's condition is both sufficient and necessary for a complete match.

## Proof

The necessecity is obvious. The *sufficient* part is shown by induction. The case of
n = 1 and a single pair liking each other requires a mere technicality to arrange a match. Assume we have already established the theorem for all k by k matrices with k < n. For the case of n girls and boys, the marriage condition may be satisfied with room to spare
or just barely. In the first case, there is enough room for the first girl to marry whomever she likes; the Hall's condition will still be satisfied for the remaining (n - 1) and (n - 1) boys.
Indeed, every 0 < r < n girls like more than r boys. One of those boys may have been the one who married the first girl - but without whom there are still at least r boys. So, after marrying off any eligible pair we shall be left with (n - 1) girls and boys for whom the *marriage condition* still holds and, by the inductive hypothesis, complete match is possible.

In the second case, there are r < n girls who like exactly r boys. By the inductive hypothesis, a complete match exists for these r girls so they can be married to the r boys they like. The trick is to show that the remaining girls can be matched to the remaining boys. Consider any s of the remaining n - r girls. The r married girls plus these s girls must like at least r + s boys as assured by Hall's condition. Since the r married girls don't like boys other than the r they married, the s girls must like s boys other than the married boys. Hence the remaining n - r girls satisfy the marriage condition with the unmarried boys; and so a complete match is possible for the remaining girls with the remaining boys, providing a complete match for all the girls.

Another proof based on the *Inclusion-Exclusion* principle deals directly with
subsets A_{1}, A_{2}, ..., A_{n} and establishes existence of an SDR. The *Inclusion-Exclusion* principle asserts that for any two finite sets A and B

|A∪B| + |A∩B| = |A| + |B|,

where vertical bars denote the cardinality (the number of elements) of a set.

## Proof #2

Assuming that the marriage condition holds for the sets A_{1}, A

_{2}, ..., A

_{n}, let the sets be depleted until a family F = {B

_{1}, B

_{2}, ..., B

_{n}} is reached such that removal of 1 more element from any of the B

_{i}would cause the marriage condition to be violated. We assert that each member of F consists of a single element; because these elements are distinct (by the marriage condition), F itself is the required SDR. Suppose, on the contrary, that, say B

_{1}has 2 elements, Let's say, B

_{1}contains at least two elements, x and y. By the minimality of the collection, removal of either x or y would violate the matching condition. Therefore, there exist two sets of indices P and Q such that

X = (B_{1}-{x})∪(∪{B_{i}: i∈P}) and Y = (B_{1}-{y})∪(∪{B_{i}: i∈Q})

with |X| ≤ |P| and |Y| ≤ |Q|.

Consequently, by the Inclusion-Exclusion priciple,

(*)

|X∪Y| + |X∩Y| = |X| + |Y| ≤ |P| + |Q|

On the other hand,

X∪Y = B_{1}∪(∪{B_{i}: i∈P∪Q}) and X∩Y = ∪{B_{i}: i∈P∩Q}

the marriage condition gives

|X∪Y| ≥ 1 + |P∪Q| and |X∩Y| ≥ |P∩Q|.

From here, with one more application of the Inclusion-Exclusion principle, we obtain

|X∪Y| + |X∩Y| ≥ 1 + |P∪Q| + |P∩Q| = 1 + |P| + |Q| > |P| + |Q|

which contradicts (*).

## References

- V.K.Balakrishnan,
*Theory and Problems of Combinatorics*, Schaum's Outline Series, McGraw-Hill, 1995 - O.Ore (with R.J.Wilson),
*Graphs and Their Uses*, MAA, New Math Library, 1990. - G.Strang,
*Introduction to Applied Mathematics*, Wellesley-Cambridge Press, MA, 1986.

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

Copyright © 1996-2018 Alexander Bogomolny