Table of Contents About the Author What's new Abstract Main Results The Transformation Method The Permutation Method The Intermediate Square Method Enumeration Programs Some References Notations, Definitions & Conventions An Example of Enumeration Programs Magic Squares of Order 4 Magic Squares of Order 5 Magic Squares of Order 6 Magic Squares of Order 7
Structure of Magic and Semi-Magic Squares,
Methods and Tools for Enumeration
by Francis Gaspalou

Order 4 allows to compute easily the set of magic (or semi-magic) squares. Then you can handle this set for examination and you have a lot of results on the structure. For orders superior to 4, it is practically impossible to handle the set: the squares are too numerous or can't be computed.

1. The Group of 32

The 32 transformations of a given magic square of order 4 can be obtained as follows:

  • you take first the 8 classical transformations of the octic group of the square: I, V, H, G, D, R1, R2, R3 (the notations are arbitrary: I=Identity, V=Vertical, H=Horizontal, G=left or Gauche in French, D=right or Droite in French, R1 = rotation of 90° anticlockwise, R2=symetry from the centre, R3=rotation of 90° clockwise)

  • then you multiply these 8 transformations by the transformation IT (see hereafter; IT=permutation of interior rows and columns, that is to say in the order 1324): you get 16 transformations,

  • after that, youmultiply these 16 transformations by the transformation A (see hereafter; A=permutation in the order 2143 of rows and columns).

With the matricial notation, these 32 transformations are:

A1A2A3A4
B1B2B3B4
C1C2C3C4
D1D2D3D4

I
A4A3A2A1
B4B3B2B1
C4C3C2C1
D4D3D2D1

V
D1D2D3D4
C1C2C3C4
B1B2B3B4
A1A2A3A4

H
A1B1C1D1
A2B2C2D2
A3B3C3D3
A4B4C4D4

G
 
 
D4C4B4A4
D3C3B3A3
D2C2B2A2
D1C1B1A1

D
A4B4C4D4
A3B3C3D3
A2B2C2D2
A1B1C1D1

R1
D4D3D2D1
C4C3C2C1
B4B3B2B1
A4A3A2A1

R2
D1C1B1A1
D2C2B2A2
D3C3B3A3
D4C4B4A4

R3
 
 
A1A3A2A4
C1C3C2C4
B1B3B2B4
D1D3D2D4

IT
D4D2D3D1
B4B2B3B1
C4C2C3C1
A4A2A3A1

EX
A1C1B1D1
A3C3B3D3
A2C2B2D2
A4C4B4D4

M
D4B4C4A4
D2B2C2A2
D3B3C3A3
D1B1C1A1

N
 
 
A4A2A3A1
C4C2C3C1
B4B2B3B1
D4D2D3D1

X
D1D3D2D4
B1B3B2B4
C1C3C2C4
A1A3A2A4

Y
A4C4B4D4
A2C2B2D2
A3C3B3D3
A1C1B1D1

Z
D1B1C1A1
D3B3C3A3
D2B2C2A2
D4B4C4A4

T
 
 
B2B1B4B3
A2A1A4A3
D2D1D4D3
C2C1C4C3

A
B3B4B1B2
A3A4A1A2
D3D4D1D2
C3C4C1C2

V*A
C2C1C4C3
D2D1D4D3
A2A1A4A3
B2B1B4B3

H*A
B2A2D2C2
B1A1D1C1
B4A4D4C4
B3A3D3C3

G*A
 
 
C3D3A3B3
C4D4A4B4
C1D1A1B1
C2D2A2B2

D*A
B3A3D3C3
B4A4D4C4
B1A1D1C1
B2A2D2C2

R1*A
C3C4C1C2
D3D4D1D2
A3A4A1A2
B3B4B1B2

R2*A
C2D2A2B2
C1D1A1B1
C4D4A4B4
C3D3A3B3

R3*A
 
 
C3C1C4C2
A3A1A4A2
D3D1D4D2
B3B1B4B2

IT*A
B2B4B1B3
D2D4D1D3
A2A4A1A3
C2C4C1C3

