Given a Latin square of order $n$, we define a diagonal as $n$ cells, no two of which lie in the same row or column. If you had $n$ non-attacking rooks placed on the grid, you’d have a diagonal. The main diagonal is defined to be the cells (row $i$, column $i$) for $1 \leq i \leq n$.
A transversal is a diagonal in which all of the symbols are distinct. For example, the red squares below are a transversal of this Latin square of order 9.
| 7 |
6 |
3 |
4 |
2 |
1 |
8 |
9 |
5 |
| 3 |
5 |
6 |
2 |
4 |
7 |
1 |
8 |
9 |
| 2 |
4 |
8 |
7 |
6 |
9 |
5 |
3 |
1 |
| 4 |
8 |
2 |
1 |
3 |
5 |
9 |
6 |
7 |
| 8 |
3 |
7 |
9 |
5 |
6 |
2 |
1 |
4 |
| 1 |
2 |
5 |
3 |
9 |
8 |
4 |
7 |
6 |
| 5 |
9 |
1 |
6 |
7 |
2 |
3 |
4 |
8 |
| 6 |
1 |
9 |
5 |
8 |
4 |
7 |
2 |
3 |
| 9 |
7 |
4 |
8 |
1 |
3 |
6 |
5 |
2 |
It is easy to show that every Latin square of order $n$ has $n!$ diagonals. However, the number of transversals is not so easy to calculate; this is because a pair of different (i.e. not main class equivalent) Latin squares of order $n$ can have a different number of transversals.
Picking a transversal uniformly at random from a square of size $n$, isn’t an issue. To do this, just generate a random permutation; if it’s a transversal keep it, otherwise throw it away and generate another one. However, I like Markov chains, so I thought I’d describe how to do it by perturbing diagonals.
Begin by picking any diagonal you like; the main diagonal will do. Now repeat the following move, which we shall call a “flip”:
- Pick two cells on your diagonal, say $(r, c, s)$ (i.e. row r, column c contains symbol s) and $(r’,c’,s’)$.
- Find $u$ and $v$ such that $(r’,c,u)$ and $(r,c’,v)$ exist.
- With probability 1/2 STOP. Otherwise, add $(r’,c,u)$ and $(r,c’,v)$ to the diagonal and remove $(r,c,s)$ and $(r’,c’,s’)$ and then STOP.
For example, suppose I have the following square and diagonal:
| 1 |
2 |
3 |
4 |
| 2 |
3 |
4 |
1 |
| 3 |
4 |
1 |
2 |
| 4 |
1 |
2 |
3 |
If I picked the cells (row 1, column 1), (row 3, column 3) in step 1 of the flip, with probability $1/2$, I would result in the following configuration:
| 1 |
2 |
3 |
4 |
| 2 |
3 |
4 |
1 |
| 3 |
4 |
1 |
2 |
| 4 |
1 |
2 |
3 |
Claim
Performing the flip takes a random walk on a regular, non-bipartite, finite, connected, undirected graph.
If this claim is true, then it is well known that the flip is a Markov chain with a unique stationary distribution, which is equal to the uniform distribution.
Remark: Before proving this claim, we remark that every diagonal can be represented as a permutation $\pi$ by saying that row $i$, column $\pi(i)$ is contained on our diagonal. Also, notice that the flip move amounts to multiplying $\pi$ by a transposition, and every transposition can be applied from any state.
Proof
Regular: The number of moves from any state is just the number of transpositions, which is always $n \choose 2$.
Non-bipartite: With probability $1/2$, the flip move returns you to the same position you started with, so every state has a loop.
Finite: there are only $n!$ possible states.
Undirected: The flip is immediately reversible; to reverse the effect of applying the transposition $q$, simply apply the transposition $q$ again.
Connected: Let $\rho$ and $\pi$ be the permutations representing any arbitrary states. There is some permutation $\mu$ such that $\pi\mu = \rho$ . Therefore we decompose $\mu$ in to a product of transposition and for each transposition, apply the corresponding flip move.
So this Markov chain really does converge to the uniform distribution, but how many flips do we have to make before the approximation is good enough? Coupling is probably the answer here – that is, have two squares of the same size and find a diagonal in each of them. If the diagonals are not in the same location, toss a coin apply the flip move to the first square if the coin yields a head, otherwise, apply the move to the second square. The coupling time is the time it takes for the diagonals to first coincide.
Anyway, as I already said – you’d probably never want to use this method, because generating a random permutation is exactly the uniform distribution, but this is a fun toy anyway.
