Talk:Most-perfect magic square

From Wikipedia, the free encyclopedia

[edit] Move!

Dear friends, please note that Most-perfect magic square should be used and Most-perfect square and Talk:Most-perfect square should be redirected. See google "most-perfect magic square" and google "perfekte magische quadrate". Regards Gangleri 18:32, 2004 Oct 9 (UTC)

[edit] Templates

Halló! I created some templates to ilustrate some special properties of the 4x4 type Most-perfect magic squares.

With the availability of <inputbox> (meta:Help:inputbox) and its expected improuvments "one click previews" for these properties could be generated without overloding the page.

Please let me know if you will have some time to generate more of the required templates and to work on this page. Please drop a note at meta:examples. Thanks in advance. Best regards Gangleri | Th | T 09:45, 14 July 2005 (UTC)

Tip: to see how to use the templates, edit this item. Templates used are listed at the bottom of the page -- LarryLACa 18:33, 4 November 2005 (UTC)

[edit] Jain squares

[edit] Comments on Jain Squares

You ask on Meta:Babel about if their is some interest in the Jain magic squares.

I guess that there is some call for a curtural note on the use of these squares in Jain tradition, with some references and explaining a bit more about the cultural and cosmological significance.

A few Q's:

Whats the significance of 384 is it the number of different Jain squares?

Some of the examples show negative numbers and are hence not technically Most Perfect Magic Squares.

I didn't really understand the special properties of the squares, "fractional mirroring NW - SE" etc. Are these ways to generate new squares?

I suggest that the info be removed from Meta:Babel, its not really appropriate there. Also see the editoral guidlines, for what should and should not be included.

Pfafrich 09:50, 6 August 2005 (UTC)

[edit] some notes about analysis methods for magic squares

• From the mathematical point of view many different representations are equivalent:

1. either using "standard" values from 1 to n²
2. using the transformation n -> (n -1) and "working with squares containing the values 0 to n² - 1
3. for n eaven: using the transformation n -> (magical constant - 2n) and obtaining consecutive odd values from - n² + 1 to n² - 1
   note: instead of last transformation its "negative" transformation n -> (2n - magical constant) can be used
   
4. for n odd: -t, -(t-1), ..., (t-1), t where t = -(n^2-1)/2

Selecting either representation is a mather of personal prefference: "Good loves / likes / enjoys odd numbers." is attributed to Gottfried Wilhelm Leibniz: "numero deus impari gaudet".

[edit] construction method for 4n type squares

For 4n type squares a construction method can be specified where the "odd" numbers apear in consecutive order and their sign follows another "repetitive pattern":

-15     13      11      -9
7       -5      -3      1
-1      3       5       -7
9       -11     -13     15

Starting with

63      61      59      57      55      53      51      49
47      45      43      41      39      37      35      33
31      29      27      25      23      21      19      17
15      13      11      9       7       5       3       1
1       3       5       7       9       11      13      15
17      19      21      23      25      27      29      31
33      35      37      39      41      43      45      47
49      51      53      55      57      59      61      63

placing the "pattern" for the signs in the center

x                       x
        x       x       
x                       x
        x       x       

and expanding it

-1              -1                      -1              -1
        -1              -1      -1              -1      
-1              -1                      -1              -1
        -1              -1      -1              -1      
-1              -1                      -1              -1
        -1              -1      -1              -1      
-1              -1                      -1              -1
        -1              -1      -1              -1      

helps you generate

-63     61      -59     57      55      -53     51      -49
47      -45     43      -41     -39     37      -35     33
-31     29      -27     25      23      -21     19      -17
15      -13     11      -9      -7      5       -3      1
-1      3       -5      7       9       -11     13      -15
17      -19     21      -23     -25     27      -29     31
-33     35      -37     39      41      -43     45      -47
49      -51     53      -55     -57     59      -61     63

using now either n -> (magical constant - n)/2 or n -> (magical constant + n)/2 generates either a magic square or its complement in the second case

64      2       62      4       5       59      7       57
9       55      11      53      52      14      50      16
48      18      46      20      21      43      23      41
25      39      27      37      36      30      34      32
33      31      35      29      28      38      26      40
24      42      22      44      45      19      47      17
49      15      51      13      12      54      10      56
8       58      6       60      61      3       63      1

Beside the main and secondary diagonal a parallel of each will sum(e) to the magic constant too. Many 2x2 subsquares will add to magic constant/2.

notes:

1. For n=1 the square generates the Yang Hui square which has the same Frénicle standard form is "table of Jupiter". Some years ago I found the / an example for n=2 in a book (written in German) about Kabbalah beside another 8x8 magical square.

