Marriage Theorem, Solutions to Problems

Problem # 1

Consider a matrix with 1s in squares next to the diagonal and 0s everywhere else, a_ij = 1 iff |i - j| = 1, and a_ij = 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 (n-1)/2 < (n+1)/2. The n even case shows that a maximal matching with only one girl going unmarried exists for n odd.

Solution #2 (by W.McWorter)

The problem can also be solved by row and column changes. For n > 0 even, interchange rows 2i-1 and 2i, for i = 1, ..., n/2. The main diagonal is now all 1's. For n>1 odd, do the same thing. Interchange rows 2i-1 and 2i, for i = 1, ..., (n-1)/2. You get the picture

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.

Solution #3

We may apply induction. Depending on the parity of n induction starts either with n = 1 or 2. For the inductive step, match girls {1, 2} with boys {1, 2}. Remove the columns 1, 2 and rows 1, 2. What remains is a matrix of exactly the same kind (bidiagonal) with the order reduced by 2.

Solution #4

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.

Latin Squares