The Mathematics of Marriage

linking-wedding-ringsIt’s been a while since my last blog post — one reason being that I recently got married.  In honor of that occasion, and my return to math blogging, here is a post on Hall’s Marriage Theorem.

Consider the following game of solitaire: you deal a deck of cards into 13 piles of 4 cards each, and your goal is to select one card from each pile so that no value (Ace through King) is repeated.  It is a beautiful mathematical fact that this can always been done, no matter how the cards were originally dealt!

We will deduce this from a more general result due to Philip Hall commonly known as Hall’s Marriage Theorem.  Suppose you are given finite sets A_1, A_2,\ldots, A_n and you wish to find distinct elements x_1 \in A_1,\ldots, x_n \in A_n.  (In our solitaire example, take A_j to be the values of the cards in the j^{\rm th} pile.)  Such a collection is called a transversal or SDR (system of distinct representatives).  Under what conditions is this possible?  Well, for a transversal to exist it is necessary that for each subset J \subset \{ 1,\ldots, n \}, the set A_J:= \bigcup_{j \in J} A_j contains at least \#J elements.  Hall’s theorem asserts that these conditions are also sufficient.

In the solitaire example, if we choose any k piles, they contain 4k cards between them.  Since there are only four cards of any given value, when we combine our chosen piles there must be at least k different values.  Thus Hall’s conditions are satisfied and the Marriage Theorem implies that we can always win.

As another example, consider the following problem whose solution becomes much simpler with Hall’s Marriage Theorem in hand:

[2012 Putnam Exam Problem B-3] A round-robin tournament of 2n teams lasted for 2n-1 days, as follows.  On each day, every team played one game against another team, with one team winning and one team losing in each of the n games. Over the course of the tournament, each team played every other team exactly once. Can one necessarily choose one winning team from each day without choosing any team more than once?

Hall’s result is known as the marriage theorem because it can be reformulated in the following way.  Suppose that each of a finite set of boys is acquainted with a finite set of girls.  Under what conditions is it possible for each boy to marry one of his acquaintances?  The answer is that it is necessary and sufficient that every finite set of k boys be, collectively, acquainted with at least k girls.  The equivalence of this result with the previously stated version is easy to see (let A_j be the set of girls that the j^{\rm th} boy is acquainted with).

The simplest proof of Hall’s theorem which I know first appeared in a lovely 2-page paper by Halmos and Vaughan, and proceeds by induction on the number n of boys.  We quote directly from Halmos-Vaughn:

For n=1 the result is trivial.  If n>1 and if it happens that every set of k boys, 1 \leq k < n, has at least k+1 acquaintances, then an arbitrary one of the boys may marry any one of his acquaintances and refer the others to the induction hypothesis.  If, on the other hand, some group of k boys, 1 \leq k < n, has exactly k acquaintances, then this set of k may be married off by induction and, we assert, the remaining n-k boys satisfy the necessary condition with respect to the as yet unmarried girls.  Indeed if 1 \leq h \leq n-k, and if some set of h bachelors were to know fewer than h spinsters, then this set of h bachelors together with the k married men would have known fewer than k+h girls.  An application of the induction hypothesis to the n-k bachelors concludes the proof.

There is another beautiful proof of Hall’s theorem, due to Jack Edmonds, which is based on linear algebra.  It is a nice example of the use of algebraic techniques for solving combinatorial problems.  Before we give Edmonds’ proof, we need two definitions:

Definition: Let B be an m \times n matrix with entries in a field F of characteristic zero.  We say that B is generic if its nonzero entries are algebraically independent (i.e., they do not satisfy a nonzero polynomial with coefficients in {\mathbf Q}).

Definition: Let B be an m \times n matrix with rank r < n.  We say that B is in Edmonds Normal Form (ENF) if it can be written in block form with the upper-left block B_1 an r \times (r+1) matrix such that (a) the first r+1 columns of B form a minimal linearly dependent set, and (b) each row of the lower-left block B_2 is a linear combination of the rows of B_1.

Untitled

It is easy to see that every m \times n matrix B with rank r < n can be put in ENF by permuting the rows and columns.  Indeed, by permuting the columns, we may assume that the first r+1 of them form a minimal linearly dependent set.  The submatrix B' determined by the first r+1 columns has rank r, so by permuting the rows we may assume that the first r rows form a basis for the row space of B'.  The resulting matrix is in ENF.

We can now give Edmonds’ proof of Hall’s theorem:

Proof: Let n be the number of boys and let m be the number of girls.  Let B be a generic m \times n matrix with B_{ij} \neq 0 iff the i^{\rm th} girl is acquainted with the j^{\rm th} boy.  Using the standard formula for the determinant of a matrix as a sum over permutations, together with the genericity of B, we see that there is a happy marriage if and only if the determinant of some n \times n minor of B is nonzero, which happens if and only if B has rank at least n.  Suppose for the sake of contradiction that the rank r of B is less than n.  Without loss of generality, we may assume (by permuting the rows and columns if necessary) that B is in Edmonds Normal Form.  Since the columns of B_1 are linearly dependent, there exists a nonzero vector v in the kernel of B_1.  By Gaussian Elimination, we can assume that the coordinates of v are polynomials in the nonzero entries of B_1.  By property (a) of the ENF, no entry of v can be zero.  And by property (b), each row of B_2 is orthogonal to v.  As B is generic, it follows that B_2 = 0.  But then the set of boys corresponding to the first r+1 columns is acquainted with only the girls corresponding to the first r rows, a contradiction.

