Magic Squares

A Chinese legend tells the story of a flood by the Lo river. People offered sacrifices to appease the river. Each time a turtle emerged, walked around the sacrifice, and returned to the water. Fuh-Hi, the founder of Chinese civilization, interpreted this to mean that the river was still cranky. Fortunately, a child noticed that on its shell the turtle had the pattern on the left below, which is today called Lo Shu (“river scroll”).

The dots make the matrix on the right where the rows, columns, and diagonals add to $15$. Now that the people knew how much to sacrifice, the river’s anger cooled.

A square matrix is magic if each row, column, and diagonal adds to the same number, the matrix’s magic number.

Another magic square appears in the engraving Melencolia I by Dürer.

One interpretation is that it depicts melancholy, a depressed state. The figure, genius, has a wealth of fascinating things to explore including the compass, the geometrical solid, the scale, and the hourglass. But the figure is unmoved; all of the things lie unused. One of the potential delights, in the upper right, is a $4\times 4$ matrix whose rows, columns, and diagonals add to $34$.

The middle entries on the bottom row give $1514$, the date of the engraving.

The above two squares are arrangements of $1\dots n^2$. They are normal. The $1\times 1$ square whose sole entry is $1$ is normal, Exercise 2 shows that there is no normal $2\times 2$ magic square, and there are normal magic squares of every other size; see [Wikipedia, Magic Square]. Finding how many normal magic squares there are of each size is an unsolved problem; see [Online Encyclopedia of Integer Sequences].

If we don’t require that the squares be normal then we can say much more. Every $1\times 1$ square is magic, trivially. If the rows, columns, and diagonals of a $2\times 2$ matrix

$$\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)$$

add to $s$ then $a+b=s$, $c+d=s$, $a+c=s$, $b+d=s$, $a+d=s$, and $b+c=s$. Exercise 2 shows that this system has the unique solution $a=b=c=d=s/2$. So the set of $2\times 2$ magic squares is a one-dimensional subspace of ${\mathrm{ℳ}}_{2\times 2}$.

A sum of two same-sized magic squares is magic and a scalar multiple of a magic square is magic so the set of $n\times n$ magic squares ${\mathrm{ℳ}}_n$ is a vector space, a subspace of ${\mathrm{ℳ}}_{n\times n}$. This Topic shows that for $n\ge 3$ the dimension of ${\mathrm{ℳ}}_n$ is $n^2-n$. The set ${\mathrm{ℳ}}_{n,0}$ of $n\times n$ magic squares with magic number $0$ is another subspace and we will verify the formula for its dimension also: $n^2-2n-1$ when $n\ge 3$.

We will first prove that $\dim {\mathrm{ℳ}}_n=\dim {\mathrm{ℳ}}_{n,0}+1$. Define the trace of a matrix to be the sum down its upper-left to lower-right diagonal $\mathrm{Tr}(M)=m_{1,1}+\cdots +m_{n,n}$. Consider the restriction of the trace to the magic squares $\mathrm{Tr}:{\mathrm{ℳ}}_n\to \mathrm{ℝ}$. The null space $\mathrm{𝒩}(\mathrm{Tr})$ is the set of magic squares with magic number zero ${\mathrm{ℳ}}_{n,0}$. Observe that the trace is onto because for any $r$ in the codomain $\mathrm{ℝ}$ the $n\times n$ matrix whose entries are all $r/n$ is a magic square with magic number $r$. Theorem Two.II.2.14 says that for any linear map the dimension of the domain equals the dimension of the range space plus the dimension of the null space, the map’s rank plus its nullity. Here the domain is ${\mathrm{ℳ}}_n$, the range space is $\mathrm{ℝ}$ and the null space is ${\mathrm{ℳ}}_{n,0}$, so we have that $\dim {\mathrm{ℳ}}_n=1+\dim {\mathrm{ℳ}}_{n,0}$.

