12
$\begingroup$

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.

$\endgroup$

2 Answers 2

13
$\begingroup$

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

$\endgroup$
4
  • 9
    $\begingroup$ 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. $\endgroup$ Oct 3, 2019 at 21:52
  • $\begingroup$ would that give you an orthogonal basis ? (as I understood the cited papers, that was the aim, to provide an efficient orthogonalization) $\endgroup$ Oct 3, 2019 at 21:53
  • 6
    $\begingroup$ 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. $\endgroup$ Oct 3, 2019 at 21:58
  • 1
    $\begingroup$ Thanks. Is there a more meaningful interpretation of the eigenvectors? See the edit in the question above. $\endgroup$
    – MCH
    Oct 4, 2019 at 17:45
7
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Oct 5, 2019 at 20:23
  • $\begingroup$ @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. $\endgroup$ Oct 5, 2019 at 20:31
  • $\begingroup$ @GerhardPaseman : Well, a scalar multiple of a unitary matrix.... $\endgroup$ Oct 6, 2019 at 10:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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