   Structure of Magic and Semi-Magic Squares, Methods and Tools for Enumeration by Francis Gaspalou    The two methods described in the two previous pages allow to deduce one square from another square, by transformation or permutation.

Here, an intermediate square is deducted from one square, and therefore all a set of squares. It is the intermediate square method: you look at a glance all a set of squares. The intermediate square is a parametric representation of this set of squares.

However, the intermediate square method is linked to the permutation method. At the limit, you can consider that the intermediate square method is a special case of the permutation method and you will see that the permutations are those coming from a "basis".

But in fact, the intermediate square method is a method in itself. You will see that this method is mainly used to enumerate and represent special sets of squares: regular and semi-regular sets. For order 4, these sets have a very large population (5 760 semi-regular squares, with at least one basis, on the 7 040) in front of irregular squares; for superior orders irregular squares are the most numerous and regular or semi-regular squares are the exception.

 1. Principle of the Method

The method consists in deducting from one square an intermediate square - sum of two elementary squares built with capital and lower-case letters - , and after in writing magic conditions of these letters, and finally in sweeping the domain of variation of these letters. By such a tabulation of parameters, a set of squares is obtained.

Different configurations for the values of the letters are possible (see § 3 hereunder); then you can generate others sets of squares from one intermediate square (as many as the number of different basis: see § 3).

The two squares are called the capital letter square and the lower-case letter square. They are the BENSON and JACOBY' notations - main reference I used in the beginning of my research - .

These two squares are orthogonal squares, that is to say the sum of the two squares gives a square with all the n² possible couples, each one occurring only one time.

Note that in other books, the two elementary squares are built with Greek and Latin letters. This notation is rather reserved to Latin squares and Greco-Latin squares (see § 4 hereunder).

Note also you can apply the group G of transformations to an intermediate square. I don't apply this group G and by personal convention, I limit enumeration strictly to the set of squares given by an intermediate square without any transformation.

 2. Example Top of the page   DURER's square:

 16 3 2 13 5 10 11 8 9 6 7 12 4 15 14 1

gives with the basis (a=1, b=2, c=3, d=4; A=0, B=4, C=8, D=12) the intermediate square:

 D+d A+c A+b D+a B+a C+b C+c B+d C+a B+b B+c C+d A+d D+c D+b A+a

 Therefore, 1 is replaced by A+a, 2 is replaced by A+b, etc.

For this intermediate square, the 10 magic conditions on the 4 rows, 4 columns and 2 diagonals give (a, b, c, d; A, B, C, D are now parameters):
A+B+C+D+a+b+c+d=34
A+D=B+C
a+d=b+c

By tabulation, that is to say when choosing a, b, c, d among the set {1, 2, 3, 4} and when choosing A, B, C, D among the set {0, 4, 8, 12}, and with respect to the above magic conditions, you obtain a set of 64 different squares.

In fact, other basis are possible for a, b, c, d, A, B, C, D (see next §) and finally you obtain 6 * 64 = 384 different squares, which are the classical 384 symmetrical squares of order 4.

From one square, you can have 384 squares!

 3. Different possible basis Top of the page   3.1 Definition

The n² first integers can be obtained by addition from the two arithmetic progressions:
 lower-case letters: 1, 2, 3, 4,..., n capital letters: 0, n, 2n, 3n,..., (n-1) n

A table of addition (cf. GARDNER) can be built:

 1 2 3 4 ... n 0 1 2 3 4 ... n n n+1 n+2 n+3 n+4 ... 2n 2n 2n+1 2n+2 2n+3 2n+4 ... 3n 3n 3n+1 3n+2 3n+3 3n+4 ... 4n ... (n-1)n n²

But there is not only one decomposition. For example for n=4, it is possible to build other tables of addition, as:

 1 2 5 6 0 1 2 5 6 2 3 4 7 8 8 9 10 13 14 10 11 12 15 16

