3
$\begingroup$

Given $X$, a set of $n^2$ integers what are necessary and sufficient conditions for forming a magic square with them?

For eg: if $X$ has members from an arithmetic sequence, we can create a magic square.

Here is a magic square formed using $X = \{ 1, 2, \dots, 9 \}$

enter image description here

Here is another with $X = \{ 5 + 3k : k \in [1, 9] \}$

enter image description here

and this one using $Y = \{ 5 + 3k : k \in X \}$, where $X$ is the set defined above.

enter image description here

Are there other sets apart from elements from Arithmetic Sequences that can be arranged into a magic square?

$\endgroup$
5
  • 2
    $\begingroup$ Of course, consider these prime magic squares. $\endgroup$ – player3236 Sep 29 '20 at 14:26
  • 2
    $\begingroup$ These magic squares of order 3 are characterized here. They are a family with 3 parameters - this seems reasonable as there are 10 numbers (including the common sum) and 8 conditions which have one relation: The sum of the 3 rows equals the sum of the 3 columns. $\endgroup$ – Helmut Sep 29 '20 at 15:53
  • 1
    $\begingroup$ Here's a $3\times3$ not from an arithmetic sequence: $$\matrix{13&11&6\cr3&10&17\cr14&9&7\cr}$$ $\endgroup$ – Gerry Myerson Oct 13 '20 at 11:55
  • $\begingroup$ Thanks. It appears this uses the Édouard Lucas' construction as outlined in the reference link provided by Helmut in comment above. $\endgroup$ – vvg Oct 13 '20 at 13:29
  • 1
    $\begingroup$ Every $3\times3$ is a linear combination of these three: $$\matrix{1&1&1\cr1&1&1\cr1&1&1\cr},\qquad\matrix{0&1&-1\cr-1&0&1\cr1&-1&0\cr},\qquad\matrix{1&0&-1\cr-2&0&2\cr1&0&-1\cr}$$ I added ten of the first, one of the second, and three of the third. $\endgroup$ – Gerry Myerson Oct 13 '20 at 22:40
3
+50
$\begingroup$

Yes, there is a formula for any $(n+1)\times (n+1)$ magic square, which can be deduced with a bit of hard work and clever moves:

Lets start

Because I do not have acces to editing tools, I will say thet cell $(a,b)$ is the cell on the $a^{th}$ line and $b^{tn}$ column.

Let us fill $(i,j)$ with $x_{(a-1)n+b}$, $\forall i,j$ with $1\leq i,j \leq n$ and $(n+1,n+1)=x$

Observe that the "magic sum" is $$\sum_{i=0}^{n-1}x_{in+i+1}+x=S$$

Rmember this property as $(*)$.

because those are the numbers on the big diagonal which starts at $(1,1)$ and ends at $(n+1,n+1)$

We can fill all the remaining cells accordingly.

We get that $\forall k$, $1\leq k\leq n$

$$(k,n+1)=S-\sum_{i=1}^{n}x_{(k-1)n+i}$$

and

$$(n+1,k)=S-\sum_{i=0}^{n-1}x_{in+k}$$

( Now, if you haven't done it already, draw this square. Maybe try for small cases like $n=4$ or $5$ first. )

For the square to be magical, we must check the property for the $(n+1)^{th}$ row, the $(n+1)^{th}$ column and the big diagonal that starts at $(1,n+1)$ and ends at $(n+1,1)$

In other words, the following must happen:

For the $(n+1)^{th}$ column:

$$S=\sum_{k=1}^{n}(k,n+1)+x=\sum_{k=1}^{n}\bigg(S-\sum_{i=0}^{n-1}x_{in+k}\bigg)+x=n\cdot S-\sum_{i=1}^{n^2}x_i+x$$

For the $(n+1)^{th}$ row:

$$S=\sum_{k=1}^{n}(n+1,k)+x=\sum_{k=1}^{n}\bigg(S-\sum_{i=1}^{n}x_{(k-1)n+i}\bigg)+x=n\cdot S-\sum_{i=1}^{n^2}x_i+x$$

For the second big diagonal:

$$S=\sum_{i=1}^{n+1}(i,n+2-1)=\bigg(S-\sum_{i=1}^{n}x_i\bigg)+\bigg(S-\sum_{i=0}^{n-1}x_{in+1}\bigg)+\sum_{i=2}^{n}x_{in-(i-2)}$$

The conditions for the $(n+1)^{th}$ column and row are the same. Using $(*)$, we get

$$x=\frac{\sum_{i=1}^{n^2}x_i-(n-1)\sum_{i=0}^{n-1}x_{in+i+1}}{n}$$

So this is the first condition. As an example, using the formula given in the comments for the $3\times 3$ square (so $n=2$), this is equivalent to:

$$c+b=\frac{\big(c-b+c+(a+b)+c-(a-b)+c\big)-\big(c-b+c\big)}{2}=\frac{2c+2b}{2}$$

which is true.

Now lets see the condition for the other big diagonal. We have

$$S=\sum_{i=1}^{n+1}(i,n+2-1)=\bigg(S-\sum_{i=1}^{n}x_i\bigg)+\bigg(S-\sum_{i=0}^{n-1}x_{in+1}\bigg)+\sum_{i=2}^{n}x_{in-(i-2)}$$

so by using $(*)$ and reducing, we get

$$x=\sum_{i=1}^{n}x_i+\sum_{i=0}^{n-1}x_{in+1}-\sum_{i=2}^{n}x_{in-(i-2)}-\sum_{i=0}^{n-1}x_{in+i+1}$$ 9again, this can be checked using the formula for $3\times 3$)

