Why are the eigenvalues of these "bitwise XOR matrices" integers? In the course of playing around with this question, I have hit upon a question of my own.
Consider the $n\times n$ symmetric matrix $\mathbf X$ whose entries are given by $x_{j,k}=(j-1)\mathbin{\mathrm{XOR}}(k-1)$, where $\mathrm{XOR}$ is bitwise XOR. (As noted in the other question, the matrix is essentially the Cayley table for nimber addition.)
Looking at the eigenvalues of $\mathbf X$ when $n$ is a power of $2$, I have observed a few things with the first few members:


*

*All the eigenvalues are integers

*If $n=2^m$, then there are $m+1$ nonzero eigenvalues.

*Of the $m+1$ nonzero eigenvalues, one is positive, and the other eigenvalues are negative.

*The positive eigenvalue of the $2^m \times 2^m$ matrix $\mathbf X$ is $2^{m-1}(2^m-1)$.

*The $m$ negative eigenvalues of $\mathbf X$ are the negatives of the powers of $2$ between $2^{m-1}$ and $2^{2m-2}$, inclusive.


(For those who want to try it out in Mathematica: Table[Eigenvalues[Array[BitXor, {2^n, 2^n}, {0, 0}], n + 1], {n, 8}])
Is there a simple explanation for these observations?
 A: It is best to index the rows and columns from $0$ to $2^m-1$, so $X_{ij}=i\,XOR\,j$.
We have a recursive construction for these matrices. Let $J$ denote the matrix of all ones.
Let $X_m$ denote the matrix of size $2^m\times2^m$. Then we have in the block form
$$
X_{m+1}=\pmatrix{X_m&X_m+2^mJ\cr X_m+2^mJ&X_m\cr}
$$
for all natural numbers $m$.
On any row of $X_m$ all the integers in the range $[0,2^m-1]$ appear exactly once, so all the row sums are $\sum_{j=0}^{2^m-1}j=\frac12\,2^m(2^m-1)=2^{m-1}(2^m-1)$, and thus the vector $(1,\ldots,1)^T$ is an eigenvector belonging to this eigenvalue.
Assume that $v_m\in\mathbf{R}^{2^m}$ is an eigenvector of $X_m$ belonging to an eigenvalue $\lambda$. Furthermore, assume that either the entries of $v_m$ are all equal to one or that their sum is equal to zero. This latter requirement implies that $v_m$ is an eigenvector of the matrix $J$ belonging to the eigenvalue $\mu=2^m$ or to the eigenvalue $\mu=0$ depending which case applies.
Given this we can then construct two eigenvectors of $X_{m+1}$: $v_{m+1}^+=(v_m|v_m)$ and
$v_{m+1}^-=(v_m|-v_m)$ by replicating the components of $v_m$ either without or with a sign change. We then see that $v_{m+1}^+$ is an eigenvector of $X_{m+1}$ belonging to the eigenvalue $\lambda+(\lambda+2^m\mu)=2\lambda+2^m\mu$, and $v_{m+1}^-$ is an eigenvector belonging to the eigenvalue $\lambda-(\lambda+2^m\mu)=-2^m\mu$.
Using this construction we can then recursively construct $2^{m+1}$ linearly independent eigenvectors of $X_{m+1}$ given $2^m$ linearly independent eigenvectors of $X_m$. This is because the component sum of $v_{m+1}^-$ is always equal to zero, and the component sum of $v_{m+1}^+$ is either zero (if that was the case with $v_m$) or it consists of all ones (ditto), so the assumption that these will be eigenvectors of $J$ will always hold. The starting point $m=0$ is covered by the all one vector, so basically this explains all the observations. Most of the time $\mu=0$, so we get the doubles of the eigenvalues of $X_{m+1}$ (with $v_{m+1}^+$) as well as zero (with $v_{m+1}^-$). The case where $\mu=2^m$ yields the positive eigenvalue (with $v_{m+1}^+$) as well as the negative eigenvalue with largest absolute value (with $v_{m+1}^-$).
