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!
 

2 comments:

  1. Everyone like Egypt Slots and that's why Ancient Egypt Classic certainly one of the|is amongst the|is probably considered one of the} hottest video games at Casino.com. However, I counsel you choose BGO Casino for this recreation - outcome of|as a outcome 점보카지노 of} they run a fantastic promotional provide that will allow you to win extra and spend much less. Website design, textual content, video games and all different digital content material aside from the Empire Materials are copyright © GAN PLC. Become a home entertainment skilled with our handpicked ideas, critiques and deals.

    ReplyDelete
  2. In December 2021, sports activities betting turned authorized in Ohio after Gov. Mike DeWine signed it into regulation. However, it is anticipated that Ohio 우리카지노 residents will not in a position to|be capable of|have the power to} place any wagers till Jan. 1, 2023 at the earliest. The last effort to legalize North Dakota sports activities betting was in 2019 and was unsuccessful.

    ReplyDelete