Marriage Problem

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

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.

71547168