Math 202B: Lecture 13

Let $G$ be a finite abelian group.

Theorem 13.1. For every $A \in \mathcal{C}(G),$ the Fourier basis of $\mathcal{C}(G)$ is an eigenbasis for the image of $A$ in the left regular representation, and the Fourier transform of $A$ is its spectrum: we have

$\mathsf{L}(A)F^\lambda = \widehat{A}(\lambda)F^\lambda, \quad \lambda \in \Lambda.$

This result has many applications because many interesting matrices can be realized in the left regular representation of an abelian group, and in any such situation Theorem 13.1 explicitly gives us the eigenvalues and eigenvectors of the matrix in question. Last lecture we considered the case of cyclic group, whose elements become circulant matrices in the regular representation.

Let us give another example, this time taking

$\Lambda = \{\alpha=(\alpha_1,\dots,\alpha_r) \colon \alpha_i \in \{0,1\}\}$

to be the group of vertices of the $r$ -dimensional unit cube. In this case, the convolution algebra $\mathcal{C}(\Lambda)$ is $2^r$ -dimensional and the group basis is

$E_\alpha=E_{(\alpha_1,\dots,\alpha_r)}$

with $(\alpha_1,\dots,\alpha_r)$ ranging over all $r$ -dimensional vectors with entries in $\{0,1\}$ . The convolution product of two basis vectors is

$E_\alpha E_\beta = E_{(\alpha_1+\beta_1,\dots,\alpha_r+\beta_r)}$

with coordinate addition performed mod 2. In addition to being a group, it is natural to view $\Lambda$ as a graph which reflects the geometry of the $r$ -dimensional cube: we consider two vertices $\alpha,\beta$ of the $r$ -dimensional cube adjacent if they differ in a single coordinate. Equivalently, we have $\alpha+\varepsilon_i=\beta$ for some $1 \leq i \leq r,$ where $\varepsilon_1,\dots,\varepsilon_r \in \Lambda$ are the vectors

$\varepsilon_1=(1,0,0\dots,0),\ \varepsilon_2=(0,1,0,\dots,0),\ \dots,\ \varepsilon_r=(0,0,\dots,0,1).$

In more general terminology, we are identifying $\Lambda$ with its Cayley graph corresponding to the generators $\{\varepsilon_1,\dots,\varepsilon_r\}.$

Adjacency in $\Lambda$ can also be expressed in $\mathcal{C}(\Lambda)$ , since $\alpha,\beta \in \Lambda$ are adjacent if and only if

$E_\alpha E_{\varepsilon_i}=E_\beta$

for some $1 \leq i \leq r.$ This means that the Wedderburn transform of

$A = E_{\varepsilon_1} +E_{\varepsilon_2}+\dots + E_{\varepsilon_r}$

is the adjacency operator of the graph $\Lambda$ , and hence that we can calculate the eigenvalues and eigenvectors of $\rho(A)$ explicitly using Theorem 13.1.

For the Boolean cube $\Lambda \simeq C_2 \times \dots \times C_2,$ the character table is

$\chi^\lambda_\alpha = \chi^{(\lambda_1,\dots,\lambda_r)}_{(\alpha_1,\dots,\alpha_r)} = (-1)^{\alpha_1\lambda_1} \dots (-1)^{\alpha_r\lambda_r} =(-1)^{\alpha \cdot \lambda},$

where $\alpha \cdot \lambda = \alpha_1\lambda_1+\dots+\alpha_r\lambda_r$ is the usual dot product. Thus, the Fourier basis of $\mathcal{C}(\Lambda)$ is

$F^\lambda = \sum\limits_{\alpha \in \Lambda} (-1)^{\alpha \cdot \lambda}E_\alpha, \quad \lambda \in \Lambda,$

and this is an eigenbasis of $\rho(A)$ . Now by direct computation

$\rho(A)F^\lambda =AF^\lambda= \left( \sum\limits_{i=1}^n E_{\varepsilon_i}\right)\left(\sum\limits_{\alpha \in \Lambda} (-1)^{\alpha \cdot \lambda} E_\alpha\right)=\sum\limits_{\alpha \in \Lambda}\sum\limits_{i=1}^n (-1)^{\alpha \cdot \lambda}E_{\alpha+\varepsilon_i}=\left(\sum\limits_{i=1}^n(-1)^{\varepsilon_i\cdot\lambda}\right)F^\lambda.$

The sum

$\sum\limits_{i=1}^r(-1)^{\varepsilon_i\cdot\lambda}$

giving the eigenvalue of $\rho(A)$ on $F^\lambda$ can be simplified: every coordinate of $\lambda$ equal to zero contributes $+1$ and every coordinate of $\lambda$ equal to $1$ contributes $-1.$ Thus writing $w(\lambda)$ for the number of entries equal to one in $\lambda$ (this is called the Hamming weight of $\lambda$ in coding theory), we have $r-w(\lambda)$ terms equal to one and $w(\lambda)$ terms equal to minus one, giving