Differences

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

--- strategies [2024/07/29 17:23] – [An efficient method to find magic squares] mino
+++ strategies [2025/08/03 15:42] (current) – [Complementary pair] mino
@@ 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 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.
         * 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 [[https://oeis.org/A266237|M-transformations]], which is 48 for N=6.
@@ Line 66: / Line 66: @@
       * 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 up-diagonal (reversed order) 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 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>.