EX*A
C3A3D3B3
C1A1D1B1
C4A4D4B4
C2A2D2B2

M*A
B2D2A2C2
B4D4A4C4
B1D1A1C1
B3D3A3C3

N*A
 
 
C2C4C1C3
A2A4A1A3
D2D4D1D3
B2B4B1B3

X*A
B3B1B4B2
D3D1D4D2
A3A1A4A2
C3C1C4C2

Y*A
C2A2D2B2
C4A4D4B4
C1A1D1B1
C3A3D3B3

Z*A
B3D3A3C3
B1D1A1C1
B4D4A4C4
B2D2A2C2

T*A

These notations are personal notations.

You have a set of 32 elements:
1 element of period 1: I,
19 elements of period 2: V, H, G, D, R2, IT, EX, M, N, X, Y, A, V*A, H*A, G*A, D*A, R2*A, Z*A, T*A,
12 elements of period 4 (all with a common square R2): R1, R3, Z, T, R1*A, R3*A, IT*A, EX*A, M*A,
N*A, X*A, Y*A.

It is possible to build a multiplication table and to demonstrate in that way you have a group.

The relations of definition ("abstract definition") allows a smarter demonstration. You have nevertheless to proceed by trial and error to find the good relations of definition among the 51 possible groups of order 32! The literature does not give exhaustive catalogues, only partial catalogues and for low orders.
When you take
s1 = R1, s2 = X*A, s3 = IT, s4 = G,
you find that all the relations of definition of group G 32 n° 7 of BURNS are verified [Reference: Josephine E. BURNS, The Abstract Definitions of Groups of Degree 8, Am. J. Math. 37 (1915), p. 207]:

s14 = s24 = s32 = s42 = s13 s2 s1 s2 = s3 s1 s3 s13 = s23 s1 s2 s1
      = (s4 s1)2 = (s4 s2)2 = (s4 s3)2 = (s3 s2)2 = 1.

Besides, you verify that the 4 generators R1, X*A, IT et G give 32 elements.
Therefore, the 32 transformations form a group: the group G 32 n° 7 of BURNS.

The 8 first transformations form the octic group D4.
The 16 first transformations form the group D4*C2. It is the group n° 4 of BURNSIDE among the 9 not abelian groups of order 16 [Reference: W. BURNSIDE, Theory of Groups of finite order, Dover 1911, p.146]:
P4 = E, Q2 = E, R2 = E, R-1PR = P3, P-1QP = Q, R-1QR = Q
You can verify it easily with P = R1, Q = IT, R = G
It is the direct product of {Q} by {P,R}.

2. Generalization
Top of the page

We can calculate the order of the group G for magic squares of order n.

For magic squares of order 4, we have seen that group G is of order 32. It is the product of 8 (order of group octic) by 4 (number of remaining transpositions).
In magic square language, we call transpositions permutations of rows and columns symmetrically located from the centre of the square (it is not the usual mathematical language for permutations). If the rows are called 1234, we see there are 8 transpositions:
We search permutations abcd such as a+d=b+c=5
It is sufficient to fix a and b: a can take 4 values, and b=2 values when a is given.
Then we have 4*2=8 solutions
Among these transpositions, the transposition 4321 is already in the octic group: it is the transformation R2 (symmetry about the centre).
Therefore, 32 is the product:
8*(number of transpositions /2) = 4*(number of transpositions)

This formula can be generalized for all the orders.

For order 6, the number of transpositions abcdef is 6*4*2=48
a can take 6 values, b can take 4 values when a is given, c can take 2 values when a and b are given, d=7-c, e=7-b, f=7-a.
Then the order of group G is 4*48 = 192.

For order 2p, the number of transpositions is 2p*(2p-2)*...*2=2p (p!)
and the order of group G is 4*2p (p!) = 2p+2 (p!).

We have the fundamental result: for magic squares of order 2p, the order of group G is 2p+2 (p!)

