Hall's Theorem

In 1935, the mathematician Philip Hall discovered a criteria of a perfect matching on a bipartite graph, known as Hall’s theorem, aka marriage theorem.

Considering two sets of vertices, denoted as A=\{a_1, \cdots, a_m\} and B=\{b_1, \cdots, b_n\}. Edges are connected between a_i and b_j for some pairs of (i, j). Here, we admit multiple edges between two vertices. This graph, named as G, is called a bipartite graph. One may think the bipartite graph as a model of a marriage system. Taken set A and set B as boys and girls, an edge between a boy and a girl tells that they might be a couple. A natural question arises that whether there exists a perfect matching, that is, every boy can find his girl without conflicting with other boys. Put formally, a perfect matching is an injective map from A to B which induces a subgraph of G.

Hall’s theorem asserted that there is a perfect matching in above bipartite graph G if and on if for every subsets S of A, the cardinal number of S(number of the members in a set) does not exceed the number of the neighbors of S. Here, the neighbors of S are all vertices in B which are connected with one vertex in S.

The necessary condition apparently holds. On the other hand, the proof of the sufficient part is a little bit tricky. Challenge yourself with this problem.

Now we represent several applications of Hall’s theorem.

• Let A=(a_{ij}) be a matrix of order n with nonnegative integers as entries, such that every row and column of A has sum l. Then A is the sum of l permutation matrices.
• Suppose all vertices of a directed graph G have the same in-degrees and out-degrees of l, a fixed positive integer. Thus the graph can be separated as l groups of circles. Every vertex appears exactly once in each group, and each edge appears in only one circle.
• (Birkhoff-von Neumann theorem) A doubly stochastic matrix, is a square matrix of nonnegative real numbers, each of whose rows and columns sums to 1. Assertion: every doubly stochastic matrix is mere a convex combination of permutation matrices.

The first two questions are equivalent with each other if one noticed the relation between a graph and its adjacent matrix. In addition, in the first problem, we construct a bipartite graph G consisting of 2n vertices, u_1, \cdots, u_n and v_1, \cdots, v_n and a_{ij} edges between each pair of vertices u_i and v_j. It can be easily verified that this graph meets the condition required in Hall’s theorem through contradictory argument. Thus we get a perfect matching in this graph, which conversely represent a permutation matrix. After Eliminating the perfect matching in this graph, it become to the situation of l-1 in-degrees and out-degrees. This allows us to use mathematical induction on the parameter l.

If the entries of the matrix are all rational in the third problem, the result is reduced to the first problem. Still, we shall cover the gap between rational numbers and reals. Denote all permutation matrix as M_1, \cdots, M_{n!}. For each matrix (a_{ij}) meets the requirement that the sum of each row or each column is 1, one can approach it by (a_{ij}^n) with rational entries which is also doubly stochastic. Thus we can decompose the rational matrix (a_{ij}^n) into a convex combination of permutation matrices with rational coefficient c_k^n, where k \in \{1, \cdots, n!\}. By finding convergent subsequence in each (c_k^n)_{n=1}^\infty, one can require that all these subsequences are convergent for the same indices, and they converge to a limit c_k. After all, the original matrix (a_{ij}) can be expressed as a convex combination of permutation matrices with coefficients c_k.