Thursday, January 3, 2019

3x3 Semi-Magic Squares

Recently I was trying to solve a puzzle involving 3x3 semi-magic squares - 3x3 grids filled with integers 1,2,...,9  in such a way that each cell contains a different integer and the sum of the numbers in each row and each column is the same. It is easy to see that for a 3x3 semi-magic square this sum (sometimes called the magic constant) should be 15. The definition of a semi-magic square does not require (but does not preclude) that the sum of the numbers in each diagonal should also be equal to the magic constant. If that's the case a semi-magic square becomes a magic square. Here are a few examples of 3x3 semi-magic squares. The middle square is not only a semi-magic square, but also a magic square.

I could not find a list of all 3x3 semi-magic squares, so I wrote a little program to generate my own. If you ever need a list of all these squares,  -  here it is, arranged in lexicographical order.

It turned out, there are 72 different 3x3 semi-magic squares. But how "different" are they really? It is easy to see that each of the 8 geometric transformations of a square (identity, 90°, 180°, 270° counterclockwise rotations around the center, reflections across the horizontal axis, the vertical axis, and each diagonal) transforms a semi-magic square into another semi-magic square.

We can therefore split 72 semi-magic squares into 9 non-intersecting equivalency classes. Members of same class are reflections or rotations of each other; members of different classes are not. Below are representatives of each of the 9 classes . Every semi-magic square in a class is a geometric transformation of its representative. All 72 semi-magic squares can be produced out of these 9 by applying geometric transformations. From this perspective there are only 9 "substantially different" semi-magic squares.

But why stop at just geometric transformations? What other transformations turn one semi-magic square into another? Column swaps, row swaps (and sequences of them) do the trick. There are 6 transformations (including identity) done by row permutations and 6 transformations done by column permutations.  The picture below shows the 6 row permutations.

It turns out the 6 row permutations are independent from the 6 column permutations and taken together as sequences of row/column permutations, they constitute 36 different transformations.  Based on this transformation group we can split 72 semi-magic squares into just 2 non-intersecting equivalency classes. Members of the same class are sequences of row/column permutations of each other, members of different classes are not. Here are the 2 classes representatives. All other semi-magic squares are produced out of these two by series of row/column permutations.

Look carefully at the two representatives above... they are reflections of each other across the main diagonal! What does that mean? It means that all 72 semi-magic squares are the result of applying row/columns permutations and geometric transformations to just one semi-magic square. And we a free to choose any one of them as "the one". Let's actually make it a magic square, just for fun!

No comments:

Post a Comment