Recreational APL
Eugene McDonnell
Fall 1976

Magic Squares and Permutations

APL has helped in the discovery of some interesting connections between magic squares and permutations. This article discusses some of them, and gives a few problems for you to solve.

The APL function for generating odd-order magic squares is well known: the basic algorithm appears in Sandra Pakin’s APL/360 Reference Manual, published by SRA, and is attributed to Ray Polivka (I have seen only iterative algorithms for this function in other programming languages):

      ms←r⊖r⌽m

where m is the square matrix formed by (n,n)⍴⍳n*2 , and r is the vector of n elements (⍳n)-⌈n÷2 . For example, if n is 3 , then m is

      1 2 3 
      4 5 6
      7 8 9

and r is ¯1 0 1 . After applying the first rotation we have

      3 1 2
      4 5 6 
      8 9 7

and after the second rotation

      8 1 6
      3 5 7 
      4 9 2

+/ms , +⌿ms , +/1 1⍉ms and +/1 1⍉⌽ms can be used to verify that the row, column, and diagonal sums all add to the same amount.

You may wish to verify that, if f is the function that applies rotations along the two dimensions of a square matrix in the manner shown, then f m is a magic square if m is an odd-order square matrix of integers in row-normal order. Then note that f f m is equal to ⌽⊖m ; that f f f m is also magic; and that f f f f m is equal to m .

If we add the sums of the broken diagonals (i.e. 8 7 9 , 3 1 2 , 3 9 6 , and 4 1 7), we get sums different from the magic sum 15 . Let me suggest an experiment: try generating other odd-order magic squares by this algorithm, and see what the broken diagonal sums are. Problem: determine the rule for when all the diagonal sums are the same.

There are eight possible variations of the row normal ordering, corresponding to the eight elements of the group of symmetries of the square:

      1 2 3   7 4 1   9 8 7   3 6 9 
      4 5 6   8 5 2   6 5 4   2 5 8 
      7 8 9   9 6 3   3 2 1   1 4 7

      3 2 1   1 4 7   7 8 9   9 6 3
      6 5 4   2 5 8   4 5 6   8 5 2 
      9 8 7   3 6 9   1 2 3   7 4 1

We obtain a magic square no matter which of these squares we begin with. It’s easy to generate the first in this series. How do you go about generating the other seven in APL? If you generate them all, and then apply the magic square function to each, you end up with eight trivially different magic squares:

      8 1 6   4 3 8   2 9 4   6 7 2
      3 5 7   9 5 1   7 5 3   1 5 9
      4 9 2   2 7 6   6 1 8   8 3 4

      6 1 8   8 3 4   4 9 2   2 7 6
      7 5 3   1 5 9   3 5 7   9 5 1
      2 9 4   6 7 2   8 1 6   4 3 8

The first four of these have an especially interesting property: their ravels are permutations which are equal to their downgrades:

      (⍒,m)^.=,m

For example, letting ms1 be the first of these,

      ,ms1
8 1 6 3 5 7 4 9 2
      ⍒,ms1
8 1 6 3 5 7 4 9 2

The other four have the property that their ravels are permutations which are equal to their double downgrades:

      (⍒⍒,m)^.=,m

For example, letting the first matrix in the second row be ms5 ,

      ,ms5 
6 1 8 7 5 3 2 9 4
      ⍒,ms5 
8 3 4 1 5 9 6 7 2
      ⍒⍒,ms5 
6 1 8 7 5 3 2 9 4

The question arises: Is their any correlation between self-downgrading permutations (sdp’s) and magic squares? That is, does every sdp of order n*2 give rise to a magic square of order n , for n odd? And, conversely, does every odd-order magic square give rise (possibly after rotation and reflection) to an sdp? The answer is no.

Let’s discuss the general topic of sdp’s, first. For a given length of permutation, how many sdp’s are there?

