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.
No comments:
Post a Comment