# Burnside Decomposition in Kuperberg's Hidden Shift

In "Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem", Kuperberg writes that $$\mathbb{C}[G]$$ has a "Burnside decomposition" of

$$\mathbb{C}[G]\cong \bigoplus_{V} V^*\otimes V$$

where each $$V$$ is an irreducible representation.

He defines $$\mathbb{C}[G]$$ as a Hilbert space with an orthonormal basis identified by $$G$$, a finite group. So $$\mathbb{C}[G]$$ is the span of $$\{\vert g\rangle :g\in G\}$$ for orthonormal vectors $$\vert g\rangle$$.

This means $$\mathbb{C}[G]$$ works naturally as the representation space of either the left-regular or right-regular representation of $$G$$. Thus, it makes sense to me that, letting $$V_i$$ be the representation spaces of different representations, we would have

$$\mathbb{C}[G]=\bigoplus_{i} V_i.$$

But I don't see why the tensor product appears. Even if we consider $$B(\mathbb{C}[G])$$, the set of operators on $$\mathbb{C}[G]$$, to get the density matrices on this Hilbert space, we would end up with vectors of the form $$v_j\otimes v_i$$, where $$v_j\in V_j$$ and $$v_i\in V_i$$ for $$i\neq j$$.

Alternatively, he may be identifying $$\mathbb{C}[G]$$ with the left- or right-regular representation itself, and then decomposing it into the representations, not the representation spaces. But this doesn't make sense to me either; $$V$$ is finite-dimensional, so $$V^*\otimes V\cong M_n$$ for some $$n$$, so this decomposition would imply that every irreducible representation of $$G$$ is isomorphic to $$M_n$$ for some $$n$$, which I don't think is true.

So what is this decomposition?

The second part of each tensor product serves as a multiplicity space. It might be more satisfying to write it as a full decomposition like your second one.

So you have $$\bigoplus V_\lambda \otimes V_\lambda^*$$ and you want it to look more like your second equation.

What would happen is each $$V_\lambda$$ would show up as a direct summand $$d_\lambda$$ times where $$d_\lambda$$ is the dimension of $$V_\lambda^*$$.

The tensor product there is as vector spaces with one of the factors being a bookkeeping device to say how many times that irreducible is a summand. It is not tensoring as representations that have to be broken down by further C-G coefficients.

More detail possible, but for a first pass just leave it at that. Don't take it beyond just conveniently keeping track of multiplicities.

Maschke's theorem

• Wouldn't that imply that $d_\lambda$ is also the dimension if $V_\lambda$? Does every irreducible representation really appear a number of times equal to its own dimension? – Sam Jaques Apr 15 at 14:45
• Have you seen the sum of squares formula in character tables? – AHusain Apr 15 at 15:01