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

1. All the eigenvalues are integers
2. If $n=2^m$, then there are $m+1$ nonzero eigenvalues.
3. Of the $m+1$ nonzero eigenvalues, one is positive, and the other eigenvalues are negative.
4. The positive eigenvalue of the $2^m \times 2^m$ matrix $\mathbf X$ is $2^{m-1}(2^m-1)$.
5. 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?

-
Item #4 follows from the fact that the row sums are all equal (a consequence of the Cayley table property). Thus the 'all ones' vector is an eigenvector belonging to this eigenvalue. –  Jyrki Lahtonen Dec 23 '11 at 16:39
Perhaps if you use the decomposition of the matrix into 4x4 blocks you can get something to work by induction. –  mt_ Dec 23 '11 at 16:50

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}^-$).

-
IOW the Hadamard matrix $H_m$ defined recursively by $H_0=(1)$ and $$H_{m+1}=\pmatrix{H_m&H_m\cr H_m&-H_m\cr}$$ will have columns that are eigenvectors of $X_m$. –  Jyrki Lahtonen Dec 23 '11 at 17:31
It feels like there should be a simpler description of either the end result or the recursive step using the Hadamard matrix approach. After all, the Hadamard matrix gives also the character table of the underlying NIM-group (an elementary abelian 2-group). Thinking... –  Jyrki Lahtonen Dec 23 '11 at 17:46
Yessssss!!!! Let $G$ be the group $\{0,1,\ldots,2^m-1\}$ under NIM-sum. The matrix $X_m$ represents left multiplication by the element $\sum_{x\in G} xe_x\in \mathbf{R}[G]$ in the left regular representation of the group algebra of $G$. Because $G$ is abelian, this element acts semisimply, and has eigenvalues that are $\lambda_\chi=\sum_{x\in G}x\chi(x)$, where $\chi$ ranges over the characters of the group $G$. We can build the characters recursively as above! –  Jyrki Lahtonen Dec 23 '11 at 17:59
Looks quite good, so far! I'm not accepting for now in case other answers pop up, but I've given you my last upvote for today. Thanks for this! –  Ｊ. Ｍ. Dec 23 '11 at 18:15
Thanks, @J.M. I really should work on the presentation. Hopefully it is mostly readable. Something better is probably out there. –  Jyrki Lahtonen Dec 23 '11 at 18:25
$\qquad \small \begin{array} {r|rrrrrr} n & \lambda_0 & \lambda_1 & \lambda_2 & \lambda_3 & \ldots \\ \hline \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1.00000 & -1.00000 & 0 & 0 & 0 & 0 & 0 \\ 3 & 4.11309 & -3.20191 & -0.911179 & 0 & 0 & 0 & 0 \\ 4 & 6.00000 & -4.00000 & -2.00000 & 0 & 0 & 0 & 0 \\ 5 & 14.5045 & -9.00554 & -3.58620 & -1.91276 & 0 & 0 & 0 \\ 6 & 19.4007 & -12.7896 & -3.61105 & -3.00000 & 0 & 0 & 0 \\ 7 & 24.1164 & -14.2248 & -6.83415 & -3.05741 & 0 & 0 & 0 \\ 8 & 28.0000 & -16.0000 & -8.00000 & -4.00000 & 0 & 0 & 0 \\ 9 & 49.6139 & -24.4997 & -13.6182 & -7.57719 & -3.91876 & 0 & 0 \\ 10 & 62.8155 & -35.9022 & -14.2844 & -7.62891 & -5.00000 & 0 & 0 \\ 11 & 74.0458 & -43.7856 & -14.3322 & -10.7731 & -5.15484 & 0 & 0 \\ 12 & 83.5162 & -51.1273 & -14.3889 & -12.0000 & -6.00000 & 0 & 0 \\ 13 & 94.1939 & -53.6516 & -22.1227 & -12.2067 & -6.21279 & 0 & 0 \\ 14 & 103.443 & -56.8879 & -27.3301 & -12.2248 & -7.00000 & 0 & 0 \\ 15 & 112.117 & -60.2314 & -29.8447 & -14.7815 & -7.25961 & 0 & 0 \\ 16 & 120.000 & -64.0000 & -32.0000 & -16.0000 & -8.00000 & 0 & 0 \\ 17 & 171.867 & -73.7456 & -45.2712 & -29.3182 & -15.6086 & -7.92300 & 0 \\ 18 & 206.909 & -97.7047 & -54.2836 & -30.2568 & -15.6638 & -9.00000 & 0 \\ 19 & 235.941 & -121.404 & -56.1933 & -30.3942 & -18.7220 & -9.22729 & 0 \\ 20 & 260.889 & -143.387 & -57.0271 & -30.4750 & -20.0000 & -10.0000 & 0 \\ 21 & 285.172 & -159.208 & -57.1153 & -38.0783 & -20.4854 & -10.2847 & 0 \\ 22 & 306.935 & -175.009 & -57.2218 & -43.0863 & -20.6174 & -11.0000 & 0 \\ 23 & 327.175 & -189.915 & -57.3281 & -45.8065 & -22.8020 & -11.3230 & 0 \\ 24 & 345.906 & -204.451 & -57.4546 & -48.0000 & -24.0000 & -12.0000 & 0 \\ 25 & 368.769 & -209.111 & -74.0415 & -48.6899 & -24.6126 & -12.3138 & 0 \\ 26 & 389.681 & -214.564 & -88.4471 & -48.8194 & -24.8500 & -13.0000 & 0 \\ 27 & 409.338 & -220.649 & -99.6532 & -48.8630 & -26.8285 & -13.3448 & 0 \\ 28 & 427.728 & -227.530 & -109.308 & -48.8902 & -28.0000 & -14.0000 & 0 \\ 29 & 446.112 & -233.927 & -114.351 & -54.7713 & -28.7024 & -14.3607 & 0 \\ 30 & 463.458 & -240.919 & -119.376 & -59.1247 & -29.0380 & -15.0000 & 0 \\ 31 & 480.118 & -248.234 & -123.848 & -61.8143 & -30.8469 & -15.3747 & 0 \\ 32 & 496.000 & -256.000 & -128.000 & -64.0000 & -32.0000 & -16.0000 & 0 \end{array}$
These are also the singular values. It is possible to compute a cholesky-decomposition of the matrix $\small A^2$. That the sets of eigenvectors are submatrices of Hadamard-matrices was already mentioned in Jyrki's comment and makes things even more interesting...