# Sets of integers that can be placed in a magic square

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 \}$$

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

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

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

• Of course, consider these prime magic squares. – player3236 Sep 29 '20 at 14:26
• 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. – Helmut Sep 29 '20 at 15:53
• Here's a $3\times3$ not from an arithmetic sequence: $$\matrix{13&11&6\cr3&10&17\cr14&9&7\cr}$$ – Gerry Myerson Oct 13 '20 at 11:55
• Thanks. It appears this uses the Édouard Lucas' construction as outlined in the reference link provided by Helmut in comment above. – vvg Oct 13 '20 at 13:29
• 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. – Gerry Myerson Oct 13 '20 at 22:40

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)$$

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 :(

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.

• 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. – vvg Oct 14 '20 at 3:30
• 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$. – Mark Oct 14 '20 at 13:18

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$$.

• 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. – vvg Oct 14 '20 at 3:38