We see easily that for magic squares of order 2p +1, the order of group G is the same: 2p+2 (p!).
As a matter of fact, the number of transpositions is the same as for order 2p (the middle number doesn't move).

These two groups are isomorphic; they have the same abstract definition.

Therefore, for magic squares of order n=2p or n=2p+1, the order of group G is 2p+2 (p!).
This last formula seems original. The first values are:

Order
of squares
Order
of group G
38
432
532
6192
7192
81 536

Note: for semi-magic of order n, the order of group G is 2 (n!)2.
The demonstration is here obvious: for a given square, you have n! possible permutations of rows, idem for columns, therefore (n!)2 possible transformations and you double this number with symmetry about the first diagonal.

3. The Set of 3 456 Semi-Pandiagonal Squares
Top of the page

This set is defined for example by A1+A2+B1+B2=34 (it is not the only definition: you can have also A2+B1+C4+D3=34 or A1+A3+C1+C3=34, etc.).

3.1 Group G


The group G (transformations) is of order 1 152; you have 3 elementary squares.

I identified this group: it is the only group of order 1 152 of degree 8 (reference: J. BURNS's article already quoted). Its abstract definition is:

s112 = s22 = (s14 s2)2(s18 s2) 2 = (s13 s2)2(s19 s2) 2 = (s13 s2 s14 s2) 2 = 1

with for example

s1
D1A4D4A1
C2B3C3B2
D2A3D3A2
C1B4C4B1
s2 = IT = 
A1A3A2A4
C1C3C2C4
B1B3B2B4
D1D3D2D4

You can verify that all the relations of definition are true with these two generators (and you need to verify also that you have 1 152 generated elements: these relations aren't abstract definition of a subgroup).

This group has a large number of subgroups (non exhaustive list, notations of J. BURNS's article if any else indication) - it is a mine! -:
G 576 n° 1, 2, 3
G 288 n° 3
G 192 n° 1, 2
G 144 n° 1
G 128
G 96 n° 3, 4, 6
G 72 degree 6
G 64 n° 2, 3, 5
G 48 n° 1
G 32 n° 6, 7, 8, 9
G 24 degree 4
G 16 n° 1 (?), 9
G 8 (octic group) and its subgroups.
For each subgroup, the abstract definition is in the literature and I can give example of generators.
I think G 1 152 has not subgroup of order 384.

3.2 Group G'

The group G' (permutations) is of order 384; you have 9 elementary squares.
This group is G 384 degree 8.
Subgroups (non exhaustive list):
G 192 n° 4, 5
G 128 and its subgroups (the same as above).

G 1 152 and G 384 have G 128 as a common subgroup (with also all its own subgroups).

3.3 Decomposition

The set of 3 456 semi-pandiagonal squares is made with 9 types of squares:


Type I


Type II


Type III


Type IV


Type V


Type VI


Type IV' Type V' Type VI'


Note: I put a double frame in a type diagram and a simple frame in a transformation diagram.

Each type has 384 squares and a group structure.

There are the 6 DUDENEY's types I, II, III, IV, V, VI (IV and IV' are the same type for DUDENEY; idem for V and V'; idem also for VI and VI').

It is funny to identify the transformations between the 9 types of squares (internal transformations for some types, but external transformations for other types). With these external transformations, you see that the 9 sets of 384 squares are isomorphic.

Note you have 2 supplementary isomorphic sets with 384 squares: they are of DUDENEY's type VI. These 768 squares aren't semi-pandiagonal.
They can be defined - for example - as squares of DUDENEY's type VI with condition A2+B4+C1+D3=34 or A3+B1+C4+D2=34.
You have 1 152 squares with condition A2+B4+C1+D3=34 or A3+B1+C4+D2=34: the 384 symmetrical squares and the 2 supplementary sets above.

3.4 Intermediate Square

All the 3 456 semi-pandiagonal squares can be built with only one intermediate square. For example, you can take (cf. BENSON & JACOBY, page 111):

A+aB+bC+cD+d
D+cC+dB+aA+b
B+dA+cD+bC+a
C+bD+aA+dB+c

This intermediate square is a Greco-Latin square: it is magic, diagonal (see definition in The intermediate square method, § 4) and semi-pandiagonal.

You have no magic conditions. You have 4! =24 solutions for capital letters, 4! solutions too for lower-case letters, k=6 basis; therefore you have a set of 6*24*24 = 3 456 squares.

This demonstration is simplier than BENSON & JACOBY'.

4. Graph of Filiation
Top of the page

For magic squares of order 4, you find the following graph of filiation:




K is the number of magic series (relations a+b+c+d = 34). Cf. The transformation method, § 5.1.

The origin set of 27 648 squares is the set of semi-magic squares of DUDENEY's type VI, i.e. defined by the 3 conditions:

A1+D1=A2+D2=A3+D3=17

Type VI

The set n° 2 of 1 216 squares is the set of 27 648 semi-magic squares with condition:
A1+B2+C3+D4=34 (and D1+C2+B3+A4=34 which is a consequence of DUDENEY's type VI)

The set n° 1 of 384 squares is the set n° 2 of 1 216 squares with condition of semi-pandiagonal squares:
A1+A2+B1+B2=34 for example (and other induced relations).
This set n° 1 is the set of semi-pandiagonal squares of DUDENEY's type VI.

The set of 3 072 squares is the set of semi-magic squares of DUDENEY's type IX.


Type IX

It is also the set of 27 648 semi-magic squares with condition:
D1+B2+B3+D4=34 (and other induced relations) given by transformation

A1A2A3A4
D1B2B3D4
C1C2C3C4
B1D2D3B4

The set n° 3 of 224 squares is the set of 3 072 squares with magic conditions for the diagonals (and with other induced conditions).

5. Generation of Squares from Gallic Squares
Top of the page

For order 4, it is possible to show exactly how the 7 040 magic squares are generated from capital and lower-case letter squares. For that, it is not necessary to enumerate all the possible Gallic squares, you need only to identify the elementary lower-case letter Gallic squares (and the induced squares by group G of 32 and by permutations). You search after the orthogonal squares to these elementary Gallic squares.

You have to search only Gallic squares with semi-regular rows and columns because only diagonals can be irregular (you verify this property a posteriori on all the 7 040 squares and all the basis; maybe it is possible to demonstrate directly that rows and columns cannot be irregular). If you classify the Gallic squares according to the value of the parameter S1, sum of the first diagonal, you verify on the 7 040 squares that S1 can take only some values (then the sum of the second diagonal is S2=2σ-S1). And among these Gallic squares, you have to take only those which have orthogonal squares.

I give hereafter the result of my research.

With the first basis (1,2,3,4;0,4,8,12), I found:

  • there are 9 elementary squares S1=10 in a normalized position (the numbers hereafter are those of my program of enumeration), and each one has orthogonal squares:

    1) 
     1  2  3  4 
    2413
    3142
    4321
    2) 
     1  2  3  4 
    3412
    2143
    4321
    3) 
     1  2  4  3 
    2314
    3241
    4312
    4) 
     1  2  4  3 
    4312
    1243
    4312
    5) 
     1  3  4  2 
    1324
    4231
    4213
     
    8) 
     1  3  4  2 
    4213
    2431
    3124
    9) 
     1  3  4  2 
    4321
    1234
    4213
    12) 
     1  4  3  2 
    4123
    2341
    3214
    13) 
     1  4  4  1 
    3223
    2332
    4114

    (squares # 1, 2 and 12 are Latin and magic, square # 8 is Latin diagonal)

  • there are 7 elementary squares S1=6, but only 6 with orthogonal squares:

    1) 
     1  1  4  4 
    2233
    3322
    4411
    2) 
     1  1  4  4 
    3232
    2323
    4411
    4) 
     1  2  3  4 
    3124
    2431
    4321
     
    5) 
     1  2  3  4 
    4123
    1432
    4321
    8) 
     1  2  4  3 
    4132
    1423
    4312
    18) 
     1  4  2  3 
    4132
    1423
    4132

    (squares # 1, 2 and 12 are Latin and magic, square # 8 is Latin diagonal)

  • there are 9 elementary squares S1=9, but only 7 with orthogonal squares:

    1) 
     1  2  3  4 
    2314
    3241
    4321
    3) 
     1  2  3  4 
    3322
    2143
    4411
    6) 
     1  2  4  3 
    3214
    2341
    4312
    7) 
     1  2  4  3 
    4213
    1342
    4312
     
    11) 
     1  3  4  2 
    3214
    2431
    4123
    13) 
     1  3  4  2 
    4213
    1432
    4123
    23) 
     1  4  4  1 
    2233
    3322
    4114

    (square # 11 is Latin but not magic).

For each elementary square, I searched the number of induced squares and the number of orthogonal squares:

S1=10# of elementary
square
Number of induced squares
(group 32 * permutations)
Number of orthogonal
squares for each
Total number
of orthogonal squares
1  4*2=  816   8*16=   128
2  4*2=  832   8*32=   256
332*2=6412 64*12=   768
416*2=324032*40=1 280
532*1=32  8   32*8=   256
816*3=482448*24=1 152
932*1=32  8   32*8=   256
1216*1=1632 16*32=   512
1316*1=1640 16*40=   640
2565 248

(There are 80 Latin magic squares, coming from the elementary squares # 1, 2, 8 and 12.
There are 48 Latin diagonal squares coming from the elementary square # 8.
You see that Latin magic squares haven't the maximum number of orthogonal squares.
The total number of orthogonal squares to Latin magic squares is 2 048 - with 1 152 orthogonal to Latin diagonal squares - ).


S1=6# of elementary
square
Number of induced squares
(group 32 * permutations)
Number of orthogonal
squares for each
Total number
of orthogonal squares
116*1=161616*16=256
216*1=161616*16=256
432*1=321232*12=384
532*1=321432*14=448
832*1=32  632*  6=192
1816*1=161616*16=256
1441 792


S1=10# of elementary
square
Number of induced squares
(group 32 * permutations)
Number of orthogonal
squares for each
Total number
of orthogonal squares
132*2=64464*4=256
332*2=64464*4=256
632*2=64464*4=256
732*1=32632*6=192
1132*3=96496*4=384
1332*2=64364*3=192
2332*1=32832*8=256
4161 792

Then, I built two figures: one for the 5 248 semi-regular squares and another for the 1 792 irregular squares:







The 7 040 magic squares are distributed in blocks of squares. In each block, all the squares come from the same couple of two elementary Gallic squares, each one in a normalized position.

In fact, for the capital letters values (0,4,8,12), I used the same program as for lower-case letters values (1,2,3,4) with:
01        42        83        124
In that way, the Gallic squares are written in a normalized form.

The figures give the number of magic squares in each block, but naturally I identified each magic square in the list of 7 040.

All the 7 040 magic squares can be built from 9+6+7=22 elementary Gallic squares (with the first basis).


I also drove the decomposition of the 7 040 squares with the second and the third basis (with the 3 other basis, the diagrams are obtained by permutation of capital and lower-case letters, i.e. by symmetry about the first bisecting line).

I give the results:

Basis # 1Basis # 2Basis #3
Number of semi-regular squares5 248
(with 1 152 regular)
4 224
(with 1 152 regular)
4 736
(with 1 152 regular)
Number of irregular squares1 7922 8162 304
Number of elementary squares223245
Number of blocks of squares364141

The set of 1 152 regular squares is different in the 3 basis. The 3 sets of 1 152 constitute the set of 3 456 semi-pandiagonal squares.

There are 4 224 squares which are always semi-regular in all the basis
          and 1 280 squares which are always irregular in all the basis.

There are 5 760 semi-regular squares with at least one basis.


Note: for orders superior to 4, it is naturally impossible to do the same task up to the very end.

6. Decompositions in Sets of Intermediate Squares
Top of the page

It is possible to have other decompositions (of the 7 040 squares) than decomposition in types. I show here 2 decompositions in sets of intermediate squares.

6.1 Decomposition with a given basis

You can make a review of the 7 040 squares with a given basis, the first one for example.

Each square generates an intermediate square, and this intermediate square generates a set of squares by tabulation with the first basis. The 7 040 squares can then be distributed in sets of disjointed intermediate squares. For each set, you can define an elementary square and search isomorphic sets (by transformations and permutations).

You find 9 elementary squares with the first basis (the numbers hereafter are those of my classical program of enumeration, which is a reduced/32 program):

1) 
 1  8  12  13 
