Do successive maximum permutations pick latin squares uniformly?

Question

Suppose we start with a $n\times n$ matrix with entries sampled independently and uniformly at random from $[0,1]$. The weight of a set of entries will simply be the sum of those entries. A permutation refers to a set of $n$ entries, no two on the same row or column.

Pick a permutation whose corresponding entries have the largest weight, and place a label "1" in all those entries. Proceed to erase the values of those entries. At step k, pick a permutation from the remaining entries with largest weight and place a label "k" in all the selected entries.

This procedure ends with an $n\times n$ latin square. Do all latin squares appear with the same probability?

Answer 1

I wanted to point out that there seems to be biases even in the set it does generate (regardless if that is all that is possible). I know this is not a proof (and therefore not an answer), but I think it might help someone else who is going to attack the problem. I ran a simulation in python for $n = 4$. Results represent the set of permutations of size $n$ that constitute the latin square and the number of times they turned up out of 100000. There are 24 which makes sense once you mod out relabelling from the 576 latin squares ($24 = 576 / 4!$)

    frozenset([(1, 3, 0, 2), (0, 2, 1, 3), (3, 0, 2, 1), (2, 1, 3, 0)]) 5021
    frozenset([(2, 3, 1, 0), (0, 1, 3, 2), (1, 0, 2, 3), (3, 2, 0, 1)]) 1817
    frozenset([(0, 3, 1, 2), (1, 2, 0, 3), (3, 0, 2, 1), (2, 1, 3, 0)]) 1748
    frozenset([(0, 1, 3, 2), (3, 2, 1, 0), (2, 3, 0, 1), (1, 0, 2, 3)]) 4938
    frozenset([(3, 0, 1, 2), (0, 3, 2, 1), (1, 2, 0, 3), (2, 1, 3, 0)]) 5069
    frozenset([(3, 1, 2, 0), (2, 3, 0, 1), (0, 2, 1, 3), (1, 0, 3, 2)]) 4958
    frozenset([(3, 0, 1, 2), (1, 2, 3, 0), (2, 3, 0, 1), (0, 1, 2, 3)]) 4903
    frozenset([(3, 0, 1, 2), (2, 1, 0, 3), (0, 3, 2, 1), (1, 2, 3, 0)]) 1835
    frozenset([(0, 1, 3, 2), (1, 2, 0, 3), (3, 0, 2, 1), (2, 3, 1, 0)]) 4941
    frozenset([(1, 3, 0, 2), (2, 0, 3, 1), (3, 1, 2, 0), (0, 2, 1, 3)]) 1795
    frozenset([(1, 3, 0, 2), (2, 0, 1, 3), (3, 1, 2, 0), (0, 2, 3, 1)]) 4962
    frozenset([(3, 1, 0, 2), (2, 0, 3, 1), (1, 3, 2, 0), (0, 2, 1, 3)]) 4974
    frozenset([(1, 3, 2, 0), (3, 1, 0, 2), (2, 0, 1, 3), (0, 2, 3, 1)]) 1759
    frozenset([(1, 0, 3, 2), (2, 3, 1, 0), (3, 2, 0, 1), (0, 1, 2, 3)]) 4958
    frozenset([(1, 0, 3, 2), (2, 3, 0, 1), (3, 2, 1, 0), (0, 1, 2, 3)]) 1817
    frozenset([(1, 2, 3, 0), (0, 3, 1, 2), (2, 1, 0, 3), (3, 0, 2, 1)]) 4826
    frozenset([(3, 1, 2, 0), (2, 0, 3, 1), (0, 3, 1, 2), (1, 2, 0, 3)]) 4980
    frozenset([(1, 3, 0, 2), (2, 0, 3, 1), (3, 2, 1, 0), (0, 1, 2, 3)]) 4933
    frozenset([(1, 3, 2, 0), (0, 1, 3, 2), (2, 0, 1, 3), (3, 2, 0, 1)]) 4995
    frozenset([(3, 0, 1, 2), (2, 1, 0, 3), (1, 3, 2, 0), (0, 2, 3, 1)]) 4857
    frozenset([(2, 1, 3, 0), (0, 3, 1, 2), (1, 0, 2, 3), (3, 2, 0, 1)]) 4941
    frozenset([(1, 2, 3, 0), (3, 1, 0, 2), (2, 0, 1, 3), (0, 3, 2, 1)]) 4958
    frozenset([(3, 2, 1, 0), (2, 1, 0, 3), (1, 0, 3, 2), (0, 3, 2, 1)]) 4936
    frozenset([(3, 1, 0, 2), (2, 3, 1, 0), (1, 0, 2, 3), (0, 2, 3, 1)]) 5079 

In particular these don't do as well:

frozenset([(2, 3, 1, 0), (0, 1, 3, 2), (1, 0, 2, 3), (3, 2, 0, 1)]) 1817
frozenset([(0, 3, 1, 2), (1, 2, 0, 3), (3, 0, 2, 1), (2, 1, 3, 0)]) 1748
frozenset([(3, 0, 1, 2), (2, 1, 0, 3), (0, 3, 2, 1), (1, 2, 3, 0)]) 1835
frozenset([(1, 3, 0, 2), (2, 0, 3, 1), (3, 1, 2, 0), (0, 2, 1, 3)]) 1795
frozenset([(1, 3, 2, 0), (3, 1, 0, 2), (2, 0, 1, 3), (0, 2, 3, 1)]) 1759
frozenset([(1, 0, 3, 2), (2, 3, 0, 1), (3, 2, 1, 0), (0, 1, 2, 3)]) 1817

I am curious why they are different. Here is the code that produced it

from random import random, shuffle
from itertools import permutations

N = 4
DEBUG = False

def score(matrix):
    '''Used to score a permutation in a current matrix'''
    def helper(perm):
        s = 0
        for i in range(N):
            s = s + matrix[i][perm[i]]
        return s
    return helper

def compatible(partial_lat_sq, perm):
    '''You don't want a perm which interferes with existing perms'''
    for perm2 in partial_lat_sq:
        for i in range(N):
            if perm[i] == perm2[i]:
                return False
    return True

result = {}
# here is the experiment
for experiment_number in xrange(100000):
    lat_sq = []
    s_n = list(tuple(p) for p in permutations(range(N)))
    matrix = [[random() for c in range(N)] for r in range(N)]
    while len(lat_sq) < N:
        shuffle(s_n)
        s_n = sorted(s_n, key=score(matrix), reverse=True) # perms sorted by matrix, big first
        for perm in s_n
            if compatible(lat_sq, perm):
                lat_sq.append(perm)
                for i in range(N):
                    matrix[i][perm[i]] = 0
                if DEBUG:
                    print 'Lat Sq.', lat_sq
                    print 'Matrix', matrix
                break
    lat_sq = frozenset(lat_sq)
    result[lat_sq] = 1 + result.get(lat_sq, 0)

for k, v in sorted(result.items()):
    print k, v

Answer 2

Studying the results given in YBerman's answer gave me the following. Consider these two possibilities after drawing two symbols (in order) for $n=4$:

$$ \begin{align*} A &= \begin{pmatrix} 1 & 2 & . & . \\ 2 & 1 & . & . \\ . & . & 1 & 2 \\ . & . & 2 & 1 \end{pmatrix}, & B &= \begin{pmatrix} 1 & 2 & . & . \\ . & 1 & 2 & . \\ . & . & 1 & 2 \\ 2 & . & . & 1 \end{pmatrix} \end{align*} $$

(Up to permutation of rows and columns, which doesn't change the probability distribution, any square with two symbols is equivalent to one of these.)

The square $A$ can be completed to $4$ different Latin squares, and $B$ can be completed to $2$ different Latin squares. So the probability of $A$ should be twice the probability of $B$. However, out of 10,000,000 trials, $A$ occurred 35,581 times and $B$ occurred 51,481 times.

So "almost surely" this is a counterexample, but I don't know if there's a simple proof for that.