To conclude

The only condition (sufficient and necessary) for a square to be perfect is: (note, I got the final result by using the 2 equalities for $x$ and by reducing some terms)

Consider an $(n+1)\times(n+1)$ square. Consider $(a,b)$ the cell situated on the $a^{th}$ line and $b^{tn}$ column. Let us fill $(i,j)$ with $x_{(a-1)n+b}$, $\forall i,j$ with $1\leq i,j \leq n$. Then, we must have: $$\sum_{i=1}^{n^2}x_i+\sum_{i=0}^{n-1}x_{in+i+1}=n\cdot\bigg(\sum_{i=1}^{n}x_i+\sum_{i=0}^{n-1}x_{in+1}-\sum_{i=2}^{n}x_{in-(i-2)}\bigg)$$

So to answer your questions:

Given a set of $(n+1)^2$ integers, we can form an $(n+1)\times (n+1)$ perfect square with them if and only if there exist $x_1,x_2,...,x_{n^2}$ such that $$\sum_{i=1}^{n^2}x_i+\sum_{i=0}^{n-1}x_{in+i+1}=n\cdot\bigg(\sum_{i=1}^{n}x_i+\sum_{i=0}^{n-1}x_{in+1}-\sum_{i=2}^{n}x_{in-(i-2)}\bigg)$$

Finishing touches

To get the actual formula for every single damn cell, just use whichever formula for $(n+1,n+1)=x$ you want, and then the formulas for $(n+1,k$ and $k,n+1)$

P.S. I am sorry, but the formulas cannot get nicer than this :(

$\endgroup$
1
$\begingroup$

The problem of determining whether a set $L$ of $n^2$ integers can be arranged into a magic square is NP-complete. This is because the problem is very SUBSET-SUM-like: a necessary condition for $L$ to be arrangeable as a magic square is that there exists a subset of $L$ that sums to $\frac{1}{n}\sum_{i\in L}i$. Assuming $P\neq NP$, you won't find a simple procedure for this problem.

Proof (sketch) of NP-completeness: the NP-completeness proof for SUBSET-SUM gives instances of the following form: a set $W=\{w_{i,b}\}_{i\in[k],b\in\{0,1\}}$ and a target $T$. The guarantee of the proof is that:
(1) Any subset of $W$ which sums to $T$ must pick exactly one of $w_{i,0},w_{i,1}$, for each $i$.
(2) If you can decide whether $W$ has a subset summing to $T$, then you can solve all of NP.

We can easily modify the proof to add the guarantee that
(3) $\sum_{i,b} w_{i,b}=2T$

We now embed this into a magic square problem as follows. Set $n=(2k+1)$. The idea is choose $X$ which contains $W$, so that the only way to build a magic square of $X$ is to place the SUBSET-SUM solution on the diagonal (say as the first $k$ entries), and all the remaining elements of $W$ on the anti-diagonal, with $w_{i,0}$ and $w_{i,1}$ belonging to the same row. It isn't too hard to choose elements in $X$ with this guarantee.

$\endgroup$
2
  • $\begingroup$ At least for 3x3, if we use Édouard Lucas' construction and solve for 8 equations and 1 inequality, we can find a magic square. See A method for constructing a magic square of order 3 (in en.wikipedia.org/wiki/…). Link courtesy @Helmut in earlier comment to question. $\endgroup$ – vvg Oct 14 '20 at 3:30
  • $\begingroup$ Sure, for any constant $n$, you may be able to characterize which sets of $n^2$ integers can be arranged into a magic square. But as $n\rightarrow\infty$, the complexity of such a characterization will necessarily grow very fast, assuming $P\neq NP$. $\endgroup$ – Mark Oct 14 '20 at 13:18
1
$\begingroup$

It's not hard to answer in full for $n=3$. If you're given nine integers, and you want to know whether you can use them to form a magic square,

  1. arrange them in increasing order: $a_1\le a_2\le\cdots\le a_8\le a_9$. If they aren't symmetric around the one in the middle (that is, if you don't have $a_6-a_5=a_5-a_4$, $a_7-a_5=a_5-a_3$, and so on) then stop: you can't form a magic square. If they are symmetric,

  2. form the numbers $b_n=a_n-a_5$ for $n=6,7,8,9$. If $b_8=b_6+b_7$ and $b_9$ equals either $b_6+2b_7$ or $2b_6+b_7$, then you can form a magic square; otherwise, not.

Why this works: by Linear Algebra, every $3\times3$ magic square is of the form $$\matrix{a+d&a+c&a-c-d\cr a-c-2d&a&a+c+2d\cr a+c+d&a-c&a-d\cr}$$ Arranging the nine numbers in increasing order we get $$a-c-2d\le a-c-d\le a-d\le a-c\le a\le a+c\le a+d\le a+c+d\le a+c+2d$$ if $c\le d$, $$a-c-2d\le a-c-d\le a-c\le a-d\le a\le a+d\le a+c\le a+c+d\le a+c+2d$$ if $d\le c$. In the first case, we have $b_6,b_7,b_8,b_9$ are $c,d,c+d,c+2d$ so $b_8=b_6+b_7$ and $b_9=b_6+2b_7$; in the second case, $b_6,b_7,b_8,b_9$ is $d,c,c+d,c+2d$ so $b_8=b_6+b_7$ and $b_9=b_7+2b_6$.

$\endgroup$
1
  • $\begingroup$ Yes. For squares of order 3, it looks like we can efficiently check if arbitrary sets can be placed into a magic square or not. $\endgroup$ – vvg Oct 14 '20 at 3:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.