Can we find two mutually orthogonal diagonal latin squares of orders $4$ and $8$? A diagonal Latin square is a Latin square of order $n$ where the symbols $1$ thru $n$ fil both the forward diagonal and the back diagonal? It'd be great if you could show me the actual MOLS as well as the methodology.
[Math] Can we find two mutually orthogonal diagonal latin squares of orders $4$ and $8$
combinatoricslatin-square
Related Solutions
The info given in the OP is almost correct. As noted in Jyrki Lahtonen's answer, $k$ cannot be congruent to $n$.
In $A_k(i,j)$, $k$ is the index of the square: the algorithm generates $n-1$ MOLS, one for each $k$ in $\{1,\cdots,n-1\}$. Using normal matrix conventions, $i$ is the row index and $j$ is the column index, but the formula still works if those are swapped.
Here's some rudimentary Python code that uses that formula to generate a set of mutually orthogonal Latin squares (MOLS) and then tests each combination for orthogonality. This code was originally developed using Python 2.6 but it runs correctly on Python 3.
In this code, $i$ and $j$ run from 0 to $n-1$ and $k$ runs from 1 to $n-1$; note that $n$ must be prime.
If you pass a composite value for $n$, the program will generate some Latin squares, and if that $n$ is odd you'll get some pairs of MOLS, which is useful if you want to construct magic squares.
""" Generate sets of mutually orthogonal Latin squares (MOLS)
See https://math.stackexchange.com/a/1624875/207316
Written by PM 2Ring 2016.01.24
Updated 2021.01.31
"""
#from __future__ import print_function
import sys
def show_grid(g):
for row in g:
print(row)
print()
def test_mols(g):
""" Check that all entries in g are unique """
a = set()
for row in g:
a.update(row)
return len(a) == len(g) ** 2
def mols(n):
""" Generate a set of mutually orthogonal Latin squares
n must be prime
"""
r = range(n)
#Generate each Latin square
allgrids = []
for k in range(1, n):
grid = []
for i in r:
row = []
for j in r:
a = (k*i + j) % n
row.append(a)
grid.append(row)
# Test that there are no repeated items in the 1st column.
# This test is unnecessary for prime n, but it lets us
# produce some pairs of MOLS for odd composite n
if len(set([row[0] for row in grid])) == n:
allgrids.append(grid)
for i, g in enumerate(allgrids):
print(i)
show_grid(g)
print('- ' * 20 + '\n')
# Combine the squares to show their orthogonality
m = len(allgrids)
for i in range(m):
g0 = allgrids[i]
for j in range(i+1, m):
g1 = allgrids[j]
newgrid = []
for r0, r1 in zip(g0, g1):
newgrid.append(list(zip(r0, r1)))
print(i, j, test_mols(newgrid))
show_grid(newgrid)
def main():
# Get order from command line, or use default
n = int(sys.argv[1]) if len(sys.argv) > 1 else 5
mols(n)
if __name__ == '__main__':
main()
output for n=3
0
[0, 1, 2]
[1, 2, 0]
[2, 0, 1]
1
[0, 1, 2]
[2, 0, 1]
[1, 2, 0]
- - - - - - - - - - - - - - - - - - - -
0 1 True
[(0, 0), (1, 1), (2, 2)]
[(1, 2), (2, 0), (0, 1)]
[(2, 1), (0, 2), (1, 0)]
output for n=5
0
[0, 1, 2, 3, 4]
[1, 2, 3, 4, 0]
[2, 3, 4, 0, 1]
[3, 4, 0, 1, 2]
[4, 0, 1, 2, 3]
1
[0, 1, 2, 3, 4]
[2, 3, 4, 0, 1]
[4, 0, 1, 2, 3]
[1, 2, 3, 4, 0]
[3, 4, 0, 1, 2]
2
[0, 1, 2, 3, 4]
[3, 4, 0, 1, 2]
[1, 2, 3, 4, 0]
[4, 0, 1, 2, 3]
[2, 3, 4, 0, 1]
3
[0, 1, 2, 3, 4]
[4, 0, 1, 2, 3]
[3, 4, 0, 1, 2]
[2, 3, 4, 0, 1]
[1, 2, 3, 4, 0]
- - - - - - - - - - - - - - - - - - - -
0 1 True
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
[(1, 2), (2, 3), (3, 4), (4, 0), (0, 1)]
[(2, 4), (3, 0), (4, 1), (0, 2), (1, 3)]
[(3, 1), (4, 2), (0, 3), (1, 4), (2, 0)]
[(4, 3), (0, 4), (1, 0), (2, 1), (3, 2)]
0 2 True
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
[(1, 3), (2, 4), (3, 0), (4, 1), (0, 2)]
[(2, 1), (3, 2), (4, 3), (0, 4), (1, 0)]
[(3, 4), (4, 0), (0, 1), (1, 2), (2, 3)]
[(4, 2), (0, 3), (1, 4), (2, 0), (3, 1)]
0 3 True
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
[(1, 4), (2, 0), (3, 1), (4, 2), (0, 3)]
[(2, 3), (3, 4), (4, 0), (0, 1), (1, 2)]
[(3, 2), (4, 3), (0, 4), (1, 0), (2, 1)]
[(4, 1), (0, 2), (1, 3), (2, 4), (3, 0)]
1 2 True
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
[(2, 3), (3, 4), (4, 0), (0, 1), (1, 2)]
[(4, 1), (0, 2), (1, 3), (2, 4), (3, 0)]
[(1, 4), (2, 0), (3, 1), (4, 2), (0, 3)]
[(3, 2), (4, 3), (0, 4), (1, 0), (2, 1)]
1 3 True
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
[(2, 4), (3, 0), (4, 1), (0, 2), (1, 3)]
[(4, 3), (0, 4), (1, 0), (2, 1), (3, 2)]
[(1, 2), (2, 3), (3, 4), (4, 0), (0, 1)]
[(3, 1), (4, 2), (0, 3), (1, 4), (2, 0)]
2 3 True
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
[(3, 4), (4, 0), (0, 1), (1, 2), (2, 3)]
[(1, 3), (2, 4), (3, 0), (4, 1), (0, 2)]
[(4, 2), (0, 3), (1, 4), (2, 0), (3, 1)]
[(2, 1), (3, 2), (4, 3), (0, 4), (1, 0)]
Best Answer
This may also be of interest. From the two 4x4 squares given in a previous answer, two 8x8 squares can be grown.
If we transpose the symbols thus;
The two squares are different only by the chosen symbols the cells contain.
a) Place the two latin squares side by side to give a rectangle.
b) Then swap rows 2 and 4 with the transposed rows 2 and 4 to give;
c) Then take the resulting rectangle from b) and copy it backwards below the rectangle resulting from b).
Then we get;
The same process may be performed again and again from the resulting squares, swapping each even numbered rows.