I will call basis a set of n values for lower-case letters a,b,c,d,... and of n values for capital letters A,B,C,D,.... allowing to build such a table of addition, that is to say to generate the n² first integers.

 a b c d ... A A+a A+b A+c A+d ... B B+a B+b B+c B+d ... C C+a C+b C+c C+d ... D D+a D+b D+c D+d ... ... ... ... ... ... ...

In such a table, each letter, capital or lower-case, is occurring n times, therefore:
nA+nB+nC+...+na+nb+nc+...= n²(n²+1)/2
and then: A+B+C+...+a+b+c+...= S
where S=n(n²+1)/2 is the magic constant.
The sum of the numbers in the first diagonal of the table of addition is equal to S.

The n values for capital letters are of course different; idem for the n values for lower-case letters. Therefore I can range these values by growing values (for capital as well as for lower-case letters) and call by personal convention capital letters the sets including 0, lower-case letters the sets including 1 (1 is obtained with the sum 0+1): such a basis will be called an orderly basis. Then A=0 and a=1. This convention is only for orderly basis, and otherwise A can take the value 1 in any other basis.

Note than in an orderly basis, the sum of the 2 maximum values for capital and lower-case letters is equal to n² (D+d=16 for n=4).

Taking the successive numbers in the order of the rows of the addition table (from left to right and from top to bottom), you see that a basis is a way to design a special "permutation" on the n² first numbers. The intermediate square method is well a special case of the permutation method.

3.2 Enumeration of the different basis

This enumeration is done with a computer.

You can only compute the orderly basis.
For example, for n=4, you will search the numbers a, b, c, d; A, B, C, D as:
A=0 and A< B< C< D
a=1 and a< b< c< d
A+B+C+D+a+b+c+d=34
D+d=16
and allowing to generate by addition the 16 first numbers.
You find 6 orderly basis (classified here by growing values for lower-case letters):

Basis   Σ      σ
1,2,3,4;0,4,8,12  2410
1,2,5,6;0,2,8,102014
1,2,9,10;0,2,4,61222
1,3,5,7;0,1,8,91816
1,3,9,11;0,1,4,51024
1,5,9,13;0,1,2,3628

A basis can be defined by the value of the sum of capital letters Σ=A+B+C+D (or of the sum of lower-case letters σ=a+b+c+d, with the property Σ+σ=S where S=n(n²+1)/2=34 here).
The first basis is classical: you have σ=n(n+1)/2, and Σ=n²(n-1)/2.

In fact, 3 elementary basis (the 3 first ones for example) are sufficient to define the set of 6 basis, because the 3 other ones can be deducted by the theorem:
If (a, b, c, d; A, B, C, D) is a solution, then (A+1, B+1, C+1, D+1; a-1, b-1, c-1, d-1) is also solution.
I call this last basis the corresponding basis.
The associated square to the corresponding basis is obtained by permutation of capital and lower-case letters (on the associated square to the first basis).
The corresponding tables of addition are symmetrical by the first diagonal. You can suppose for example B>b-1 for reducing enumeration to 3 elementary basis.

You see a posteriori than the 6 basis are symmetrical for capital and for lower-case letters, that is to say you have for all the basis:
A+D=B+C=M
a+d=b+c=m
(and M+m= n²+1).

Here are the number k of orderly basis for the first values of n:

n            k
32
46
52
614
72
820

k is even. I call the k/2 first orderly basis the elementary basis. There are sufficient to describe all the set of k basis.

The 7 first orderly basis for n=6 are (always classified according to growing values for lower-case letters):
 1, 2, 3, 4, 5, 6; 0, 6, 12, 18, 24, 30 1, 2, 3, 7, 8, 9; 0, 3, 12, 15, 24, 27 1, 2, 3, 10, 11, 12; 0, 3, 6, 18, 21, 24 1, 2, 3, 19, 20, 21; 0, 3, 6, 9, 12, 15 1, 2, 5, 6, 9, 10; 0, 2, 12, 14, 24, 26 1, 2, 7, 8, 13, 14; 0, 2, 4, 18, 20, 22 1, 2, 13, 14, 25, 26; 0, 2, 4, 6, 8, 10

