= Solution
Use $c>0$, the necessary parameter range for the bounds involving $1/c$. The construction comes from the <singular value decomposition> of <matrix Fourier blocks>. For each inequivalent <unitary irreducible representation> $\rho$ of <dimension> $d_\rho$, consider the <Hilbert space> $\mathcal H_\rho=M_{n\times d_\rho}(\mathbb C)$ with the <Hilbert-Schmidt inner product> $\langle A,B\rangle=\operatorname{tr}(A^*B)$ and the operator
$$
T_\rho(A)=\mathbb E_x f(x)A\rho(x)^*.
$$
Its <operator norm> is at most one, since $\rho(x)$ is a <unitary matrix> and $\|f(x)\|_{\mathrm{op}}\leq1$. Thus all its <singular values> $\lambda_{\rho,j}$ lie in $[0,1]$.
Two identities control their weighted moments:
$$
S_2=\sum_\rho d_\rho\sum_j\lambda_{\rho,j}^2
=\mathbb E_x\operatorname{tr}(f(x)f(x)^*)\leq n,
$$
$$
S_4=\sum_\rho d_\rho\sum_j\lambda_{\rho,j}^4
=\mathbb E_{xy^{-1}zw^{-1}=e}\operatorname{tr}(f(x)f(y)^*f(z)f(w)^*)\geq cn.
$$
Here the <expectation> in $S_4$ is uniform on the $|G|^3$ solutions of the constraint, and the <trace> on $\mathcal H_\rho$ used to compute each moment is the ordinary operator <trace>. We justify the identities explicitly to fix their normalizations and the noncommutative order.
The <adjoint operator> is $T_\rho^*(A)=\mathbb E_yf(y)^*A\rho(y)$, so
$$
T_\rho T_\rho^*(A)
=\mathbb E_{x,y}f(x)f(y)^*A\rho(yx^{-1}).
$$
For rectangular matrices, the operator $A\mapsto LAR$ has <trace> $\operatorname{tr}(L)\operatorname{tr}(R)$, as is seen on the matrix-unit <basis>. Squaring the previous operator therefore gives
$$
\begin{aligned}
\operatorname{Tr}_{\mathcal H_\rho}(T_\rho T_\rho^*)&=\mathbb E_{x,y}\operatorname{tr}(f(x)f(y)^*)\chi_\rho(yx^{-1}),\\
\operatorname{Tr}_{\mathcal H_\rho}((T_\rho T_\rho^*)^2)&=\mathbb E_{x,y,z,w}\operatorname{tr}(f(x)f(y)^*f(z)f(w)^*)\chi_\rho(wz^{-1}yx^{-1}).
\end{aligned}
$$
The required <representation theory> consists of <unitarization of a finite-group representation>, the <Schur orthogonality relations>, and the <regular representation> decomposition. The last gives the <character expansion of the identity delta>
$$
\sum_\rho d_\rho\chi_\rho(g)=|G|1_{\{g=e\}}.
$$
Summing the two operator <traces> with weights $d_\rho$ selects $x=y$ in the first, and $w=xy^{-1}z$ in the second. Multiplication by $|G|$ converts each independent-variable <expectation> to its conditional <expectation>. This proves $S_2,S_4$. In particular $S_4$ is real and nonnegative, despite the apparently complex summands in its original formula. Since $S_4\leq S_2\leq n$, the nonvacuous hypothesis has $0<c\leq1$.
Select every <singular value> satisfying $\lambda_{\rho,j}\geq\sqrt{c/2}$. Index the selected pairs by $p=1,\ldots,r$, set $\rho_p=\rho$, $n_p=d_\rho$, and choose unit <right singular vectors> $A_p$ and unit <left singular vectors> $B_p$ with $T_{\rho_p}A_p=\lambda_pB_p$. Define
$$
\boxed{U(p)=\sqrt{n_p}A_p,\qquad V(p)=\sqrt{n_p}B_p.}
$$
Both are $n\times n_p$ matrices, proving (i). Repeated <group representations> in this list are literally the same chosen representative, rather than different equivalent realizations.
Back to article page