notes about prefferences:

1. While some people are "impressed" by great numbers others (as me) might be impressed about "nothing" – zero playing a major role in indian culture.
2. All magic squares (also those where higher numbers are involved) when represented in odd value notation have the magic constant equal to zero.
3. The "magic" of the arangement relates to the equilibrium. If transformations will be applied to a sqaure nothing is "added" and only a rearangment is performed preserving the equilibrium and possibly some other properties like transforming a pandiagonal magic square in another pandiagonal or a most perfect into another most perfect.
4. the second example was build some years ago as an exercise using the odd value representation in order to find some greather magic squares starting from a known Jain square

• Regards Gangleri | Th | T 05:12, 9 August 2005 (UTC)

Compare with examples of Fabrizio Pivari: 4 x 4 jupiter.gif, 8 x 8 mercury.gif etc.

Regards Gangleri | Th | T 14:32, 10 August 2005 (UTC)

[edit] method of generating most-perfect magic squares of order 2ⁿ

• The method described below does neither cover the general case of squres of order 4n nor does it generate all magic squares for order 2ⁿ of any order higher then 4 (2²). Nevertheless it is possible to generate a number of 2ⁿ!*2²ⁿ most-perfect magic squares.
• The method is useing neither exhaustive tests nor recursions to distinguish "matchs" / "does not match". Recursion is used either to identify "usefull neighbour values" for a given start value – this requires log₂(2²ⁿ) = 2n steps – or recursion is used (mainly) to "fill gaps" on raws and / or columns for the 1st requirement: Each 2×2 subsquare sums to 2s, where s = n² − 1.
• Because the / some 4x4 sqaures where known long time ago in India and the method is straight forward it is very likely that it has been / equivalent variants of it have been known long time ago and records could still be found.
• So far I was not able to read about the work of Dame Kathleen Ollerenshaw and David Brée on these topics. Beside printed books and articles http://www.magic-squares.com/ is often mentioned in link collections on magical sqaures but unfortunatelly the original content is not available any more on that site since more years.
• As the described algorithm was found due to own observations it should be concluded that it could have be found (long time) before. Various approaches can be used for analysis of (magic) squares. In the following the squares are refered using values from 0 to 2²ⁿ-1. No proof is provided. Would be happy for any feedback on this and related topics. Gangleri | Th | T 09:01, 9 August 2005 (UTC)

I strongly suggest you do not add content based on your own original observations without finding a corroborating authoritative source. See Wikipedia:No original research. That's not to say you have to add the opposite - just don't talk about this for now. Deco 02:10, 27 January 2006 (UTC)

[edit] algorithm

The algorithm is based on some observations about the 4x4 most-perfect magic squares reffered also as Jain squares. There the neighbour values of a given value are always the same. See all 384 squares and the "neighbourship" table at meta:. Beside the transformations of mirroring and rotations used to obtain the Frénicle standard form also "arbitrary shifting" would "generate" 4x4 most-perfect magic squares. "Repeating the squares" is probably an old technique and "understanding" them as a subset of the "endless plain" should be nothing new.
There is no doubth that the transformations mirroring, rotation and shifting will preserve neigbourship (up, down, left, right). This experience is known from day to day live regarding handling of solid objects. But the "neighbourship relation" is preserved also in the other 4x4 most-perfect magic squares. (The "nontrivial" sqaures derived from a first square can be obtained in many ways by a playing child: exchanging column 1 and 3; dividing the 4x4 sqaure in four 2x2 subsquares and rotating, mirroring them using some patterns etc.) The number of 384 different squares also includes this (384 = 4!*16) because for an arbitrary given value (one of 16) the neigbours can be placed in 4! different ways.

The "neighbourship property" was probably known long time ago eighter for individual values or assuming some training and praxis they can be memorized for more / all values. About the relation between "neigbourship" and representation of these in binary notation I can make only speculative assumptions. I was told that magic sqaures of order 4x4 where embeded in magic sqaures of higher order and that some of these where related to "universes" assigned to different (indian) deities.

The main questions would be

1. which are the "usefull neighbour values"
2. how (when and where) to place them

a) from neighbourship (using the representation of the quare with values from 0 to 2²ⁿ - 1) it could be seen that for a given $start_value and its complement $start_value_complement = 2²ⁿ - 1 - $start_value the calculation of the $relevant_values can be done with

$no_of_neighbours                       = 0;
$next_neighbour                         = 0;
$neighbour_difference                   = 1;
while ( $neighbour_difference < $complement_reference )
    {
    if ( bcmod($start_value_complement, 2 * $neighbour_difference) < $neighbour_difference )
        { $relevant_values[$no_of_neighbours] = $start_value_complement + $neighbour_difference; }
        else
        { $relevant_values[$no_of_neighbours] = $start_value_complement - $neighbour_difference; }
    $no_of_neighbours++;
    $neighbour_difference = $neighbour_difference * 2;
    }

For a square of order 2ⁿ 2n neighbours will be identified this way.

about the formula: basicaly the "usefull neighbour values" of $start_value are all values where the value for only one binary position of $start_value_complement is "toggled" ("0" changes to "1" or "1" changes to 0")

example: assumed we are constructing a square where values higher then 16 are used we take a value $start_value and calculate $start_value_complement

we divide $start_value_complement by 32 and look if the remainder is smaller then 16

if so we take $start_value_complement + 16 as a "usefull neighbour value" else we take $start_value_complement - 16

this is done for each of the 2n binary positions – 09:34, 11 August 2005 (UTC)

note: for the description presented below it is important to understand the mapping of working areas relative to an "endless plane" where content is repeated; this can be achieved with indexing using modular arithmetic

b) now the question is about how to place the values;
b1) select a random location b in the square of order 2ⁿ and place value $start_value; place its complement according to the requirement from the definition: "All pairs of integers distant n/2 along a (major) diagonal sum to s."
b2) select one of the 16 4x4 subsqaures to which b can belong
b3) filling the square selected at b2)
b3.1) select one of the 2n neighbours of $start_value and place it as a "neighbour" (up, down, left, right) of $start_value inside the subsquare selected at b2); place the complement accordingly
b3.2) select another of the remaining 2n neighbours of $start_value and place it as a "neighbour" (up, down, left, right) of $start_value inside the subsquare selected at b2); positions already "occupied" can not be used again; place the complement accordingly
b3.3) note that depending on b3.1) and b3.2) a value can be computed;

if the $start_value and the two "neighbours" are located either on the same row or the same column of the 4x4 subsqaures selected in b) the value for the "remaining" place in that row / column should be computed as 2s - available values;

if this is not the case the value for the "remaining" place will be computed to follow the first requirement from the definition

b3.4) select another of the remaining 2n neighbours of $start_value and place it as a "neighbour" (up, down, left, right) of $start_value inside the subsquare selected at b2); positions already "occupied" can not be used again; place the complement accordingly

after this selection all values of the 4x4 subsqaures selected in b) can be computed according to the description from b3.3); in parallel the complement values of the newly compluted values are identified and located to follow the first requirement from the definition

c) for squares of order higher then 8 the following intermediate steps are made as long as there are more then two "usefull neighbour values" left over; c) will not apply for squares of order 8
c1) initial step:

1. the number of remaining neighbours of $start_value is now 2n - 4
2. the 4x4 subsquare is refered from now on as "coherent area of identified values" and can grow in arbitrary directions
3. inside the 4x4 subsqaures selected in b) a position (one of 16) can be selected and the "coherent area of identified values" can grow in arbitrary directions (up, down, left, right) relative to this subsquare unless a quarter of the original square is filled by selected / computed values and another quater is filled with the complement of these values
4. possible places to locate the next "neighbour" now are the postions on the same row closest to the 4x4 subsquare (left, right) or the postions on the same column closest to the 4x4 subsquare (up, down); these are initial "valid neighbour positions"

c2) select another of the remaining neighbours of $start_value and place it at a "valid neighbour position" of the "coherent area of identified values"; place the complement to fulfill / to follow the first requirement from the definition
c3) the newly selected location will belong to a raw or column where values are selected or computed already; the task is to "duplicate the lenght" of that raw / column "segments"; to perform this task the difference between the two ends of this segment is calculated; this difference is used with alternated sign to compute the remainig values of the segment with double lenght; together with newly identified vales their complement value is inserted to fulfill / to follow the second requirement from the definition
c4) once a segment is "doubled" all values belonging to the smallest subsquare / subsrectangle containing this segment and an coherent segment of already selected / computed values can be computed to fulfill / to follow the first requirement from the definition; the complement values are located / inserted to fulfill / to follow the second requirement from the definition
c5) depending of the order of the square and of the selection at c2) or at previous iteration steps it is either

1. possible to expand the coherent area in the same direction as selected at c2) or in a direction selected at another previous iteration unless its length reaches n/2;

in other words: onece one of the directions of the pairs (up, down) or (left, right) was selected the other is not available any more and expansion stops at n/2 in this direction; expansion might still be possible in another direction

1. possible to chose one of the two perpendicular directions to the one selected at c2) or used repeatedly at c2) as long as no such direction was selected before at another iteration step
2. only two "usefull neighbour values" have left; this is the exit condition for c)

d) the positions of the last two "usefull neighbour values" are a sort of "strategical positions" which can be identified already in squares of order 8; their position is given relative to the two quarters of the original subsqaure:
if the area with the values selected and / or computed already is maped to the subsquare with values in the cells i, j and 0 <= i <= n/2 - 1 and 0 <= j <= n/2 - 1 (and the complented values located in the cells i, j and n/2 <= i <= n - 1 and n/2 <= j <= n - 1) their position will be

1. n/2 , n/2 - 2
2. n/2 - 2 , n/2

step d) of the algorithm allows only the selection of one of the two "usefull neighbour values" and one of the two "valid neighbour positions"

[edit] notes

• Analysing the algorithm it can be seen that the number of generated squares is either

1. 2ⁿ!*2²ⁿ for n = 2 and n = 3
2. 16*2ⁿ!*2²ⁿ for n > 3

• An example of an most-perfect magic square which will not be generated by this algorithm is mentioned at the end of de: ... Beispiele pandiagionaler magischer Quadrate und einiges zu deren Analysemethoden. It can be seen that the value 126 which is half the value equivalent to the magic constant does not occur as sume of four "consecutive" values in any column.
• An implementation was made at http://easy.go.is/gangleri/ferningar/ around end of 2003 in phtml. Some examples from [1] (all using random values) as [2] or [3] are displaying squares using a 3D effect.

parameters:

1. "&x_signs=" alows different representations:
   1. default (absent), &x_signs=0 or &x_signs=1 values from 1 to 2ⁿ
   2. &x_signs=2 values from 0 to 2ⁿ - 1
   3. &x_signs=3 (negative an positive) odd value representation
2. "&x_max_tables=99" shows intermediate steps in the generation; this parameter is overwritten for 4x4 sqaures
3. "&x_square_type=" defines the order of the square: 0 for 4x4, 1 for 8x8, 2 for 16x16, 3 for 32x32, 4 for 64x64 and 5 for 128x128

Enjoy! Gangleri | Th | T 18:08, 10 August 2005 (UTC)

• Generating squares with order higher then 128 x 128 is dissabeled by the code. A 256 x 256 square would require about 2MByts.
• Using the squares for encryption (indexing) would require a lot of memory, simple implementations would be peer to peer encryption. Supporting many "sessions" with different keys should take memory constraints into consideration.
• Depending on other wiki activities I work from time to time on algebraic properties of the transitions between most-perfect magic squares which form a noncommutative group for n = 2. Regrads Gangleri | Th | T 11:26, 9 August 2005 (UTC)

[edit] about the unique binary pattern

• To be continued after feedback from meta:Help talk:Table. Regards Gangleri | Th | T 19:59, 16 August 2005 (UTC)

[edit] Only Three Squares, Only One Pattern

Only Three Squares, Only One Pattern shows that the 4x4 most-perfect magic squares have only one underlaying pattern. To ilustrate this please take a look at the binary representation of one of these squares:

We can see that each of the colors occur only two times in each row, each column and in each of the diagonals. We can verify how the pattern relates to all of the broken diagonals and to the 16 2x2 subsquares using wrap around. In all these "entities" we have each color only two times. This means that you can change the coding of the pattern:

a) changing "a div 8 = 1 with "a mod 2 = 1" and vice versa would give the square:

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

If we "change" only the weights for the binary representation we will have 4! permutations and the values "0" and "15" will be always fixed.
b) changing "a mod 2 = 1 with "a mod 2 = 0" and vice versa would give the square:

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

We can see that doing this there are 16 times more possibilities. Gangleri | Th | T 22:34, 16 August 2005 (UTC)

[edit] more advanced (/ general?) method for the generation of most-perfect magic squares of order 2ⁿ

A good approach to understand the method described below would be to visit the page The 8x8 Pan-Magic Squares. However it is about constructing panmagic squares and not most-perfect magic squares (the last term seems to be used the first time by Henry Ernest Dudeney – see [4]).

The site is using the representations of the squares with values from 0 to n² and the term "carpets". We should note that for the generation of most-perfect magic squares no carpet containing a 2x2 subsquare like

1 1
1 1

can be used (in general). If that carpet would be used together with the value 2^2n-1 the sum of this subsquare would be for this carpet already 2²ⁿ⁺¹ which is greather then 2(2²ⁿ-1) – this is 2²ⁿ⁺¹ - 2 – the maximum sum allowed for a 2x2 subsquare inside the final most-perfect magic square. Requirement a) would be that such a pattern would never occur.

Note that not all listed (panmagic) carpets fulfill "for every cell a the cell located at n/2 rows and n/2 columns is the complement of a". This would be requirement b) which is a requirement from the definition of most-perfect magic squares.

Clasifying the carpets who fulfills a) and b) we find some which can be decomposed

M    M
c(M) c(M)

– lets talk about as "type v" (v from vertical) – and others which can be decomposed as

M c(M)
M c(M)

– lets talk about as "type h" (v from horizontal) – where c(M) is a subsquare replacing all values with their binary complement.

The task mentioned at the page is to find all carpets and to find a way how to select the "usefull subsets" to generate the squares of the required type.

It can be noticed that if you take two of the carpets A and B which fulfill a) and b) the following can happen:

c1) the number of cells where the value in both carpets is 0 is 2^{2n - 2}

c2) the number of cells where the value in both carpets is 1 is 2^{2n - 2}

c3) the number of cells where the value A is 0 the value B is 1 is 2^{2n - 2}

c4) the number of cells where the value A is 1 the value B is 0 is 2^{2n - 2}

Last condition is fulfilled automatically if c1) and c2) and c3) is fulfilled.

This would be requirement c). Note this is a "symmetrical" condition. Note that neither the pair (A, A) nor pair (A, c(A)) fullfils c). Take some time to understand that you may "swap" to raws which are in a distance of n/2 raws in a carpet of "type v" (up to n/2 such "independend and commutative" transitions are possible) and you may "swap" to colums which are in a distance of n/2 colums in a carpet of "type h" (up to n/2 such "independend and commutative" transitions are possible) but not vice versa – columns in a distance of n/2 columns in a carpet of "type v" have the same content and raws in a distance of n/2 raws in a carpet of "type h" have same content too.

"Swaping" two raws which are in a distance of n/2 or two columns which are in a distance of n/2 is a usefull technique to be used with squares which fulfill b) and can be used to expand the first algorithm described on this page. The total number of these transitions (for squares) is "n" – not to be confused with the discussion from above relating to carpets. The algebraic closure of the composition should be handeled later.

Please note that if we take a carpet of "type v" and "swap" only two raws the values for 3/4 of all cells will be unchanged while 1/4 will "toggle" to the complement of these cells.

To identify the / all carpets of "type h" respective all of "type v" we should remember that the final goal here is to generate a "most perfect magic square". Similar to requirement a) we should realise that every raw and column must contain exactly n/2 cells with value "0" and exactly n/2 cells with value "1".

A (general?) solution to construct carpets of "type h" would be as follow:

a00    a01    a02    a0(n/2)    c(a00) c(a01) c(a02) c(a0(n/2))
c(a00) c(a01) c(a02) c(a0(n/2)) a00    a01    a02    a0(n/2)

Only these two raws would be used to fill the carpet. The number of such carpets is 2^n/2. If this is the general solution it should be possible to proof it (with mathematical induction ?).

The carpets of "type v" are the transposed of the carpets of "type h". Note that the transposition is an isomorphism transition, the number of such carpets is 2^n/2 too. The number of zeros and ones in the raws of "type v" is balanced, else they would be of no use.

There are some interesting properties:

Every carpet A and its transposition fulfills c).

Every pair of carpets (A, B) where A is of "type h" and B is of "type v" (or vice versa) fullfills c).

[edit] selecting "usefull subsets" of carpets

To describe the general case lets take first carpet A from the 2^n/2 of "type h" as the "first" carpet. The first values in A represents as "a00 a01 a02 a0(n/2)".

Let us take as second carpet a carpet of "type h" where half of the values of "a00 a01 a02 a0(n/2)" are preserved and the other half of the values is exchanged with their complement. For n=3 we would have 6 (3!) carpets to choose from.

To understand the method lets continue with the case n=3. As 3rd carpet we select a carpet of "type h" to filfill the following conditions:

we preserve one of the two values preserved in the second selection together with one of the two values we have exchanged with its complement in the second selection

the other two values are exchanged with their complement

There are 4 (2²) possibilities to do so. We see that all pairs of these three carpets fulfill c) and it would not be possible to find another carpet of "type h" which would fulfill c) in combination with the three already found.

We have the coice to select other three carpets of "type v" in a similar way. Then we can assign (binary) "weights" to the carpets. By multiplying the "weights" with the carpets and adding all results together we get a new square. Due to construction we have generated a most-perfect magic square.

In order to count the generated squares we should note that the way / the order we selected the "usefull" set of carpets is not relevant when we generate the squares.

Regards Gangleri | Th | T 10:29, 20 August 2005 (UTC)