and the 10 first for n=8:
 1, 2, 3, 4, 5, 6, 7, 8; 0, 8, 16, 24, 32, 40, 48, 56 1, 2, 3, 4, 9, 10, 11, 12; 0, 4, 16, 20, 32, 36, 48, 52 1, 2, 3, 4, 17, 18, 19, 20; 0, 4, 8, 12, 32, 36, 40, 44 1, 2, 3, 4, 33, 34, 35, 36; 0, 4, 8, 12, 16, 20, 24, 28 1, 2, 5, 6, 9, 10, 13, 14; 0, 2, 16, 18, 32, 34, 48, 50 1, 2, 5, 6, 17, 18, 21, 22; 0, 2, 8, 10, 32, 34, 40, 42 1, 2, 5, 6, 33, 34, 37, 38; 0, 2, 8, 10, 16, 18, 24, 26 1, 2, 9, 10, 17, 18, 25, 26; 0, 2, 4, 6, 32, 34, 36, 38 1, 2, 9, 10, 33, 34, 41, 42; 0, 2, 4, 6, 16, 18, 20, 22 1, 2, 17, 18, 33, 34, 49, 50; 0, 2, 4, 6, 8, 10, 12, 14

These results seem original.

If n is a prime, then it seems that k=2 (it is not possible to find other solutions than the 2 classical solutions).
It seems also that the properties found for n=4 can be generalized: all the basis are symmetrical, for capital letters as well as for lower-case letters.

 4. Latin and Gallic Squares. Regular and Irregular Squares. Greco-Latin Squares Top of the page   The notion of basis defined at the previous paragraph is very fruitful for specific sets of magic or semi-magic squares: the squares built from intermediate Greco-Latin squares, therefore made from two elementary orthogonal Latin squares. These squares are also called eulerian squares. Among these squares, the regular squares are a very important set.
I remember that a Latin square is a square where each letter occurs only one time in each row and each column. A Latin square is diagonal if the two diagonals have also the property. A Latin square is magic if the two diagonals are magic. A Latin diagonal square is a specific kind of Latin magic square: in a Latin magic square, the two diagonals are magic, but not necessarily Latin.
A Greco-Latin square is made from two orthogonal Latin squares (each couple of letters occurs only one time). A Greco-Latin square made from two orthogonal Latin diagonal squares is said a diagonal Greco-Latin square. A Greco-Latin square made from two orthogonal Latin magic squares is said a magic Greco-Latin square.
The rows and columns of a Latin square (or of a Greco-Latin square) are said regular.
A semi-magic square is said regular if it is possible to make a correspondence with an intermediate Greco-Latin square.
A magic square is said regular if it is possible to make a correspondence with an intermediate diagonal Greco-Latin square.
Caution! The regular squares are a part of magic eulerian squares. For example, you have 1 536 magic eulerian squares of order 4 with the first basis: 1 152 are regular and 384 are magic eulerian but with diagonals only magic and not regular.

The following fundamental property can be stated: if a Greco-Latin square of order n can be built, then it is possible to associate k (n!)² semi-magic squares to it.
For a given basis, a can take n values, b can take the (n-1) remaining values, c can take (n-2) remaining values, etc., therefore you have n! values for lower-case letters, so much for the capital letters; and you have k different basis giving finally k disjointed sets.
This proposition seems original.

