Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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
add comment

2 Answers

up vote 12 down vote accepted
+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}^-$).

share|improve this answer
    
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! –  J. M. 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
show 3 more comments

This is not yet an answer but I like everything I've seen so far in experimenting with this question. Just for the record - here is the list of eigenvalues for dimensions 2 to 32.

$ \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...

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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