This Page: | Construction Latin Graeco-Latin Duplicates Fewest How Many Formulae |
Regular prime number, magic squares are constructed in an orderly manner composed of magic carpets (Latin squares) with the following properties:
Irregular. Panmagic squares which cannot be decomposed into regularly patterned Latin squares are called Irregular Pan-Magic Squares. Mutsumi Suzuk has recently described Abe Gakuho's construction technique for these squares which he called Pairwise Exchange.
Regular prime number pan-magic squares decompose into two Magic Carpets - or Latin Squares if they are presented as letters. Although the smallest magic square (order-3) is not pan-magic it has the advantage that its decomposition is easily visualized. In addition, so can the subsequent assembly of the Latin squares into one Graeco-Latin square.
|
= 3 x |
|
+ |
|
||||||||||||||||||||||||||||||||
Latin Squares: |
|
+ |
|
= |
|
The two Latin squares are identical but rotated. They cannot be panmagic because the "Knight's" move is stunted to a 1x1 step and consequently produces diagonals which may be magic but never pan-magic - the broken diagonals cannot add to the magic total. With larger prime number magic squares, there are more options.
This Page: | Construction Latin Graeco-Latin Duplicates Fewest How Many Formulae |
Prime number Latin squares are made with "Knight's moves" - two steps forward and one to the side (2x1). A generalized Knight's move consists of any length of step forward and one step to the side, e.g., 1x1, 2x1, 3x1, 4x1, etc. For an order-N magic square, there are N-1 knight's moves and, therefore, N-1 "Orthogonal" Latin Squares:
|
|
|
|
|
|
|
These order-7 squares (above) provide a convenient illustration - big enough but not overwhelming. Of these, 1 to 6 are Latin squares but the first and sixth are not pan-magic because their steps produce diagonal rows of letters. Eliminating three leaves four pan-magic Latin squares – 2, 3, 4, and 5. They are mutually orthogonal and can be combined to make "Graeco-Latin" squares. Therefore, the total number of Pan-Magic Latin Squares (L) for prime order N is:
L = N - 3 = 4
Observe that, despite using increasing steps, all four of these pan-magic squares (2, 3, 4, 5) actually contain a 2x1 step in one or other axis. They are a related group. This will be important when we analyze the Fewest Representative Graeco-Latin Squares below.
This Page: | Construction Latin Graeco-Latin Duplicates Fewest How Many Formulae |
A Graeco-Latin square is made from a pair of orthogonal Latin squares. Each one of the L Latin squares can combine with all the others (L - 1). Because L = N - 3, the total number of Graeco-Latin squares (G) is:
G = ( N - 3 ) x ( N - 4)
For order-7: G = ( 7 - 3 ) x ( 7 - 4 ) = 12
To make Regular Pan-Magic Magic Squares, numbers are substituted for the letters in each Graeco-Latin square, e.g., in the order-7 square, for the first letter in each cell, the numbers 0 - 6 can be substituted - a total of 7! (= 7x6x5x4x3x2) options. Similar considerations apply to the second letter. For the order-7 square, therefore, there are (7!)2 pan-magic squares for each Graeco-latin square. The total number of Pan-Magic squares (P) is:
P = ( N - 3 ) x ( N - 4) x ( N ! )2
For order-7: P = ( 7 - 3 ) x ( 7 - 4 ) x ( 7 ! )2 = 304,819,200
This Page: | Construction Latin Graeco-Latin Duplicates Fewest How Many Formulae |
The technique above properly calculates the total number of different pan-magic squares; there are no duplicates if each square is constrained to stay in the same orientation with no translocation.
Huge duplication is apparent when squares are reflected, rotated, and translocated. Just by reflection and rotation, each square is present eight times; and by translocation, these groups of eight appear N2 times. The total number of duplicates (D) is:
D = 8 x N2
For order-7: D = 8 x 72 = 392
A Unique Pan-Magic square is a normalised representative of all the duplicates. It is normalised by reflection, rotation, and translocation to put the zero in the top left square, with the smallest possible number beside it, the next smallest possible below it. When duplicates are eliminated, the number of Unique Pan-Magic squares (U) is:
U = ( N - 3 ) x ( N - 4) x ( N ! )2 / ( 8 x N2 ), or:
U = ( N - 3 ) x ( N - 4) x ( (N - 1) ! )2 / 8
For order-7: U = ( 7 - 3 ) x ( 7 - 4 ) x ( (7-1) ! )2 / 8 = 777,600
Translocation. Many of the duplicates arise from using ( N ! ) 2 in the formula for P above, which puts the zero just once in every possible cell. This is avoided by using ( (N - 1) ! ) 2 in the formula for U, the mathematical equivalent of normalising the duplicates and keeping the zero in the top left position.
Reflections and Rotations. These rise from using all possible combinations of Graeco-Latin squares. One Graeco-Latin square produces two copies of each Pan-Magic square - oriented differently. Four related Graeco-Latin squares actually produce four sets of similar pairs - which, between them, provide all eight different reflections/rotations of all the squares, i.e., any one of the four is capable of generating a sample of every Unique square.
This Page: | Construction Latin Graeco-Latin Duplicates Fewest How Many Formulae |
Avoid the Duplication. If many of the Graeco-Latin squares produce duplicates, the implied question is: "To represent the pan-magic squares of order-N, what is the fewest number of Graeco-Latin squares required?" For the order-7 square it is a quarter (see paragraph above). However, this is too simplistic. The formula required to calculate the fewest number is more complicated:
Calculate Fewest. The Fewest Representative Pan-Magic squares is the number of Graeco-Latin squares produced when a single representative of each group of related Latin squares is paired with just the remaining Latin squares not already paired. A "group" in this context comprises the Latin squares which contain similar Knight's move, e.g., as described above, the apparently different order-7 pan-magic latin squares all contain the 2x1 jump in different orientations. Any one of the four can, therefore, be chosen and combined with the remaining ones. The Fewest number is:
F = INT( N / 4 ) x ( 2 x N - INT( N / 4 ) - 7 ) / 2
For order- 7: F = INT( 7 / 4) x (2 x 7 - INT( 7 / 4) - 7 ) / 2 = 1 x ( 14 - 1 - 7 ) / 2 = 3
For order-11: F = INT(11 / 4) x (2 x 11 - INT(11 / 4) - 7 ) / 2 = 2 x ( 22 - 2 - 7 ) / 2 = 13
For order-13: F = INT(13 / 4) x (2 x 13 - INT(13 / 4) - 7 ) / 2 = 3 x ( 26 - 3 - 7 ) / 2 = 24
This Page: | Construction Latin Graeco-Latin Duplicates Fewest How Many Formulae |
The number of Regular Pan-Magic, Latin and Graeco-Latin squares up to order 31 is given in the following table. The table following it summarizes the above formulae.
Numbers: (G-L stands for Graeco-Latin)
Order |
Pan-Magic Latin Squares |
All G-L Squares |
Fewest G-L Squares |
Total Pan-Magic Squares |
Dupli- cates |
Unique Pan-Magic Squares |
---|---|---|---|---|---|---|
N | L | G | F | P | D | U |
5 | 2 | 2 | 1 | 28800 | 200 | 144 |
7 | 4 | 12 | 3 | 304,819,200 | 392 | 777,600 |
11 | 8 | 56 | 13 | 8.92276 x 1016 | 968 | 9.21773 x1013 |
13 | 10 | 90 | 24 | 3.48982 x 1021 | 1352 | 2.58122 x1018 |
17 | 14 | 182 | 46 | 2.30254 x 1031 | 2312 | 9.95911 x1027 |
19 | 16 | 240 | 54 | 3.55140 x 1036 | 2888 | 1.22971 x1033 |
23 | 20 | 380 | 85 | 2.53964 x 1047 | 4232 | 6.00104 x1043 |
29 | 26 | 650 | 154 | 5.08148 x 1064 | 6728 | 7.55274 x1060 |
31 | 28 | 756 | 168 | 5.11169 x 1070 | 7688 | 6.64893 x1066 |
This Page: | Construction Latin Graeco-Latin Duplicates Fewest How Many Formulae |
Order of Magic Square: | N |
Number of Pan-Magic Latin Squares: | L = N - 3 |
Number of G-L Squares: | G = (N - 4) x (N - 3) |
Fewest Representative G-L Squares: | F = INT( N / 4 ) x ( 2 x N - INT( N / 4 ) - 7 ) / 2 |
Total Number of Pan-Magic Squares: | P = ( N - 3 ) x ( N - 4 ) x ( N ! )2 |
Number of Duplicate Pan-Magic Squares: | D = 8 x N2 |
Number of Unique Pan-Magic Squares: | U = ( N - 3 ) x ( N - 4) x ( (N - 1) ! )2 / 8 |
Beyond order-7, the number of Regular Prime Number Magic Squares are so vast that the only numbers we can begin to understand are the numbers of Graeco-Latin squares. For the smaller squares the number is easy to visualize and can be fairly readily confirmed. The masses of squares which can be derived from each Graeco-Latin square may all look quite different but they share the underlying Magic Carpets - their Latin Squares. For these reasons, when ennumerating the Magic Carpets and their product, counting the number of Graeco-Latin squares is more fundamental.
Copyright © Mar 2010 | Magic Squares Website |
Updated Mar 6, 2010 |