But the k (n!)² squares in the associated set are not only semi-magic. Their real properties depend on those of the original Greco-Latin square. For example:
• the 3 456 semi-pandiagonal squares of order 4 (n=4, k=6) are generated from one Greco-Latin square which is semi-pandiagonal,
• the 28 800 pandiagonal squares of order 5 (n=5, k=2) are generated from one Greco-Latin square which is pandiagonal and cyclical,
• the only isomorphic set of 28 800 pandiagonal*IT squares of order 5 is generated from the previous Greco-Latin square transformed by IT or A (i. e. by application of the group G of order 32: see Appendix 4, § 2),
• it is impossible to build a Greco-Latin square of order 6 (cf. EULER and TARRY),
• the 304 819 200 regular pandiagonal squares of order 7 can be built with 6 different Greco-Latin squares which are pandiagonal and cyclical (cf. BENSON and JACOBY, page 139); each one generates 50 803 200 squares (n=7, k=2),
• the application of the group G of order 192 to each of these 6 Greco-Latin pandiagonal squares of order 7 generates 7 other isomorphic sets of squares: these squares are regular but not pandiagonal (and you get a grand total of 8*304 819 200 = 2 438 553 600 regular squares)
• ...

Note that Greco-Latin squares exist for any order different from 2 and 6 (cf. BOUTELOUP, reference given hereafter).

In fact, the important thing is the lack of conditions on capital and lower-case letters. The above-mentioned proposition could rather be expressed: if an intermediate square of order n can be built without any condition on capital and lower-case letters, then it is possible to associate k (n!)² semi-magic squares to it.

Note that the notions of regular lines or Greco-Latin squares are specific to a basis. A line is not regular (or a square is not Greco-Latin) by itself; if you change the basis the property may disappear.

The following property can be stated: the 2 (n!)² squares given by a Greco-Latin square of order n (with one basis and with its corresponding basis) have a group structure.
I haven't really a demonstration. It is true for order 4 and 5.
For order 4, the 1 152 squares have a group structure, but not the k (n!)² = 3 456 semi-pandiagonal squares (see Appendix 3, § 3); on the k=6 basis, there are k/2=3 elementary basis.
For order 5, the 28 800 squares have also a group structure.
This probable property can also be expressed in the following way: you have a group structure on the 2 (n!)² squares obtained by association between the (n!)² squares given by a Greco-Latin square of order n and the (n!)² squares given by the second Greco-Latin square obtained by permutation of capital and lower-case letters.

There is a large literature on Latin squares and Greco-Latin squares. I think the best book that gives the state of the art on this subject is the book of Jacques BOUTELOUP, Carrés Magiques, Carrés Latins et Eulériens, éditions du Choix, 1991 (sorry, it is in French!). One classical subject in this literature is the regular cyclical squares (see for example the book of BENSON and JACOBY).