714211
103156
16954
7) 
 1  7  14  12 
813211
94156
161035
13) 
 1  14  8  11 
712213
105154
16396
 
17) 
 1  16  5  12 
81349
103147
152116
25) 
 1  8  13  12 
161125
361510
14947
33) 
 1  12  13  8 
610315
117142
16549
 
35) 
 1  13  12  8 
610315
117142
16459
39) 
 1  15  10  8 
511414
126133
16279
54) 
 1  12  15  6 
79414
108133
165211


# of squareConditions on lettersNumber
of squares
(with the
intermediate
square)
Number of
isomorphic sets
Total number
of squares
Remark
13no conditions57621 152regular and semi-regular
1A+D=B+C
a+d=b+c
64483 072semi-regular
25A+D=B+C
a+d=b+c
2b=a+c
16641 024semi-regular
35a+d=b+c
A+2B+D+2c+2d=S
248192irregular
39a+d=b+c
A+2B+D+b+3d=S
1216192irregular
33A+D=B+C
a+d=b+c
A+2B+D+2c+2d=S
848384irregular
17A+D=B+C
a+d=b+c
A+B+2D+2a+2b=S
848384irregular
7A+D=B+C
a+d=b+c
A+B+2D+3a+c=S
480320irregular
54A+D=B+C
a+d=b+c
A+2B+D+b+3d=S
480320irregular
7 040


