Mutually Orthogonal Latin Squares (MOLS)#
The main function of this module is mutually_orthogonal_latin_squares()
and can be can be used to generate MOLS (or check that they exist):
sage: MOLS = designs.mutually_orthogonal_latin_squares(4,8) # needs sage.schemes
For more information on MOLS, see the Wikipedia entry on MOLS. If you are only
interested by latin squares, see latin.
The functions defined here are
Return \(k\) Mutually Orthogonal \(n\times n\) Latin Squares. |
|
Check that the list |
|
Return the product of two (or more) latin squares. |
|
Prints the MOLS table. |
Table of MOLS
Sage can produce a table of MOLS similar to the one from the Handbook of Combinatorial Designs [DesignHandbook] (available here).
sage: from sage.combinat.designs.latin_squares import MOLS_table
sage: MOLS_table(600) # long time
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
________________________________________________________________________________
0| +oo +oo 1 2 3 4 1 6 7 8 2 10 5 12 4 4 15 16 5 18
20| 4 5 3 22 7 24 4 26 5 28 4 30 31 5 4 5 8 36 4 5
40| 7 40 5 42 5 6 4 46 8 48 6 5 5 52 5 6 7 7 5 58
60| 5 60 5 6 63 7 5 66 5 6 6 70 7 72 5 7 6 6 6 78
80| 9 80 8 82 6 6 6 6 7 88 6 7 6 6 6 6 7 96 6 8
100| 8 100 6 102 7 7 6 106 6 108 6 6 13 112 6 7 6 8 6 6
120| 7 120 6 6 6 124 6 126 127 7 6 130 6 7 6 7 7 136 6 138
140| 6 7 6 10 10 7 6 7 6 148 6 150 7 8 8 7 6 156 7 6
160| 9 7 6 162 6 7 6 166 7 168 6 8 6 172 6 6 14 9 6 178
180| 6 180 6 6 7 9 6 10 6 8 6 190 7 192 6 7 6 196 6 198
200| 7 7 6 7 6 8 6 8 14 11 10 210 6 7 6 7 7 8 6 10
220| 6 12 6 222 13 8 6 226 6 228 6 7 7 232 6 7 6 7 6 238
240| 7 240 6 242 6 7 6 12 7 7 6 250 6 12 9 7 255 256 6 12
260| 6 8 8 262 7 8 7 10 7 268 7 270 15 16 6 13 10 276 6 9
280| 7 280 6 282 6 12 6 7 15 288 6 6 6 292 6 6 7 10 10 12
300| 7 7 7 7 15 15 6 306 7 7 7 310 7 312 7 10 7 316 7 10
320| 15 15 6 16 8 12 6 7 7 9 6 330 7 8 7 6 7 336 6 7
340| 6 10 10 342 7 7 6 346 6 348 8 12 18 352 6 9 7 9 6 358
360| 7 360 6 7 7 7 6 366 15 15 7 15 7 372 7 15 7 13 7 378
380| 7 12 7 382 15 15 7 15 7 388 7 16 7 7 7 7 8 396 7 7
400| 15 400 7 15 11 8 7 15 8 408 7 13 8 12 10 9 18 15 7 418
420| 7 420 7 15 7 16 6 7 7 7 6 430 15 432 6 15 6 18 7 438
440| 7 15 7 442 7 13 7 11 15 448 7 15 7 7 7 15 7 456 7 16
460| 7 460 7 462 15 15 7 466 8 8 7 15 7 15 10 18 7 15 6 478
480| 15 15 6 15 8 7 6 486 7 15 6 490 6 16 6 7 15 15 6 498
500| 7 8 9 502 7 15 6 15 7 508 6 15 511 18 7 15 8 12 8 15
520| 8 520 10 522 12 15 8 16 15 528 7 15 8 12 7 15 8 15 10 15
540| 12 540 7 15 18 7 7 546 7 8 7 18 7 7 7 7 7 556 7 12
560| 15 7 7 562 7 7 6 7 7 568 6 570 7 7 15 22 8 576 7 7
580| 7 8 7 10 7 8 7 586 7 18 17 7 15 592 8 15 7 7 8 598
Comparison with the results from the Handbook of Combinatorial Designs (2ed) [DesignHandbook]:
sage: MOLS_table(600,compare=True) # long time
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
________________________________________________________________________________
0| + +
20|
40|
60|
80|
100|
120|
140|
160|
180|
200| -
220|
240|
260|
280|
300|
320| -
340|
360| - -
380| -
400|
420| -
440|
460|
480|
500| -
520|
540|
560|
580|
Todo
Look at [ColDin01].
REFERENCES:
Douglas R. Stinson, Combinatorial designs: construction and analysis, Springer, 2004.
Charles Colbourn, Jeffrey Dinitz, Mutually orthogonal latin squares: a brief survey of constructions, Volume 95, Issues 1-2, Pages 9-48, Journal of Statistical Planning and Inference, Springer, 1 May 2001.
Functions#
- sage.combinat.designs.latin_squares.MOLS_table(start, stop=None, compare=False, width=None)#
Prints the MOLS table that Sage can produce.
INPUT:
start,stop(integers) – print the table of MOLS for value of \(n\) such thatstart<=n<stop. If only one integer is given as input, it is interpreted as the value ofstopwithstart=0(same behaviour asrange).compare(boolean) – if sets toTruethe MOLS displays with \(+\) and \(-\) entries its difference with the table from the Handbook of Combinatorial Designs (2ed).width(integer) – the width of each column of the table. By default, it is computed from range of values determined by the parametersstartandstop.
EXAMPLES:
sage: # needs sage.schemes sage: from sage.combinat.designs.latin_squares import MOLS_table sage: MOLS_table(100) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ________________________________________________________________________________ 0| +oo +oo 1 2 3 4 1 6 7 8 2 10 5 12 4 4 15 16 5 18 20| 4 5 3 22 7 24 4 26 5 28 4 30 31 5 4 5 8 36 4 5 40| 7 40 5 42 5 6 4 46 8 48 6 5 5 52 5 6 7 7 5 58 60| 5 60 5 6 63 7 5 66 5 6 6 70 7 72 5 7 6 6 6 78 80| 9 80 8 82 6 6 6 6 7 88 6 7 6 6 6 6 7 96 6 8 sage: MOLS_table(100, width=4) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ____________________________________________________________________________________________________ 0| +oo +oo 1 2 3 4 1 6 7 8 2 10 5 12 4 4 15 16 5 18 20| 4 5 3 22 7 24 4 26 5 28 4 30 31 5 4 5 8 36 4 5 40| 7 40 5 42 5 6 4 46 8 48 6 5 5 52 5 6 7 7 5 58 60| 5 60 5 6 63 7 5 66 5 6 6 70 7 72 5 7 6 6 6 78 80| 9 80 8 82 6 6 6 6 7 88 6 7 6 6 6 6 7 96 6 8 sage: MOLS_table(100, compare=True) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ________________________________________________________________________________ 0| + + 20| 40| 60| 80| sage: MOLS_table(50, 100, compare=True) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ________________________________________________________________________________ 40| 60| 80|
- sage.combinat.designs.latin_squares.are_mutually_orthogonal_latin_squares(l, verbose=False)#
Check whether the list of matrices in
lform mutually orthogonal latin squares.INPUT:
verbose- ifTruethen print why the list of matrices provided are not mutually orthogonal latin squares
EXAMPLES:
sage: from sage.combinat.designs.latin_squares import are_mutually_orthogonal_latin_squares sage: m1 = matrix([[0,1,2],[2,0,1],[1,2,0]]) sage: m2 = matrix([[0,1,2],[1,2,0],[2,0,1]]) sage: m3 = matrix([[0,1,2],[2,0,1],[1,2,0]]) sage: are_mutually_orthogonal_latin_squares([m1,m2]) True sage: are_mutually_orthogonal_latin_squares([m1,m3]) False sage: are_mutually_orthogonal_latin_squares([m2,m3]) True sage: are_mutually_orthogonal_latin_squares([m1,m2,m3], verbose=True) Squares 0 and 2 are not orthogonal False sage: m = designs.mutually_orthogonal_latin_squares(7,8) # needs sage.schemes sage: are_mutually_orthogonal_latin_squares(m) # needs sage.schemes True
- sage.combinat.designs.latin_squares.latin_square_product(M, N, *others)#
Return the product of two (or more) latin squares.
Given two Latin Squares \(M,N\) of respective sizes \(m,n\), the direct product \(M\times N\) of size \(mn\) is defined by \((M\times N)((i_1,i_2),(j_1,j_2))=(M(i_1,j_1),N(i_2,j_2))\) where \(i_1,j_1\in [m], i_2,j_2\in [n]\)
Each pair of values \((i,j)\in [m]\times [n]\) is then relabeled to \(in+j\).
This is Lemma 6.25 of [Stinson2004].
INPUT:
An arbitrary number of latin squares (greater than 2).
EXAMPLES:
sage: from sage.combinat.designs.latin_squares import latin_square_product sage: m=designs.mutually_orthogonal_latin_squares(3,4)[0] # needs sage.schemes sage: latin_square_product(m,m,m) # needs sage.schemes 64 x 64 sparse matrix over Integer Ring (use the '.str()' method to see the entries)
- sage.combinat.designs.latin_squares.mutually_orthogonal_latin_squares(k, n, partitions=False, check=True)#
Return \(k\) Mutually Orthogonal \(n\times n\) Latin Squares (MOLS).
For more information on Mutually Orthogonal Latin Squares, see
latin_squares.INPUT:
k(integer) – number of MOLS. Ifk=Noneit is set to the largest value available.n(integer) – size of the latin square.partitions(boolean) – a Latin Square can be seen as 3 partitions of the \(n^2\) cells of the array into \(n\) sets of size \(n\), respectively:The partition of rows
The partition of columns
The partition of number (cells numbered with 0, cells numbered with 1, …)
These partitions have the additional property that any two sets from different partitions intersect on exactly one element.
When
partitionsis set toTrue, this function returns a list of \(k+2\) partitions satisfying this intersection property instead of the \(k+2\) MOLS (though the data is exactly the same in both cases).check– (boolean) Whether to check that output is correct before returning it. As this is expected to be useless (but we are cautious guys), you may want to disable it whenever you want speed. Set toTrueby default.
EXAMPLES:
sage: designs.mutually_orthogonal_latin_squares(4,5) # needs sage.schemes [ [0 2 4 1 3] [0 3 1 4 2] [0 4 3 2 1] [0 1 2 3 4] [4 1 3 0 2] [3 1 4 2 0] [2 1 0 4 3] [4 0 1 2 3] [3 0 2 4 1] [1 4 2 0 3] [4 3 2 1 0] [3 4 0 1 2] [2 4 1 3 0] [4 2 0 3 1] [1 0 4 3 2] [2 3 4 0 1] [1 3 0 2 4], [2 0 3 1 4], [3 2 1 0 4], [1 2 3 4 0] ] sage: designs.mutually_orthogonal_latin_squares(3,7) # needs sage.schemes [ [0 2 4 6 1 3 5] [0 3 6 2 5 1 4] [0 4 1 5 2 6 3] [6 1 3 5 0 2 4] [5 1 4 0 3 6 2] [4 1 5 2 6 3 0] [5 0 2 4 6 1 3] [3 6 2 5 1 4 0] [1 5 2 6 3 0 4] [4 6 1 3 5 0 2] [1 4 0 3 6 2 5] [5 2 6 3 0 4 1] [3 5 0 2 4 6 1] [6 2 5 1 4 0 3] [2 6 3 0 4 1 5] [2 4 6 1 3 5 0] [4 0 3 6 2 5 1] [6 3 0 4 1 5 2] [1 3 5 0 2 4 6], [2 5 1 4 0 3 6], [3 0 4 1 5 2 6] ] sage: designs.mutually_orthogonal_latin_squares(2,5,partitions=True) # needs sage.schemes [[[0, 1, 2, 3, 4], [5, 6, 7, 8, 9], [10, 11, 12, 13, 14], [15, 16, 17, 18, 19], [20, 21, 22, 23, 24]], [[0, 5, 10, 15, 20], [1, 6, 11, 16, 21], [2, 7, 12, 17, 22], [3, 8, 13, 18, 23], [4, 9, 14, 19, 24]], [[0, 8, 11, 19, 22], [3, 6, 14, 17, 20], [1, 9, 12, 15, 23], [4, 7, 10, 18, 21], [2, 5, 13, 16, 24]], [[0, 9, 13, 17, 21], [2, 6, 10, 19, 23], [4, 8, 12, 16, 20], [1, 5, 14, 18, 22], [3, 7, 11, 15, 24]]]
What is the maximum number of MOLS of size 8 that Sage knows how to build?:
sage: designs.orthogonal_arrays.largest_available_k(8)-2 # needs sage.schemes 7
If you only want to know if Sage is able to build a given set of MOLS, query the
orthogonal_arrays.*functions:sage: designs.orthogonal_arrays.is_available(5+2, 5) # 5 MOLS of order 5 False sage: designs.orthogonal_arrays.is_available(4+2,6) # 4 MOLS of order 6 # needs sage.schemes False
Sage, however, is not able to prove that the second MOLS do not exist:
sage: designs.orthogonal_arrays.exists(4+2,6) # 4 MOLS of order 6 # needs sage.schemes Unknown
If you ask for such a MOLS then you will respectively get an informative
EmptySetErrororNotImplementedError:sage: designs.mutually_orthogonal_latin_squares(5, 5) Traceback (most recent call last): ... EmptySetError: there exist at most n-1 MOLS of size n if n>=2 sage: designs.mutually_orthogonal_latin_squares(4,6) # needs sage.schemes Traceback (most recent call last): ... NotImplementedError: I don't know how to build 4 MOLS of order 6