This is a continuation of my question asked here.
I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations. In Definition 2, the authors start with the following function.
$$ f : G \to \mathbb{C} $$
Then the Fourier transform of $f$ at the irrep $\rho$ is defined as the $d_\rho \times d_\rho$ matrix:
$$ \hat{f}(\rho) = \sqrt{\frac{d_\rho}{|G|}} \sum_{g \in G} f (g) \rho(g) $$
In the quantum computational settings, the authors identify the superposition $\sum_{g \in G} f_g |g\rangle$ ($|a\rangle$ is a quantum state which is the $a$-th computational basis vector), with the function $f:G\to\mathbb{C}$ defined by $f(g) = f_g$.
In this notation, $\sum_{g \in G} f(g)|g\rangle$ is mapped under the Fourier transform to $\sum_{\rho \in \hat{G}, 1\le i,j \le d_\rho} \hat{f}(\rho)_{i,j} |\rho, i, j\rangle$.
$(\rho, i, j)$ is the label of the $(\rho, i, j)$-th computational basis vector $|\rho, i, j\rangle$. $\hat{f}(\rho)_{i,j}$ is a complex number and the $(i,j)$-th element of the matrix $\hat{f}(\rho)$. $\hat{G}$ is the collection of all irreps of $G$.
Then the authors say as follows.
When the first portion of this triple is measured, we observe $\rho \in \hat{G}$ with probability
$$ \sum_{1\le i,j\le d_\rho} |\hat{f}(\rho)_{i,j}|^2 = ||\hat{f}(\rho)||^2\\ = tr ((\hat{f}(\rho))^* \hat{f}(\rho)) $$
Here, ($\rho, i, j$) is the triple the authors are referring to. Measuring $\rho$ means measuring the qubits which encode the label $\rho$.
I understand up to this part. Then in Section 3, right after Equation 2, the authors go on saying:
$$ ||\hat{f}(\rho)||^2 = ||\sqrt{\frac{d_\rho}{|G|}} \sum_{h\in H} \rho(h)||^2 $$
I know that $\rho$ may not be an irrep for $H$. But, the matrix elements in $\hat{f}(\rho)$ comes from the direct sum of the matrices $\rho(h)$. I assume the previous equation works because of the Equation (2) in the paper.
I do not understand from here. The equation written by the authors is as follows:
$$ ||\hat{f}(\rho)||^2 = ||\sqrt{\frac{d_\rho}{|G|}} \sum_{h\in H} \rho(h)||^2\\ = \frac{d_\rho}{|G|} \frac{1}{|H|} |H|^2 \langle \chi_\rho, \chi_{1_H} \rangle_H \\= \frac{|H|}{|G|} d_\rho \langle \chi_\rho, \chi_{1_H} \rangle_H $$
Here, $\chi_{1_H} $ is the character of the trivial representation of the subgroup $H$.
My question:
Why is $||\sum_{h\in H} \rho (h)||^2 = \frac{1}{|H|} |H|^2 \langle \chi_\rho, \chi_{1_H} \rangle_H$? According to the definition of the Frobenius Norm, it should be like $||\sum_{h\in H} \rho (h)||^2 = Tr \left(\left(\sum_{h\in H} \rho (h)\right)\left(\sum_{h\in H} \rho (h)\right)^\dagger\right)$. I do not understand the following relationship.
$$ Tr \left(\left(\sum_{h\in H} \rho (h)\right)\left(\sum_{h\in H} \rho (h)\right)^\dagger\right) = \frac{1}{|H|} |H|^2 \langle \chi_\rho, \chi_{1_H} \rangle_H $$
It's important that on the first page the paper states that, without loss of generality, all of their irreducible representations are unitary, so that $\rho(g)^\dagger=\rho(g)^{-1}$ for all $g\in G$.
By the way, the beginning of section $3$ is in error. The sum $\sum_{h\in H}\rho(h)$ is not a projection, because it is not normalized correctly. Instead, $|H|^{-1}\sum_{h\in H}\rho(h)$ is the projection:
$$\left(\frac{1}{|H|}\sum_{h\in H}\rho(h)\right)^2=\frac{1}{|H|^2}\sum_{h_1,h_2\in H} \rho(h_1 h_2)=\frac{1}{|H|}\sum_{h\in H}\rho(h)$$
because $h_1h_2=h$ has $|H|$ solutions $(h_1,h_2)\in H\times H$.
Next, I am not sure why the bottom of the page introduces $\sqrt{d_\rho/|G|}$. According to the definition of the Fourier transform on the previous page, one introduces this constant when transforming from an initially given function $f:G\to\mathbb{C}$ to $\widehat{f}$. However section $3$ begins by defining $\widehat{f}$ to be a certain projection operator (at least it wanted to it seems), so there's no need for that constant.
Thus, let's just talk about the projection map $\widehat{f}(\rho)=|H|^{-1}\sum_{h\in H}\rho(h)$. We have
$$\begin{array}{ll} \|\widehat{f}(\rho)\|^2 & \displaystyle =\left\|\frac{1}{|H|}\sum_{h\in H}\rho(h)\right\|^2 \\ & \displaystyle =\frac{1}{|H|^2}\mathrm{tr}\left(\sum_{h_1\in H}\rho(h_1)\right)\left(\sum_{h_2\in H}\rho(h_2)\right)^\dagger \\ & \displaystyle =\frac{1}{|H|^2}\mathrm{tr}\sum_{h_1,h_2\in H}\rho(h_1h_2^{-1}) \\ & \displaystyle =\frac{1}{|H|}\sum_{h\in H}\chi(h), \end{array}$$
again because $h_1h_2^{-1}=h$ has $|H|$ solutions $(h_1,h_2)\in H\times H$. The above is $\langle \chi,\chi_{1_H}\rangle_H$.
The inner product $\langle \chi,\psi\rangle_H=\frac{1}{|H|}\sum_{h\in H}\chi(h)\overline{\psi(h)}$ on characters can be used to sift for the multiplicities of irreps within a given rep. Suppose that $V$ is a complex representation of $H$, and that $V\cong \bigoplus_{X\in\widehat{H}}X^{\oplus m(X)}$ is $V$'s decomp into irreps $X\in\widehat{H}$ with multiplicities $m(X)$. Then for a fixed irrep $Y$, because $\hom$ distributes over $\oplus$, we have
$$\begin{array}{ll} \hom_H(V,Y) & \displaystyle =\hom_H\left(\sum_{X\in\widehat{H}} X^{\oplus m(X)},Y\right) \\ & \displaystyle \cong\bigoplus_{X\in\widehat{H}} \hom_H(X,Y)^{\oplus m(X)} \\ & \displaystyle \cong \mathbb{C}^{\oplus m(Y)} \end{array}$$
This follows since, by Schur's lemma, $\hom_H(X,Y)\cong\mathbb{C}$ if $X=Y$ and is $0$ otherwise (when $X,Y$ are irreps of $H$). On the other hand, $\hom(V,Y)$, as a representation of $H$, is isomorphic to the tensor product $V^*\otimes Y$ (a special case of tensor-hom adjunction, the linearization of currying), and so $\dim\hom_H(V,Y)\cong\dim(V^*\otimes Y)^H$. But if $Z$ is an $H$-rep, the dimension of $Z^H$ is just the trace of any projection operator $Z\to Z^H$, which we know $|H|^{-1}\sum_{h\in H}\rho_Z(h)$ is, so applying this with $Z=V^*\otimes Y$ yields $m(Y)=|H|^{-1}\sum_{h\in H}\overline{\chi_V(h)}\chi_Y(h)=\langle \chi_Y,\chi_V\rangle$.
In response to comment thread:
For example, suppose $H=\langle\omega\rangle=\{1,\omega,\omega^2\}$ is the group of $3$rd roots of unity. If we write
$$\sum_{h_2\in H}\rho(h_2)=\rho(1)+\rho(\omega)+\rho(\omega^2)$$
and set $h_1=\omega$, then we have
$$\sum_{h_2\in H}\rho(h_1h_2)=\rho(\omega)+\rho(\omega^2)+\rho(1).$$
It's the same sum, only permuted. Therefore,
$$\sum_{h_1\in H}\left(\sum_{h_2\in H}\rho(h_1h_2)\right)=\left(\color{Purple}{\sum_{h_2\in H}\rho(h_2)}\right)+\left(\color{Blue}{\sum_{h_2\in H}\rho(\omega h_2)}\right)+\left(\color{Green}{\sum_{h_2\in H}\rho(\omega^2 h_2)}\right)$$
$$=\begin{array}{ccccc} & \color{Purple}{\rho(1)} & \color{Purple}{+} & \color{Purple}{\rho(\omega)} & \color{Purple}{+} & \color{Purple}{\rho(\omega^2)} \\ + & \color{Blue}{\rho(\omega)} & \color{Blue}{+} & \color{Blue}{\rho(\omega^2)} & \color{Blue}{+} & \color{Blue}{\rho(1)} \\ + & \color{Green}{\rho(\omega^2)} & \color{Green}{+} & \color{Green}{\rho(1)} & \color{Green}{+} & \color{Green}{\rho(\omega)} \end{array} \quad =3\big[\rho(1)+\rho(\omega)+\rho(\omega^2)\big]$$