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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.