Non-abelian Fourier transform on a finite group

Intuition [Beginner]

The classical Fourier transform decomposes a periodic signal into sine and cosine waves of different frequencies. For a finite abelian group, this is a sum over characters — homomorphisms from the group to the complex unit circle. Each character is a "pure frequency."

For a non-abelian group, the pure frequencies are no longer enough. Characters are too coarse to separate all information. Instead, the "frequencies" become matrix-valued: each irreducible representation $\rho$ contributes an entire matrix of coefficients. The Fourier transform of a function $f$ on $G$ at the "frequency" $\rho$ is a matrix $\hat{f}(\rho )$, obtained by summing $f(g)\rho (g)$ over all group elements.

Why does this concept exist? The group algebra $\mathbb{C}G$ decomposes as a direct product of matrix algebras, one per irreducible representation. The Fourier transform is the algebra isomorphism carrying a function to its collection of matrix transforms. It diagonalises the convolution operation: convolving two functions on $G$ corresponds to multiplying their Fourier transforms matrix-by-matrix.

Visual [Beginner]

The non-abelian Fourier transform sends a function on group elements (arranged in a circle or grid) to a collection of small matrices, one per irreducible representation. For an abelian group, each matrix is $1\times 1$ (a scalar), recovering the classical discrete Fourier transform.

Worked example [Beginner]

Take $G=S_3$, the symmetric group on 3 elements. $S_3$ has three irreducible representations: the principal ${\chi }_1$ (dimension 1), the sign ${\chi }_{\mathrm{sgn}}$ (dimension 1), and the standard $V_{\mathrm{std}}$ (dimension 2).

Consider the function $f:S_3\to \mathbb{C}$ defined by $f(e)=3$, $f((12))=1$, $f((13))=1$, $f((23))=1$, $f((123))=0$, $f((132))=0$.

Step 1. Compute the Fourier transform at the principal representation ${\rho }_1$: $\hat{f}({\rho }_1)=3+1+1+1+0+0=6$.

