# 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.