# Why is Frobenius norm related to the inner product of characters?

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$.

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]$$

• @Omar for instance, $(\sum_i a_i)^2=(\sum_i a_i)(\sum_j a_j)=\sum_{i,j}a_ia_j$. same idea. – arctic tern May 3 '16 at 6:07
• @Omar because for all $h\in H$, $\rho(h)$ appears as a summand in $\sum_{h_1,h_2\in H}\rho(h_1h_2)$ a total of $|H|$ times. If it helps, you can think of $x\mapsto h_1x$ as a bijection, hence $$\frac{1}{|H|^2}\sum_{h_1\in H}\left(\sum_{h_2\in H}\rho(h_1h_2)\right)=\frac{1}{|H|^2}\sum_{h_1\in H}\left(\sum_{h_2\in H}\rho(h_2)\right)=\frac{1}{|H|^2}|H|\sum_{h\in H}\rho(h)$$ – arctic tern May 3 '16 at 6:53
• I'll repeat what I said: "for all $h\in H$, $\rho(h)$ appears as a summand in $\sum_{h_1,h_2\in H}\rho(h_1h_2)$ a total of $|H|$ times." This is because we can write any particular $h$ in the form $h_1h_2$ with $h_1,h_2\in H$ a total of $|H|$ many ways. Equivalently, the map $H\times H\to H$ given by $(h_1,h_2)\mapsto h_1h_2$ is an $|H|$-to-$1$ function. I am running out of ways to say the same thing. Also see my previous comment: Do you get why, for any fixed $h_1$, we have $\sum_{h_2\in H}\rho(h_1h_2)=\sum_{h_2\in H}\rho(h_2)$? – arctic tern May 3 '16 at 19:49
• @OmarShehab Because for fixed $h_1$, the map $x\mapsto h_1x$ is a bijection on $H$, and so both sums have exactly the same summands, just possibly in a different order. – arctic tern May 4 '16 at 1:44
• For example, suppose $H$ is the fifth roots of unity generated by a primitive root $\zeta$. If we write $$\sum_{h_2\in H}\rho(h_2)=\rho(1)+\rho(\zeta)+\rho(\zeta^2)+\rho(\zeta^3)+\rho(\zeta^4),$$ and set $h_1=\zeta^2$, then we have $$\sum_{h_2\in H}\rho(h_1h_2)=\rho(\zeta^2)+\rho(\zeta^3)+\rho(\zeta^4)+\rho(1)+\rho(\zeta),$$ which is exactly the same sum, only with its summands permuted. – arctic tern May 4 '16 at 1:51