We present constructions of semi-magic squares of side \(n=2k\), whose entries are elements of a dihedral group \(D_{2k^2}\), for every \(n\equiv0\pmod4\).
Magic squares are one of the oldest mathematical structures, reportedly dating back to the 4-th century BCE. A magic square of side \(n\) is an \(n\times n\) array with entries \(1,2,\dots, n^2\) such that the sum of each row, column, and the main forward and backward diagonal is the same magic constant \(c=n(n^2+1)/2\). When we only require the row and column sum to be equal and disregard the diagonals, we speak about a semi-magic square.
A generalization of a magic square is an \(m\times n\) magic rectangle with entries \(1,2,\dots ab\) where all row sums are equal to the row constant \(r=n(mn+1)/2\) all column sums are equal to the column constant \(c=m(mn+1)/2\). A semi-magic square is then an \(n\times n\) magic rectangle.
Magic squares and rectangles can be generalized in may different ways. For instance, we may require that the entries are all primes or elements of an Abelian group (see [1, 2, 4, 5, 11]).
We are not aware of any result on magic or semi-magic squares over non-Abelian groups. In this paper, we construct \(4k\times 4k\) semi-magic squares over dihedral groups \(D_{8k^2}\) with \(16k^2\) elements.
Disclaimer Some parts of this and the following two sections may be similar or identical to corresponding parts of other papers by the author and Cichacz [1, 5] on Abelian magic squares.
We first define magic rectangles over Abelian groups.
Definition 2.1. Let \(\Gamma\) be an Abelian group of order \(mn\) and \(MR_{\Gamma}(m,n)\) and \(m\times n\) array whose entries are all elements of \(\Gamma\). Then \(MR_{\Gamma}(m,n)\) is a \(\Gamma\)-magic rectangle if all row sums are equal to some element \(\rho\in\Gamma\) and all column sums are equal to some element \(\sigma\in\Gamma\).
If \(m=n\) and \(\rho=\sigma\), then \(MR_{\Gamma}(m,n)\) is called \(\Gamma\)-semi-magic square and denoted \(MS_{\Gamma}(n)\). If moreover the sums of both the main and backward main diagonals are equal to \(\rho=\sigma\), then \(MR_{\Gamma}(m,n)\) is called \(\Gamma\)-magic square.
Notice that unlike in integers, an \(n\times n\) \(Z_{n^2}\)-magic rectangle \(MR_{\Gamma}(n,n)\) is not necessarily a \(Z_{n^2}\)-magic or semi-magic square, because we may have \(\rho\neq\sigma\). Consider, for instance \[\begin{array}{|c|c|} \hline 0&1 \\ \hline 3&2 \\ \hline \end{array}\] where \(\rho=1\) and \(\sigma=3\).
While for Abelian groups the order in which the edge labels are considered is irrelevant, for non-Abelian groups different orders may produce different weights. It is indeed desirable that the order in every row and column is in some way predictable or uniform.
Definition 2.2. Let \(\Gamma\) be a group of order \(mn\) and \(MR_{\Gamma}(m,n)= (a_{i,j})\) an \(m\times n\) array whose entries are all elements of \(\Gamma\). If for every row \(i\) there exists an ordering of elements such that \[a_{i,j_1} a_{i,j_2} \dots a_{i,j_{n-1}} a_{i,j_n} = \rho,\] and for every column \(j\) there exists an ordering of elements such that \[a_{i_1,j} a_{i_2,j} \dots a_{i_{m-1},j} a_{i_m,j} = \sigma,\] then \(MR_{\Gamma}(m,n)\) is called a \(\Gamma\)-magic rectangle.
Definition 2.3. Let \(\Gamma\) be a group of order \(n^2\) and \(MR_{\Gamma}(n,n)\) a \(\Gamma\)-magic rectangle. If the row and column products are equal, that is, \(\rho=\sigma\), then we call \(MR_{\Gamma}(n,n)\) a \(\Gamma\)-semi-magic square of side \(n\) and denote it \(SMS_{\Gamma}(n)\). If moreover the products of both the main and backward main diagonals are equal to \(\rho=\sigma\), then \(MR_{\Gamma}(n,n)\) is called a \(\Gamma\)-magic square of side \(n\) and denoted \(MS_{\Gamma}(n)\).
If the product starts at the last entry in each row or bottom entry in each column and proceeds linearly to the first or top entry, we call such rectangle linear. We state an exact definition (just for semi-magic squares) next.
Definition 2.4. Let \(SMS_{\Gamma}(n)\) be a \(\Gamma\)-semi-magic square. If for every row and column the ordering is \[a_{i,1} a_{i,2} \dots a_{i,{n-1}} a_{i,n} = \rho,\] and \[a_{1,j} a_{2,j} \dots a_{{m-1},j} a_{m,j} = \sigma,\] then \(SMS_{\Gamma}(m,n)\) is linear \(\Gamma\)-semi-magic.
When we split the square into four subsquares and all row products within each subsquare start on the same forward subsquare diagonal and proceed circularly from right to left or from bottom to top, we call the square half-diagonal circular. Note that the starting diagonal for the row products may be different from the one for column products. An exact definition follows.
Definition 2.5. Let \(SMS_{\Gamma}(2k)\) be a \(\Gamma\)-semi-magic square consisting of four subsquares \(A^{s,t},s,t\in\{1,2\}\) with entries \(a^{s,t}_{i,j};i,j\in\{1,2,\dots,k\}\). If for every row and column the ordering in each \(A^{s,t}\) satisfies \[a^{s,t}_{i,i+u+1} a^{s,t}_{i,i+u+2} \dots a^{s,t}_{i,k} a^{s,t}_{i,1} \dots a^{s,t}_{i,{i+u-1}} a^{s,t}_{i,i+u} = \rho,\] and \[a^{s,t}_{j+v+1,j} a^{s,t}_{j+v+2,j} \dots a^{s,t}_{k,j} a^{s,t}_{1,j} \dots a^{s,t}_{{j+v-1},j} a^{s,t}_{j+v,j} = \sigma,\] for some \(u\) and \(v\), respectively, then \(SMS_{\Gamma}(m,n)\) is half-diagonal circular \(\Gamma\)-semi-magic. By half-diagonal we mean a diagonal in one of the subsquares \(A^{s,t}\).
We will use the term “side” instead of the more common “order” to avoid confusion with the order of the groups which will form our squares.
The dihedral group \(D_{k}\) of order \(2k\) (sometimes also denoted by \(D_{2k}\)) is the group consisting of \(k\) rotations \(r_i\) and \(k\) reflections \(s_i\), where the rotations form a cyclic group of order \(k\) and and each reflection generates a subgroup of order 2. More formal definition is below.
Definition 2.6. The dihedral group \(D_{k}\) of order \(2k\) where \(k\geq3\) is defined on the set of elements \(\{r_0,r_1,\dots,r_{k-1},s_0,s_1,\dots,s_{k-1}\}\) where \(r_0=e, r_1=r, r_i=r^i\), \(s_0=s\), \(s_i=r^i s\), \(s^2_i=e\) and \(r^is=sr^{-i}\) for \(i=0,1,\dots,k-1\). The elements \(r_i\) are called rotations, and \(s_i\) are called reflections.
An important property of \(D_{k}\) will be used in our constructions. If follows directly from the definition.
Proposition 2.7. In any dihedral group \(D_{k}\), we have \(sr^is=r^{-i}\) for every \(i=0,1,\dots,k-1\).
When we have a \(\Gamma\)-magic or semi-magic square where \(\Gamma=D_k\), the dihedral group on \(2k\) elements, we speak about a dihedral magic or semi-magic square.
We add here the obvious necessary conditions. Because dihedral groups are always of even order, an odd side \(MR_{D_k}\) cannot exist.
Observation 2.8. Let \(n\) be odd. Then no magic rectangle or semi-magic square of side \(n\) over a dihedral group \(D_k\) exists.
Observation 2.9. Let \(k\) be odd. Then no semi-magic square of side \(n\) over a dihedral group \(D_k\) exists.
Proof. Because a magic square of side \(n\) has \(n^2\) elements, we must have \(D_k\) with \(2k=n^2\) elements. Therefore, \(k\) must be even. \(\square\)
Theorem 2.10. If a dihedral magic square \(MS_{D_k}(n)\) or semi-magic square \(SMS_{D_k}(n)\) exists, then both \(n\) and \(k\) must be even.
Evans [4] defined a modular \((m,n)\)-magic rectangle as an \(m\times n\) array with entries \(1,2,\dots, mn\) where all row sums are mutually congruent modulo \(mn\) and all column sums are mutually congruent modulo \(mn\). It may be more convenient to re-define it as a \(Z_{mn}\)-magic rectangle, where \(Z_{mn}\) is the cyclic group of order \(mn\).
Evans [4] proved the following.
Theorem 3.1 (Evans [4]). There exists a non-trivial \(Z_{mn}\)-magic rectangle \(MR_{Z_{mn}}(m,n)\) if and only if \(m>1,n>1\) and \(m\equiv n\pmod2\).
One can notice that the characterization is exactly the same as for magic rectangles in integers, except the case of \(m=n=2\) when a magic rectangle does not exist while a \(Z_4\)-magic \(2\times2\) rectangle does (and is shown in Section 2).
Sun and Yihui [11] (without proper proof) made the following claim. The claim was only proved for groups \(Z_n\oplus Z_n\).
Claim 1. For every \(n\geq3\) and any Abelian group \(\Gamma\) of order \(n^2\) there exists a \(\Gamma\)-magic square \(MS_{\Gamma}(n)\) of side \(n\).
Cichacz and Hincz [2] proved a somewhat weaker result on \(\Gamma\)-magic rectangles. Their construction does not produce magic (or semi-magic) squares, since in general their row and product sums are not necessarily equal.
Theorem 3.2 (Cichacz and Hincz [2]). Let \(\Gamma\) be an Abelian group of order \(\Gamma=mn\). There exists a non-trivial \(\Gamma\)-magic rectangle \(MR_{\Gamma}(m,n)\) if and only if \(m>1,n>1\) and \(m\equiv n\pmod2\).
Quite recently, Cichacz and Froncek [1] dealt with magic squares over arbitrary Abelian groups and proved the following:
Theorem 3.3 (Cichacz and Froncek [1]). Let \(n\geq3\) be an integer. Then there exists a \(\Gamma\)-magic square \(MS_{\Gamma}(n)\) for any Abelian group of order \(n^2\). There is no \(\Gamma\)-magic square of side \(2\).
Froncek [5] also presented a different construction for Abelian groups of odd square orders.
An interesting detour from this directions are magic squares on primes. Due to the important result of Green and Tao [6] on the existence of arithmetic progressions of primes, it is possible to construct magic rectangles on primes of any order greater than two.
Theorem 3.4 (Green and Tao [6]). For every \(n>0\), there exists an arithmetic progression of length \(n\) consisting of primes.
Corollary 3.5. For every \(n\geq3\), there exists a magic square \(MS_p(n)\) consisting of primes.
There are, however, even examples of prime magic squares consisting of primes that do not form arithmetic progressions. According to Katrnoška, Křížek, and Somer [9], Ondrejka [10] discovered the square shown in Figure 1.
According to Dénes and Keedwell [3], Johnson [8] discovered a magic square consisting of consecutive primes. It is shown in Figure 2.
In one of our constructions we will need the notion of \(n\)-dimensional magic rectangle, which was introduced by Hagedorn in [7].
Definition 3.6. An \(m\)-dimensional magic rectangle \(m{\text-}MR(a_1,a_2,\dots,a_m)\) is an \(a_1\times a_2\times\dots\times a_m\) array with entries \(d_{i_1,i_2,\dots,i_m}\) which are elements of \(\{1,2,\ldots,a_1a_2\dots a_m\},\) each appearing once, such that all sums in the \(k{\text-}\)th direction are equal to a constant \(\sigma_k\). That is, for every \(k,~1\leq k\leq m\), we have \[\sum_{j=1}^{a_k} d_{b_1,b_2,\dots,b_{k-1},j,b_{k+1},\dots,b_m}=\sigma_k,\] for every selection of indices \(b_1,b_2,\dots,b_{k-1},b_{k+1},\dots,b_m,\) and \(\sigma_k=a_k(a_1a_2\dots a_m +1)/2\).
The following existence results were also proved in [7].
Theorem 3.7. [7] If an \(m{\text-}\)dimensional magic rectangle \(m{\text-}MR(a_1,a_2,\dots,a_m)\) exists, then \(a_1\equiv a_2\equiv\dots\equiv a_m\pmod2\).
Theorem 3.8. [7] An \(m{\text-}\)dimensional magic rectangle \(m{\text-}MR(a_1,a_2,\dots,a_m)\) with \(a_1\leq a_2\leq \dots\leq a_m\) and all \(a_i\) even exists if and only if \(4\leq a_2\leq \dots\leq a_m\).
We start with an ad-hoc construction of \(Q(8)\), because the general construction for \(k\equiv0\pmod4\) requires existence of a 3-dimensional magic rectangle \(3\)–\(MR(k/2,k/2,8)\) which only exist when \(k\equiv0\pmod4\) and \(k\geq8\).
Construction 4.1. \(D_{32}\)-semi-magic square \(Q(8)\)
The products in the square \(Q(8)\) shown in Figure 3 are performed as follows. In rows, we just list the elements in natural order and multiply the element, reading them from right to left Say, in row 1 we start with entry \(q_{1,8}=r^{11}s\) and have \[\begin{aligned} \rho_1&=(r^{18}s)(r^{19}s)(r^{26}s)(r^{27}s)(r^{2}s)(r^{3}s)(r^{10}s)(r^{11}s)\\ &=(r^{18})(sr^{19}s)(r^{26})(sr^{27}s)(r^{2})(sr^{3}s)(r^{10})(sr^{11}s)\\ &=(r^{18})(r^{-19})(r^{26})(r^{-27})(r^{2})(r^{-3})(r^{10})(r^{-11})\\ &= r^{28}, \end{aligned}\] and in row 2 we obtain \[\begin{aligned} \rho_2&=(r^{16}s)(r^{17}s)\dots(r^{8}s)(r^9s)\\ &=(r^{16})(sr^{17}s)\dots(r^{8})(sr^{9}s)\\ &=(r^{16})(r^{-17})\dots(r^{8})(r^{-9})\\ &= r^{28}. \end{aligned}\]
The remaining four rows contain only rotations and can be multiplied in any order.
The rotations obtained by the simplification using identity \(sr^as=r^{-a}\) are shown in Figure 4. We simply add the modified exponents to obtain the resulting power of \(r\).
In the columns, we list the elements from bottom to top and again perform the multiplication from right to left. So, for column 1 we have \[\begin{aligned} \sigma_1&=r^{31} r^{24} r^{21} r^{16} (r^{22}s)(r^{20}s)(r^{16}s)(r^{18}s)\\ &=r^{31} r^{24} r^{21} r^{16} (r^{22})(sr^{20}s)(r^{16})(sr^{18}s)\\ &=r^{31} r^{24} r^{21} r^{16} (r^{22})(r^{-20})(r^{16})(r^{-18})\\ &= r^{28}, \end{aligned}\] and for column 2 \[\begin{aligned} \sigma_2&=r^{28} r^{27} r^{20} r^{17} (r^{23}s)(r^{21}s)(r^{17}s)(r^{19}s)\\ &=r^{28} r^{27} r^{20} r^{17} (r^{23})(sr^{21}s)(r^{17})(sr^{19}s)\\ &=r^{28} r^{27} r^{20} r^{17} (r^{23})(r^{-21})(r^{17})(r^{-19})\\ &= r^{28}. \end{aligned}\]
The rotations obtained by the simplification using identity \(sr^as=r^{-a}\) are shown in Figure 5.
For the general case, we set \(k=4h\) and build \(Q({2k})\) from partial squares \(Q^{uv}({k})\) for \(u,v\in\{1,2\}\) that are then combined into \(Q({2k})\). Because the partial squares are always identified by the superscript \(uv\), we believe that no confusion will arise when we drop the square side and write simply \(Q\) instead of \(Q({2k})\) and \(Q^{uv}\) instead of \(Q^{uv}({k})\).
The squares \(Q^{11}\) and \(Q^{22}\) will consist of rotations and \(Q^{12}\) and \(Q^{21}\) of reflections. To simplify notation and calculations, we first build power squares \(T^{11}, T^{22}\) for rotations and \(F^{12},F^{21}\) for reflections.
Rather than using the group elements and entries and performing the group operation, we simply use the exponents in elements \(r_i=r^i\) and \(s_i=r^is\). Then when in our square we would perform the product (read from right to left) \(\dots r^i r^j\dots\), we instead just add the exponents \(\dots i+j\dots\). For reflections, we recall that from Proposition 2.7 it follows that \[(r^is)(r^js) = r^i(s r^j s) = r^i r^{-j},\] and we use just the term \(i-j\).
The entries in the respective squares \(T^{uv},F^{uv}\) and \(Q^{uv}\) are denoted by \(t^{uv}_{i,j},f^{uv}_{i,j}\) and \(q^{uv}_{i,j}\) for \(1\leq i,j\leq k\). Similarly, the entries in the resulting square \(Q\) are denoted \(q_{i,j}\) for \(1\leq i,j\leq 2k\). An entry \(p=t^{uv}_{i,j}\) in \(T^{uv}\) represents the power \(r^p\) of element \(r\) in entry \(q^{uv}_{i,j}\) of \(Q^{uv}\) and entry \(p=f^{uv}_{i,j}\) in \(F^{uv}\) represents the power of \(r\) in \(r^ps\), that is, in the entry \(q^{uv}_{i,j}\) of \(Q^{uv}\). Therefore in \(T^{uv}\) and \(F^{uv}\) we use entries \(0,1,\dots,k^2-1\) and employ addition modulo \(2k^2\).
The row sums in row \(i\) will be \(\tau^{uv}_i\) in both \(T^{uv}\) and \(F^{uv}\) and \(\rho^{uv}_{i}\) in \(Q^{uv}\), and similarly the column sums in column \(j\) will be \(\eta^{uv}_j\) in \(T^{uv}\) and \(F^{uv}\) and \(\sigma^{uv}_{j}\) in \(Q^{uv}\). The magic constants will be \(\nu^{uv}\) in \(T^{uv}\) and \(F^{uv}\) and \(\mu^{uv}\) in \(Q^{uv}\). The row and column sums in the squares \(F^{uv}\) are calculated according to more specific rules that are explained in detail when the actual squares are constructed. We will remind the reader the notation later when we actually use it.
In particular, in \(Q^{11}\) and \(Q^{22}\) we have \[q^{uu}_{i,j} = r^{t^{uu}_{i,j}},\] and in \(Q^{12}\) and \(Q^{21}\) \[q^{uv}_{i,j} = r^{f^{uv}_{i,j}}s.\]
The row and column constants will be always rotations, because in our constructions each row and column contains \(k\) reflections and \(k\) is always even. We then have \[\rho^{uv}_i = r^{\tau^{uv}_i},\] and \[\sigma^{uv}_j = r^{\eta^{uv}_j}.\]
Now we present a general construction for \(k\geq8\), using the partial squares \(Q^{uv}\) as described earlier in this section.
Construction 4.2 (Rotations). We construct first the squares \(T^{11}\) and \(T^{22}\). Let \(\tilde{M}(k)\) be a magic square (in integers) with elements \(\tilde{m}_{i,j}\) and magic constant \(\tilde{\mu}\). Substituting \(m_{i,j}=\tilde{m}_{i,j}-1\) and performing addition modulo \(2k^2\) gives a square \(M(k)\) with magic constant \(\mu^*=(\tilde{\mu}- k)\mod{2k^2}\). We remark here that \(M(k)\) is not a \(Z_{2k^2}\)-magic square, because it only contains \(k^2\) smallest elements of \(Z_{2k^2}\), which will be used in the power square \(T^{11}\). The remaining elements will be used in \(T^{22}\).
Now we can define \(t^{11}_{i,j}=m_{i,j}\) and \(t^{22}_{i,j}=m_{i,j}+k^2\). For \(T^{11}\) it gives \[\tau^{11}_i =\eta^{11}_j=\mu^*,\] for each \(i\) and \(j\).
For \(T^{22}\) we can see that for each fixed \(i, 1\leq i\leq k\), performing addition again modulo \(2k^2\) and remembering that \(k=4h\), \[\begin{aligned} \tau^{22}_i&=\sum_{j=1}^{k} t^{22}_{i,j} \\ &=\sum_{j=1}^{k} (t^{11}_{i,j} +k^2)\\ &=\Big(\sum_{j=1}^{k} t^{11}_{i,j}\Big) +k(k^2)\\ &=\mu^* + 4hk^2\\ &=\mu^* + 2h(2k^2)\\ &=\mu^*. \end{aligned}\]
The same is true for each fixed \(j, 1\leq j\leq k\) and summing over \(i\) to obtain \(\eta^{22}_j\). Hence, both squares \(T^{11}\) and \(T^{22}\) have all their row and column sums equal to \(\mu^*\).
Our next step is the partial squares with reflections.
Construction 4.3 (Reflections, \(k\geq8\)). We construct each \(F^{uv}({4h})\) from four squares \(F^w({2h})\) arising from a 3-dimensional magic rectangle \(MR(2h,2h,8)\).
It follows from Theorem 3.8 that there exists a three-dimensional magic rectangle \(3{\text-}MR{(2h,2h,8)}\) for every even \(m\geq2\). We use entries in \(Z_{2k^2}=Z_{32h^2}\) instead of positive integers and denote each of the eight \(2h\times2h\) rectangles in \(3{\text-}MR{(2h,2h,8)}\) by \(M^w\) for \(w=1,2,\dots,8\) with entries \(m^w_{i,j}\). The row and column sums in each \(2h\times2h\) rectangle are all equal and denoted by \(\bar{\mu}\).
We combine \(M^1,\dots,M^4\) to \(F^{12}\) and \(M^5,\dots,M^8\) to \(F^{21}\) by placing entries of each \(M^w\) in every other row and column of \(F^{uw}\). In particular, we set \[\begin{aligned} &f^{12}_{2i-1,2j-1} &&= m^1_{i,j},\\ & f^{12}_{2i-1,2j} &&= m^2_{i,j},\\ & f^{12}_{2i,2j-1} &&= m^3_{i,j},\\ & f^{12}_{2i,2j} &&= m^4_{i,j}. \end{aligned}\]
Remembering that the row \(a\) entries \(f^{12}_{a,1},f^{12}_{a,2}, \dots f^{12}_{a,4h}\) in the power square \(F^{12}\) represent the powers of element \(r\) in the square of reflections \(Q^{12}\) in the product \[(r^{f^{12}_{a,1}}s)(r^{f^{12}_{a,2}}s)\dots(r^{f^{12}_{a,4h-1}}s)(r^{f^{12}_{a,4h}}s),\] we can regroup the product as \[(r^{f^{12}_{a,1}})(sr^{f^{12}_{a,2}}s)\dots (r^{f^{12}_{a,4h-1}})(sr^{f^{12}_{a,4h}}s),\] which is by Proposition 2.7 equal to \[(r^{f^{12}_{a,1}})(r^{-f^{12}_{a,2}})\dots (r^{f^{12}_{a,4h-1}})(r^{-f^{12}_{a,4h}}).\]
We now want to verify that in each row \(a\), the product is the same, that is, \[(r^{f^{12}_{a,1}})(r^{-f^{12}_{a,2}})\dots (r^{f^{12}_{a,4h-1}})(r^{-f^{12}_{a,4h}})=\rho^{12}_a,\] for every \(a\). But for every \(i=1,2,\dots,2h\) we have \[\begin{aligned} \tau^{12}_{2i-1} &=f^{12}_{2i-1,1}- f^{12}_{2i-1,2}+ \dots+f^{12}_{2i-3,2h}-f^{12}_{2i-1,2h}\\ &=( f^{12}_{2i-1,1}+ f^{12}_{2i-1,3}+\dots+ f^{12}_{2i-1,2h-1}) -( f^{12}_{2i-1,2}+ f^{12}_{2i-1,4}+\dots+ f^{12}_{2i-1,2h})\\ &=(m^1_{i,1}+m^1_{i,2}+\dots+m^1_{i,h}) -(m^2_{i,1}+m^2_{i,2}+\dots+m^2_{i,h})\\ &=\bar{\mu} -\bar{\mu}\\ &=0, \end{aligned}\] and \[\begin{aligned} \tau^{12}_{2i} &=f^{12}_{2i,1}- f^{12}_{2i,2}+\dots+f^{12}_{2i,2h}-f^{12}_{2i,2h}\\ &=( f^{12}_{2i,1}+ f^{12}_{2i,3}+\dots+ f^{12}_{2i,2h-1})-( f^{12}_{2i,2}+ f^{12}_{2i,4}+\dots+ f^{12}_{2i,2h})\\ &=(m^3_{i,1}+m^3_{i,2}+\dots+m^3_{i,h})-(m^4_{i,1}+m^4_{i,2}+\dots+m^4_{i,h})\\ &=\bar{\mu}-\bar{\mu}\\ &=0. \end{aligned}\]
By interchanging the subscripts \(i\) and \(j\) we can check the column sums \(\eta^{12}_j\) in the same way, again obtaining each sum equal to zero.
We can repeat the procedure for \(F^{21}\) using the rectangles \(M^5,\dots,M^8\) to obtain the same magic constant 0.
We are now ready to state our first result.
Theorem 4.4. There exists a linearly \(D_{2k^2}\)-semi-magic square \(Q(2k)\) for every \(k\equiv0\pmod4\), \(k\geq4\).
Proof. For \(k=4\), refer to Construction 4.1. For \(k\geq8\) we use Constructions 4.2 and 4.3.
In Construction 4.2, using the additive group \(Z_{k^2}\), we constructed power squares \(T^{11}\) and \(T^{22}\) with row sums \(\tau^{uv}_i=\mu^*\) and column sums \(\nu^{uv}_j=\mu^*\) for every feasible combination of \(u,v,i,\) and \(j\). It can be readily checked that \(\mu^*=-k/2\). One can see that we can obtain a more convenient constant \(\mu^{**}=k/2\) by simply adding 1 to each entry in both squares.
From \(T^{11}\) and \(T^{22}\) we obtain squares of rotations of the group \(D_{2k^2}\), \(Q^{11}\) and \(Q^{22}\) with the row and column products \(\rho^{uv}_i=\sigma^{uv}_j=r^{k/2}\).
Using again the group \(Z_{k^2}\), in Construction 4.3 we created squares \(F^{12}, F^{21}\) with the row sums \(\tau^{uv}_i=0\) and column sums \(\nu^{uv}=0\) for every feasible combination of \(u,v,i,\) and \(j\). From them, we can obtain squares of reflections of \(D_{2k^2}\), \(Q^{12}\) and \(Q^{21}\) with the row and column products \(\rho^{uv}_i=\sigma^{uv}_j=r^0=e\).
Each row product is now performed linearly as \[\rho_i=(q^{11}_{i,1}\ q^{11}_{i,2}\dots q^{11}_{i,k})\ (q^{12}_{i,1}\ q^{12}_{i,2}\dots q^{12}_{i,k}) = \rho^{11}_i \rho^{12}_i =r^{k/2}r^0 =r^{k/2},\] or \[\rho_{k+1}=(q^{21}_{i,1}\ q^{21}_{i,2}\dots q^{21}_{i,k})\ (q^{22}_{i,1}\ q^{22}_{i,2}\dots q^{22}_{i,k}) = \rho^{21}_i \rho^{22}_i =r^0 r^{k/2} =r^{k/2},\] and the columns products as \[\sigma_j=(q^{11}_{1,j}\ q^{11}_{2,j}\dots q^{11}_{k,j})\ (q^{21}_{1,j}\ q^{21}_{2,j}\dots q^{21}_{k,j}) = \sigma^{11}_i \sigma^{12}_i =r^{k/2}r^0 =r^{k/2} ,\] and \[\sigma_{k+j}=(q^{12}_{1,j}\ q^{12}_{2,j}\dots q^{12}_{k,j})\ (q^{22}_{1,j}\ q^{22}_{2,j}\dots q^{22}_{k,j}) = \sigma^{11}_i \sigma^{12}_i =r^0 r^{k/2} =r^{k/2}.\]
All row and column products in the square \(Q(2k)\) are equal to the magic constant \(r^{k/2}\), which completes the proof. \(\square\)
Remark 4.5. The semi-magic square obtained in Theorem 4.4 is not magic, because the product on the main diagonal is equal to \(r^k\). Because the entries are all rotations, the product cannot be re-arranged to obtain \(r^{k/2}\).
The method used in Section 4 cannot be used for \(k\equiv2\pmod4\), because it requires existence of a 3-dimensional magic rectangle \(3\)–\(MR(k/2,k/2,8)\) which only exists when \(k/2\) is even. Therefore, we do not rely on magic squares and define the partial squares explicitly.
We again start with an ad-hoc construction for the smallest case, \(k=2\).
Construction 5.1. \(D_{8}\)-semi-magic square \(Q(4)\)
The products in the square \(Q(4)\) shown in Figure 6 are performed in both row and columns as follows. First we find the product of reflections, starting with the red entry, and then multiply it by the rotations.
For example, in row 1 we have \[\begin{aligned} \rho_1 &=r^{1}r^{7}(r^0s)(r^1s) \\ &=r^{1}r^{7}r^0(sr^1s) \\ &=r^{1}r^{7}r^0r^{-1} \\ &=r^{7}, \end{aligned}\] and in column 2 we obtain \[\begin{aligned} \sigma_2&=r^{7}r^{2}(r^4s)(r^6s) \\ &=r^{7}r^{2}r^4(sr^6s) \\ &=r^{7}r^{2}r^4r^{-6} \\ &=r^{7}. \end{aligned}\]
The powers of rotations obtained by the row and column products are shown in the power square in Figure 7. The powers arising from the simplification \(sr^as = r^{-a}\) are shown in red.
For the general case, we again first construct the partial squares with rotations.
Construction 5.2 (Rotations). Let \(k=4h+2\). For \(j=1,2,\dots,k\) we define \[\begin{aligned} t^{11}_{1,j}=& \begin{cases} j-1 &\mathrm{\ for\ }j\mathrm{\ odd,}\\ 2k-j &\mathrm{\ for\ }j\mathrm{\ even}.\\ \end{cases} \end{aligned}\] and \[{t^{11}_{2,j} = 2k^2-t^{11}_{1,j}-1.}\]
The remaining rows are defined recursively by \[t^{11}_{i,j} = t^{11}_{i-2,j} +{(-1)^{i+1} 2k}.\]
For our calculations it will be more convenient to use explicit formula \[\begin{aligned} t^{11}_{i,j}=& \begin{cases} j-1 + k(i-1) &\mathrm{\ for\ }i\mathrm{\ odd},\ \ j\mathrm{ \ odd,}\\ 2k-j+ k(i-1) &\mathrm{\ for\ }i\mathrm{\ odd},\ \ j\mathrm{\ even,}\\ 2k^2-j- k(i-2) &\mathrm{\ for\ }i\mathrm{\ even},\ j\mathrm{\ odd,}\\ 2k^2+j-1 – ki &\mathrm{\ for\ }i\mathrm{\ even},\ j\mathrm{\ even}. \end{cases} \end{aligned}\]
We observe that for every \(i\) and \(j\) odd we have \[\begin{aligned} t^{11}_{i,j}+t^{11}_{i,j+1} &= j-1+k(i-1) + 2k-(j+1)+k(i-1)\\ &= 2k-2 +2k(i-1)\\ &=2ki-2. \end{aligned}\]
Now because every row in \(T^{11}\) contains \(k/2\) such pairs, we obtain \[\begin{aligned} \tau^{11}_i &= \frac{k}{2}(2ki-2)\\ &= k^2 i – k. \end{aligned}\]
Because \(i\) is odd, say \(i=2l+1\), we have \[\begin{aligned} \tau^{11}_i &= k^2 (2l+1) – k\\ &= 2k^2 l +k^2 – k\\ &= k^2 – k, \end{aligned}\] and \[\rho_i=r^{k^2-k},\] since our calculations are performed modulo \(2k^2\).
Similarly, for every \(i\) even and \(j\) odd we have \[\begin{aligned} t^{11}_{i,j}+t^{11}_{i,j+1} &= 2k^2-j-k(i-2)+2k^2+(j+1)-1-ki\\ &= 4k^2 -2k(i-1)\\ &=-2k(i-1)\\ &=2k(1-i). \end{aligned}\]
Again, every row in \(T^{11}\) contains \(k/2\) such pairs, which yields \[\begin{aligned} \tau^{11}_i &= \frac{k}{2} \; 2k(1-i)\\ &= k^2 (1-i). \end{aligned}\]
Because \(i\) is even, say \(i=2l\), we have \[\begin{aligned} \tau^{11}_i &= k^2 (1-2l) \\ &= k^2 – 2k^2 l\\ &= k^2, \end{aligned}\] and \[\rho_i = r^{k^2},\] since we perform our calculations modulo \(2k^2\).
Putting the odd and even case together, we have \[\begin{aligned} \rho^{11}_{i}=& \begin{cases} r^{k^2 – k} &\mathrm{\ for\ }i\mathrm{\ odd,}\\ r^{k^2} &\mathrm{\ for\ }i\mathrm{\ even}. \end{cases} \end{aligned}\]
For the column constants, we notice that for each odd \(i\) and \(j\) we have \[\begin{aligned} t^{11}_{i,j}+t^{11}_{i+1,j} &=\big(j-1+k(i-1)\big)+\big(2k^2-j-k((i+1)-2) \big)\\ &=2k^2 -1\\ &=-1. \end{aligned}\]
Also, for each odd \(i\) and even \(j\) we have \[\begin{aligned} t^{11}_{i,j}+t^{11}_{i+1,j} &=\big(2k-j+k(i-1)\big)+\big(k^2+j-1-k(i+1)\big)\\ &=2k^2-1\\ &=-1. \end{aligned}\]
Now, because we have \(k/2=2h+1\) such pairs \(t^{11}_{i,j},t^{11}_{i+1,j}\) in each column, for every \(j\) we obtain \[\begin{aligned} \eta^{11}_j &= – k/2, \end{aligned}\] and \[\sigma^{11}_j= r^{-k/2}.\]
Now we define entries in \(T^{22}\) simply as \[t^{22}_{i,j} = t^{11}_{i,j} + (-1)^{i+1}k^2,\] but because we have \(k^2 = -k^2\), then \[\tau^{22}_i=\tau^{11}_i + k(k^2)=\tau^{11}_i,\] because \(k\) is even and hence \(k(k^2)=0\). Also \[\eta^{22}_j=\eta^{11}_j + k(k^2)=\eta^{11}_j.\]
This then yields \[\begin{aligned} \rho^{22}_{i}=& \begin{cases} r^{k^2 – k} &\mathrm{\ for\ }i\mathrm{\ odd,}\\ r^{k^2} &\mathrm{\ for\ }i\mathrm{\ even}, \end{cases} \end{aligned}\] and \[\sigma^{22}_j= r^{-k/2}.\]
In Figure 8 we present an example of the power squares \(T^{11}(6)\) and \(T^{22}(6)\) used to build the square \(SMS_{D_{72}}(12)\).
Now we proceed to the partial squares with reflections.
Construction 5.3 (Reflections). For \(j=1,2,\dots,k\) we define \[\begin{aligned} f^{12}_{1,j}=& \begin{cases} j-1 &\mathrm{\ for\ }j\mathrm{\ odd,}\\ k+j-1 &\mathrm{\ for\ }j\mathrm{\ even}, \end{cases} \end{aligned}\] and \[f^{12}_{2,j} = {f^{12}_{1,j} +(-1)^{j+1}k,}\] that is, \[\begin{aligned} f^{12}_{2,j}=& \begin{cases} f^{12}_{1,j} + k &\mathrm{\ for\ }j\mathrm{\ odd,}\\ f^{12}_{1,j} – k &\mathrm{\ for\ }j\mathrm{\ even}.\\ \end{cases} \end{aligned}\]
The remaining rows are defined recursively by \[\begin{aligned} f^{12}_{i,j}=f^{12}_{i-2,j}+2k. \end{aligned}\]
For our calculations it will be more convenient to use explicit formula \[\begin{aligned} f^{12}_{i,j}=& \begin{cases} j-1 + k(i-1) &\mathrm{\ for\ }i\mathrm{\ odd},\ \ j\mathrm{\ odd,}\\ j-1 + ki &\mathrm{\ for\ }i\mathrm{\ odd},\ \ j\mathrm{\ even,}\\ j-1 + k(i-1) &\mathrm{\ for\ }i\mathrm{\ even},\ j\mathrm{\ odd,}\\ j-1 + k(i-2) &\mathrm{\ for\ }i\mathrm{\ even},\ j\mathrm{\ even}. \end{cases} \end{aligned}\]
We now perform the multiplication in row \(i\) of the square \(Q^{12}\) starting with the entry \(r^{f^{12}_{i,i}}s\) corresponding to \(f^{12}_{i,i}\) in \(F^{12}\) (reading from right to left) \[\begin{aligned} \rho^{12}_i &=(r^{f^{12}_{i,i+1}}s)(r^{f^{12}_{i,i+2}}s)\dots (r^{f^{12}_{i,i-1}}s)(r^{f^{12}_{i,i}}s) \\ &=(r^{f^{12}_{i,i+1}})(sr^{f^{12}_{i,i+2}}s)\dots (r^{f^{12}_{i,i-1}})(sr^{f^{12}_{i,i}}s) \\ &=r^{f^{12}_{i,i+1}}\ r^{-f^{12}_{i,i+2}}\dots r^{f^{12}_{i,i-1}}\ r^{-f^{12}_{i,i}} \\ &=r^{f^{12}_{i,i+1}-f^{12}_{i,i+2}\dots +f^{12}_{i,i-1}-f^{12}_{i,i}}. \end{aligned}\]
We notice here that the parameter \(u\) used in Definition 2.5 is \(u=0\), and thus the ordering is half-diagonal circular.
Now we need to verify that in each row \(i\), the product is the same. To do that, it is enough to check that each sum \(\tau^{12}_i\), defined as \[\tau^{12}_i = f^{12}_{i,i+1}-f^{12}_{i,i+2}+\dots +f^{12}_{i,i-1}-f^{12}_{i,i},\] is the same for every \(i=1,2,\dots,n\).
First we look at \(i\) odd. We observe that for every \(i\) and \(j\) odd we have \[\begin{aligned} -f^{12}_{i,j}+f^{12}_{i,j+1} &= -\big(j-1 + k(i-1)\big) + \big((j+1)-1 +ki\big)\\ &= k+1, \end{aligned}\] and because there are \(k/2\) such pairs in every row, we obtain \[\tau^{12}_i = \frac{k(k+1)}{2} ,\] For every even \(i\) and every odd \(j\) we have \[\begin{aligned} f^{12}_{i,j}-f^{12}_{i,j+1} &= \big(j-1+k(i-1)\big)-\big((j+1)-1+k(i-2)\big)\\ &= k-1, \end{aligned}\] and for the same reason as above \[\tau^{12}_i = \frac{k(k-1)}{2}.\]
Therefore, \[\begin{aligned} \tau^{12}_{i}=& \begin{cases} {k(k+1)}/{2} &\mathrm{\ for\ }i\mathrm{\ odd,}\\ {k(k-1)}/{2} &\mathrm{\ for\ }i\mathrm{\ even}, \end{cases} \end{aligned}\] and hence \[\begin{aligned} \rho^{12}_{i}=& \begin{cases} r^{{k(k+1)}/{2}} &\mathrm{\ for\ }i\mathrm{\ odd,}\\ r^{{k(k-1)}/{2}} &\mathrm{\ for\ }i\mathrm{\ even}. \end{cases} \end{aligned}\]
The square \(F^{21}\) is defined recursively by \[\begin{aligned} f^{21}_{i,j}= f^{12}_{i,j} +k^2. \end{aligned}\]
It follows that for \(i\) and \(j\) odd \[\begin{aligned} -f^{21}_{i,j}+f^{21}_{i,j+1} &= -(f^{12}_{i,j}+k^2)+(f^{12}_{i,j+1}+k^2) \\ &= -f^{12}_{i,j}+f^{12}_{i,j+1} \\ &= k+1, \end{aligned}\] and \[\tau^{21}_i = \frac{k(k+1)}{2}.\]
The same argument for \(i\) even yields \[\tau^{21}_i = \frac{k(k-1)}{2},\] which implies \[\begin{aligned} \rho^{21}_{i}=& \begin{cases} r^{{k(k+1)}/{2}} &\mathrm{\ for\ }i\mathrm{\ odd,}\\ r^{{k(k-1)}/{2}} &\mathrm{\ for\ }i\mathrm{\ even}. \end{cases} \end{aligned}\]
For the column products, we start with the entry just below the main diagonal, and proceed upward. That is, we define them for each \(j=1,2,\dots,n\) as \[\begin{aligned} \sigma^{12}_j &=(r^{f^{12}_{j+2,j}}s)(r^{f^{12}_{j+3,j}}s)\dots(r^{f^{12}_{j,j}}s)(r^{f^{12}_{j+1,j}}s)\\ &=(r^{f^{12}_{j+2,j}})(sr^{f^{12}_{j+3,j}}s)\dots(r^{f^{12}_{j,j}})(sr^{f^{12}_{j+1,j}}s)\\ &=r^{f^{12}_{j+2,j}}\ r^{-f^{12}_{j+3,j}}\dots r^{f^{12}_{j,j}}\ r^{-f^{12}_{j+1,j}}\\ &=r^{f^{12}_{j,j+2}-f^{12}_{j,j+3}\dots+f^{12}_{j,j}-f^{12}_{j+1,j}}. \end{aligned}\]
Here the parameter \(v\) used in Definition 2.5 is \(v=1\), and thus the ordering is half-diagonal circular.
We again want to verify that in each column \(j\), the product is the same. We observe that for each odd \(j\) and \(i\) we have \[\begin{aligned} f^{12}_{i,j}-f^{12}_{i+1,j} &=\big(j-1+k(i-1)\big)-\big(j-1+k((i+1)-1) \big)\\ &=-k. \end{aligned}\]
Similarly for each even \(j\) and odd \(i\) we have \[\begin{aligned} -f^{12}_{i,j}+f^{12}_{i+1,j} &=-\big(j-1+ki\big)+\big(j-1+k((i+1)-2) \big)\\ &=-k. \end{aligned}\]
Again we always have \(k/2\) such pairs \(f^{12}_{i,j},f^{12}_{i+1,j}\) for any \(j\), therefore \[\eta^{12}_j=-k^2/2,\] and \[\sigma^{12}_j=r^{-k^2/2}.\]
Now recall that \(F^{21}\) was defined recursively as \[f^{21}_{i,j}= f^{12}_{i,j} + k^2.\]
Then for \(j\) and \(i\) both odd \[\begin{aligned} f^{21}_{i,j}-f^{21}_{i+1,j} &= (f^{12}_{i,j}+k^2)-(f^{12}_{i+1,j}+k^2) \\ &=f^{12}_{i,j}-f^{12}_{i+1,j} \\ &=-k, \end{aligned}\] and \[\eta^{21}_i = \eta^{12}_j=-k^2/2,\] which yields \[\sigma^{21}_j=\sigma^{12}_j=r^{-k^2/2}.\]
The same can be performed for \(j\) even, and therefore for every \(j\) we have \[\sigma^{21}_j=\sigma^{12}_j=r^{-k^2/2}.\]
In Figure 9 we present an example of the power squares \(F^{12}(6)\) and \(F^{21}(6)\) used to build the square \(SMS_{D_{72}}(12)\).
Now we can prove our second result.
Theorem 5.4. There exists a half-diagonal circular \(D_{2k^2}\)-semi-magic square \(Q(2k)\) for every \(k\equiv2\pmod4\), \(k\geq2\).
Proof. The square \(Q(4)\) was constructed in Construction 5.1. For \(k\geq6\), the row products for \(i=1,2,\dots,k\) are performed as \[\rho_i = (q^{11}_{i,i+1}\ q^{11}_{i,i+2}\dots q^{11}_{i,i-1} q^{11}_{i,i})\ (q^{12}_{i,i+1}\ q^{12}_{i,i+2}\dots q^{12}_{i,i-1}\ q^{12}_{i,i}) = \rho^{11}_i \rho^{12}_i,\] or \[\rho_{k+i}= (q^{21}_{i,i+1}\ q^{21}_{i,i+2}\dots q^{21}_{i,i-1}q^{21}_{i,i})\ (q^{22}_{i,i+1}\ q^{22}_{i,i+2}\ \dots q^{22}_{i,i-1} q^{22}_{i,i}) = \rho^{21}_i \rho^{22}_i.\]
The product always starts on the main half-diagonal and continues circularly from right to left.
For \(i\) odd, we obtain \[\rho_i = \rho^{11}_i \rho^{12}_i = r^{k^2-k} r^{{k(k+1)}/{2}} = r^{(3k^2-k)/2},\] and for \(i\) even, we have \[\rho_i = \rho^{11}_i \rho^{12}_i = r^{k^2} r^{{k(k-1)}/{2}} = r^{(3k^2-k)/2},\] as well. Because the row products \(\rho^{uv}_i\) are all rotations, the multiplication is commutative and remembering that \(\rho^{11}_i=\rho^{22}_i\) and \(\rho^{12}_i=\rho^{21}_i\), we have \[\rho_{k+i} = \rho^{21}_i \rho^{22}_i = \rho^{12}_i \rho^{11}_i = \rho^{11}_i \rho^{12}_i = \rho_i,\] for every \(i\) as well.
The column products for \(j=1,2,\dots,k\) are \[\sigma_j=(q^{11}_{j+2,j}\ q^{11}_{j+3,j}\dots q^{11}_{j+1,j}) \ (q^{21}_{j+2,j}\ q^{21}_{j+3,j}\dots q^{21}_{j,j}\ q^{21}_{j+1,j}) = \sigma^{11}_i \sigma^{21}_i =r^{-k/2}\ r^{-k^2/2} = r^{(-k^2-k)/2},\] and \[\sigma_{k+j}=(q^{12}_{j+1,j}\ q^{12}_{j+2,j}\dots q^{12}_{j-1,j}\ q^{12}_{k,j})\ (q^{22}_{j+2,j}\ q^{22}_{j+3,j}\dots q^{22}_{j+1,j}) = \sigma^{12}_i \sigma^{22}_i =r^{-k^2/2}\ r^{-k/2} = r^{(-k^2-k)/2}.\]
The column product always starts on the second forward half-diagonal (the one just above the main half-diagonal) and continues circularly upwards.
Now because the subgroup of rotations is of order \(2k^2\), we have \[r^{(-k^2-k)/2} = r^{2k^2+(-k^2-k)/2}=r^{(4k^2-k^2-k)/2}=r^{(3k^2-k)/2}.\]
Therefore, all row and column products in the square \(Q(2k)\) are equal to the magic constant \(\mu=r^{(3k^2-k)/2}\), which completes the proof. \(\square\)
In Figure 10 we present \(SMS_{D_{72}}(12)\). For better readability, the partial squares with rotations are shown in blue, the starting elements in the row products of reflections are in red, and the starting elements in the column products of reflections are in green.
In Figure 11 we show \(SMS_{D_{72}}(12)\) after simplification for row products where after re-bracketing we use the identity \(sr^as=r^{-a}\). The partial squares with rotations are again in blue, and the elements arising from the simplifying replacement are in red.
The same for the column products is shown in Figure 12, where the elements arising from the simplifying replacement are in green.
Remark 5.5. The semi-magic square in Theorem 5.4 is again not magic, because the product on the main diagonal is equal to \(r^{k^2-k}\).
We have shown that a magic square over a dihedral group must be of even side, and proved existence of such semi-magic rectangles for some even \(n\). We summarize out two previous results in the following.
Theorem 6.1. There exist a \(\Gamma\)-semi-magic square \(SMS_{\Gamma}(n)\), where \(\Gamma\) is a dihedral group, for every \(n\equiv0\pmod4\), \(n\geq4\).
Because we were unable to find such squares for \(n\equiv2\pmod4\), we pose an open problem here.
Problem 6.2. Construct \(\Gamma\)-semi-magic squares \(SMS_{\Gamma}(n)\), where \(\Gamma\) is a dihedral group, for every \(n\equiv2\pmod4\), \(n\geq6\).
It can be verified easily that such \(MS_{\Gamma}(2)\) does not exist. Finally because all our squares are \(\Gamma\)-semi-magic but not \(\Gamma\)-magic, we conclude with the following.
Problem 6.3. Construct \(\Gamma\)-magic squares \(MS_{\Gamma}(n)\), where \(\Gamma\) is a dihedral group, for every even \(n\), \(n\geq4\).