# Marriage Problem

MThe applet below is a simulation of the W. McWorter's algorithm. The following controls are available:

- You can manually swap rows, columns, or both. There are three radio buttons: r, c, and b to indicate the action of your choice. Click outside the board near the row/column you want to be swapped. Then, in the same manner, pick another row/column.
- You can instruct the applet to perform the next step of the algorithm by pressing Step.
- It will continue until finished if you press either Fast or Slow.
- Reset can be pressed at any time.
- The same is true of Log. Have it on if you want a logout of the steps.
- When you press reset the board is filled randomly. You may click on squares to toggle their value.
- You may take your steps back. Note, however, that some algorithmic steps do two swaps, some do only one. You may only take back one swap at a time.

What if applet does not run? |

Experimenting with the applet leads to several observations:

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.Start with the unit (diagonal) matrix: a

_{ij}= 1 iff i = j. This matrix has the property that there is just a single 1 in every column and every row. General matrices with this property are called*permutation matrices*. Such matrices appear in the Calendar Magic puzzle and the Rook Problem. The name*permutation matrices*is explained by the fact that such matrices supply an additional way to represent a permutation. Every permutation matrix encodes a solution to the marriage problem. The algorithm is blind to this fact. It attempts to construct a*transversal*of 1s, and results in the longest sequence of 1s that may be placed on the diagonal. Prove that, for a permutation matrix, the algorithm performs this task within the Greedy Phase.

|Contact| |Front page| |Contents| |Algebra| |Eye opener|

Copyright © 1996-2018 Alexander Bogomolny