What is known about the eigenvectors of the $2^n \times 2^n$ Hadamard matrix?

Question

What is known about the eigenvectors of the $2^n \times 2^n$ Hadamard matrix defined recursively by $H_1=(1)$ and $$ H_N=\begin{pmatrix}H_{N/2} & H_{N/2} \\ H_{N/2} & -H_{N/2}\end{pmatrix}, $$ where $N=2^n$?

Edit: The answer below provides a "literal" answer to the problem. However, is there a deeper meaning to the eigenvectors? For the Fourier transform operator, for example, Hermite polynomials provide an excellent and rich theory of the eigenvectors. Since the Hadamard transform is indeed a Fourier transform (over the Boolean cube as the underlying group), one could expect the eigenvectors to have a clean interpretation.

Answer 1

The $2^n\times 2^n$ dimensional Hadamard matrices $H_{2^n}$ are also called Sylvester matrices or Walsh matrices. There are only two distinct eigenvalues $\pm 2^{n/2}$, so the eigenvectors are not in general orthogonal. An orthogonal basis of eigenvectors is constructed recursively in A note on the eigenvectors of Hadamard matrices of order $2^n$ (1982) and in Some observations on eigenvectors of Hadamard matrices of order $2^n$ (1984). See also Chapter 5 of Hadamard Matrix Analysis and Synthesis (2012).

Answer 2

It seems to me that $H_{N}$ is the character table of an elementary Abelian $2$-group of order $2^{n}$ (with respect to a suitable ordering of elements). As such, its rows are orthogonal by the orthogonality relations for group characters. Also, it is clear, by induction that $H_{N}$ is symmetric.Hence we have $H_{N}H_{N}^{t} = 2^{n}I$ (since it is a character table) and $H_{N}^{2} = 2^{n}I$. Thus the eigenvalues of $H_{N}$ are $\pm \sqrt{2^{n}}$, as already noted by Carlos Beenakker.

Note also that $H_{N}$ has trace zero for $N > 1,$ so that both square roots occur with equal multiplicity as eigenvalues.

Note that since $H_{N}$ is a character table of an Abelian group for $N \geq 2$, its rows and columns are mutually orthogonal. Now since $T = \frac{H_{N}}{2^{\frac{n}{2}}}$ is a matrix of multiplicative order two, we have $T\frac{I+T}{2} = \frac{I+T}{2}$ and likewise $T\frac{I-T}{2} = -\frac{I-T}{2}.$ Hence the columns of $\frac{I+T}{2}$ are eigenvectors of $T$ with eigenvalue $1$ and the columns of $\frac{I-T}{2}$ are eigenvectors of $T$ with eigenvalue $-1$. We can also see that $\frac{I+T}{2}$ and $\frac{I-T}{2}$ are mutually orthogonal idempotent matrices with sum $I$.

It follows that $\frac{I+T}{2}$ has rank $2^{n-1}$, as does $\frac{I-T}{2}.$ Hence the columns of $\frac{I}{2} + \frac{H_{N}}{2^{1+\frac{n}{2}}}$ are eigenvectors of $H$ with eigenvalue $2^{\frac{n}{2}}$ spanning the $2^{\frac{n}{2}}$-eigenspace and the columns of $\frac{I}{2} - \frac{H_{N}}{2^{1+\frac{n}{2}}}$ are eigenvectors of $H$ with eigenvalue $-2^{\frac{n}{2}}$ spanning the $-2^{\frac{n}{2}}$-eigenspace.