Differences

This shows you the differences between two versions of the page.

--- strategies [2024/06/12 10:46] – [An efficient method to find magic squares] mino
+++ strategies [2025/08/03 15:42] (current) – [Complementary pair] mino
@@ Line 7: / Line 7: @@
 To construct a magic square of order N, We need 2N+2 magic series for rows, columns and diagonals which satisfy the following constraints:
-    * row magic series don't have common elements with each other,
+    * Row magic series don't have common elements with each other.
-    * column magic series don't have common elements with each other,
+    * Column magic series don't have common elements with each other.
-    * each row magic series shares only one element with each column magic series,
+    * Each row magic series shares only one element with each column magic series.
-    * up/down diagonal (candidate) magic series shares only one element with each row/column magic series, and
+    * Up/down diagonal (candidate) magic series shares only one element with each row/column magic series.
-    * diagonal (candidate) magic series don't have common elements for even N, and share only one common element for odd N.
+    * Diagonal (candidate) magic series don't have common elements when N is even, and share only one common element when N is odd.
-We generate sets of rows and columns as sorted sets reserving freedom of shuffling the members of each set. And, at this stage, we allow the elements of diagonal magic series scattered in a square, not in a diagonal line, so we call them 'candidates'.
+We generate sets of rows and of columns as sorted sets reserving freedom of shuffling the members of each set. And, at this stage, we allow the elements of diagonal magic series scattered in a square, not in a diagonal line, so we call them 'candidates'.
@@ Line 43: / Line 43: @@
 the largest complement of row/column magic series.
-We can omit counting the case 2. by doubling the count for the case 1 because the cases 1. and 2. transform into each other under the complementary transformation,  In the case 3, we just count magic squares without doubling.
+We can omit counting the case 2 by doubling the count for the case 1 because the cases 1 and 2 transform into each other under the complementary transformation,  In the case 3, we just count magic squares without doubling.
-Note that all squares in the case 3. are not necessarily self-complementary. You may break down the case 3. into finer cases and reduce redundancy further if you can handle them with low overhead.
+Note that all squares in the case 3. are not necessarily self-complementary. You may break down the case 3. into finer cases to reduce redundancy further if you can handle them with low overhead.
@@ Line 56: / Line 56: @@
       * Thus the final question is:
         * "Can we make the up-diagonal candidate magic series aligned correctly by permuting conjointly rows and columns?"
-      * The answer is "It depends". We, however, can utilize the help of symmetry. Up diagonal line is symmetric under the row-column exchange and any conjoint permutations of rows and columns always preserve that symmetry. We, therefore, have the following lemma.
+      * The answer is "It depends". We can, however, find a charming necessary condition by utilizing power of symmetry. Up diagonal line is symmetric under the row-column exchange and any conjoint permutations of rows and columns always preserve that symmetry. We, therefore, have the following lemma.
-        * Up-diagonal candidate can be aligned correctly //**only if**// they are symmetric under the row-column exchange.
+        * An up-diagonal candidate can be aligned correctly //**only if**// it is symmetric under the row-column exchange.
-      * While we cannot simply claim that symmetric patterns are always transformable into the up-diagonal line, it is an easy task to check all symmetric patterns of up-diagonal candidates for a specific small N. We have only {{ :up-diag2.pdf |15 such patterns}} for N=6 and all of them are transformable into the up-diagonal line. Thus, once we find a symmetric up-diagonal candidate, we obtain as many magic squares as the number of M-transformations, where the multiplicity is 48 for N=6.
+      * While we cannot simply claim that symmetric patterns are always transformable into the up-diagonal line, it is an easy task to check all symmetric patterns of up-diagonal candidates for a specific small N. We have only {{ :up-diag2.pdf |15 such patterns}} for N=6 and all of them are transformable into the up-diagonal line. Thus, once we find a symmetric up-diagonal candidate, we obtain as many magic squares as the number of [[https://oeis.org/A266237|M-transformations]], which is 48 for N=6.
-      * As mentioned in the second subsection, duplicates form 180deg rotation should be eliminated, we, therefore, have the multiplicity halved (24 for N=6).
+      * As mentioned in the second subsection, duplicates from 180deg rotation should be eliminated, we, therefore, have the multiplicity halved (24 for N=6).
 == in mathematical terms  ==
-      * Since elements of a diagonal candidate magic series appear only once in every row and in every column, the arrangement of a diagonal candidate corresponds to a permutation of N objects, or an element of    symmetric group S<sub>N</sub>
+      * Since every element of a diagonal candidate magic series appear only once in every row and in every column, the arrangement of a diagonal candidate corresponds to a permutation of N objects, or an element of the symmetric group S<sub>N</sub>
       * Let us denote (the arrangements of) the down and up diagonal candidates as d and u, respectively, which are elements of S<sub>N</sub>.
       * Permuting columns to make the down diagonal candidate diagonal corresponds to multiplying by d<sup>-1</sup>. By this permutation, we get  dd<sup>-1</sup> = e and ud<sup>-1</sup>, where e is the identity.
-      * The current arrangement of the up diagonal candidate ud<sup>-1</sup> is transformable into the up diagonal line by a conjoint permutation of columns and rows if and only if ud<sup>-1</sup> belongs to the same conjugacy class as the reversal (up diagonal) permutation. For N=6, this conjugacy class consists of 15 elements which are just depicted in the figure above.
+      * The current arrangement of the up diagonal candidate ud<sup>-1</sup> is transformable into the up diagonal line by a conjoint permutation of columns and rows if and only if ud<sup>-1</sup> belongs to the same conjugacy class as the up-diagonal (reversed order) permutation does. For N=6, this conjugacy class consists of 15 elements which are just depicted in the figure above.
-      * Practically, we can distinguish the conjugacy class of a permutation by its cycle type, and the cycle type of the reversal permutation consists of floor(N/2) doublets and (N mod 2) singlet. Since we have already checked that the number of common elements of down and up diagonal candidates equals to (N mod 2), the correct singlet component is already guaranteed. Then the remaining condition to check reduces to ( ud<sup>-1</sup> ) <sup>2</sup> = e or ud<sup>-1</sup> = du<sup>-1</sup>.
+      * Practically, we can distinguish the conjugacy class of a permutation by its cycle type, and the cycle type of the reversed order permutation consists of floor(N/2) 2-cycles and (N mod 2) 1-cycle. Since we have already checked that the number of common elements of down and up diagonal candidates equals to (N mod 2), the correct 1-cycle component is already guaranteed. Consequently, all we have to check is that **ud<sup>-1</sup> does not have any cycles longer than 2**, in other words, ( ud<sup>-1</sup> ) <sup>2</sup> = e or ud<sup>-1</sup> = du<sup>-1</sup> = ( ud<sup>-1</sup> )<sup>T</sup>.