# 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

#### Solution #2 (by W.McWorter)

The problem can also be solved by row and column
changes. For

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

#### 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.

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny