Magic Squares with Powered Sum

Magic Squares with Powered Sum

Shozan Chikaraishi Midori Kobayashi Nobuaki Mutoh Gisaku Nakamura

In this paper, we show that there is a normal magic square withk-powered sum for every integerk≥2. The order of our example is2^k/2+1.

Keywords: magic square,k-powered sum

1 Introduction

Letn≥1be an integer. A magic square of ordernis ann×nmatrix consisting of distinct integers arranged so that the sum of thennumbers in each row, each column, ans each of the two diagonals are the same. The sum is called the magic number of the matrix. If, in addition, its matrix elements consist of the consecutive integers1,2, . . . , n², the matrix is called a normal magic square [2].

Normal magic squares have been known and studied for many centuries. Yang Hui made normal magic squares of order3to10in his book in the 13th century [1] (pp. 39 - 44). Among them, the following normal magic square which is the second magic square of order8in [1]

has an interesting property;

Y₈=















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













 .

LetE = (e_ij)be the4×8matrix formed by the first4 rows of Y₈,F = (f_ij)the 4×8 matrix formed by the last4 rows ofY₈, G = (g_ij) the8×4 matrix formed by the first4 columns ofY₈, and H = (u_ij) the8×4 matrix formed by the last 4 columns ofY₈. Put E⁽²⁾ =

1≤i≤4,1≤j≤8e²_ij,F⁽²⁾ =

1≤i≤4,1≤j≤8f_ij²,G⁽²⁾ =

1≤i≤8,1≤j≤4g²_ij,H⁽²⁾ =

1≤i≤8,1≤j≤4h²_ij, then it holds thatE⁽²⁾ =F⁽²⁾ =G⁽²⁾ =H⁽²⁾. Furthermore, putE⁽³⁾ = e³_ij,F⁽³⁾ =

f_ij³,G⁽³⁾ =

g_ij³,H⁽³⁾ =

h³_ij;E⁽⁴⁾ =

e⁴_ij,F⁽⁴⁾ =

f_ij⁴,G⁽⁴⁾ = g_ij⁴,H⁽⁴⁾ =

h⁴_ij. Then, surprisingly it also holds thatE⁽³⁾ =F⁽³⁾ =G⁽³⁾ =H⁽³⁾ and E⁽⁴⁾=F⁽⁴⁾=G⁽⁴⁾=H⁽⁴⁾.

In this paper, we consider normal magic squares with such a property.

Letn≥2be an even number. LetAbe a normal magic square of ordernandE_A= (e_ij) then/2×nmatrix formed by the firstn/2rows ofA,F_A= (f_ij)then/2×nmatrix formed by the lastn/2rows ofA,G_A= (g_ij)then×n/2matrix formed by the firstn/2columns ofA, andH_A= (h_ij)then×n/2matrix formed by the lastn/2columns ofA. DefineE_A^(l)=

e^l_ij, F_A^(l)=

f_ij^l,G^(l)_A =

g^l_ij,H_A^(l)=

h^l_ij. Letkbe an integer withk≥2. A normal magic squareAis defined to be a magic square withk-powered sum ifE_A^(l)= F_A^(l) =G^(l)_A =H_A^(l) for anyl(2≤l≤k). The squareY₈is a magic square with4-powered sum.

We consider the problem of constructing magic squares with k-powered sum for every k≥2, and we obtain an affirmative answer to the problem:

Problem 1.1 Construct a magic square withk-powered sum for everyk≥2.

Theorem 1.1 Letkbe an integer withk≥2and putn= 2^k/2+1. Then there exists a magic square of ordernwithk-powered sum.

2 Notation and preliminaries

Letn≥2be an even number. LetA= (a_ij)be ann×nmatrix. We define the functionf byf(a_ij) = 2(a_ij−(n²+ 1)/2), and putf(A) = (f(a_ij)). WhenAis a normal magic square of ordern, we call the matrixf(A)the prototype of a magic squareA.

Proposition 2.1 Letn ≥ 2be an even number. IfA is a normal magic square of order n, thenf(A)is a magic square with the magic number 0and the set of the matrix elements is {b| −(n²−1)≤b≤n²−1, bis odd}, and vice versa.

Let{s_i}i=0,1,... be an infinite sequence such thats_iis the parity ofi, that iss_i =−1ifi has an odd number of1s in binary,s_i = 1ifihas an even number of1s in binary. Then we have{s_i}i=0,1,... = {1,−1,−1,1,−1,1,1,−1, . . .}. The sequence{s_i}is equivalent to the Thue-Morse sequence, also called the Morse sequence or Prouhet-Thue-Morse sequence. It is known that it has the following properties.

