1
$\begingroup$

I am very interested in using mutually orthogonal latin squares (MOLS) to reduce the number of test cases but I struggle to find a way how to implement the algorithm. In an article published in a foreign language, I did find a formula including the source code.

This is said to be a formula to construct a series of squares (if $n$ is a prime power):

For $i,j\in\mathbb F_n$, $k\in\mathbb F_n^×$ $$A_k(i,j)=ki+j$$ Is this correct? I tried to find other sources but failed.

If this is correct, what is meant by $k$, $i$ and $j$? In the code, they pass "size" of the latin square to all of these variables.

$\endgroup$
3
  • 1
    $\begingroup$ Include the subject of you question in the body as well. Newspaper headlines don't state "President says X" and then, in the body, never mention the president nor X. The title is not the beginning of the question. $\endgroup$
    – Thomas Andrews
    Commented Jan 24, 2016 at 12:42
  • $\begingroup$ Thanks, I updated the question. The formula should produce the squares required. (is there a way to show the image in the body instead as a link?) $\endgroup$
    – Pietross
    Commented Jan 24, 2016 at 12:47
  • $\begingroup$ A notion of whether the algorithm is correct depends on the interpretation of inputs $i,j,k$, so it is preferred that you state for your Readers what these mean. I suspect that $k$ should be $0 \lt k \lt n$, so that $k$ is coprime to (prime) $n$. Then $A_k(i,j)$ should give you a matrix entry ($i$th row and $j$th column, or vice versa, as you wish to interpret). $\endgroup$
    – hardmath
    Commented Jan 24, 2016 at 14:48

2 Answers 2

Reset to default
4
$\begingroup$

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)]
$\endgroup$
2
  • $\begingroup$ Thank you very much! So the "n" has to be: n>=m and n-1 >=number of parameters. Where "m" is the number of values (e.g. a parameter can have 4 values). And that n has to be prime. So if I have 4 parameters that have 5 values, I will need squares of size 5. $\endgroup$
    – Pietross
    Commented Jan 24, 2016 at 13:34
  • 1
    $\begingroup$ This short Sage script generates MOLS using Galois Field arithmetic. $m$ has to be a prime, or a prime power. $\endgroup$
    – PM 2Ring
    Commented May 30, 2021 at 19:30
1
$\begingroup$

Yes, that formula works. If $n=p$ is a prime it gives you a set of $p-1$ MOLS - one for each $k=1,2,\ldots,p-1$. The variables $i$ and $j$ stand for the row and column index respectively.

If $n=p^m$ is a power of a prime $p$, then there exists a similar formula for $n-1$ MOLS, but that requires you to do arithmetic in an extension field of integers modulo $p$.

$\endgroup$
6
  • $\begingroup$ Thanks. So "k" is the square and i and j are its rows and columns, if I get it right. Out of curiosity, why there is "A" in the formula? $\endgroup$
    – Pietross
    Commented Jan 24, 2016 at 13:36
  • $\begingroup$ @Pietross: $A_k$ is just the name of the $k$th array. $\endgroup$
    – PM 2Ring
    Commented Jan 24, 2016 at 13:39
  • $\begingroup$ @PM 2Ring Thanks. What if N=8? Or if that happens, should I go for the next closest prime number? $\endgroup$
    – Pietross
    Commented Jan 24, 2016 at 14:48
  • $\begingroup$ @Pietross: Well, you could, but using the next prime, 11, gives you a lot of "wasted" combinations, since $11^2$ is almost double $8^2$. As Jyrki says, there are ways to generate MOLS for non-primes. It's pretty easy to generate a pair of MOLS for any odd $n$: that's a standard way to generate magic squares. But that's (possibly) a topic for a new question... $\endgroup$
    – PM 2Ring
    Commented Jan 24, 2016 at 14:58
  • $\begingroup$ @PM 2Ring Thanks. One last thing - how do I know the value of K? Assume there are 4 parameters, some of which can have 5 values. So n=5. But when I want to code the actual algorithm, how do I determine k? $\endgroup$
    – Pietross
    Commented Jan 24, 2016 at 15:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .