Magic-preserving Permutations on a 4x4 Magic Square

Question

Messing around with some magic-square puzzles, I faced the problem of deciding whether some two magical squares are, in fact, the one and same square wearing a different hat. It seemed to me, that for this job, the proper tool would be the application of

Magic-preserving permutations

Definition: A permutation of $N^2$ items is magic-preserving, if you can use it to reorder the numbers in any magic square of size $N \times N$ so that the resulting square is guaranteed to be magical.

For example, horizontal mirroring is a magic-preserving permutation for magic squares of any size: in the mirrored square

each row has the same numbers as before
each column has exactly the same numbers as some column in the original square
the diagonals are the same as in the original square, only swapped

Naming the permutations

To distinguish between the permutations, let's name them so that when applied to an alphabetical square, their name is readable from the resulting square. Again using horizontal mirroring as an example, its name is dcba-hgfe-lkji-ponm, because it works like this:

a b c d              d c b a
e f g h   (mirror)   h g f e
i j k l     -->      l k j i
m n o p              p o n m

The "identity permutation" or ("no permutation") is of course also magic-preserving, and its name is abcd-efgh-ijkl-mnop.

With these definitions out of the way, here's finally

The puzzle: Find all of them

How many different (distinguished by having a unique name) magic-preserving permutations exist for $4 \times 4$ magic squares?

Listing all of them constitutes a valid answer, and so does counting them (convincingly) without naming any of them. Providing a general formula of the count for different N is probably worth a scientific paper, or at least a research grant of a 100 rep provided by yours truly.

Epilogue

With the help of this tool, it's easy to identify duplicate magic-square puzzle solutions: magic square A is equivalent to magic square B if (and only if) one of the squares can be created by applying a magic-preserving permutation to the other.

Magic-preserving permutations are also of "immense" "practical" use, since they can be used to significantly narrow down the search space in a magic square puzzle.

I don't know how many times this particular idea has been invented by others, and by which names. Quick googling, followed by an exhaustive search of the magic-square tag (and a cursory glance at Wikipedia) revealed nothing. :-)

The graph-theory tag is there because there's definitely something graph-y going on in here; a graph-theoretical answer isn't required, though.

Jaap Scherphuis · Accepted Answer · 2018-04-04 15:31:41Z

These permutations form a group, in the mathematical sense. This means that if you do one magic-preserving permutation followed by another, the combined permutation is still magic-preserving. This is somewhat obvious, but it means that we don't have to explicitly find every permutation, we only need a small set of them (called generators) which when combined generate all of them.

Firstly there is rotation by 90 degrees:
 a b c d      m i e a
 e f g h  ->  n j f b
 i j k l      o k g c
 m n o p      p l h d
Combining this with itself we also get the 180 degree rotation and the anti-clockwise 90 degree rotation. Together with the identity permutation (the one that does nothing) we have $4$ magic-preserving permutations so far.
Next there is a reflection:
 a b c d      d c b a
 e f g h  ->  h g f e
 i j k l      l k j i
 m n o p      p o n m
The one here flips the square horizontally. Combining this with the rotations we get all the other reflections too (i.e. vertical or diagonal). We now have a total of $2\times 4=8$ magic-preserving permutations.

Thirdly we can swap the middle rows and middle columns:
 a b c d      a c b d
 e f g h  ->  i k j l
 i j k l      e g f h
 m n o p      m o n p
This keeps the corners in place, so it is clearly distinct from a rotation/reflection. Note that the diagonals keep the same set of numbers, as they should. Combining this with the rotations/reflections, we have $2\times 8=16$ magic-preserving permutations.

Note that we could instead swap the outer rows and outer columns. However, this is the same as doing the above permutation followed by a 180 degree rotation, so it is already included in the 16 permutations found so far.

Fourthly, we can turn it inside out by swapping the outer rows with the inner rows, and the outer columns with the inner columns.
 a b c d      f e h g
 e f g h  ->  b a d c
 i j k l      n m p o
 m n o p      j i l k
This is different from all the others found so far, because this has a different set of numbers on the corners. Combining this with the previous permutations, we have $2\times 16=32$ magic-preserving permutations.

I've come across this particular transformation before in a 3-dimensional context where you swap layers of a $4\times 4\times 4$ cube in all 3 axis directions. When David Singmaster used it for analysing the $4\times 4\times 4$ Rubik's Cube he called it evisceration. I've also seen it used in the analysis of 3-dimensional tic-tac-toe to simplify things.

I believe these $32$ are the only permutations that work on every magic square (I may edit in a proof later if I find one). If your magic square uses the consecutive numbers from $k$ to $k+15$, then it is also possible to replace every number $x$ by $2k+15-x$. This is also a permutation of the numbers, which would double the number of permutations to $64$. However, it might coincide with one of the $32$ magic-preserving ones above, in which case the number remains $32$.

Now that is what I call a spoiler block! (Also: great answer, this is pretty much exactly what I had in mind.) — Bass, Commented Apr 4, 2018 at 15:41
The evisceration technique can be extended to yield many more. For the sake of simplicity, assume n is even. Then there are at least n(n-2)/4 from extended evisceration. My challenge to you, a subpuzzle, is to find this technique. — Caleb, Commented Apr 4, 2018 at 18:32
@CalebDevine: For even $n$, you can do any permutation of the top $n/2$ rows, as long as you do the same permutation in mirror image on the bottom $n/2$ rows and then apply the same permutations to the columns. This gives $(n/2)!$ permutations of the $n\times n$ magic square (including the identity). The third permutation in my answer can also be generalised to give $2^{n/2}$ permutations. Multiply that with rotations and reflections, you get $8\times 2^{n/2}\times(n/2)!$ permutations of the $n\times n$ magic square. — Jaap Scherphuis, Commented Apr 4, 2018 at 18:51
Yes, Exactly! You've certainly the mind of a combinatorist :). I'm surprised though, these weren't in your answer above — Caleb, Commented Apr 4, 2018 at 19:01

Bass · Accepted Answer · 2018-04-06 03:23:34Z

As the others have indicated, there are

32

distinct permutations. Here is a simple proof.

In order for a permutation to work for all squares, each of the rows and columns, as well as the two diagonals, must remain together. Thus, {a,f,k,p} must be on one diagonal, while {d,g,j,m} must be on the other. Also {a,b,c,d} must be on the same row or column, etc.

Counting:

a can be anywhere on either diagonal: 8 options.
d is on the other diagonal, either on the same row or same column as a: 2 options.
m is on the same diagonal as d, also on the same row or column as a, but since d is already placed, m's location is fixed.
p is on the same diagonal as a, and on the same row or column as both d and m, therefore its location is fixed.
f can be in either of the two remaining empty locations on the same diagonal as a and p: 2 options.
k's location is now fixed as the fourth location on the diagonal containing {a,f,p}.
Once a, d, and f are placed, b's location is fixed: same row or column as a and d, same column or row as f.
With b placed, c's location is fixed as the last open spot on the row or column containing {a,b,d}.
With c placed, g must be on the same row or column, so its location is fixed.
Likewise, all remaining numbers' locations are fixed based on the locations of the already placed numbers.

Thus, there are $8\times 2\times 2 = 32$ possible permutations.

Mike Earnest · Accepted Answer · 2018-04-05 19:30:39Z

According to Jaap's answer, the set of magic square preserving permutations contains at least

90° rotation
horizontal reflection
evisceration (rotating each 2x2 corner sub-square by 180°)
crucifixion (interchanging the central columns, and same for the rows)
which together generate 32 permutations.

Are there any others? There is a brute force way to check:

List all 880 magic squares of order four, up to rotation and reflection, $m_1,m_2,\dots,m_{880}$. (I got this data from http://www.magic-squares.net/order4list.htm).
For each $i\ge 2$, compute the permutation $p_i$ which transforms $m_1$ to $m_i$.
For each $p_i$, check if $p_i$ is magic-preserving by applying it to each $m_j$.

I have done exactly this. The code is online at

https://repl.it/@mearnest/Magic-Square-Preserving-Permutations

Assuming the program works correctly, it should print out all of the magic-preserving permutations which are not generated by rotation and reflection.Just click the "run" button at the top, it takes about 20 seconds. When you do so, it prints exactly three permutations, which after are (suitable rotation/reflections of) the three nontrivial permutations (evisceration, crucifixion, and the combination of the two) listed by Jaap. Therefore, Jaap has found them all.

Stack Exchange Network

Magic-preserving Permutations on a 4x4 Magic Square