Let’s begin by trying to construct an sdp, say of length 9 . We find that the first element can’t be 1 , nor can it be 9 . Each is contradictory. We can’t put 5 as the first element, either, since this would put 9 as the fifth element, indicating that 5 is the 9 th element: another contradiction. (In fact, the only element that can be located in the central position is the central element, and thus we must place 5 in the fifth position.) This leaves 6 elements that can be used as the first element: 2 , 3 , 4 , 6 , 7 , and 8 . Suppose we choose 6 as the first element. Having made the choice, we find that this forces the location of four elements altogether, as follows: 6 in position 1 forces 9 to be in position 6 (since the element in position 1 gives the location of the largest element); 9 in position 6 forces 4 in position 9 (since the element in position 6 gives the location of the sixth largest element, that is, 4); and 4 in position 9 forces 1 in position 4 . So far we have:

      6 _ _ 1 5 9 _ _ 4

Of the remaining elements 2 , 3 , 7 , and 8 , we find that neither 2 nor 8 can be used in the second position, for the same reason that neither 1 nor 9 could be used in the first position. Thus, either 3 or 7 can be used there. If we choose 3 as the second element, we find again that the location of four elements is forced: 3 in position 2 forces 8 in position 3 ; 8 in position 3 forces 7 in position 8 ; and 7 in position 8 forces 2 in position 7 :

      6 3 8 1 5 9 2 7 4

Thus we have created an sdp. When we put it to the test to see whether it can be made into a magic square, we find that it is not magic at all:

      6 3 8 
      1 5 9 
      2 7 4

We also have a clue to enumerating the sdp’s for a given order: first, since elements are chosen four at a time (except for a possible central element), sdp’s are possible only for orders 4×n or 1+4×n . Since, at any time, we can choose the next element in two fewer ways than the number of unfilled positions remaining, for a given n , the number of sdp’s is ×/¯2+4×⍳n . Tabulating for the first several values of n we get:

The numbers in this series correspond to those in series 808 in the indispensable volume A Handbook of Integer Sequences, by N. J. A. Sloane (Academic Press, N. Y., 1973). Sloane describes them as coefficients of Hermite polynomials, and gives the reference MTAC 3, p. 168, 1948. The article has something to do with approximating polynomials, and nothing at all to do with permutations.

Another formula for obtaining values in the same series is ×/n+⍳n . Thus, it should be possible to derive one formula from the other. As a problem, try to work out a proof in APL of this fact. You want to show that the following samples, and all like them, give the same result:

      ×/2           ×/2
      ×/2 6         ×/3 4
      ×/2 6 10      ×/4 5 6
      ×/2 6 10 14   ×/5 6 7 8

The twelve sdp’s of order 9 are:

 *2 9 4 7 5 3 6 1 8   *8 1 6 3 5 7 4 9 2
  2 9 6 3 5 7 4 1 8    8 1 4 7 5 3 6 9 2
  3 4 9 8 5 2 1 6 7    7 6 1 2 5 8 9 4 3
  3 6 9 2 5 8 1 4 7    7 4 1 8 5 2 9 6 3
 *4 3 8 9 5 1 2 7 6   *6 7 2 1 5 9 8 3 4
  4 7 2 9 5 1 8 3 6    6 3 8 1 5 9 2 7 4

The sdp’s which form magic squares of order 3 are marked with a star. The sdp’s in the left and right columns are reversals of each other. It is true that if p is an sdp, then so is ⌽p . The left and right columns are complementary in that, if l is an sdp from the left column and r is the corresponding sdp from the right column, the elements of l+r (that is, l+⌽l) are identical.

Magic squares of odd order constructed in the manner described above are named after Simon de La Loubère, who brought this construction from Siam to France in 1687.

Permutations that are self-double downgrading (sddp) are more common than those that are self-downgrading. Any sddp must have a downgrade which is also an sddp. That is, if p is the same as ⍒⍒p , then, letting q equal ⍒p , we have q equal to ⍒⍒⍒p , and therefore q is also equal to ⍒⍒q . In particular, it should be clear that any sdp is also an sddp (since if p is equal to ⍒p , then also ⍒p is equal to ⍒⍒p , and therefore p is equal to ⍒⍒p).

If p is an sddp of odd length n , the only element that can be in the central position is the central element. It is true that if the reversal of a permutation is equal to its downgrade, then it is also an sddp: that is, if (⌽p)^.=⍒p .