But curiously, there is very little works on irregular squares (each letter, capital or lower-case, doesn't occur one time and only one time in each row, column or diagonal). CANDY seems the reference in this matter; BENSON and JACOBY deal with some specific pandiagonal 7x7 squares (irregular for lower-case letters, but regular for capital letters). The irregular squares - irregular for capital letters as well for lower-case letters - are the most numerous (see hereafter).

Curiously too, I did not find any work in the literature on what I call the Gallic squares (squares with n letters a, n letters b, etc.). It is not compulsory, as in the Latin squares, that each row (or column) has only one a letter; it is sufficient that a occurs n times in the square. Idem for b, etc. The sums of rows, columns and two diagonals are not necessarily equal to σ. I call these squares Gallic by opposition to Latin because Gallic people was known to be less orderly than Latin people! The "interesting" Gallic squares are those that have an orthogonal. These squares constitute an unexplored mine! Their properties have to be studied.
I began to do it. The Gallic squares can be used to find magic squares: you build first a Gallic square and you search after the orthogonal squares to this Gallic square. This method is very fruitful when you search specific properties of the magic square or when the general program gives very little solutions because the large number of cases to examine.

Therefore, to search an orthogonal to a given lower-case letter square (or capital letter square) is a very powerful method to find magic squares!
Ex: you can search "self orthogonal" or "auto-orthogonal" squares (the capital letter square is the lower-case letter square symmetrical by the first diagonal) or most generally a capital letter square which is the lower-case letter square transformed by a transformation of group G. In this way, you generate a magic square from a lower-case letter square only.

You can reduce the enumeration of orthogonal squares to a given lower-case letter square (Latin or Gallic) using the notions of group G (transformation and permutation):
• if the Gallic square is the same by a transformation, then this transformation is also a transformation for any orthogonal square. Therefore you have to find all these transformations among all the transformations of the classical group G (e.g.: group of 192 if you deal with Latin squares of order 6). These transformations form a subset of the classical group G, but they belong also to the group G (transformation) of the orthogonal squares.
• you have to find after the transformations of the classical group G which give a lower-case letter square equivalent by permutation (to the lower-case letter square of origin). These transformations form an other subset (including the previous subset). If you have an orthogonal square, you can apply any transformation of this new subset to the capital letter square and add to the lower-case letter square: the resultant square is also an orthogonal square.
Examples of application are given in Appendix 4, § 4 and Appendix 5, § 1 for Latin diagonal squares.

Note: 3 different kinds of squares can be defined:
• the regular squares: the sum of capital letters is equal to Σ and each letter occurs only one time; idem for lower-case letters and σ;
• the semi-regular squares: the sum of capital letters is equal to Σ (therefore the sum of lower-case letters is equal to σ); with my conventions, regular squares are a subset of semi-regular squares;
• the irregular squares: the sum of capital letters is different from Σ (or equivalent definition for lower-case letters), but the sum capital letters + lower-case letters is naturally equal to S;
all these sums being for all the "lines" of the square (n rows + n columns + 2 diagonals if it is a magic square, or n rows + n columns if it is a semi-magic square).

All these definitions are specific to a basis. A square is not regular or irregular in itself, but by reference to a basis.
E.g.: with the classical basis ( 1, 2, 3, 4; 0, 4, 8,12), the 7 040 squares of order 4 can be distributed in
5 248 semi-regular squares (with 1 152 regular squares),
1 792 irregular squares.
There are 5 760 semi-regular squares with at least one basis among the 7 040 magic squares (and there are 3 456 regular squares with at least one basis among the 7 040).
See Appendix 3, § 5.

 5. Structure of Magic Squares and Semi-Magic Squares of order n Top of the page   I suppose - but it is only a conjecture - that magic squares and semi-magic squares of order n can be decomposed in elementary sets.

With the intermediate square method, the largest set - if it exists - is in relation with a Greco-Latin square and has (n!)2 squares; there is no conditions on capital and lower-case letters (except A+B+C+...+a+b+c+...=S).

The other elementary sets are obtained with conditions on capital and lower-case letters; they are sets with q squares, q being a divisor of (n!)2 .

As explained in page about The transformation method § 5.1, it is necessary to associate some isomorphic sets (but not all the isomorphic sets) to each elementary set.

This conjecture is true for magic squares of order 4 (see Appendix 3, § 6)

 6. Remark Top of the page   The intermediate square method is a powerful tool for enumerating regular squares or semi-regular squares.

For order 4, these squares constitute the largest family (cf. § 4 above), but for orders superior to 4, these squares are not the most numerous: irregular squares is the rule, regular or semi-regular squares the exception. For example:
• for order 5, you have only 57 600 regular squares (they are pandiagonal or pandiagonal*IT), but the total number of squares is 2 202 441 792,
• for the symmetrical pandiagonal 7x7 squares, I computed in August 2004 the number of semi-regular squares. I found 7 658 elementary solutions with A1=1 and 4 924 elementary solutions with A2=1, therefore a total of 12 582 * 96 = 1 207 872 semi-regular squares. There are 12 582/1 682 557 = 0.75 % of semi-regular squares among all the symmetrical pandiagonal squares. There are 27 648/1 207 872 = 2.29 % of regular squares among semi-regular squares.

For irregular squares, the intermediate square method can also be applied, but the set of generated squares is very little.    