We will finish by finding the dimension of the vector space ${\mathrm{ℳ}}_{n,0}$. For $n=1$ the dimension is clearly $0$. Exercise 3 shows that $\dim {\mathrm{ℳ}}_{n,0}$ is also $0$ for $n=2$.

That leaves showing that $\dim {\mathrm{ℳ}}_{n,0}=n^2-2n-1$ for $n\ge 3$. The fact that the squares in this vector space are magic gives us a linear system of restrictions, and the fact that they have magic number zero makes this system homogeneous: for instance consider the $3\times 3$ case. The restriction that the rows, columns, and diagonals of

$$\left(\begin{array}{ccc}a& b& c\\ d& e& f\\ g& h& i\end{array}\right)$$

add to zero gives this $(2n+2)\times n^2$ linear system.

$$\begin{array}{rcrcrcrcrcrcrcrcrcr}a& +& b& +& c& & & & & & & & & & & & & =& 0\\ & & & & & & d& +& e& +& f& & & & & & & =& 0\\ & & & & & & & & & & & & g& +& h& +& i& =& 0\\ a& & & & & +& d& & & & & +& g& & & & & =& 0\\ & & b& & & & & +& e& & & & & +& h& & & =& 0\\ & & & & c& & & & & +& f& & & & & +& i& =& 0\\ a& & & & & & & +& e& & & & & & & +& i& =& 0\\ & & & & c& & & +& e& & & +& g& & & & & =& 0\end{array}$$

We will find the dimension of the space by finding the number of free variables in the linear system.

The matrix of coefficients for the particular cases of $n=3$ and $n=4$ are below, with the rows and columns numbered to help in reading the proof. With respect to the standard basis, each represents a linear map $h:{\mathrm{ℝ}}^{n^2}\to {\mathrm{ℝ}}^{2n+2}$. The domain has dimension $n^2$ so if we show that the rank of the matrix is $2n+1$ then we will have what we want, that the dimension of the null space ${\mathrm{ℳ}}_{n,0}$ is $n^2-(2n+1)$.

$$\begin{array}{rccccccccc}& 1& 2& 3& 4& 5& 6& 7& 8& 9\\ {\overrightarrow{\rho }}_1& 1& 1& 1& 0& 0& 0& 0& 0& 0\\ {\overrightarrow{\rho }}_2& 0& 0& 0& 1& 1& 1& 0& 0& 0\\ {\overrightarrow{\rho }}_3& 0& 0& 0& 0& 0& 0& 1& 1& 1\\ {\overrightarrow{\rho }}_4& 1& 0& 0& 1& 0& 0& 1& 0& 0\\ {\overrightarrow{\rho }}_5& 0& 1& 0& 0& 1& 0& 0& 1& 0\\ {\overrightarrow{\rho }}_6& 0& 0& 1& 0& 0& 1& 0& 0& 1\\ {\overrightarrow{\rho }}_7& 1& 0& 0& 0& 1& 0& 0& 0& 1\\ {\overrightarrow{\rho }}_8& 0& 0& 1& 0& 1& 0& 1& 0& 0\end{array}$$

$$\begin{array}{rcccccccccccccccc}& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16\\ {\overrightarrow{\rho }}_1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ {\overrightarrow{\rho }}_2& 0& 0& 0& 0& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ {\overrightarrow{\rho }}_3& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 0& 0& 0& 0\\ {\overrightarrow{\rho }}_4& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1\\ {\overrightarrow{\rho }}_5& 1& 0& 0& 0& 1& 0& 0& 0& 1& 0& 0& 0& 1& 0& 0& 0\\ {\overrightarrow{\rho }}_6& 0& 1& 0& 0& 0& 1& 0& 0& 0& 1& 0& 0& 0& 1& 0& 0\\ {\overrightarrow{\rho }}_7& 0& 0& 1& 0& 0& 0& 1& 0& 0& 0& 1& 0& 0& 0& 1& 0\\ {\overrightarrow{\rho }}_8& 0& 0& 0& 1& 0& 0& 0& 1& 0& 0& 0& 1& 0& 0& 0& 1\\ {\overrightarrow{\rho }}_9& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1\\ {\overrightarrow{\rho }}_{10}& 0& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 1& 0& 0& 0\end{array}$$