To enumerate the sddp’s, note that a permutation that has a reversal equal to its downgrade is also a permutation whose reversal is complementary to the permutation (that is, the elements of p+⌽p are identical and equal to 1+⍴p). Also, if the permutation is of odd length, the central element must have the central value. For example, if ⍴p is 5 , then p[3] must be 3 for the permutation to be an sddp. If we let g be a function that enumerates the sddp’s of order k , it is clear that g 1+2×n is the same as g 2×n . If we choose as our first element a , then our last element must be 1+k-a . This leaves k-2 ways to choose the next element, which choice forces the choice of the element in the next-to-last position, and so on. If we have a permutation of length 2×n , there are 2×n ways we can choose the first element, and this forces a choice of the last element. We are left with g ¯2+2×n ways to choose the next element. Thus g 2×n is equal to (2×n)×g ¯2+2×n . From this, we conclude that g 1+2×n is equal to g 2×n which is equal to (!n)×2*n . The first several values of g n are tabulated below:

The numbers in the series 1 2 8 18 ... are called double factorials, and the series is number 742 in Sloane.

Magic squares of doubly-even order (that is, having sides whose length are multiples of 4) may be formed by another algorithm, not as simple as that for the odd-order squares. The famous magic square in Durer’s engraving Melencolia I is formed by one of the standard techniques for generating doubly-even magic squares. This square is:

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

The central squares in the bottom row give the year of the engraving. As another problem, try writing an APL function to generate such squares (that is, order 4, 8, 12, etc.) The ravels of such squares are not self-downgrading. However, there are four ways in which their ravels a re self-upgrading. If we call Durer’s magic square d , then

      (⍋,d)^.=,d .

The permutations which are self-upgrading (sup’s) have been studied extensively. Muir (A Treatise on the Theory of Determinants, Dover, N. Y., 1960) calls them self-conjugate permutations . According to Knuth (Sorting and Searching, Addison-Wesley, 1973, p. 48) they were first studied by H. A. Rothe, using the term self-inverse, in 1800. Knuth calls them involutions.

The number of sup’s is given by Rothe’s formula: t 1 is 1 , t 2 is 2 , and t n is (t n-1)+(n-1)×t n-2 for n greater than 2 . The first several values of t n are:

       n      t n

       1        1 
       2        2
       3        4
       4       10
       5       26
       6       76
       7      232
       8      764
       9     2620
      10     9496
      11    35696

The formula can be derived by observing that t n-1 gives the number of sup’s of order n that begin with 1.  There are t n-2 sup’s of order n that begin with each of the remaining n-1 elements, whence the term (n-1)×t n-2 . The series is number 469 in Sloane.

Edouard Lucas, in his Theorie des Nombres, Paris, Gauthier-Villars et Fils, 1891, studies the question of permutation matrices that are invariant to certain rotations and transpositions. This subject is closely related to the questions of sdp’s, sddp’s, and sup’s. Lucas’ book is well worth reading today.

The third kind of magic square is that which is singly-even, that is, of order 6, 10, 14, etc. (There is no magic square of order 2). The algorithm for generating such magic squares is more difficult to express than the other two, and is left as a problem for the reader. My colleague Howard Smith has written a function for generating magic squares of all orders but 2 in about a dozen lines.

Here is a result which bears on the topic of sup’s: If we take a truth table of order n (formed, for example, in 0-origin, by t←(n⍴2)⊤⍳2*n), permute its rows by an sup p of length n , and evaluate the result in base 2 , we obtain a permutation q which is also an sup. For example:

      t←(4⍴2)⊤⍳2*4
      t
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
      p
2 3 0 1
      ⍋p
2 3 0 1
      t[p;]
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
      2⊥t[p;]
0 4 8 12 1 5 9 13 2 6 10 14 3 7 11 15
      ⍋2⊥t[p;]
0 4 8 12 1 5 9 13 2 6 10 14 3 7 11 15

This gives a way of using an sup of order n to generate an sup of order 2*n (The basic part of this result was discovered by my colleague Joey Tuttle).

Some miscellaneous problems:

Prove that, for a permutation p , p is equal to ⍋⍋p .

Prove that, for a permutation p , p is equal to ⍒⍒⍒⍒p (Benkard’s observation, 1968).

Create a function to produce odd-order magic squares which uses matrix product rather than rotations.