AlgoVerse

Orthogonal Latin squares

For a prime n, build two n × n Latin squares with the formula (a·i + j) mod n that are orthogonal: laid on top of each other, every ordered pair of symbols appears exactly once. Used in experimental design.

An n × n Latin square is a grid in which each of n symbols appears exactly once in every row and every column. Two Latin squares are orthogonal if, laid on top of each other, every ordered pair (x, y) of symbols appears exactly once.

Read the full explanation ↓
Input:
n=5 · a=1 · b=2PDF export

Two 5 × 5 Latin squares with a = 1 and b = 2; each of the 25 pairs (00 to 44) appears exactly once.

  1. def orthogonal_latin(n, a, b):
  2. # For a prime n, L_a[i][j] = (a·i + j) mod n is a Latin square for each a = 1..n-1, and two of them with
  3. # different a are orthogonal: laid on top of each other, every ordered pair of symbols appears exactly once.
  4. for d in range(2, n):
  5. if n % d == 0:
  6. return None
  7. if a % n == 0 or b % n == 0 or (a - b) % n == 0:
  8. return None
  9. A = [["·"] * n for _ in range(n)]
  10. B = [["·"] * n for _ in range(n)]
  11. P = [["·"] * n for _ in range(n)] # the two squares superposed
  12. for i in range(n):
  13. for j in range(n):
  14. A[i][j] = (a * i + j) % n
  15. B[i][j] = (b * i + j) % n
  16. P[i][j] = str(A[i][j]) + str(B[i][j])
  17. seen = []
  18. for i in range(n):
  19. for j in range(n):
  20. if P[i][j] in seen:
  21. return False
  22. seen.append(P[i][j])
  23. return True

Invariant: Each symbol appears once in every row and column of A (and B), since a·i + j runs through every residue as j or i varies.

Start

A

The table is still empty.

B

The table is still empty.

P

The table is still empty.

Local variables

n5
a1
b2

Orange = changed in this step

Call stack

  1. orthogonal_latin()line 1
Step 1 of 211
Black = cell · Orange = key stepcell: 0/25 · orthogonal: 0/1
    Explanation

    Latin squares

    An n × n Latin square is a grid in which each of n symbols appears exactly once in every row and every column. Two Latin squares are orthogonal if, laid on top of each other, every ordered pair (x, y) of symbols appears exactly once.

    Building them for a prime n

    If n is prime, then for each a from 1 to n − 1

    L_a[i][j] = (a·i + j) mod n

    is a Latin square, and L_a and L_b with a ≠ b are orthogonal: if the pair (L_a[i][j], L_b[i][j]) were equal in two cells, subtracting the equations gives (a − b)·(i − i') ≡ 0, and since n is prime, i = i' and then j = j'. So there are n − 1 mutually orthogonal squares (prime powers work too, with a finite field).

    History

    Euler guessed that no two orthogonal squares exist for n ≡ 2 (mod 4). It holds for n = 6 (the 36 officers problem), but in 1959 such squares were shown to exist for every other n except 2 and 6.

    The input

    n is the size (prime here), and a and b two different multipliers. The third table shows the two squares on top of each other.