Why do siamese magic squares have real eigenvalues, symmetric around zero?
There is a standard method to construct magic squares of odd size, known as the Siamese construction. I'll write $S_m$ for the $m \times m$ Siamese square. For example, here is $S_5$.
17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9
As you can see, this matrix certainly isn't symmetric! It has one obvious eigenvector, the all ones vector, whose corresponding eigenvalue is $\frac{m^3+m}{2}$, and there is no obvious reason its other eigenvalues should have nice structure. Nonetheless, experimentation suggests:
(1) All eigenvalues of $S_m$ are real.
(2) If $\lambda$ is an eigenvalue of $S_m$ other than $\frac{m^3+m}{2}$, then $-\lambda$ is as well.
Can anyone explain why?
Remark In case anyone is curious how I found this, I am teaching myself MATLAB and came up with the task of listing characteristic polynomials of magic squares as a more or less random task which would involve learning some basic control structures and some mathematical tools. This piece of MATLAB documentation describes some alternate ways of thinking about the Siamese construction, which may be relevant.
Solution 1:
Partial answer (explaining but not proving why the non-trivial eigenvalues come in pairs with opposite signs).
It should not be too hard to prove that construction yields a matrix with the property that rotating it by 180 degrees gives "an entrywise complementary magic square", i.e. the sum of $A=S_m$ and its rotated copy $\tilde{A}$ is the matrix with all entries equal to $m^2+1$.
In other words $$ A_{i,j}=m^2+1-A_{m+1-i,m+1-j} $$ for all $i,j$. Let $B=(A-\tilde{A})/2$. It follows that the row and column sums of $B$ are all zero, and that $$B_{i,j}=-B_{m+1-i,m+1-j}\qquad(*)$$ for all $i,j$. When $m=5$ we have $$ B=\left( \begin{array}{ccccc} 4 & 11 & -12 & -5 & 2 \\ 10 & -8 & -6 & 1 & 3 \\ -9 & -7 & 0 & 7 & 9 \\ -3 & -1 & 6 & 8 & -10 \\ -2 & 5 & 12 & -11 & -4 \\ \end{array} \right). $$
If $u=(x_1,\ldots,x_m)$ is an eigenvector of $B$ belonging to eigenvalue $\lambda$, then it is easy to show that $\tilde{u}=(x_m,x_{m-1},\ldots,x_1)$ is an eigenvector of $B$ belonging to eigenvalue $-\lambda$. Namely the assumption is that for all $i$ we have $$ \sum_j B_{i,j}x_j=\lambda x_i. $$ Taking $(*)$ into account this implies that $$ \sum_j B_{i,j}x_{m+1-j}=-\sum_j B_{m+1-i,m+1-j}x_{m+1-j}=-\lambda x_{m+1-i} $$ as required.
Clearly $B$ commutes with the all ones matrix $\mathbf{1}$ (the products are zero in either direction, because row and column sums of $B$ vanish). So if $B$ is diagonalizable, then it is simultaneously diagonalizable with $\mathbf{1}$. We can take advantage of the known eigenvalues of $\mathbf{1}$: the all ones vector spans the 1-dimensional eigenspace with $\lambda=m$, and its orthogonal complement $V$ (the zero sum subspace of $\Bbb{R}^m$) is the $(m-1)$-dimensional eigenspace belonging to $\lambda=0$.
The all ones vector belongs to eigenvalue $0$ of $B$, so all the eigenvectors of $B$ belonging to non-zero eigenvalues are in $V$. This is important because $$ A=\frac{m^2+1}2\mathbf{1}+B. $$ If $u$ belongs to eigenvalue $\lambda\neq0$ of $B$, then $\mathbf{1}u=0$ and thus $Au=\lambda u$. So the non-zero eigenvalues of $B$ are also eigenvalues of $A$ and the claim follows.
Missing:
- Why are the eigenvalues of $B$ all real and distinct (so that $0$ has multiplicity one, and that $B$ is diagonalizable)?
- Prove that the Siamese construction implies $(*)$.
Solution 2:
Here are some partial results.
This paper states that every regular magic square $\mathbf A\in\mathbb N^{n\times n}$ (that is, its entries satisfy $a_{i,j}+a_{n-i+1,n-j+1}=n^2+1$) is representable as a rank-$1$ correction of a skew-centrosymmetric matrix $\mathbf Z$ (that is, $\mathbf Z=-\mathbf J\mathbf Z\mathbf J$, where $\mathbf J$ is the exchange matrix, or the identity matrix with its columns reversed). In other words, the matrix you get when you subtract $\frac{n^2+1}{2}$ from all of the entries of $\mathbf A$ is skew-centrosymmetric. This is important since the eigenvalues of $\mathbf A$, apart from the magic eigenvalue $\frac{n^3+n}{2}$, are the same as the eigenvalues of $\mathbf Z$, which now has $0$ as an eigenvalue.
We can now use the results of this paper, which says that if $\lambda$ is an eigenvalue of $\mathbf Z$, then $-\bar{\lambda}$ must also be an eigenvalue, with the same algebraic multiplicity.
Thus, the remaining task is to prove that all the eigenvalues of a Siamese magic square are necessarily real.
A tantalizing result: Pressman, in this paper, shows the stronger result that if $\lambda$ is an eigenvalue of $\mathbf Z$, then $-\lambda$ is also an eigenvalue. There seems to be a criterion in the paper for saying when a skew-centrosymmetric matrix has all its eigenvalues real, but I have not yet figured how to apply it to this case.