Proposition 2.2 Letkbe an integer withk≥1. Then we have (1)₂^k₋₁

i=0 s_i= 0.

(2)s_i+2k =−s_i (0≤i≤2^k−1).

Proposition 2.3 ([3], p. 204) Letkbe an integer withk≥2. Then we have

2^k−1 i=0

s_ii^t= 0 (1≤t≤k−1).

The next proposition follows from Prop. 2.2 (1) and 2.3.

Proposition 2.4 Letkbe an integer withk≥2. For any integerλandµ, we have

2^k−1 i=0

s_i(λi+µ)^t= 0 (1≤t≤k−1).

3 A proof of the theorem

Letk≥4be even and putn= 2^k/2+1. Putc_i=s_i(2i+ 1),(i= 0,1, . . .). We define an n×nmatrixBas

B = (b_ij) =



 U₁(B) U₂(B) U₃(B) U₄(B)



,

whereU_i(B)is ann/2×n/2matrix such that U₁(B) =







c₀ c₁ · · · c₂k/2−1

c₂k/2 c₂k/2+1 · · · c_2·2k/2−1

· · · · · · · · · · · · c₍₂k/2−1)2^k/2 c₍₂k/2−1)2^k/2+1 · · · c₂k−1





,

U₃(B) =







c₂k c₂k+1 · · · c₂k+2^k/2−1

c₂k+2^k/2 c₂k+2^k/2+1 · · · c₂k+2·2^k/2−1

· · · · · · · · · · · · c₂k+(2^k/2−1)2^k/2 c₂k+(2^k/2−1)2^k/2+1 · · · c₂k+1−1





,

U₂(B) =−U₃(B)andU₄(B) =−U₁(B). Lemma 3.1

(1) The matixBis a magic square with the magic number0.

(2) The set of the matrix elements is{b| −(n²−1)≤b≤n²−1, bis odd}. Proof. (1) The sum of 4 numbers₃

i=0c_4l+i is0 (l ≥0) since(s_4l, s_4l+1, s_4l+2, s_4l+3) = (1,−1,−1,1)or(−1,1,1,−1)by Prop. 2.2 (2). So the sum of then/2numbers in each row ofU₁(B)andU₃(B)is0. Therefore the sum of thennumbers in each row ofBis0. The sums of the two diagonals ofBare0sinceU₂(B) =−U₃(B)andU₄(B) =−U₁(B).

Next we consider the sum of then/2numbers in each column ofU₁(B). First, consider 4 numbersc₀, c₂k/2, c_2·2k/2, c_3·2k/2 in the first column. We have(s₀, s₂k/2, s_2·2k/2, s_3·2k/2) = (1,−1,−1,1)since we haves₂k/2 =−s₀and(s_2·2k/2, s_3·2k/2) =−(s₀, s₂k/2)by Proposition 2.2 (2). So the sum of the 4 numbersc₀+c₂k/2+c_2·2k/2+c_3·2k/2 is0. Similarly the sum of 4 numbersc_4l·2k/2+c_(4l+1)·2k/2+c_(4l+2)·2k/2+c_(4l+3)·2k/2 in the first column is0 (l ≥1). Thus the sum of then/2numbers in the first column ofU₁(B)is0. Similarly we see that the sum of then/2numbers in each column ofU₁(B)is0.

The sum of then/2numbers in each column ofU₃(B)is also0. Therefore we find that the sum of thennumbers in each column ofBis0. This completes the proof of (1). (2) is trivial.

We have the following lemma, where we writex∈X whenxis a component of a matrix X.

Lemma 3.2

b∈U1(B)

b^t=

b∈U2(B)

b^t=

b∈U3(B)

b^t=

b∈U4(B)

b^t= 0 (t odd, 1≤t≤k−1). (1)

b∈U1(B)

b^t=

b∈U4(B)

b^t,

b∈U2(B)

b^t=

b∈U3(B)

b^t (t even, 1≤t≤k). (2)

Proof. (1) Lettbe an odd with1 ≤t ≤k−1. Then we have

b∈U1(B)b^t =₂^k₋₁

i=0 c^t_i = ₂^k₋₁

i=0 s^t_i(2i+ 1)^t = ₂^k₋₁

i=0 s_i(2i+ 1)^t = 0by Prop. 2.4. And we have

b∈U3(B)b^t = ₂^k+1₋₁

i=2^k c^t_i = ₂^k+1₋₁

i=2^k s^t_i(2i+ 1)^t = ₂^k+1₋₁

i=2^k s_i(2i+ 1)^t = ₂^k₋₁

j=0 s_j+2k(2(j+ 2^k) + 1)^t=₂^k₋₁

j=0 (−s_j)(2j+ 2·2^k+ 1)^t = 0by Prop. 2.2 (2) and 2.4. The remaining equation

b∈U2(B)b^t=

b∈U4(B)b^t= 0is obtained fromU₂(B) =−U₃(B)andU₄(B) =−U₁(B). (2) is trivial.

Define A=f⁻¹(B), and put

A= (a_ij) =



 U₁(A) U₂(A) U₃(A) U₄(A)



,

whereU_i(A)is ann/2×n/2matrix(1≤i≤4). ThenAis a normal magic square of ordern by Prop. 2.1 and Lemma 3.1.

Lemma 3.3

a∈U1(A)

a^t=

a∈U4(A)

a^t,

a∈U2(A)

a^t=

a∈U3(A)

a^t (1≤t≤k).

Proof. Since

a∈U1(A)a^t=

b∈U1(B)(b/2+(n²+1)/2)^tand

a∈U4(A)a^t=

b∈U4(B)(b/2+

(n²+ 1)/2)^t, we have the first equation by Lemma 3.2. The second equation is obtained in a similar way. Note thatkis even by our assumption.

Lemma 3.4

a∈E(A)

a^t=

a∈F(A)

a^t=

a∈G(A)

a^t=

a∈H(A)

a^t (1≤t≤k).

Proof. The above equation holds by Lemma 3.3 since

a∈E(A)a^t=

a∈U1(A)a^t+

a∈U2(A)a^t,

a∈F(A)a^t =

a∈U3(A)a^t+

a∈U4(A)a^t,

a∈G(A)a^t =

a∈U1(A)a^t+

a∈U3(A)a^t, and

a∈H(A)a^t=

a∈U2(A)a^t+

a∈U4(A)a^t. From Lemma 3.4, we obtain the following proposition.

Proposition 3.1 Letk≥4be even and putn= 2^k/2+1. ThenAis a magic square of ordern withk-powered sum.

Whenk= 2,

D=







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







is a magic square with2-powered sum. Then we obtain the following proposition.

Proposition 3.2 Letk≥2be even and putn= 2^k/2+1. Then there exists a magic square of ordernwithk-powered sum.

Ifk ≥3is odd, thenk+ 1is even and there is a magic square of ordern= 2^(k+1)/2+1 withk-powered sum by Prop. 3.2. Therefore we complete the proof of the theorem.

Example Whenk= 4, we haven= 8and

B=















1 −3 −5 7 33 −35 −37 39

−9 11 13 −15 −41 43 45 −47

−17 19 21 −23 −49 51 53 −55 25 −27 −29 31 57 −59 −61 63

−33 35 37 −39 −1 3 5 −7

41 −43 −45 47 9 −11 −13 15 49 −51 −53 55 17 −19 −21 23

−57 59 61 −63 −25 27 29 −31













 ,

A=















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













 .

ThenAis a magic square with 4-powered sum.

4 Remarks

We mention that there is a similar concept to a magic square withk-powered sum, that is a multimagic square. A normal magic squareMis called to bek-multimagic ifM^∗2, M^∗3, . . . , M^∗k are all magic, whereM^∗jis the square formed by replacing each element ofMby itsjth power (j= 1,2, . . . , k). Fork= 2, it is known that there is ak-multimagic square of order8, and for anykwithk≥3, Derksen et al. proved the following theorem.

Theorem A ([2]) Letkbe an integer withk≥3and letpbe a prime withp≥2k−1. Then there exists ak-multimagic square of orderp^k.

If a normal magic square A isk-multimagic, then A is a magic square withk-powered sum¹. Therefore Theorem A is also an answer to Problem 1.1. However, Theorem 1 shows that there exists a magic square withk-powered sum whose order is less than the order of the magic square in Theorem A.

References

[1] Yang Hui suan fa (楊輝算法), 1274, in Chinese,

http://www.tulips.tsukuba.ac.jp/limedio/dlam/B14/B1407158/1.pdf, reprint, 1433.

[2] H. Derksen, C. Eggermont and A. van den Essen, Multimagic Squares, American Mathe- matical Monthly, Vol. 114, No. 8, October 2007, 703-713.

[3] S. Savchev and T. Andreescu, Mathematical Miniatures, The Mathematical Association of America, Washington DC, 2003.

1The converse does not hold. In fact, the squareY8made by Yang Hui is a magic square with4-powered sum, but it is not4-multimagic or even2-multimagic.