# Are magic squares inevitable?

Consider: If we are given a reasonably well-behaved statistical population of real numbers, then samples that are not small will have mean approximately equal to that of the population, right? Then: let n be a large positive integer, and choose n positive integers at random, without replacement, from among the integers from 1 to n squared. Do this a total of n times. (The n squared numbers are depleted at the end of this process, no two selections containing common members.) Let these be the rows of a matrix. The all the rows, columns, and the two diagonals constitute a random sample of size n, and will have mean approximately that of the mean of the integers from 1 to n squared. Therefore this matrix, generated so easily, is already nearly a magic square. It is plausible that all it needs is some tweaking (swapping a few entries here and there) to be exactly a perfect square. Thus, magic squares are, contrary to one’s naïve initial reaction, inevitable, and, indeed, abundant, rather than unlikely or rare. The only surprise is that non-trivial magic squares of very low order exit.

So, here is my first question: In all that I have ever seen about magic squares, this statistical perspective has never been given. But perhaps there is mention that I simply haven’t noticed. That is why I made one of the tags for this question “reference-request”. If I’ve overlooked it, please tell me.

My main question is this: Is it indeed the case that, contrary to first blush, one can plausibly assert, in light of the statistical argument given above, without the need of exhibiting any magic square at all, that magic squares are inevitable and exist in abundance?

-
How does your consideration jive with the fact that there are no $2\times 2$ magic squares? – Willie Wong Jun 28 '11 at 1:43
The statistical argument suggests that tweaking will give a square with integer entries which is nearly magic; perhaps the row and column sums will be off by $1$ or $2$. I don't see how it necessarily says anything about whether tweaking will give a square which is exactly magic. For example, if I randomly choose $3$ numbers which sum to $10$, then round, I might get integers which are close to equal. But it is impossible for me to tweak them to be exactly equal. – Qiaochu Yuan Jun 28 '11 at 4:39
I want to thank everyone for their sobering comments and answers. – Mike Jones Jun 28 '11 at 23:42

There are 362,880 ways to put the 9 digits into a $3\times3$ array. Of these, exactly 8 are magic squares. They are about as abundant as needles in haystacks. It gets worse for larger sizes.

-
You're talking about relative abundance, whereas I had in mind absolute abundance. Nonetheless, you make a good point, and I think your answer is the most relevant/spot-on/sobering of those given, and so am up-voting it and accepting it. – Mike Jones Jun 28 '11 at 23:44

This kind of reasoning leads to false results. For instance, to construct a projective plane of a given order $N$, take $N^2+N+1$ points and $N^2+N+1$ lines, randomly choose $(N+1)(N^2+N+1)$ pairs $(l,p)$ of lines and points and say that $p$ lies on $l$ iff $(l,p)$ is one of the chosen pairs. Then each line will on average have $N+1$ points on it, and each point will on average lie on $N+1$ lines, so it is plausible that all it needs is some tweaking (moving a few points to different lines here and there) to get a projective plane. In fact, however, it is known that there are orders for which there are no projective planes. The fact that the constraints are fulfilled in the mean says little about whether it's possible to fulfill them all exactly.

-
Flase results? No surprise there, as this is only a heuristic. But I appreciate the specific example you give, and so am up-voting your answer. – Mike Jones Jun 28 '11 at 23:40

One problem with your argument is that rows are not independent of columns or diagonals. Another is that the usual definition of magic square requires all elements distinct.

-
I think the OP's claim (not my claim, just my interpretation) is that "Each $N\times N$ matrix is easily associated to an $N^2$-tuple. So start with $1\ldots N^2$ and take an arbitrary permutation of it, and fill the square based on that." Using some hand-waving argument about the mean, it is then asserted that "a significant portion of all possible permutations should lead to almost-magic squares, which can conceivably be modified into a magic square." – Willie Wong Jun 28 '11 at 1:42
(Of course, the above comment is only about your second sentence. Your first is very much to the point.) – Willie Wong Jun 28 '11 at 1:46
@Willie: That was also my first reaction to Robert's answer, but the question does in fact say "choose n positive integers at random, without replacement, from among the integers from 1 to n squared. Do this a total of n times." Taken literally, that doesn't ensure that all the entries are distinct. – joriki Jun 28 '11 at 1:49
@joriki Actually "without replacement" does ensure distinct integers. That reduces to arbitrary permutations of all $n^2$ elements. – trutheality Jun 28 '11 at 2:05
@trutheality: I guess it depends on how you interpret "this". Without context, I would have thought it means that exactly the same thing is done $n$ times, i.e. each of the $n$ draws of $n$ integers starts from scratch; but I guess knowing that the result is supposed to be a magic square, one could interpret it such that "without replacement" applies across the $n$ repetitions of the process, not just within each repetition. – joriki Jun 28 '11 at 4:41