The complete match is impossible if n is odd. 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. Alexander Bogomolny 2412897 .