You find that the numbers of squares in the 9 elementary sets are 576 and its divisors (64, 24, 16, 12, 8 and 4). You haven't all the divisors. With the second basis, you find also sets of 32 squares.

The 7 040 squares of order 4 can be decomposed in elementary sets of q squares, q being a divisor
of (n!)2
.

It is possible to have other decompositions with the 5 other basis.

6.2 Decomposition with all the basis at the same time

You can do the same at the beginning but you apply after the 6 basis to each intermediate square. Then you have to choose each elementary square in order to have disjointed sets with the 6 basis.

You find 6 elementary squares among the 9 previous elementary squares:

Sub-
set
# of
square
Conditions
on letters
Number of squares
(with the intermediate square)
Total
number
of
squares
(6 basis)
Number
of
iso-
morphic
sets
Total
number
of
squares
Basis
#1
Basis
#2
Basis
#3
Basis
#4
Basis
#5
Basis
#6
I13no conditions5765765765765765763 45613 456
II1A+D=B+C
a+d=b+c
6464646464643842768
III25A+D=B+C
a+d=b+c
2b=a+c
16160001648321 536
IV33A+D=B+C
a+d=b+c
A+2B+D+2c+2d=S
8000801648768
V54A+D=B+C
a+d=b+c
A+2B+D+b+3d=S
4040401232384
VI7A+D=B+C
a+d=b+c
A+B+2D+3a+c=S
404404168128
7 040

This decomposition is more "symmetrical".
You have the same property: the 7 040 squares of order 4 can be decomposed in elementary sets of q squares, q being a divisor of (n!)2.

7. Different Generations and Decompositions
Top of the page

Finally, you have different ways to generate and to decompose the 7 040 magic squares of order 4:

7.1 Generations

  • the generation by elementary squares and variations of a same square:
    220 elementary squares with transformation method
    or 166 elementary squares with transformations * permutations (cf. The permutation method, § 3)

  • the generation by Gallic elementary squares and blocks (cf. § 5 above)
    Note that blocks of two Gallic elementary squares aren't intermediate squares. In a block, each Gallic elementary square can be transformed by transformation or permutation: it isn't a tabulation of values as in an intermediate square.

7.2 Decompositions

  • the decomposition in types (cf. page The transformation method, § 5.1),

  • the decompositions in intermediate squares (cf. § 6 above)
    with a given basis
    or with all the basis at the same time.

Maybe, it should be possible to find other generations and decompositions.