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

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.

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).

• Aren't the eigenvectors easy to compute from the fact that $H_{2^n} = \underbrace{H_2 \otimes H_2 \otimes \dots \otimes H_2}_{\text{$n$times}}$? You can diagonalize a Kronecker product factor by factor. – Federico Poloni Oct 3 '19 at 21:52
• would that give you an orthogonal basis ? (as I understood the cited papers, that was the aim, to provide an efficient orthogonalization) – Carlo Beenakker Oct 3 '19 at 21:53
• Yes, if I am not missing anything. If $H_2 = QDQ^*$, with $Q$ orthogonal (which exists since $H_2$ is symmetric), then $H_{2^n} = (Q\otimes Q \otimes \dots \otimes Q)(D\otimes D \otimes \dots \otimes D) (Q\otimes Q \otimes \dots \otimes Q)^*$. I tested this quickly with Octave and it seems to work. – Federico Poloni Oct 3 '19 at 21:58
• Thanks. Is there a more meaningful interpretation of the eigenvectors? See the edit in the question above. – MCH Oct 4 '19 at 17:45

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.

• Interesting. Do any of these remarks apply or extend to other orders? In particular, what can be said for orders 12,20, and 24? Gerhard "Hadamard Minds Want To Know" Paseman, 2019.10.05. – Gerhard Paseman Oct 5 '19 at 20:23
• @GerhardPaseman : Usually, the character table of a finite Abelian group is just a unitary matrix. In this case, we have the unusual fact that it is also symmetric, which makes it a matrix of multiplicative order $2$. This gives some special properties, which would not apply for the orders you mention. – Geoff Robinson Oct 5 '19 at 20:31
• @GerhardPaseman : Well, a scalar multiple of a unitary matrix.... – Geoff Robinson Oct 6 '19 at 10:24