Fourier analysis becomes representation theory when we ask which coordinates make a symmetry action easier to understand. For a finite abelian group, the natural frequency coordinates are scalar characters. For a non-abelian group, they are matrices.
The word frequency can therefore mean more than a sine wave. It can mean an irreducible way for a group to act. A function on the group can be reorganised into these irreducible components; convolution can then be performed separately in the resulting blocks. The Fourier transform changes the coordinates of the problem without losing the original function. The finite-group foundations are developed in the representation-theory references collected at the end of this guide. [1–2]
This article works entirely with finite groups and complex-valued functions unless a later boundary section says otherwise. It is an undergraduate enrichment guide, not a statement of Singapore school examination requirements. Read the character-theory guide first when irreducibility, characters or orthogonality are unfamiliar. For quantum circuits and amplitude encoding, the separate Quantum Fourier Transform guide owns that different mathematical job.
Conventions · Cyclic worked example · Matrix frequencies · An exact random walk · Practice and solutions · BTT Mathematics Hub
Why a change of coordinates can change the difficulty
Imagine four measurements arranged around a circular track. One description lists the measurements in position order. Another separates the average level, an alternating pattern and two quarter-turn patterns. These descriptions have the same amount of information. Nevertheless, an operation that repeatedly blends neighbouring measurements can be complicated in the first description and simple in the second.
The reason is structural. Circular shifting is a symmetry of the arrangement. Blending according to the same rule at every position respects that symmetry. Coordinates adapted to shifting make the blending operation easier to inspect. We do not improve the calculation by guessing better numbers; we improve it by choosing a basis that matches the operation.
The group viewpoint also tells us when this intuition must change. Rotations and reflections of a triangle do not all commute. There is no reason to expect every relevant operation to become a scalar in one common basis. Small matrix blocks, rather than individual numbers, are the correct units of analysis.
Fix the conventions before doing any arithmetic
Let G be a finite group of order N. A function f:G→C assigns one complex number to each group element. The vector space of all such functions has dimension N. Let δa denote the function that is 1 at a and 0 elsewhere. These delta functions form the position basis.
We use unnormalised convolution:
(f*h)(x) = Σy∈G f(y)h(y−1x).
Choose one unitary representative ρ from each equivalence class of irreducible complex representations, and write dρ for its dimension. Our forward transform is
Fρ(f) = Σg∈G f(g)ρ(g).
There is no factor 1/N in either definition. We deliberately put the group element, not its inverse, in the forward transform. Some texts use the inverse and a negative exponential instead. Both conventions work, but inversion formulas and multiplication order must travel with the convention that produced them. A mismatch is a mathematical error, not a stylistic difference.
Convolution is group multiplication extended linearly
Apply the definition to two delta functions. The only possible nonzero summand has y=a, and the remaining factor is δb(a−1x). It equals 1 exactly when x=ab. Therefore δa*δb=δab.
This tiny calculation explains the whole construction. Convolution is what group multiplication becomes when we allow linear combinations of group elements. The convolution algebra of functions is a coordinate form of the group algebra C[G]. Associativity follows from associativity of group multiplication and bilinearity. Commutativity occurs precisely when the group itself is abelian.
The identity for convolution is δe, not the constant function 1. The constant probability distribution u(g)=1/N has a different role: convolving a function with u replaces it by its average value. Confusing these two functions is a common source of incorrect normalisation.
The convolution theorem, with its multiplication order visible
Expand the transform of f*h and substitute x=yz. Then ρ(x)=ρ(y)ρ(z), so
Fρ(f*h) = Σy,z f(y)h(z)ρ(y)ρ(z) = Fρ(f)Fρ(h).
The sums separate, but the matrices do not change order. This proof is short enough to repeat whenever a convention is uncertain. It also explains why non-abelian Fourier analysis is matrix-valued: the target must retain the possible noncommutativity of the original multiplication.
For a probability mass function μ, repeated independent group increments correspond to convolution powers. Consequently Fρ(μ*k)=Fρ(μ)k. A repeated averaging problem can become a matrix-power problem in each irreducible block.
Worked example: every frequency of C4
Write C4 additively as {0,1,2,3}, with addition modulo 4. Set i²=−1. Its four one-dimensional representations are ρk(j)=ikj, where k=0,1,2,3. Thus each Fourier block is a scalar.
Take the position data f=(2,1,0,3). We compute the four forward coefficients using our positive-exponent convention. At k=0, every multiplier is 1, giving 6. At k=1, the multipliers are 1,i,−1,−i, giving 2+i−3i=2−2i. At k=2 they are 1,−1,1,−1, giving −2. At k=3 they are 1,−i,−1,i, giving 2+2i.
F(f) = (6, 2−2i, −2, 2+2i).
The first coefficient is the total, not the average, because our forward transform is unnormalised. Divide it by 4 to obtain the mean 3/2. The third coefficient measures the alternating component. The second and fourth coefficients are complex conjugates because this particular input is real.
Reconstruct the original data rather than merely trusting the transform
For C4, inversion reads f(j)=(1/4)Σk=03 Fk(f)i−kj. At j=0, the sum is 6+(2−2i)−2+(2+2i)=8, giving f(0)=2.
At j=1, multiply the four coefficients by 1,−i,−1,i respectively. The terms are 6,−2−2i,2,−2+2i. Their sum is 4, giving f(1)=1. The imaginary parts cancel as they must. Repeating at j=2 and j=3 gives 0 and 3.
This reconstruction is not an optional presentation flourish. It checks the sign in the exponent, the ordering of the coefficients and the factor 1/4 simultaneously. When learning a new transform, one successful round trip is often more informative than several additional forward examples.
A complete filtering calculation
Define a circular smoothing kernel q=(1/2,1/4,0,1/4). It keeps half the current value and adds one quarter of each neighbour. Its Fourier coefficients are (1,1/2,0,1/2). Hence the transformed output is
F(q*f) = (6, 1−i, 0, 1+i).
Inverting gives q*f=(2,1,1,2). Direct convolution confirms the result. The first entry is (1/2)·2+(1/4)·3+(1/4)·1=2. The second is (1/2)·1+(1/4)·2+(1/4)·0=1. The remaining entries are 1 and 2.
The Fourier description explains what happened rather than merely reproducing the output. The mean component survives unchanged. Two oscillatory components are halved. The alternating component is annihilated. The transformation is simple because the chosen coordinates match the circular symmetry of the filter.
Why this filter cannot be reversed uniquely
The alternating vector a=(1,−1,1,−1) has all its Fourier information in the k=2 component. Since the filter multiplier there is zero, q*a=0. Therefore f and f+ca produce exactly the same filtered result for every complex number c.
Information has been lost by the filter, not by the Fourier transform. The transform itself is invertible. This distinction matters whenever a processing pipeline is described as reversible: changing coordinates can preserve information while a subsequent multiplier destroys it.
For a general finite group, left convolution by q is invertible exactly when every Fourier matrix Fρ(q) is invertible. Small nonzero singular values also warn that inversion can amplify error. In the scalar cyclic case, that warning reduces to small frequency multipliers.
What changes when the group is non-abelian?
For finite groups over C, the group algebra decomposes into matrix algebras indexed by irreducible representations. Its dimension identity is N=Σρdρ². This is the algebraic foundation of the full finite-group Fourier transform. [1]
For S3, the irreducible dimensions are 1,1,2. Consequently 6=1²+1²+2². A function on the six group elements is represented by two scalar blocks and one 2×2 block. That is still six complex coordinates. We have not reduced the amount of data; we have organised it into symmetry-adapted pieces.
A frequent mistake is to retain only the trace of each block. Three traces cannot encode an arbitrary six-dimensional function space. Irreducible characters are enough to expand class functions, which are constant on conjugacy classes. Arbitrary functions require the full collection of matrix coefficients.
General Fourier inversion
With our conventions, the inverse formula is
f(x) = (1/N) Σρ dρ tr(Fρ(f)ρ(x−1)).
To see why, expand Fρ(f). The proposed reconstruction becomes (1/N)Σgf(g)Σρdρχρ(gx−1). The inner sum is the regular character: it equals N when g=x and zero otherwise. Everything except f(x) disappears. The regular-character identity is a standard consequence of complete reducibility. [1–2]
Notice the position of the inverse and the dimension factor. Both are doing work. The inverse aligns a group element with the position being reconstructed. The factor dρ compensates for the multiplicity with which that irreducible occurs in the regular representation.
Plancherel: an energy check for every block
For a matrix A, its Hilbert–Schmidt norm satisfies ||A||HS²=tr(AA*)=Σi,j|Aij|², where A* is conjugate transpose. Finite-group Plancherel, in our normalisation, is
Σg|f(g)|² = (1/N)Σρdρ||Fρ(f)||HS².
This follows by expanding the right side, using unitarity to replace ρ(h)* by ρ(h−1), and applying the same regular-character identity. Only terms with g=h remain. Matrix coefficient orthogonality provides an equivalent route. [1–2]
For f=(2,1,0,3), the position energy is 4+1+0+9=14. The Fourier squared magnitudes are 36,8,4,8. Their sum is 56; dividing by 4 gives 14. A transform implementation that returns a different total has a normalisation, conjugation or arithmetic problem.
An explicit matrix representation of S3
Write S3 as the triangle group generated by r and s, where r³=e, s²=e and srs=r−1. Every element is rasb, with a∈{0,1,2} and b∈{0,1}. The standard representation uses
R = [ -1/2 -sqrt(3)/2 ]
[ sqrt(3)/2 -1/2 ]
S = [ 1 0 ]
[ 0 -1 ]
R is a 120-degree rotation and S is a reflection. Direct multiplication verifies R³=I, S²=I and SRS=R−1. The other irreducible representations are the trivial representation and the sign representation. Their values on rotations are 1; the sign representation is −1 on reflections.
These matrices provide a small laboratory for noncommutativity. RS and SR represent different triangle symmetries. Any calculation that interchanges them without justification is no longer representing the group that was specified.
A function that characters alone cannot recover
Take f=δs−δrs. Both s and rs are reflections, hence conjugate in S3. The trivial Fourier coefficient is 1−1=0. The sign coefficient is −1−(−1)=0. The standard block is S−RS, a nonzero matrix whose trace is also zero.
Keeping only the three traces would therefore report zero everywhere, although f is not the zero function. The off-diagonal and diagonal arrangement inside S−RS contains information that its trace has discarded.
The norm test confirms that the information is still present in the full transform. The squared Hilbert–Schmidt norm of S−RS is 6. Its contribution to Plancherel is (2/6)·6=2, matching |1|²+|−1|² in position space. This is a concrete reason to distinguish characters from matrix-valued Fourier coefficients.
Class functions make matrix blocks scalar
Suppose f is constant on conjugacy classes. Conjugating Fρ(f) by ρ(h) merely reindexes its defining sum, so the block commutes with the whole representation. Schur’s lemma then makes it a scalar matrix on each irreducible. [1–2]
Write Fρ(f)=cρI. Taking the trace gives cρ=(1/dρ)Σgf(g)χρ(g). Central convolution problems can therefore be reduced to scalar multipliers even when G itself is non-abelian.
This does not contradict the need for matrix frequencies. It identifies a special, lower-dimensional part of the full problem where symmetry has supplied extra simplification. The hypothesis that f is a class function must not disappear from the statement.
Worked application: a random walk that fails to converge
Start at the identity of S3. At each step, choose one of the three transpositions uniformly and multiply by it. Let μ be this step distribution. Because transpositions form a conjugacy class, every Fourier block is scalar.
The trivial multiplier is 1 because probabilities sum to 1. The sign multiplier is −1 because every allowed step is odd. The standard multiplier is 0 because the standard character is zero on transpositions. Thus the k-step sign coefficient is (−1)k.
The walk cannot converge to the uniform distribution on all six elements: after an even number of steps it is supported on even permutations, and after an odd number on odd permutations. Fourier analysis exposes the obstruction as a nontrivial multiplier of absolute value 1. The conclusion is also visible directly from parity, providing an independent check.
Repair the walk by allowing it to stay still
Now stay at the current position with probability 1/2, and choose each transposition with probability 1/6. Call the new step distribution ν. Its irreducible multipliers are 1,0 and 1/2 for the trivial, sign and standard representations.
After k≥1 steps, inversion gives
ν*k(g) = [1 + 2·2−kχstd(g−1)]/6.
Therefore the identity has probability (1+4·2−k)/6; each transposition has probability 1/6; and each 3-cycle has probability (1−2·2−k)/6. At k=1 this gives 1/2,1/6 and 0 respectively, exactly the specified step distribution.
At k=2 the identity probability is 1/3, each transposition still has probability 1/6, and each 3-cycle has probability 1/12. The total is 1/3+3/6+2/12=1. As k increases, every value approaches 1/6.
Quantify the remaining error
The total variation distance from uniform is half the sum of the absolute probability differences. For the distribution just calculated, only the identity and the two 3-cycles contribute. The identity excess is 4·2−k/6, and each 3-cycle deficit is 2·2−k/6.
Consequently the distance is (2/3)·2−k for k≥1. At one step it is 1/3; at two steps it is 1/6. This is an exact calculation for this particular walk, not a universal convergence formula for all random walks on S3 or other groups.
The example completes the modelling cycle. We specified allowed moves, translated them into representation blocks, diagnosed periodicity, changed the move rule, computed the new distribution and checked the answer in probability space.
A Fourier transform is not automatically a fast algorithm
The direct definition computes N terms for every matrix entry. Since Σdρ²=N, a naive implementation with representation matrices already available uses on the order of N² scalar accumulation operations. Merely naming the transform does not make the computation faster.
A fast algorithm needs additional structure: factorisation of a cyclic length, subgroup decompositions, sparse support, repeated use of the same basis, or another exploitable pattern. Even then, producing all N output coordinates requires representing N pieces of data. Block diagonalisation can make a repeated calculation economical without making every one-off calculation economical.
Separate three questions: does the transform exist, can its blocks be constructed conveniently, and does using it lower the cost of this particular task? The first is a theorem. The second and third are algorithm-design questions.
Numerical verification without hiding convention errors
For a small group, first verify the group table and every generator relation exactly. Then test δa*δb=δab, transform and reconstruct arbitrary sample functions, and compare convolution computed by both routes. A Plancherel check tests a different aspect of the implementation and should accompany the round trip.
For floating-point matrices, report a residual such as the largest absolute reconstruction error rather than asserting exact equality. Test more than class functions: central inputs can conceal multiplication-order bugs because their blocks are scalar. The noncentral example δs−δrs is useful precisely because it forces the matrix structure to participate.
Do not repair a large residual by increasing tolerance before checking conventions. A missing factor N can produce a stable but completely wrong answer. A transposed multiplication order may pass every abelian test and fail immediately on S3.
Where the finite theory stops
The formulas here are finite sums. They do not require convergence theorems. Moving to the circle, compact Lie groups or noncompact groups introduces topology, measures, Hilbert spaces and potentially infinite-dimensional representations. Fourier expansion on the circle is a related but analytically richer setting. [2]
The field also matters. Complex finite-group representations are completely reducible; in characteristic dividing the group order, the same matrix-block decomposition is not available in this form. The modular representation guide explains what replaces it.
Finally, an ordinary Fourier transform of a data array is not by itself a quantum circuit. State preparation, unitary normalisation and measurement are additional questions. Keeping the boundaries visible makes the connections more useful, not less.
Practice: compute, diagnose and reconstruct
1. The two canonical constant-looking objects
Which function is the convolution identity, and which probability distribution sends f to its mean? Solution: δe is the identity because only y=e contributes. The uniform distribution u(g)=1/N gives (u*f)(x)=(1/N)Σyf(y−1x), which is the mean since y−1x runs through G.
2. A delta function on C4
Find the transform of δ1. Solution: only j=1 contributes, so the coefficients are (1,i,−1,−i). Inversion at j=1 adds four copies of 1 before dividing by 4. At other positions the roots cancel.
3. An alternating input
Transform (1,−1,1,−1). Solution: the result is (0,0,4,0). The smoothing filter q therefore maps it to zero. This identifies a nontrivial kernel vector and proves non-invertibility without computing a determinant.
4. Repeated smoothing
What is q*q for q=(1/2,1/4,0,1/4)? Solution: square its Fourier multipliers to obtain (1,1/4,0,1/4). Inverting gives (3/8,1/4,1/8,1/4). All entries are nonnegative and sum to 1, as required for convolution of probability distributions.
5. Count matrix coordinates
A finite group has four one-dimensional irreducibles and one two-dimensional irreducible. What group order does the dimension identity imply? Solution: 4·1²+2²=8. Counting only five characters would recover only the five-dimensional class-function space, not every function on eight elements.
6. Why the order matters
Compare δr*δs and δs*δr in S3. Solution: they are δrs and δsr. Because rs and sr differ, the functions differ. Their standard Fourier blocks are RS and SR respectively.
7. Detect a missing normalisation
A student reconstructs (8,4,0,12) from the transform of (2,1,0,3). What is the likely error? Solution: the inverse omitted its factor 1/4. The output has the right pattern but is four times too large. An energy check would show a factor of sixteen in squared norm.
8. Diagnose a random walk from one representation
Why does a sign multiplier of −1 obstruct convergence to uniform in the transposition walk? Solution: it becomes (−1)k, which never approaches zero. Uniform distribution has zero Fourier coefficient on the nontrivial sign representation. The coefficient therefore cannot converge to its required limiting value.
9. Use the exact distribution
In the lazy S3 walk, find the probability of a specified 3-cycle after three steps. Solution: substitute k=3 to obtain (1−2/8)/6=1/8. This is the probability of one specified cycle; the total over both 3-cycles is 1/4.
10. Decide what the transform has preserved
A full Fourier transform is stored, but every nontrivial block is then deleted. What remains? Solution: only the trivial block, which records the total of f. Inversion returns the constant mean function. The information loss occurred in deleting blocks, not in applying the full transform.
A teaching route that tests understanding rather than vocabulary
Begin with the four-position example and require both direct convolution and Fourier multiplication. Next change one input while keeping the filter fixed. Ask which part of the answer can be predicted before calculation. The learner should identify the preserved mean and the removed alternating pattern.
Then introduce S3 only after the learner can explain why scalar frequencies worked for C4. The key question is not whether the learner remembers the word non-abelian, but whether they can demonstrate a multiplication-order difference and explain why one matrix entry cannot replace a whole block.
Finish by comparing the periodic and lazy walks. Require an explanation in both languages: parity in position space, multipliers in Fourier space. Agreement between independent descriptions is the strongest local check in this lesson. The learner should leave able to reconstruct the original problem, not merely perform a transform detached from its meaning.
Mathematical references and further study
[1] Pavel Etingof and collaborators, Introduction to Representation Theory: finite-group representations, the regular representation, characters and semisimple algebra decompositions. [2] Constantin Teleman, Representation Theory: orthogonality, complete reducibility and the passage to compact-group Fourier analysis. The small filtering and random-walk calculations above are developed explicitly here so that their conventions and checks remain visible.
Continue Representation Mathematics — Batch 03
To organise irreducible permutation symmetries, continue to Symmetric Group Representations, Young Tableaux and Specht Modules. To study several spaces connected by linear maps, use Quiver Representations and Gabriel’s Theorem. To extract polynomial quantities unchanged by symmetry, use Invariant Theory, Reynolds Operators and Molien Series. Return to the BTT Mathematics Learning Hub for the complete route.