We want to show that the rank of the matrix of coefficients, the number of rows in a maximal linearly independent set, is $2n+1$. The first $n$ rows of the matrix of coefficients add to the same vector as the second $n$ rows, the vector of all ones. So a maximal linearly independent must omit at least one row. We will show that the set of all rows but the first $\{{\overrightarrow{\rho }}_2\dots {\overrightarrow{\rho }}_{2n+2}\}$ is linearly independent. So consider this linear relationship.

$$\begin{array}{cc}{c}_2{\overrightarrow{\rho }}_2+\cdots +c_{2n}{\overrightarrow{\rho }}_{2n}+c_{2n+1}{\overrightarrow{\rho }}_{2n+1}+c_{2n+2}{\overrightarrow{\rho }}_{2n+2}=\overrightarrow{0}& \text{(}\ast \text{)}\end{array}$$

Now it gets messy. Focus on the lower left of the tables. Observe that in the final two rows, in the first $n$ columns, is a subrow that is all zeros except that it starts with a one in column $1$ and a subrow that is all zeros except that it ends with a one in column $n$.

First, with ${\overrightarrow{\rho }}_1$ omitted, both column $1$ and column $n$ contain only two ones. Since the only rows in ($\ast$) with nonzero column $1$ entries are rows ${\overrightarrow{\rho }}_{n+1}$ and ${\overrightarrow{\rho }}_{2n+1}$, which have ones, we must have $c_{2n+1}=-c_{n+1}$. Likewise considering the $n$-th entries of the vectors in ($\ast$) gives that $c_{2n+2}=-c_{2n}$.

Next consider the columns between those two— in the $n=3$ table this includes only column $2$ while in the $n=4$ table it includes both columns $2$ and $3$. Each such column has a single one. That is, for each column index $j\in \{2\dots n-2\}$ the column consists of only zeros except for a one in row $n+j$, and hence $c_{n+j}=0$.

On to the next block of columns, from $n+1$ through $2n$. Column $n+1$ has only two ones (because $n\ge 3$ the ones in the last two rows do not fall in the first column of this block). Thus $c_2=-c_{n+1}$ and therefore $c_2=c_{2n+1}$. Likewise, from column $2n$ we conclude that $c_2=-c_{2n}$ and so $c_2=c_{2n+2}$.

Because $n\ge 3$ there is at least one column between column $n+1$ and column $2n-1$. In at least one of those columns a one appears in ${\overrightarrow{\rho }}_{2n+1}$. If a one also appears in that column in ${\overrightarrow{\rho }}_{2n+2}$ then we have $c_2=-(c_{2n+1}+c_{2n+2})$ since $c_{n+j}=0$ for $j\in \{2\dots n-2\}$. If a one does not appear in that column in ${\overrightarrow{\rho }}_{2n+2}$ then we have $c_2=-c_{2n+1}$. In either case $c_2=0$, and thus $c_{2n+1}=c_{2n+2}=0$ and $c_{n+1}=c_{2n}=0$.

If the next block of $n$-many columns is not the last then similarly conclude from its first column that $c_3=c_{n+1}=0$.

Keep this up until we reach the last block of columns, those numbered $(n-1)n+1$ through $n^2$. Because $c_{n+1}=\cdots =c_{2n}=0$ column $n^2$ gives that $c_n=-c_{2n+1}=0$.

Therefore the rank of the matrix is $2n+1$, as required.

The classic source on normal magic squares is [Ball & Coxeter]. More on the Lo Shu square is at [Wikipedia, Lo Shu Square]. The proof given here began with [Ward].

References cited in this section