The magic squares are a space

A magic square is a grid of numbers whose rows, columns and two main diagonals all add to the same total. The oldest on record is the Lo Shu of Chinese legend, the digits one to nine with every line adding to fifteen; Albrecht Dürer engraved one of order four into Melencolia I in 1514; and for centuries the subject was a matter of construction recipes and counting by hand. The recipes were never short of ingenuity, and they hid the plainest fact about the objects: the conditions are linear. A line adding to a given number is a linear equation in the entries, and the set of solutions to linear equations is a space. It is the same change of viewpoint that the boards on which every light goes out made for a puzzle of switches, where an arrangement game turned into a system of equations and the question of which boards can be cleared turned into a question about one matrix.

What a map throws away set out the bookkeeping that governs such spaces, and a hole is a cycle that bounds nothing used it to count the holes in a shape by subtracting one rank from another: a linear map from one space to another loses exactly as many dimensions as its kernel has, and keeps the rest. Applied to magic squares, that bookkeeping turns a subject of recipes into one of dimensions. It says how much freedom there is in a magic square of each order, why the centre of every three-by-three square is forced, and why the eight classical squares of order three are one square seen eight ways. And applied to the squares themselves as matrices, it finds something the recipes never noticed: two thirds of the squares of order four are singular, and the reason sits in where the numbers that add to seventeen are placed.

Eight lines, nine cells, three degrees of freedom #

Take an arbitrary three-by-three array of real numbers and ask for its eight lines — three rows, three columns, two diagonals — to share a common sum $s$. There are ten unknowns, the nine entries and $s$, and eight equations, each saying that one line minus $s$ is nought. The equations are not independent: the three rows together add up to the whole grid, and so do the three columns, so once five of the six are satisfied the sixth follows. That one redundancy is a small instance of the fact in counted across and counted down, that a table’s independent rows and independent columns always come to the same number: here the row conditions and the column conditions share one consequence, the total, and it can be counted only once. Seven independent conditions on ten unknowns leave a space of dimension three.

A basis for it can be written down. Let $J$ be the square of all ones, whose every line adds to three, and let $U$ and $V$ be two squares made of 1, 0 and −1 whose every line adds to nought. Then every magic square of order three is $cJ + uU + vV$ for exactly one triple of numbers $(c, u, v)$, and every such combination is magic.

The Lo Shu is the point $(5, -3, 1)$. Two things can be read off the basis at once. The common sum is $3c$, since $U$ and $V$ contribute nothing to any line. And the centre cell is $c$, since both $U$ and $V$ have nought in the middle. So in any magic square of order three, whatever its entries, the centre is exactly one third of the line sum. No search and no ingenuity is needed for that; it is a fact about a three-dimensional space and the two coordinates that vanish at one cell.

One square of order three, seen eight ways #

A normal magic square uses the numbers $1, 2, \ldots, n^2$ once each. For order three the nine numbers add to 45, so each row adds to 15, and the centre is 5. In coordinates the square is $5J + uU + vV$, and writing out its cells gives the centre 5 surrounded by the eight numbers $5 \pm u$, $5 \pm v$, $5 \pm (u + v)$ and $5 \pm (u - v)$. These must be exactly 1, 2, 3, 4, 6, 7, 8 and 9 — that is, $5 \pm 1$, $5 \pm 2$, $5 \pm 3$ and $5 \pm 4$ — so the four numbers $|u|$, $|v|$, $|u + v|$ and $|u - v|$ must be 1, 2, 3 and 4 in some order.

That leaves very little room. If $|u|$ and $|v|$ were 1 and 2 the sum and difference would be 1 and 3, repeating a 1; 1 and 4 give 3 and 5; 2 and 3 give 1 and 5; and so on. Only $\{|u|, |v|\} = \{1, 3\}$ works, giving sum and difference 2 and 4. With signs and the choice of which is which, there are exactly eight points: $(u, v) = (\pm 3, \pm 1)$ and $(\pm 1, \pm 3)$.

Trying every one of the 362,880 arrangements of the nine digits finds exactly those eight squares, and each is the Lo Shu turned or reflected — the eight symmetries of a square are the eight sign-and-swap choices of $(u, v)$. The figure also shows the classical argument for the centre, which needs no coordinates: the middle row, the middle column and the two diagonals add to $4 \times 15 = 60$, and between them they cover every cell once and the centre three more times, so $60 = 45 + 3 \times \text{centre}$. The space of squares and the counting argument say the same thing; the space says more, because it also lists every square there is.

What each set of lines costs #