The linear algebra proof might seem like overkill given how simple the combinatorial proof was.  But it actually has some intriguing features: for example, the determinental interpretation leads to an efficient probabilistic algorithm to test whether there is a transversal.  (For this, it is convenient to think of the nonzero entries of B as indeterminates.)  The above proof reduces the problem to calculating whether or not certain polynomials are nonzero.  Now it is computationally infeasible to explicitly compute the sub-determinants of B as polynomials, but if we substitute specific values for the indeterminates we can efficiently determine whether the corresponding evaluation is nonzero modulo some suitable large prime.  If one uses fast matrix multiplication to compute the determinants, this yields the asypmtotically fastest-known probabilistic algorithm for determining whether the marriage problem has a solution.  (In practice, however, there are deterministic algorithms which are much faster, and which find the matching as well.)

Finally, we would like to mention that Hall’s theorem can be extended to the case where there are infinitely many boys (but the number of girls acquainted with each boy must still be finite).  This generalization is due to Everett and Whaples.  We can again do no better than to quote the “proof from the book” by Halmos and Vaughn, which uses point-set topology to reduce to the finite case:

If the set B of boys is infinite, consider for each b \in B the set G(b) of his acquaintances, topologized by the discrete topology, so that G(b) is a compact Hausdorff space.  Write G for the topological Cartesian product of all G(b); by Tychonoff’s theorem G is compact.  If \{ b_1,\ldots,b_n \} is any finite set of boys, consider the set H of all those elements g = g(b) of G for which g(b_i) \neq g(b_j) whenever b_i \neq b_j, i,j=1,\ldots,n.  The set H is a closed subset of G and, by the result for the finite case, H is not empty.  Since a finite union of finite sets is finite, it follows that the class of all sets such as H has the finite intersection property and, consequently, has a non-empty intersection.  Since an element g = g(b) in this intersection is such that g(b') \neq g(b'') whenever b' \neq b'', the proof is complete.

Concluding Remarks:

1. The 1950 paper of Halmos and Vaughan, entitled “The Marriage Problem”, is reproduced in the book “Classic Papers in Combinatorics” (edited by Gessel and Rota), as is Hall’s original paper.  Edmonds’ 1967 paper is called “Systems of Distinct Representatives and Linear Algebra”.  My exposition of Edmonds’ proof was influenced by this paper.  The comments above about determinants and algorithmic aspects of the marriage problem are adapted from the book “Thirty-three miniatures” by Jiri Matousek.  That book contains some interesting examples of linear algebraic proofs of combinatorial results.

2. A solution to the above Putnam Problem can be found here.  If you enjoyed that problem, here is another fun exercise based on Hall’s theorem: If G is a finite group and H is a subgroup of index n, show that there exist elements g_1,\ldots,g_n \in G such that there is exactly one g_i in each left coset of H and exactly one in each right coset.

3. Richard Rado proved the following important extension of Hall’s theorem to matroids:  Let A_i be a family of subsets of a finite set S, indexed by a set I, and let M be a matroid on S.  Then there is a transversal consisting of independent elements if and only if A_J has rank at last \# J for every J \subseteq I.  As a sample consequence, if A_1,\ldots,A_n are subsets of an n-dimensional vector space V such that {\rm dim} \; {\rm span} A_J \geq \# J for all subsets J \subseteq \{ 1,\ldots, n \}, then V has a basis \{ a_1,\ldots, a_n \} with a_i \in A_i for all i.

4. There is a version of Hall’s Marriage Theorem for hypergraphs due to Aharoni and Haxell which, in particular, gives a new proof of Hall’s theorem based on Sperner’s Lemma (which itself is equivalent to the Brouwer Fixed Point Theorem in topology).  See this blog post by Gil Kalai for more information.

5. There are several famous results in combinatorics which are all “equivalent”, in the sense that there is a relatively simple argument showing that each implies the other.  These include Hall’s Marriage Theorem, Dilworth’s Theorem, the Max-Flow Min-Cut Theorem, and Menger’s Theorem.  A feature shared by each of these results is that some obviously necessary condition turns out to be sufficient.  See for example these slides.

6. Some of my other favorite mathematical problems related to “marriage” are the Stable Marriage Problem and the Fussy Suitor Problem.

7. Hall’s Theorem plays a prominent role in this paper of Zur Izhakian and Louis Rowen on supertropical matrix algebra.

8. Hall’s Marriage Theorem can be interpreted as giving necessary and sufficient conditions for the existence of a perfect matching in a bipartite graph.  Tutte proved the following generalization to arbitrary, not necessarily bipartite graphs: a graph G has a perfect matching if and only if, for every subset U of vertices, the induced subgraph on the complement of U has at most \# U connected components with an odd number of vertices.  One can think of the Tutte theorem as encompassing a broader definition of ‘marriage’.

One thought on “The Mathematics of Marriage

  1. Pingback: The Mathematics of Marriage | mathbeauty

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s