# Find basis vectors of the vector space of all $4 \times 4$ magic squares

I'm taking a course in linear algebra and I need to solve this problem:

Let's define a magic square as a matrix whose sums of all the numbers on a line, a column and on both the main diagonal and the main anti-diagonal are the same.

1. Prove that $$4 \times 4$$ magic squares form a vector space.

2. Find the basis vectors of this vector space.

There are more questions in the exercise, but I guess these are the most important ones that it will help me solve other questions.

I have already searched almost the whole Internet, but I'm not able to find the answer. Thank you!

(Edit: I'm not sure if I read the OP correctly, but to my understanding, except the sums of entries along the main diagonal or main anti-diagonal, all line sums along other diagonals are not part of the definition.)

Denote by $r_i$ the $i$-th row sum, $c_j$ the $j$-th column sum, $d$ the diagonal sum and $a$ the anti-diagonal sum. Every so-called "magic square" in question must satisfy the following 9 constraints: $$r_1=d,\ r_2=d,\ r_3=d,\ r_4=d,\ c_1=d,\ c_2=d,\ c_3=d,\ c_4=d,\ a=d.$$ (I say "so-called" in the above because the definition here deviates from the conventional one --- here, a magic square can have non-integer or even negative entries.)

Clearly the constraint $c_4=d$ is redundant, because the sum of all row sums must be equal to the sum of all column sums. Since a $4\times4$ matrix is specified by 16 entries, you now have 16 unknowns and at most 8 independent constraints. This suggests that the dimension of the vector space in question is at least 16-8=8.

So, to prove that the dimension of the vector space in question is exactly 8, you only need to show that the remaining 8 constraints are indeed linearly independent. This amounts to proving that some $8\times16$ matrix has full row rank. It takes some work but it shouldn't be hard.

Having proven that the dimension is 8, it is not hard to find a basis. All you need is to construct a magic square with nonzero row/column/diagonal/anti-diagonal sums and 7 magic squares with zero row/column/diagonal/anti-diagonal sums. This is easy: \begin{align*} &\pmatrix{1&1&1&1\\ 1&1&1&1\\ 1&1&1&1\\ 1&1&1&1}, \ \pmatrix{1&0&0&-1\\ 0&-1&1&0\\ 0&1&-1&0\\ -1&0&0&1},\\ &\pmatrix{1&-1&0&0\\ -1&1&0&0\\ 0&0&-1&1\\ 0&0&1&-1}, \ \pmatrix{1&0&-1&0\\ 0&-1&0&1\\ -1&0&1&0\\ 0&1&0&-1},\\ &\pmatrix{0&0&-1&1\\ 0&0&1&-1\\ 1&-1&0&0\\ -1&1&0&0}, \ \pmatrix{0&-1&0&1\\ 1&0&-1&0\\ 0&1&0&-1\\ -1&0&1&0},\\ &\pmatrix{0&1&-1&0\\ 0&0&0&0\\ 0&0&0&0\\ 0&-1&1&0}, \ \pmatrix{0&0&0&0\\ 1&0&0&-1\\ -1&0&0&1\\ 0&0&0&0}. \end{align*}

By looking at the diagonals and anti-diagonals of their linear combinations, it should be rather obvious that these 8 magic squares are indeed linearly independent.

• @PeterFranek Why 16-7? Would you please list those 7 constraints? – user1551 Oct 27 '16 at 10:08
• Ah, sorry, I was confused: you also want the anti-diagonal sum to be equal, althouth I didn't understand this from the OP. – Peter Franek Oct 27 '16 at 10:10
• @PeterFranek Well, the OP says "on a diagonal", so I guess the definition involves more than one diagonals. But I may be wrong. – user1551 Oct 27 '16 at 10:14
• Yes, you are correct, only the sums on both main diagonal and main anti-diagonal are the same. I edited the question. – Juice Oct 27 '16 at 14:38

Here's another basis, with an easy proof of linear independence: the entry marked with a star is the only nonzero entry in that location in any of the eight matrices. $$\pmatrix{1*&0&0&0\cr0&0&0&1\cr0&1&0&0\cr0&0&1&0\cr}\quad\pmatrix{0&1*&0&0\cr0&0&0&1\cr0&0&1&0\cr1&0&0&0\cr}\quad\pmatrix{0&0&1*&0\cr0&0&0&1\cr0&0&1&0\cr1&1&-1&0\cr}\quad\pmatrix{0&0&0&1*\cr0&0&0&1\cr0&-1&2&0\cr1&2&-1&-1\cr}\quad\pmatrix{0&0&0&0\cr1*&0&0&-1\cr0&1&-1&0\cr-1&-1&1&1\cr}\quad\pmatrix{0&0&0&0\cr0&1*&0&-1\cr0&0&-1&1\cr0&-1&1&0\cr}\quad\pmatrix{0&0&0&0\cr0&0&1*&-1\cr0&-1&0&1\cr0&1&-1&0\cr}\quad\pmatrix{0&0&0&0\cr0&0&0&0\cr1*&1&-1&-1\cr-1&-1&1&1\cr}$$

A similar approach is taken in Ward, Vector spaces of magic squares, Math Mag 53 (1980) 108-111.

I'll approach this question from the wider context of finding bases for vector spaces of $$4\times4$$ squares of various kinds of magic.

First, following user1551, let's have $$\mathbf{b}_0=\begin{bmatrix} 1&1&1&1\\1&1&1&1\\1&1&1&1\\1&1&1&1 \end{bmatrix}$$ so that we can easily shift a magic square up or down to make its lowest element what we want. (Or to put a desired value in the top left corner; all my other basis vectors have 0 there.)

Next, I add Grogono's four carpets which are collectively a basis for the 4-dimensional vector space of anchored compact complete $$4\times4$$ magic squares. (Anchored means that the top left element is 0.) With $$\mathbf{b}_0$$, we have a basis for the 5-dimensional vector space of compact complete ones (including unanchored).

$$\mathbf{b}_1=\begin{bmatrix} 0&0&1&1\\1&1&0&0\\0&0&1&1\\1&1&0&0 \end{bmatrix}$$, $$\mathbf{b}_2=\begin{bmatrix} 0&1&0&1\\0&1&0&1\\1&0&1&0\\1&0&1&0 \end{bmatrix}$$, $$\mathbf{b}_3=\begin{bmatrix} 0&1&1&0\\1&0&0&1\\0&1&1&0\\1&0&0&1 \end{bmatrix}$$, $$\mathbf{b}_4=\begin{bmatrix} 0&1&0&1\\1&0&1&0\\1&0&1&0\\0&1&0&1 \end{bmatrix}$$.

With most of my later basis vectors, the point of adding the vector to the basis is to extend the vector space to include squares which lack a certain magic property possessed by every square which is in the vector space so far. These magic properties are illustrated below. Let

$$D=\begin{bmatrix} a&b&c&d\\b&a&d&c\\c&d&a&b\\d&c&b&a \end{bmatrix}$$, $$Q=\begin{bmatrix} a&a&b&b\\a&a&b&b\\d&d&c&c\\d&d&c&c \end{bmatrix}$$, $$M=\begin{bmatrix} a&b&b&a\\d&c&c&d\\d&c&c&d\\a&b&b&a \end{bmatrix}$$, $$T=\begin{bmatrix} a&b&a&b\\d&c&d&c\\a&b&a&b\\d&c&d&c \end{bmatrix}$$.

Say a $$4\times4$$ square $$S$$ is '$$D$$-magic' if, for each of the symbols $$a, b, c$$ and $$d$$, the sum of $$S$$'s entries in the four locations containing that symbol in $$D$$ is $$S$$'s magic sum. And similarly for $$Q, M$$ and $$T$$. And say a $$4\times4$$ square is '$$R$$-magic' if each row is magic, and '$$C$$-magic' if each column is magic.

Then $$RCD$$-magic squares are magic squares with the additional property that broken diagonals that break 2 and 2 are magic. The vector space of them has 7 dimensions: 2 more. The following two squares will serve to extend the basis:

$$\mathbf{b}_5=\begin{bmatrix} 0&0&1&1\\1&1&0&0\\1&1&0&0\\0&0&1&1 \end{bmatrix}$$, $$\mathbf{b}_6=\begin{bmatrix} 0&1&1&0\\0&1&1&0\\1&0&0&1\\1&0&0&1 \end{bmatrix}$$.

Next comes the OP's vector space: $$4\times4$$ magic squares. This has 8 dimensions: 1 more. $$\mathbf{m}=\begin{bmatrix} 0&0&1&1\\0&1&0&1\\1&0&1&0\\1&1&0&0 \end{bmatrix}$$ can extend the basis. Incidentally, every $$4\times4$$ magic square is $$M$$-magic.

Return to the 7-dimensional vector space of $$4\times4$$ $$RCD$$-magic squares. $$RCD$$-magic squares are also $$QMT$$-magic. If $$DT$$-magic is dropped, the vector space now has 8 dimensions; we may extend the basis with $$\mathbf{b}_7=\begin{bmatrix} 0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0 \end{bmatrix}$$. If $$Q$$-magic is dropped, the vector space now has 9 dimensions; we may extend the basis with $$\mathbf{b}_8=\begin{bmatrix} 0&0&1&1\\0&0&1&1\\1&1&0&0\\1&1&0&0 \end{bmatrix}$$. If $$M$$-magic is dropped, the vector space now has 10 dimensions; we may extend the basis with $$\mathbf{b}_7=\begin{bmatrix} 0&1&1&0\\1&0&0&1\\1&0&0&1\\0&1&1&0 \end{bmatrix}$$.

To summarise,

• compact $$4\times4$$ magic squares are the 5-dimensional vector space $$\langle \mathbf{b}_0,\dots,\mathbf{b}_4\rangle$$

• $$4\times4$$ $$RCD$$-magic squares are also $$QMT$$-magic, and are the 7-dimensional vector space $$\langle \mathbf{b}_0,\dots,\mathbf{b}_6\rangle$$

• $$4\times4$$ magic squares are the 8-dimensional vector space $$\langle \mathbf{b}_0,\dots,\mathbf{b}_6, \mathbf{m}\rangle$$

• $$4\times4$$ $$RCQM$$-magic squares are the 8-dimensional vector space $$\langle \mathbf{b}_0,\dots,\mathbf{b}_7\rangle$$

• $$4\times4$$ $$RCM$$-magic squares are the 9-dimensional vector space $$\langle \mathbf{b}_0,\dots,\mathbf{b}_8\rangle$$

• $$4\times4$$ $$RC$$-magic squares (i.e. semi-magic squares) are the 10-dimensional vector space $$\langle \mathbf{b}_0,\dots,\mathbf{b}_9\rangle$$