| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| strategies [2024/08/24 21:33] – [An efficient method to find magic squares] mino | strategies [2025/08/03 15:42] (current) – [Complementary pair] mino |
|---|
| the largest complement of row/column magic series. | 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. | 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. |
| * 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>. | * 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. | * 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>. | * 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>. |
