2B Exercise 5: Convolutions

This exercise asks us to prove that if P is a probability measure on the finite group G, then P \star \bar{P} = U if and only if P = U. Here \star is the convolution product, U is the uniform probability on G defined by U(s) = 1/|G| for all s \in G and \bar{P} is defined by \bar{P}(s) = P(s^{-1}).

The `if’ direction is easy: just note that \bar{U} = U and U \star U =  U.

The `only if’ direction is a bit harder, and has a nice solution using the Fourier setup. The Fourier transform of \bar{P} at the representation \rho is

\hat{\bar{P}}(\rho) = \sum_{s \in G} P(s^{-1}) \rho(s) = \sum_{s \in G} P(s) \rho(s^{-1}).

If \rho is unitary, then \rho(s^{-1}) = \rho(s)^\star for all s \in G (where X^\star is the transposed complex conjugate of the matrix X). Hence

\hat{\bar{P}}(\rho) =  \hat{P}(\rho)^\star.

Hence, taking the Fourier transform of P \star \bar{P} = U at a non-trivial unitary irreducible representation \rho, we get

\hat{P}(\rho) \hat{P}(\rho)^\star = \hat{U}(\rho) = 0.

But if X is a complex matrix such that X X^\star = 0 then X = 0. So we’ve shown that \hat{P}(\rho) = 0 for all unitary irreducible representations \rho. Moreover, since P is a probability measure,

\hat{P}(1) = \sum_{s \in G} P(s) = 1.

So the Fourier transform of P agrees with the Fourier transform of U on all unitary irreducible representations. Any representation is equivalent to a direct sum of such representations, so by the Fourier Inversion Theorem, P = U.


One Response to 2B Exercise 5: Convolutions

  1. mwildon says:

    I’m adding this comment to record a simpler way to do the exercise, suggested by Jon Barrett.

    From P \star \bar{P} = U we have

    \sum_{s \in G} P(s) P(g^{-1}s) = \frac{1}{|G|}

    for all g \in G. Putting g=1 gives

    \sum_{s \in G} P(s)^2 = \frac{1}{|G|}.

    The Cauchy–Schwarz inequality applied to the dot-product of the all ones vector and the vector with entries P(s) for s \in G shows that

    |G| \sum_{s \in G}P(s)^2 \ge \Bigl( \sum_{s\in G}P(s) \Bigr)^2 = 1.

    So we have equality in the Cauchy–Schwarz inequality, and so all the P(s) must be equal.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: