Marriage Theorem, Solutions to Problems
Problem # 1
Consider a matrix with 1s in squares next to the diagonal and 0s everywhere else, aij = 1 iff |i - j| = 1, and aij = 0, otherwise. Prove that if n, the size of the matrix, is even, the complete match possible. The complete match is impossible if n is odd.
Solution #1 (by W.McWorter)
For n even, the matrix contains a diagonal of blocks of 2 by 2 permutation matrices. The 1's in these matrices make a complete matching. For n odd, the (n+1)/2 columns with odd indices together only contain 1's from the (n-1)/2 rows with even indices. Hence the marriage condition is violated because
Solution #2 (by W.McWorter)
The problem can also be solved by row and column
1 0 1 0 0 1 0 . . . . . . . . . . 0 1 0 1 0 . . 1 0 1 0 0 . . 0 1 0
None of the 1's below the main diagonal correspond to a 1 in the last column, so no way for the algorithm to get a 1 to percolate (from under the G submatrix) into the lower right corner. Hence there is no complete matching.
We may apply induction. Depending on the parity of n induction starts either with
Apply Konig's Theorem: The minimal number of lines that could be drawn through all the 1s equals the maximal number of marriages that can be arranged. For a 3×3 matrix one only needs 2 lines - through 2nd column and row. By induction, as before, for a (2n+1)×(2n+1) matrix, it will take only 2n lines to cover all 1s.
Copyright © 1996-2018 Alexander Bogomolny