Step 2. Compute the Fourier transform at the sign representation ${\rho }_{\mathrm{sgn}}$: $\hat{f}({\rho }_{\mathrm{sgn}}=3\cdot 1+1\cdot (-1)+1\cdot (-1)+1\cdot (-1)+0\cdot 1+0\cdot 1=0$.

Step 3. Compute the Fourier transform at the 2-dimensional standard representation (using the character values ${\chi }_{\mathrm{std}}(e)=2$, ${\chi }_{\mathrm{std}}(\text{transposition})=0$, ${\chi }_{\mathrm{std}}(\text{3-cycle})=-1$). The full matrix transform $\hat{f}({\rho }_{\mathrm{std}})$ is a $2\times 2$ matrix computed from the explicit matrix representation; its trace equals $3\cdot 2+1\cdot 0+1\cdot 0+1\cdot 0+0\cdot (-1)+0\cdot (-1)=6$.

What this tells us: the Fourier transform captures $f$ as a scalar (6), another scalar (0), and a $2\times 2$ matrix. The three pieces together encode $f$ completely, and convolution of $f$ with another function amounts to multiplying these matrix pieces.

Check your understanding [Beginner]

Formal definition [Intermediate+]

Let $G$ be a finite group of order $|G|$, and let ${\rho }_1,\dots ,{\rho }_r$ be a complete set of pairwise non-isomorphic irreducible representations of $G$ over $\mathbb{C}$, with $d_i=\dim {\rho }_i$. The Fourier transform of a function $f:G\to \mathbb{C}$ at the representation ${\rho }_i$ is the matrix

$$\hat{f}({\rho }_i)=\sum _{g\in G}f(g){\rho }_i(g)\in M_{d_i}(\mathbb{C}).$$

The full Fourier transform of $f$ is the collection $\hat{f}=(\hat{f}({\rho }_1),\dots ,\hat{f}({\rho }_r))$.

Matrix coefficients. For an irreducible representation $\rho$ of degree $d$ with matrix entries $\rho (g{)}_{jk}$, the functions $\sqrt{d/|G|}\cdot \rho (g{)}_{jk}$ for $1\le j,k\le d$ form an orthonormal set in $L^2(G)$ with respect to the inner product $⟨f,h⟩=\frac{1}{|G|}{\sum }_{g}f(g)\overline{h(g)}$. These are the matrix coefficients of $\rho$.

Plancherel measure. The weight assigned to ${\rho }_i$ in the Fourier inversion formula is $d_i^2/|G|$. The identity $|G|=d_1^2+\cdots +d_r^2$ (proved from character orthogonality in 07.01.04) is the statement that these weights sum to 1, so they define a probability measure on the set of irreducibles — the Plancherel measure of $G$.

Counterexamples to common slips

• Confusing the Fourier transform with the character transform. The character ${\chi }_i(g)=\mathrm{tr}({\rho }_i(g))$ is the trace of the matrix transform. Two different functions can share the same character transform but differ in their full matrix transforms. Only the full matrix Fourier transform is injective.
• Omitting the normalisation. The Fourier inversion and Plancherel formulas require the factor $d_i/|G|$ (or $d_i^2/|G|$). Dropping it produces formulas that are off by scalar multiples.

Key theorem with proof [Intermediate+]

Theorem (Fourier inversion for finite groups). Let $G$ be a finite group with irreducible representations ${\rho }_1,\dots ,{\rho }_r$ of degrees $d_1,\dots ,d_r$. For any $f:G\to \mathbb{C}$,

$$f(g)=\frac{1}{|G|}\sum _{i=1}^r{d}_i\mathrm{tr}\left(\hat{f}({\rho }_i){\rho }_i(g^{-1})\right).$$

Proof. From character orthogonality 07.01.04, the matrix coefficients $\{\sqrt{d_i/|G|}\cdot {\rho }_i(g{)}_{jk}\}$ form an orthonormal basis of $L^2(G)$. Expand $f$ in this basis:

$$f(g)=\sum _{i=1}^r\sum _{j,k=1}^{d_i}⟨f,\sqrt{\frac{d_i}{|G|}}{\rho }_i(\cdot {)}_{jk}⟩\sqrt{\frac{d_i}{|G|}}{\rho }_i(g{)}_{jk}.$$

Compute the inner product:

$$⟨f,\sqrt{\frac{d_i}{|G|}}{\rho }_i(\cdot {)}_{jk}⟩=\frac{1}{|G|}\sum _{h\in G}f(h)\sqrt{\frac{d_i}{|G|}}\overline{{\rho }_i(h{)}_{jk}}.$$

Substituting and simplifying:

$$f(g)=\sum _{i=1}^r\frac{d_i}{|G|}\sum _{j,k=1}^{d_i}\left(\sum _{h\in G}f(h)\overline{{\rho }_i(h{)}_{jk}}\right){\rho }_i(g{)}_{jk}.$$

The inner double sum is ${\sum }_{j,k}\hat{f}({\rho }_i{)}_{kj}{\rho }_i(g{)}_{jk}=\mathrm{tr}(\hat{f}({\rho }_i)\cdot {\rho }_i(g))$. Since ${\rho }_i(g^{-1})={\rho }_i(g{)}^{-1}={\overline{{\rho }_i(g)}}^T$ for unitary ${\rho }_i$, and unitarity can always be arranged by choosing an invariant inner product, $\overline{{\rho }_i(h{)}_{jk}}={\rho }_i(h^{-1}{)}_{kj}$. Thus:

$$f(g)=\frac{1}{|G|}\sum _{i=1}^r{d}_i\mathrm{tr}\left(\hat{f}({\rho }_i){\rho }_i(g^{-1})\right).\square$$

Bridge. The Fourier inversion formula builds toward the Peter-Weyl theorem 07.07.02 for compact Lie groups, where the sum over finite irreducibles is replaced by a Hilbert-space direct sum and the inversion becomes an integral over the dual. This is exactly the non-abelian generalisation of classical Fourier analysis: the matrix coefficients of irreducible representations replace sines and cosines as the fundamental oscillatory building blocks. The foundational reason the inversion works is the orthogonality of matrix coefficients, which identifies $L^2(G)$ with the Hilbert-space direct sum of matrix-algebra blocks. The bridge is between the algebraic structure of $\mathbb{C}G$ (a finite-dimensional semisimple algebra) and the analytic structure of $L^2(G)$ (a Hilbert space), connected by the isomorphism $\mathbb{C}G\cong {\prod }_i{M}_{d_i}(\mathbb{C})$.

Exercises [Intermediate+]

Advanced results [Master]

Theorem 1 (Wedderburn decomposition). The Fourier transform is an algebra isomorphism $\mathbb{C}G\cong {\prod }_{i=1}^r{M}_{d_i}(\mathbb{C})$. This is the Wedderburn decomposition of the semisimple algebra $\mathbb{C}G$.

This decomposes the group algebra into its simple components. Each factor $M_{d_i}(\mathbb{C})$ is the endomorphism algebra of the irreducible $V_i$, and the isomorphism sends $g\mapsto ({\rho }_1(g),\dots ,{\rho }_r(g))$.

Theorem 2 (Plancherel isomorphism). The Fourier transform extends to a unitary isomorphism $L^2(G)\to {⨁}_{i=1}^r{M}_{d_i}(\mathbb{C})$ with the inner product $\langle A, B \rangle_i = \frac{d_i}{|G|} \mathrm{tr}(AB^)$ on each factor.*

This is the Parseval/Plancherel identity in the non-abelian setting. The norm is preserved exactly, making the Fourier transform an isometry of Hilbert spaces.

Theorem 3 (Central functions and character transform). A function $f:G\to \mathbb{C}$ is central (constant on conjugacy classes) if and only if each $\hat{f}({\rho }_i)$ is a scalar matrix ${\lambda }_i{I}_{d_i}$ with ${\lambda }_i=\frac{1}{d_i}{\sum }_{g}f(g){\chi }_i(g)$. The map $f\mapsto ({\lambda }_1,\dots ,{\lambda }_r)$ is a reduced Fourier transform on the centre $Z(\mathbb{C}G)\cong {\mathbb{C}}^r$.

The character theory of 07.01.03 and 07.01.04 is recovered as the Fourier transform restricted to central functions.

Theorem 4 (Upper-bound lemma, Diaconis-Shahshahani 1981). For a probability measure $\mu$ on $G$, the total variation distance from uniform satisfies

$$\Vert \mu -U{\Vert }_{\mathrm{TV}}^2\le \frac{1}{4}\sum _{i=2}^r{d}_i\mathrm{tr}\left(\hat{\mu }({\rho }_i)\hat{\mu }({\rho }_i{)}^{\ast }\right).$$

This bounds mixing times of random walks using the non-abelian Fourier transform at irreducibles beyond the principal.

Theorem 5 (Peter-Weyl theorem for finite groups). The matrix coefficients $\{d_i^{1/2}{\rho }_i(g{)}_{jk}:1\le i\le r,1\le j,k\le d_i\}$ form a complete orthonormal system in $L^2(G)$. Every function $f:G\to \mathbb{C}$ decomposes uniquely as a sum of matrix coefficients, and this decomposition is the Fourier inversion formula.

This is the finite-group avatar of the Peter-Weyl theorem 07.07.02 for compact Lie groups, where $G$ is replaced by a compact group and the direct sum becomes an $L^2$ direct integral.

Theorem 6 (Convolution powers and cut-off). For a generating probability measure $\mu$ on $G$, the convolution powers ${\mu }^{\ast k}$ converge to the uniform distribution. The mixing time satisfies $t_{\mathrm{mix}}\le C\log |G|$ where $C$ depends on the spectral gap $1-{\lambda }_2^{\ast }$ and $\lambda_2^$ is the second-largest eigenvalue of the transition operator (computed via the Fourier transform).*

Synthesis. The Fourier inversion formula builds toward the Peter-Weyl theorem 07.07.02 by identifying matrix coefficients as the correct frequency basis for non-abelian harmonic analysis. The central insight is that the group algebra decomposes into matrix blocks via the Wedderburn theorem, and this is exactly the algebraic engine behind the analytic Plancherel isomorphism. Putting these together, the Fourier transform identifies the category of functions on $G$ with the category of tuples of matrices indexed by irreducibles, and the bridge is that convolution on one side corresponds to matrix multiplication on the other. This pattern recurs throughout representation theory: the regular representation decomposition of 07.01.05 is the spectral-theoretic shadow, and the character orthogonality of 07.01.04 is the Plancherel formula restricted to central functions. The foundational reason for the power of the non-abelian Fourier transform is that it generalises the familiar tool from abelian Fourier analysis to the full non-commutative setting while preserving the key property that convolution diagonalises.

Full proof set [Master]

Proposition 1 (Orthogonality of matrix coefficients). For irreducible representations ${\rho }_i$ and ${\rho }_j$ of a finite group $G$, the matrix coefficients satisfy

$$\frac{d_i}{|G|}\sum _{g\in G}{\rho }_i(g{)}_{ab}\overline{{\rho }_j(g{)}_{cd}}={\delta }_{ij}{\delta }_{ac}{\delta }_{bd}.$$

Proof. For fixed $b$ and $c$, the map $T={\sum }_g{\rho }_i(g{)}_{ab}{\rho }_j(g^{-1}{)}_{cd}\cdot$ (as a linear map from the representation space of ${\rho }_j$ to that of ${\rho }_i$) intertwines ${\rho }_j$ and ${\rho }_i$. By Schur's lemma 07.01.02, $T=0$ if ${\rho }_i\ncong {\rho }_j$, and $T=\lambda I$ if ${\rho }_i={\rho }_j$. Computing the trace determines $\lambda$. $\square$

Proposition 2 (Diaconis-Shahshahani upper bound). For a probability measure $\mu$ on $G$,

$$4\Vert \mu -U{\Vert }_{\mathrm{TV}}^2\le \sum _g|G|{\left|\mu (g)-\frac{1}{|G|}\right|}^2=\sum _{i=2}^r{d}_i\Vert \hat{\mu }({\rho }_i){\Vert }_F^2.$$

Proof. The first inequality is the Cauchy-Schwarz bound $4\Vert f{\Vert }_1^2\le |G|\Vert f{\Vert }_2^2$ for $f=\mu -U$. The second equality is the Plancherel formula: $\Vert \mu -U{\Vert }_2^2=\frac{1}{|G|}{\sum }_{i=2}^r{d}_i\mathrm{tr}(\hat{\mu }({\rho }_i)\hat{\mu }({\rho }_i{)}^{\ast })$, noting that the principal component $\hat{\mu }({\rho }_1)=1$ contributes zero since $\mu$ is a probability measure. $\square$

Connections [Master]

• Character orthogonality 07.01.04. The Fourier inversion and Plancherel formulas rest on the orthogonality of matrix coefficients, which generalises character orthogonality from central functions to all functions on $G$.

• Regular representation 07.01.05. The Wedderburn decomposition $\mathbb{C}G\cong \prod M_{d_i}(\mathbb{C})$ underlying the Fourier transform is the algebraic form of the regular representation decomposition into isotypic components.

• Peter-Weyl theorem 07.07.02. The finite-group Peter-Weyl theorem proved here is the model for the compact-Lie-group version, where $L^2(G)$ decomposes as a Hilbert direct sum of matrix-coefficient spaces indexed by all irreducible representations.

• Schur-Weyl duality 07.05.04. The matrix-coefficient perspective on Fourier analysis connects to the decomposition of tensor powers $({\mathbb{C}}^n{)}^{\otimes k}$ under the joint action of ${\mathrm{GL}}_n$ and $S_k$, where the Fourier transform on $S_k$ controls the ${\mathrm{GL}}_n$-isotypic decomposition.

Historical & philosophical context [Master]

Frobenius introduced group characters in 1896 ^{[Frobenius 1896]}, motivated by the factorisation of the group determinant. His character theory encoded the Fourier analysis of central functions on $G$, but without the matrix-algebra framework. The full matrix-coefficient perspective emerged from the work of Schur (1901), who proved the orthogonality of matrix coefficients and identified the decomposition of $\mathbb{C}G$ as a product of matrix algebras — the Wedderburn decomposition in the special case of group algebras. Wedderburn's 1907 general structure theorem for semisimple algebras generalised Schur's decomposition.

The Peter-Weyl theorem (1927) ^{[Peter-Weyl 1927]} extended the finite-group decomposition to compact Lie groups, replacing the direct sum with an $L^2$ direct sum and establishing the completeness of matrix coefficients as a basis for $L^2(G)$. The probabilistic application to random walks was developed by Diaconis and Shahshahani in the 1980s ^{[Diaconis 1988]}, using the non-abelian Fourier transform to give sharp mixing-time bounds for card shuffling and other random walks on symmetric groups. Diaconis's 1988 monograph Group Representations in Probability and Statistics remains the canonical reference for the probabilistic applications.

Bibliography [Master]

@article{Frobenius1896,
  author = {Frobenius, Ferdinand Georg},
  title = {Über Gruppencharaktere},
  journal = {Sitzungsberichte der Königlich Preußischen Akademie der Wissenschaften zu Berlin},
  year = {1896},
  pages = {985--1021},
}

@article{PeterWeyl1927,
  author = {Peter, Fritz and Weyl, Hermann},
  title = {Die Vollständigkeit der rationalen Darstellungen der kontinuierlichen Gruppen},
  journal = {Mathematische Annalen},
  volume = {97},
  year = {1927},
  pages = {737--755},
}

@book{Diaconis1988,
  author = {Diaconis, Persi},
  title = {Group Representations in Probability and Statistics},
  publisher = {Institute of Mathematical Statistics},
  year = {1988},
  series = {IMS Lecture Notes},
}

@book{Serre1977,
  author = {Serre, Jean-Pierre},
  title = {Linear Representations of Finite Groups},
  publisher = {Springer},
  year = {1977},
}

@article{DiaconisShahshahani1981,
  author = {Diaconis, Persi and Shahshahani, Mehrdad},
  title = {Generating a random permutation with random transpositions},
  journal = {Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete},
  volume = {57},
  year = {1981},
  pages = {159--179},
}

@article{Schur1901,
  author = {Schur, Issai},
  title = {Über eine Klasse von Matrizen, die sich einer gegebenen Matrix zuordnen lassen},
  year = {1901},
  journal = {Dissertation, Berlin},
}