# 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

In the paper I called it the Burnside decomposition, but it looks like the standard name is the Wedderburn decomposition. That might simply have been a mistake in terminology on my part.

Anyway, there are two good ways to get the summands to be $$V \otimes V^*$$. (Of course they are closely related.)

1) You can interpret $$\mathbb{C}[G]$$ as an associative algebra. In this case, the theorem is that $$\mathbb{C}[G]$$ is a direct sum of matrix algebras, one for each irrep $$V$$ of $$G$$. You can identify the vector space of operators on $$V$$ with $$V \otimes V^*$$. This interpretation motivates the terminology which is sometimes used that $$V$$ is the "column space" and $$V^*$$ is the "row space".

2) You can interpret $$\mathbb{C}[G]$$ as a bimodule with both a left and right $$G$$ action. In this case each summand can be read as $$V_{\text{left}} \otimes V^*_{\text{right}}$$. By definition $$G_\text{left}$$ acts trivially on $$V^*_{\text{right}}$$ and vice versa, so that each of the two tensor factors is the multiplicity space for the opposite action.

The bimodule picture also shows up in other cases such as Schur-Weyl duality. In the case of Schur-Weyl duality, both $$\text{GL}(V)$$ (or $$U(V)$$ if you want to be quantum) and $$S_n$$ act on $$V^{\otimes n}$$. You again get this cool decomposition into summands $$M_\lambda \otimes V_\lambda$$, where $$M_\lambda$$ is an irrep of $$S_n$$, $$V_\lambda$$ is an irrep of $$\text{GL}(V)$$ or $$U(V)$$, and each tensor factor is the multiplicity space of the action of the other group.