The same count works for any order. An $n \times n$ array with a common sum has $n^2 + 1$ unknowns. The $2n$ conditions on rows and columns have one redundancy — rows and columns both add up to the whole grid — and so cost $2n - 1$ dimensions. The two diagonals cost one each. That leaves $n^2 + 1 - (2n - 1) - 2 = n^2 - 2n$ dimensions of magic squares, for every $n \geq 3$, and $(n - 1)^2 + 1$ for the semi-magic squares that ask only for rows and columns.

The computed ranks agree at every order from three to eight: 3, 8, 15, 24, 35 and 48 dimensions of magic squares, two more each time for the semi-magic ones. The third set of bars asks for pandiagonal squares, in which every broken diagonal — a diagonal that wraps round the edge of the grid — also has the common sum. Those conditions overlap more, and they cost fewer dimensions than they add lines. At order three they leave only the constant squares, a space of dimension one, which is why no normal pandiagonal square of order three exists. At order four they leave five.

None of this says how many normal squares there are. The normal squares are the points of the space whose entries are a rearrangement of $1, \ldots, n^2$ — whole-number points of a particular kind in an eight-dimensional space for order four — and counting those is not linear algebra. It is a search.

Eight hundred and eighty, by search #

A search through the grid cell by cell, filling each row and letting the last entry of every row and column be forced by the sum 34, finds 7,040 normal magic squares of order four. The eight symmetries of the square divide them into classes of eight, leaving 880 essentially different squares. Bernard Frénicle de Bessy listed all 880 by hand and published the list in 1693, which makes it one of the oldest exhaustive enumerations in mathematics, and the search confirms it exactly.

Beyond order four the counting runs out quickly. Richard Schroeppel counted the squares of order five by computer in 1973: 275,305,224 up to symmetry. The squares of order six have never been counted. Klaus Pinn and Christian Wieczerkowski estimated the number in 1998 by statistical sampling at about $1.8 \times 10^{19}$, and no count has replaced the estimate. The space of squares of order six has dimension 24, which is small; the trouble is purely the arithmetic condition that the entries be a rearrangement of 1 to 36.

Twelve ways to place the pairs that make seventeen #

In a normal square of order four the numbers fall into eight pairs adding to 17: 1 and 16, 2 and 15, and so on down to 8 and 9. Henry Dudeney sorted Frénicle’s 880 squares in 1910 by where these pairs sit, drawing each square as a pattern of lines joining partners, and found twelve patterns. The search finds the same twelve and counts each: one pattern holds 304 squares, two hold 96, four hold 56, three hold 48, and two hold 8.

Dudeney’s interest was in the patterns as a classification — a way of knowing that the list was complete and of finding the squares with extra properties. One group of 48 is the pandiagonal squares, the ones whose broken diagonals also add to 34. Another group of 48 is the squares symmetric about their centre, in which any two cells opposite each other through the middle add to 17. But the patterns turn out to classify something Dudeney did not ask about, and that only appears once the square is treated as a matrix.

Two squares in three are singular #

A square of numbers is a matrix, and a matrix has a determinant, the factor by which it scales volumes. Every magic square has one obvious eigenvector: multiplying it by the column of all ones adds up each row, and every row adds to 34, so the all-ones vector is stretched by exactly 34. Nothing about magic forces the determinant to be nought, and nothing forces it to be large either; the biggest box built from signs asked how large a determinant can be when every entry is plus or minus one, a question about squares that are as far from singular as possible. And yet, computed exactly over the integers, 640 of the 880 squares of order four have determinant nought and rank three, and only 240 are invertible.

The split is not scattered. Within each of Dudeney’s twelve patterns, either every square is singular or none is: eight patterns are singular to the last square and four are invertible to the last. And the eight singular patterns have something in common that the search can name. In every one of the 640 singular squares, a single symmetry of the grid’s rows and columns carries every number to its partner — the pairs are mirrored across the middle of every row or column, or swapped with a neighbour, or set two places apart, or placed by one of these in both directions at once, which for the mirror means opposite through the centre. In none of the 240 invertible squares does any such symmetry place the pairs.

