# Do successive maximum permutations pick latin squares uniformly?

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?

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

• The less probable cases seem to have reflective and rotational symmetry. Will check. – yberman Mar 8 '17 at 7:20
• Thank you for running this. I thought I had an argument that the distribution was uniform for n=4, but now I'm not so sure. It'd be nice to know what exactly is the distribution for n=4. – Gjergji Zaimi Mar 8 '17 at 19:34
• The six less probable ones all have the property that for each pair $0\le i<j\le 3$, the entries i and j come in two 2x2 latin subsquares. So those 6 squares have indeed a kind of symmetry the others haven't. (In terms of Janne Kokkala's answer, the sub-pattern B never occurs in them.) – Wolfgang Mar 20 '17 at 14:49

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.

• Once the first permutation of the four 1's is chosen, wlog putting them in the main diagonal, there are 9 ways of choosing the 2's: 3 of them produce a pattern of type A, but 6 a pattern B. Now obviously, the original way of obtaining the permutations by the 0-1-sampling gives them different probabilities which cannot be compared with these ones. And of course A and B simply represent the 2 existing isomorphy types of 4x4 latin squares (Klein 4-group vs. $\mathbb Z_4$). – Wolfgang Mar 20 '17 at 19:43