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, 2020 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, 2020 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$ Oct 13, 2020 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, 2020 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$ Oct 13, 2020 at 22:40

3 Answers 3

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$
2
$\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, 2020 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$
    – AAA
    Oct 14, 2020 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, 2020 at 3:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .