4
$\begingroup$

An $n\times n$ magic square summing to $S$ is an assignment of distinct integers to the $n^2$ entries of an $n \times n$ grid such that each row, column, and main diagonal sums to $S$.

It is well known that for $n>2$, an $n\times n$ magic square with sum $M_n=n(n^2+1)/2$ can be formed using the integers $1,2,\ldots,n^2$. Note that adding $c$ to each entry of such a magic square yields another magic square with sum $M_n +cn$; this implies that any sum that is $M_n$ modulo $n$ works.

For $n=3$, it is easy to show that the sum must be 3 times the middle entry, and thus that the sum being $M_n$ modulo $n$ is both necessary and sufficient. But what about $n>3$?

$\endgroup$
2
  • $\begingroup$ Are you asking if there is an $n \times n$ magic square with sum $S$ that is not a multiple of $n$? $\endgroup$ Oct 31, 2016 at 10:13
  • $\begingroup$ I am asking whether there is an $n\times n$ magic square with sum $S$ for arbitrary $S$. $\endgroup$
    – dshin
    Oct 31, 2016 at 13:42

2 Answers 2

6
$\begingroup$

I don't know about the 4x4 case, but here are some things we can do for the 5x5 case.

Start with a typical 5x5 magic square (sum = 65):

\begin{array}{|c|c|c|c|c|} \hline 17 & 24 & 1 & 8 & 15\\ \hline 23 & 5 & 7 & 14 & 16 \\ \hline 4 & 6 & 13 & 20 & 22 \\ \hline 10 & 12 & 19 & 21 & 3 \\ \hline 11 & 18 & 25 & 2 & 9 \\ \hline \end{array}

Multiply all entries by 2 (sum = 130):

\begin{array}{|c|c|c|c|c|} \hline 34 & 48 & 2 & 16 & 30\\ \hline 46 & 10 & 14 & 28 & 32 \\ \hline 8 & 12 & 26 & 40 & 44 \\ \hline 20 & 24 & 38 & 42 & 6 \\ \hline 22 & 36 & 50 & 4 & 18 \\ \hline \end{array}

Add 1 to selected cells (sum = 131)

\begin{array}{|c|c|c|c|c|} \hline 34 & \color{red}{49} & 2 & 16 & 30\\ \hline \color{red}{47} & 10 & 14 & 28 & 32 \\ \hline 8 & 12 & \color{red}{27} & 40 & 44 \\ \hline 20 & 24 & 38 & 42 & \color{red}{7} \\ \hline 22 & 36 & 50 & \color{red}{5} & 18 \\ \hline \end{array}

OK, so this immediately shows that the sum need not be a multiple of n.

Obviously, I could have added 3 to those cells as well, so then the sum would be 133. I can't add 2, for then I would get duplicate entries. However, I can get a sum of 132 by adding 67 to these 5 cells in the original square. In fact, I could just stick to the original square and add any number greater than 25 to those 5 cells to get any sum of 90 or more. And by picking those 5 cells a little more carefully (or by choosing a different original 5x5 square), we can go even lower than that, though 65 is of course the minimum ... if we stick to positive numbers.

