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)
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
mutually_orthogonal_latin_squares() | Return ![]() ![]() |
are_mutually_orthogonal_latin_squares() | Check that the list l of matrices in are MOLS. |
latin_square_product() | Return the product of two (or more) latin squares. |
MOLS_table() | 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(30) # 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 7 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| 7 7 6 162 6 7 6 166 7 168 6 8 6 172 6 6 10 9 6 178
180| 6 180 6 6 7 8 6 10 6 7 6 190 7 192 6 7 6 196 6 198
200| 7 7 6 7 6 7 6 8 12 11 10 210 6 7 6 7 7 8 6 10
220| 6 12 6 222 7 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 10 7 7 255 256 6 12
260| 6 8 7 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 10 352 6 9 7 7 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 7 408 7 13 8 12 10 9 15 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 6 15 8 12 8 15
520| 7 520 6 522 7 15 8 16 15 528 7 15 8 12 7 15 8 15 10 15
540| 12 540 7 15 16 7 7 546 7 8 7 18 7 7 7 7 7 556 7 12
560| 7 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(30,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:
REFERENCES:
[Stinson2004] | Douglas R. Stinson, Combinatorial designs: construction and analysis, Springer, 2004. |
[ColDin01] | 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. |
Prints the MOLS table that Sage can produce.
INPUT:
EXAMPLES:
sage: from sage.combinat.designs.latin_squares import MOLS_table
sage: MOLS_table(5)
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(5,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|
Check wether the list of matrices in l form mutually orthogonal latin squares.
INPUT:
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)
sage: are_mutually_orthogonal_latin_squares(m)
True
TESTS:
Not a latin square:
sage: m1 = matrix([[0,1,0],[2,0,1],[1,2,0]])
sage: m2 = matrix([[0,1,2],[1,2,0],[2,0,1]])
sage: are_mutually_orthogonal_latin_squares([m1,m2], verbose=True)
Matrix 0 is not row latin
False
sage: m1 = matrix([[0,1,2],[1,0,2],[1,2,0]])
sage: are_mutually_orthogonal_latin_squares([m1,m2], verbose=True)
Matrix 0 is not column latin
False
sage: m1 = matrix([[0,0,0],[1,1,1],[2,2,2]])
sage: m2 = matrix([[0,1,2],[0,1,2],[0,1,2]])
sage: are_mutually_orthogonal_latin_squares([m1,m2])
False
Return the product of two (or more) latin squares.
Given two Latin Squares of respective sizes
, the direct product
of size
is defined by
where
Each pair of values is then relabeled to
.
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]
sage: latin_square_product(m,m,m)
64 x 64 sparse matrix over Integer Ring (use the '.str()' method to see the entries)
Return Mutually Orthogonal
Latin Squares (MOLS).
For more information on Mutually Orthogonal Latin Squares, see latin_squares.
INPUT:
k (integer) – number of MOLS. If k=None it is set to the largest value available.
n (integer) – size of the latin square.
partition (boolean) – a Latin Square can be seen as 3 partitions of
the cells of the array into
sets of size
, respectively :
These partitions have the additional property that any two sets from different partitions intersect on exactly one element.
When partition is set to True, this function returns a list of
partitions satisfying this intersection property instead of the
MOLS
(though the data is exactly the same in both cases).
existence (boolean) – instead of building the design, return:
- True – meaning that Sage knows how to build the design
- Unknown – meaning that Sage does not know how to build the design, but that the design may exist (see sage.misc.unknown).
- False – meaning that the design does not exist.
Note
When k=None and existence=True the function returns an
integer, i.e. the largest such that we can build a
MOLS of
order
.
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 to True by default.
EXAMPLES:
sage: designs.mutually_orthogonal_latin_squares(4,5)
[
[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)
[
[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)
[[[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.mutually_orthogonal_latin_squares(None,8,existence=True)
7
If you only want to know if Sage is able to build a given set of MOLS, just set the argument existence to True:
sage: designs.mutually_orthogonal_latin_squares(5, 5, existence=True)
False
sage: designs.mutually_orthogonal_latin_squares(4,6, existence=True)
Unknown
If you ask for such a MOLS then you will respecively get an informative EmptySetError or NotImplementedError:
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)
Traceback (most recent call last):
...
NotImplementedError: I don't know how to build 4 MOLS of order 6
TESTS:
The special case :
sage: designs.mutually_orthogonal_latin_squares(3, 1)
[[0], [0], [0]]
sage: designs.mutually_orthogonal_latin_squares(None,1, existence=True)
+Infinity
sage: designs.mutually_orthogonal_latin_squares(None, 1)
Traceback (most recent call last):
...
ValueError: there are no bound on k when 0<=n<=1
sage: designs.mutually_orthogonal_latin_squares(2,10,existence=True)
True
sage: designs.mutually_orthogonal_latin_squares(2,10)
[
[1 8 9 0 2 4 6 3 5 7] [1 7 6 5 0 9 8 2 3 4]
[7 2 8 9 0 3 5 4 6 1] [8 2 1 7 6 0 9 3 4 5]
[6 1 3 8 9 0 4 5 7 2] [9 8 3 2 1 7 0 4 5 6]
[5 7 2 4 8 9 0 6 1 3] [0 9 8 4 3 2 1 5 6 7]
[0 6 1 3 5 8 9 7 2 4] [2 0 9 8 5 4 3 6 7 1]
[9 0 7 2 4 6 8 1 3 5] [4 3 0 9 8 6 5 7 1 2]
[8 9 0 1 3 5 7 2 4 6] [6 5 4 0 9 8 7 1 2 3]
[2 3 4 5 6 7 1 8 9 0] [3 4 5 6 7 1 2 8 0 9]
[3 4 5 6 7 1 2 0 8 9] [5 6 7 1 2 3 4 0 9 8]
[4 5 6 7 1 2 3 9 0 8], [7 1 2 3 4 5 6 9 8 0]
]