A simple proof of Hall’s Theorem

A simple proof of Hall's Theorem

This note presents Hall's Theorem and its proof in an almost visual terminology, whose only defence is that it enabled me to design this proof without pen and paper, while still in bed on an early Sunday morning.

Take a matrix of 0s and 1s with N rows. We say that a set of rows cover a certain column iff at least one row of the set contains a 1 in that column. A matrix is called happy iff, for any n (n≤N), any n-tuple of its rows covers at least n distinct columns. Hence (i) for N=0 the matrix is happy, and a happy matrix (ii) has no row of 0s only, (iii) has at least N columns, and remains happy if (iv) a row is taken away, (v) an all-0 column is taken away, or (vi) a 0 is turned into a 1.

Hall's Theorem states that in a happy matrix the columns can be ordered in such a way that condition H is met, viz. for each row index i , the ith row has a 1 in the ith column.

Remark Above statement of the theorem refers to "the ith row", which is ugly be-

cause overspecific: the order of the rows is irrelevant in the sense that subjecting the rows and the equal number of leftmost columns to the same permutation transforms a matrix meeting condition H into a matrix that still satisfies H. Peccavi. (End of Remark.)

We prove Hall's Theorem (which is an existence theorem) by displaying an algorithm that, given a happy matrix of $N$ rows, rearranges its rows and columns in such a way that condition $H$ is met. Because for $N = 0$ condition $H$ is met, we can confine our attention to happy matrices with $N > 0$ .

Since such a matrix contains at least one 1, we can select a 1 and remove it - i.e. replace it by a (pink) 0 - if the resulting matrix is still happy. We do so repeatedly until -and that moment comes! we have selected a 1 whose removal would transform a happy matrix into an unhappy one. More specifically this means that the selected element x oc-curs in some k-tuple of rows such that with $x = 1$ , the k-tuple covers at

least $k$ columns,while with $x = 0$ ,that $k$ -tuple covers less than $k$ columns. Since the transition from $x = 1$ to $x = 0$ reduces coverages by at most one,we conclude

(0) the number of columns covered by the $k$ -tuple equals $k$ if $x = 1$ ,and equals $k - 1$ if $x = 0$

We now distinguish two cases.

$k = N$ by permuting rows and columns, we move $x$ to the top-left corner:

Because removal of the 1 at x would reduce the coverage of the whole matrix, the truncated column A consists of os only. Therefore, the set of columns covered by an n-tuple of rows from B remains the same when the rows are extended with their element from A; consequently the happiness of the whole matrix implies that B is happy. The

algorithm is applied recursively to matrix $\mathbf{B}$ ,which has only $N - 1$ rows.

we move the rows of $k$ -tuple to the top and the k columns they cover to the left:

Element x occurs in C . Since (0) states that the k top rows cover the k left columns and nothing more, submatrix D consists of 0s only. We can now conclude the happiness of C and E as follows.

Because the whole matrix is happy, so is the top part formed by $C$ and $D$ , but since $D$ , consisting of 0s only, does not contribute to the coverage, $C$ is happy, all by itself.

To establish the happiness of $E$ ,we consider an n-tuple of rows from the lower part formed by $F$ and $E$ ,and extend this n-tuple with the k rows of the top part. Because

the whole matrix is happy, these $n + k$ rows cover at least $n + k$ columns, at least $n$ of which lie in the right-hand part formed by $D$ and $E$ . Since $D$ consists of 0s only, these $n$ or more columns are covered via 1s in the $E$ -part of the $n$ -tuple of rows, hence $E$ is happy. The algorithm is now applied recursively to matrices $C$ and $E$ , both of which have fewer than $N$ rows.

And this concludes my proof of Hall's Theorem.

I thank Jayadev Misra for drawing my attention to the theorem and for suggesting later that my first proof (in which the two above partitions of the matrix were combined) could be simplified.

Austin, 3 January 1998

prof. dr Edsger W. Dyrkstra Department of Computer Sciences The University of Texas at Austin Austin, TX 78712-1188 USA