Assuming we are allowed to use negative numbers though, I can get any sum I want, since if the number I want is a multiple of 5, then add or subtract the appropriate number to each cell of the original magic square, and if what I want is not a multiple of 5, then multiply all entries by 5, and add or subtract the appropriate number to the 5 selected cells as we did above (we multiplied by 5 so as to ensure that we don't get duplicate entries when we add or subtract the number which is not a multiple of 5). E.g:

Wanted: sum = 10. OK, then take original square and subtract 11 from each entry:

\begin{array}{|c|c|c|c|c|} \hline 6 & 13 & -10 & -3 & 4\\ \hline 12 & -6 & -4 & 3 & 5 \\ \hline -7 & -5 & 2 & 9 & 11 \\ \hline -1 & 1 & 8 & 10 & -8 \\ \hline 0 & 7 & 14 & -9 & -2 \\ \hline \end{array}

Wanted: sum = 1. OK, then multiply all entries by 5 (sum = 325), and subtract 324 from the 5 selected cells:

\begin{array}{|c|c|c|c|c|} \hline 85 & -204 & 5 & 40 & 75\\ \hline -209 & 25 & 35 & 70 & 80 \\ \hline 20 & 30 & -259 & 100 & 110 \\ \hline 50 & 60 & 85 & 105 & -309 \\ \hline 55 & 90 & 125 & -314 & 45 \\ \hline \end{array}

OK, so this is just the 5x5 case, but it works for other n as well. For example, here is how you can pick 6 cells for a 6x6 to play with:

\begin{array}{|c|c|c|c|c|c|} \hline \color{red}{X} & X & X & X & X & X\\ \hline X & X & X & X & \color{red}{X} & X\\ \hline X & \color{red}{X} & X & X & X & X\\ \hline X & X & X & X & X & \color{red}{X}\\ \hline X & X & \color{red}{X} & X & X & X\\ \hline X & X & X & \color{red}{X} & X & X\\ \hline \end{array}

In fact, you can easily convince yourself that for any n>4 we can find these n cells for any nxn so that each row, column, and main diagonal has exactly one of those n cells.

Edit

OK, the 4x4 is also possible! (Thanks @RossMillikan !)

\begin{array}{|c|c|c|c|} \hline \color{red}{X} & X & X & X\\ \hline X & X & \color{red}{X} & X\\ \hline X & X & X & \color{red}{X}\\ \hline X & \color{red}{X} & X & X\\ \hline \end{array}

$\endgroup$
12
  • $\begingroup$ Very nice. This indeed generalizes to 4x4, and probably to all n>3. As long as you can prove the lemma that there exists an nxn magic square of sum 1 consisting of only 0 and 1 entries, your approach can generate all possible sums. $\endgroup$
    – dshin
    Oct 31, 2016 at 13:40
  • $\begingroup$ Oh, it does generalize to 4x4? Can you show me? $\endgroup$
    – Bram28
    Oct 31, 2016 at 13:51
  • $\begingroup$ @Bram28: I can't get a sum of $1$, but I can get a sum of $2$ with $$1001\\0110\\1001\\0110$$ so we can at least get all even numbers as sums in the $4 \times 4$ case. $\endgroup$ Oct 31, 2016 at 13:54
  • $\begingroup$ Are you uncertain how to demonstrate my lemma for n=4? Or are you uncertain how to utilize the lemma in the proof? $\endgroup$
    – dshin
    Oct 31, 2016 at 14:07
  • $\begingroup$ @RossMillikan Thanks! Do you think odd sums are impossible for n=4? $\endgroup$
    – Bram28
    Oct 31, 2016 at 14:27
2
$\begingroup$

Here is a general construction based on the examples given by Bram28 and Ross Millikan, and comments by dshin.

Revised claim: for any integer $S$, an $n$ by $n$ magic square with sum $S$ exists for all $n\ge 4$.

To see this, first notice that there are two transformations that preserve the property of being a magic square: adding an integer constant $c$ to each entry (which increases the sum by $cn$, as already observed in the question), and multiplying each entry by a non-zero integer constant $d$ (which multiplies the sum by $d$, as noted in Bram28's answer). Second, any set of $n$ squares in the $n$ by $n$ grid which has exactly one square in each row, column, and long diagonal, provides a set of locations which can be used to shift the sum of an $n$ by $n$ magic square. Let's call such an arrangement a template. Shifting the values in the locations determined by a template works as long as the values in the square differ from each other by a "large enough" value to avoid collisions with values used elsewhere in the magic square. We need to make this second observation more precise.

There are $n$ by $n$ magic squares for each $n \ge 3$. Hence to prove the claim, it is enough to construct a magic square for each $n \ge 4$ and to show how to modify it to obtain another magic square with the desired sum, based on a template.

To see that a template exists for $n=4$ or each odd integer $n \ge 5$, pick squares $(1,3),(2,2),(n,1)$ as well as the squares $(3,4),(4,5),\dots,(n-1,n)$ that are just off one of the long diagonals. For even $n\ge 6$, pick $(n,1),(n/2-1,n/2+1),(n/2,n/2)$, as well as $(1,2),(2,3),\dots,(n/2-2,n/2-1)$ and $(n/2+1,n/2+2),(n/2+2,n/2+3),\dots,(n-1,n)$. This choice of squares guarantees one square in each row and column, while the long diagonals are taken care of by $(2,2)$ or $(n/2,n/2)$ for the one diagonal and $(n,1)$ for the other, so it is a template. (This construction seems to be a version of dshin's suggestion.)

Now start with any magic square with values $1$ to $n^2$ as outlined in the question. There are two different constructions, depending on whether $S=0$ or $S\ne 0$.

First suppose $S=0$. If $n$ is odd, then subtract $(n^2+1)/2$ from each value. Otherwise $n$ is even, so multiply each value by $2$, and then subtract $n^2+1$.

Now suppose $S\ne 0$. In this case, first multiply each entry by $2n^2S \ne 0$. This intermediate magic square uses values $2n^2S, 4n^2S, 6n^2S, \dots, 2n^4S$; these all differ pairwise by at least $2n^2S$, and the square has sum $Sn^3(n^2+1)$. Subtract $Sn^2(n^2+1)$ from each entry in the magic square, giving a magic square with sum $0$. Now add $S$ to each of the entries that form a template. Since the template contains precisely one entry from each row, column, and long diagonal, this results in a final magic square with sum $S$.

(I have removed my earlier suggestion using solutions of the $n$ queens problem, since the above construction is simpler and more general.)

$\endgroup$
9
  • $\begingroup$ This almost works. But an N-queens solution does not have rows+columns+diagonals of equal sum. You can construct a square instead by, for $1 \leq i,j \leq n$, setting $A[i][j] = 1$ if $i+1 \equiv j$ mod $n$ and 0 else, and then choosing an appropriate pair $1 \leq a < b \leq n$ and setting $A[i][j] \rightarrow 1 - A[i][j]$ for $i,j \in \{a,b\}$. $\endgroup$
    – dshin
    Nov 4, 2016 at 0:09
  • $\begingroup$ You are right, my claim only works for $n$ queens solutions in which there are entries on both long diagonals. Will edit. $\endgroup$ Nov 4, 2016 at 6:42
  • $\begingroup$ Your template construction fails for all even $n>5$. My construction should work for all $n$. $\endgroup$
    – dshin
    Nov 4, 2016 at 16:48
  • $\begingroup$ I'm afraid I can't parse the "choosing..." part of your construction. $\endgroup$ Nov 4, 2016 at 22:12
  • $\begingroup$ I'm saying to just flip the 4 corners of a subrectangle. You need to choose the subrectangle well, based on whether n is even or odd. $\endgroup$
    – dshin
    Nov 4, 2016 at 22:14

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.