It’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 and you wish to find distinct elements .  (In our solitaire example, take to be the values of the cards in the 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 , the set contains at least elements.  Hall’s theorem asserts that these conditions are also sufficient.

In the solitaire example, if we choose any piles, they contain cards between them.  Since there are only four cards of any given value, when we combine our chosen piles there must be at least 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 teams lasted for 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 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 boys be, collectively, acquainted with at least girls.  The equivalence of this result with the previously stated version is easy to see (let be the set of girls that the 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 of boys.  We quote directly from Halmos-Vaughn:

For the result is trivial.  If and if it happens that every set of boys, , has at least 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 boys, , has exactly acquaintances, then this set of may be married off by induction and, we assert, the remaining boys satisfy the necessary condition with respect to the as yet unmarried girls.  Indeed if , and if some set of bachelors were to know fewer than spinsters, then this set of bachelors together with the married men would have known fewer than girls.  An application of the induction hypothesis to the 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 be an matrix with entries in a field of characteristic zero.  We say that is generic if its nonzero entries are algebraically independent (i.e., they do not satisfy a nonzero polynomial with coefficients in ).

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

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

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

Proof: Let be the number of boys and let be the number of girls.  Let be a generic matrix with iff the girl is acquainted with the boy.  Using the standard formula for the determinant of a matrix as a sum over permutations, together with the genericity of , we see that there is a happy marriage if and only if the determinant of some minor of is nonzero, which happens if and only if has rank at least .  Suppose for the sake of contradiction that the rank of is less than .  Without loss of generality, we may assume (by permuting the rows and columns if necessary) that is in Edmonds Normal Form.  Since the columns of are linearly dependent, there exists a nonzero vector in the kernel of .  By Gaussian Elimination, we can assume that the coordinates of are polynomials in the nonzero entries of .  By property (a) of the ENF, no entry of can be zero.  And by property (b), each row of is orthogonal to .  As is generic, it follows that   But then the set of boys corresponding to the first columns is acquainted with only the girls corresponding to the first 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 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 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 of boys is infinite, consider for each the set of his acquaintances, topologized by the discrete topology, so that is a compact Hausdorff space.  Write for the topological Cartesian product of all ; by Tychonoff’s theorem is compact.  If is any finite set of boys, consider the set of all those elements of for which whenever , .  The set is a closed subset of and, by the result for the finite case, is not empty.  Since a finite union of finite sets is finite, it follows that the class of all sets such as has the finite intersection property and, consequently, has a non-empty intersection.  Since an element in this intersection is such that whenever , 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 is a finite group and is a subgroup of index , show that there exist elements such that there is exactly one in each left coset of and exactly one in each right coset.

3. Richard Rado proved the following important extension of Hall’s theorem to matroids:  Let be a family of subsets of a finite set , indexed by a set , and let be a matroid on .  Then there is a transversal consisting of independent elements if and only if has rank at last for every .  As a sample consequence, if are subsets of an -dimensional vector space such that for all subsets , then has a basis with for all .

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 has a perfect matching if and only if, for every subset of vertices, the induced subgraph on the complement of has at most connected components with an odd number of vertices.  One can think of the Tutte theorem as encompassing a broader definition of ‘marriage’.