Half of this is a proof that fits in a paragraph. Suppose the pairs are mirrored within every column, so that row 1 plus row 4 is a row of seventeens and row 2 plus row 3 is too. Then row 1 + row 4 − row 2 − row 3 is a row of noughts: the combination $(1, -1, -1, 1)$ of the rows vanishes, the rows are dependent and the determinant is nought. The neighbour swap gives $(1, 1, -1, -1)$ in the same way, and the swap by two gives $(1, -1, 1, -1)$. When the symmetry acts on rows and columns at once the argument is subtler. The square then carries the two-dimensional space of vectors that the column symmetry reverses into a one-dimensional space of vectors that the row symmetry fixes and whose entries add to nought — and a linear map from a plane onto a line must send some vector in the plane to nought. Each kind of symmetry forces a kernel; that is the half the paragraph proves. The other half, that among the 880 no invertible square has its pairs placed by such a symmetry, is what the search found and no paragraph here proves.

Dürer’s parabolas #

Dürer’s square is one of the 48 symmetric about their centre: 16 sits opposite 1, 3 opposite 14, and so on. So it is singular, and its kernel can be computed exactly. It is the vector $(-1, 3, -3, 1)$, and that vector has a meaning of its own. Applied to four equally spaced values, it computes their third difference, which is nought exactly when the four values lie on a single parabola.

So every row of Dürer’s square, read left to right, lies on a parabola: 16, 3, 2, 13 has differences −13, −1, 11 and second differences 12, 12, and the other three rows behave the same way. It is unlikely Dürer intended it. He arranged the square so that the year of the engraving appeared in the bottom row and the corners, the centre four and many other groups of four added to 34; the parabolas are a consequence of the central symmetry he also built in, by way of a determinant he never computed. The same holds for every one of the 48 centrally symmetric squares, each with a kernel vector of the form $(a, b, -b, -a)$, though the parabola is special to the vectors whose entries are proportional to $(1, -3, 3, -1)$.

Euler’s route through Latin squares #

There is another way to manufacture magic squares, and it connects them to a much harder problem. A Latin square of order $n$ has each of $n$ symbols once in every row and column; two Latin squares are orthogonal if, laid over each other, every ordered pair of symbols occurs exactly once. The thirty-six officers is the story of Euler’s search for two orthogonal Latin squares of order six, which do not exist. Euler’s interest in them came partly through magic squares: if $A$ and $B$ are orthogonal Latin squares on the symbols $0, \ldots, n - 1$, then $nA + B + 1$ uses every number from 1 to $n^2$ exactly once, and each of its rows and columns adds to $n(n^2 + 1)/2$, because each row contains every value of $A$ once and every value of $B$ once. If both Latin squares also have every symbol once on each diagonal, the result is a normal magic square. The supply is limited by the same scarcity that nine thousand four hundred and eight measured for the Latin squares themselves, which are known exactly for only eleven orders.

In the language of this page, orthogonal Latin squares are a supply of whole-number points in the space of magic squares with exactly the right entries. The space itself is easy; the rows and columns cost $2n - 1$ dimensions whatever the order. What is hard is the arithmetic, and the same arithmetic that makes order six resist counting made it resist Euler’s construction.

What the pictures cannot show #

The dimensions are exact: each is a number of unknowns minus a rank computed in whole numbers, and the formula $n^2 - 2n$ is proved by the counting argument above, so the figure confirms it rather than establishing it. The enumeration of order four is exact too, and it agrees with Frénicle and with Dudeney. What the figures cannot show is any reason why the invertible squares never have a symmetric pairing. The singular half of the correspondence is proved here; the other half — that a square with no such symmetry always has nonzero determinant — is a fact about 240 particular squares, checked one at a time, and it is not clear that it says anything beyond order four.

Nor do the figures show the space of order four itself. It has eight dimensions, and the 880 squares are scattered through it in a way no plane picture can convey. The pattern figure and the rank figure sort the squares by properties that can be read off a single square; neither shows how the squares sit relative to each other in the space, which is where questions about counting them at larger orders actually live.

Still open: how many of order six #

The number of normal magic squares of order six is not known. Every method that counted the smaller orders — Frénicle’s hand listing, Schroeppel’s computer search, the recursive constructions that followed — becomes infeasible: the estimate of about $1.8 \times 10^{19}$ squares up to symmetry is far beyond what a search can visit, and no formula, generating function or structural decomposition of the kind that sometimes counts what a search cannot has been found. The estimates come from Monte Carlo methods that wander through the space of arrangements weighting each by how nearly magic it is, and they carry a statistical error rather than a proof.

The linear algebra is no obstacle at order six. The space of magic squares has dimension 24, its basis is easy to write down, and the conditions that cut it out are as simple as at order three. The difficulty is entirely in asking which points of that space have entries that are a rearrangement of 1 to 36 — a question about whole numbers inside a space, the same kind of question that makes the space of order three hold exactly eight normal squares, and that at order six nobody can yet answer.