For an $n$-by-$n$ unitary matrix $U$ and a permutation $\sigma\in S\_n$, let
$$w\_\sigma=(-1)^\sigma\det(U^\*)\prod\_{i=1}^n U\_{i,\sigma(i)}.$$
Is $\int\_{U(n)}\mathrm{Re}(w\_{\sigma\_1})\mathrm{Re}(w\_{\sigma\_2})dU\ge 0$ for all $\sigma\_1,\sigma\_2\in S\_n$?




---


The integral can be expanded to
$$\frac{1}{4}\int\_{U(n)} (w\_{\sigma\_1}+\bar w\_{\sigma\_1})(w\_{\sigma\_2}+\bar w\_{\sigma\_2})dU=\frac{1}{2}\int\_{U(n)} w\_{\sigma\_1}w\_{\sigma\_2}+w\_{\sigma\_1}\bar w\_{\sigma\_2}dU.$$
Once the $\det(U^\*)$ factors have been expanded as sums over permutations, this can be evaluated using Weingarten functions (see [Collins 2003](https://arxiv.org/abs/math-ph/0205010)). The latter term is
\begin{align}\int\_{U(n)} w\_{\sigma\_1}\bar w\_{\sigma\_2}dU&=(-1)^{\sigma\_1\sigma\_2}\int\_{U(n)}U\_{1\sigma\_1(1)}\cdots U\_{n\sigma\_1(n)}U^\*\_{\sigma\_2(1)1}\cdots U^\*\_{\sigma\_2(n)n}dU\\
&=(-1)^{\sigma\_1\sigma\_2}Wg(\sigma\_2^{-1}\sigma\_1,n).\end{align}
By [Novak 2010](https://eudml.org/doc/281749), the element $\sum\_\sigma Wg(\sigma,n)\sigma$ of the group algebra $\mathbb{C}[S\_n]$ can be written as a product of elements $(n+J\_k)^{-1}$ of the form $\sum\_\sigma (-1)^\sigma|a\_\sigma|\sigma$, hence $(-1)^\sigma Wg(\sigma,n)\ge 0$. Computer experiments suggest the former term is nonnegative as well, but I haven't been able to prove it.


Note that $\int\_{U(n)}\mathrm{Re}(w\_\sigma)dU=1/n!$ by a symmetry argument (see [here](https://math.stackexchange.com/q/3216137)).




---


I can show that
$$I\_{\sigma\_1,\sigma\_2}=\frac{1}{n!(n+1)!}\sum\_{\pi\in C}\sum\_{\tau\_1,\tau\_2\in R}(-1)^{\sigma\pi} [\tau\_1\pi\tau\_2=\sigma],$$
where $C$ and $R$ are the Young subgroups $\mathrm{Sym}(1,\dots,n)\times\mathrm{Sym}(n+1,\dots,2n)$ and $\mathrm{Sym}(1,n+1)\times\cdots\times\mathrm{Sym}(n,2n)$ respectively and $\sigma=\sigma\_1\oplus\sigma\_2\in C$. Is there a way to link this with Carlo's formula or otherwise show it's nonnegative?


**Proof:** By expanding the $\det U^\*$ factors and applying Weingarten functions,
\begin{align\*}
I\_{\sigma\_1,\sigma\_2}&=(-1)^{\sigma\_1\sigma\_2}\sum\_{\pi\_1,\pi\_2}(-1)^{\pi\_1\pi\_2}\int\_{U(n)}\prod\_{i=1}^n U\_{i\sigma\_1(i)}U\_{i\sigma\_2(i)}U^\*\_{\pi\_1(i)i}U^\*\_{\pi\_2(i)i}dU\\
&=(-1)^{\sigma}\sum\_{\pi\in C}(-1)^{\pi}\sum\_{\tau\_1,\tau\_2\in R}Wg(\sigma^{-1}\tau\_1\pi\tau\_2,n)\\
&=(-1)^{\sigma}\sum\_{\lambda\vdash 2n}\frac{\chi^\lambda(1)^2}{(2n)!^2s\_{\lambda,n}(1)}\sum\_{\pi\in C}(-1)^{\pi}\sum\_{\tau\_1,\tau\_2\in R}\chi^\lambda(\sigma^{-1}\tau\_1\pi\tau\_2).
\end{align\*}
For each $\lambda$, $\chi^\lambda$ is being summed over cosets of $R$ and the dual character $\chi^{\lambda'}=\mathrm{sgn}\cdot\chi^\lambda$ is being summed over cosets of $C$. The sum of a character $\chi$ over a coset of a subgroup $H$ is $0$ unless $\mathrm{res}\_H\chi$ contains the trivial character with multiplicity at least $1$. By the Frobenius-Young correspondence, the only irreducible contained in both $\mathrm{ind}^{S\_{2n}}\_R 1$ and $\mathrm{ind}^{S\_{2n}}\_C \mathrm{sgn}$ is $\chi^\mu$ with multiplicity $1$, where $\mu=(2^n)$. Therefore,
$$c\_\lambda:=\sum\_{\pi\in C}(-1)^{\pi}\sum\_{\tau\_1,\tau\_2\in R}\chi^\lambda(\sigma^{-1}\tau\_1\pi\tau\_2)=\begin{cases}0 & \text{if }\lambda\neq\mu\\ c\_\mu&\text{if }\lambda=\mu.\end{cases}$$
Evaluating the above formula for the character of the regular representation yields
$$\chi^\mu(1)c\_\mu=\sum\_{\lambda\vdash 2n}\chi^\lambda(1)c\_\lambda=c\_{reg}=\sum\_{\pi\in C}(-1)^{\pi}\sum\_{\tau\_1,\tau\_2\in R}(2n)![\sigma^{-1}\tau\_1\pi\tau\_2=1].$$
It's easy to show with the hook-length formula that $\chi^\mu(1)=\frac{(2n)!}{n!(n+1)!}$ and even easier to show that there is only one semistandard Young tableau of shape $\mu$ with entries in $[n]$, so $s\_{\mu,n}(1)=1$.



Nonnegativity of an integral over the unitary group
Here is a proof of Carlo's formula for $I\_{\sigma\_1,\sigma\_2}$.


Firstly, one can sample the Haar-distributed $U\in U(n)$ as $U=\lambda V$ where $\lambda$ and $V$ are independent random variables. $\lambda\in U(1)$ is a Haar-distributed complex number of modulus one, and $V$ is a Haar-distributed element of $SU(n)$.
Now with these subtitutions we have
$$
w\_\sigma=\epsilon(\sigma)\ {\rm det}(\bar{\lambda}V^{\ast})\ \lambda^n\
\prod\_{i=1}^{n} V(i,\sigma(i))= \epsilon(\sigma)\ \prod\_{i=1}^{n} V(i,\sigma(i))
$$
where I used $\epsilon(\sigma)$ instead of $(-1)^{\sigma}$ for the sign of a permutation and, for better readability, I write matrices and tensors as $V(i,j)$ instead of $V\_{i,j}$, etc.


Thus, following the explanations for $SU(n)$ integration I gave here:
[How to constructively/combinatorially prove Schur-Weyl duality?](https://mathoverflow.net/questions/255492/how-to-constructively-combinatorially-prove-schur-weyl-duality/255853#255853)


we have that
$$
I\_{\sigma\_1,\sigma\_2}=\epsilon(\sigma\_1)\epsilon(\sigma\_2)
\int\_{SU(n)}\prod\_{i=1}^{n} V(i,\sigma\_1(i))\ \prod\_{i=1}^{n} V(i,\sigma\_2(i))\ dV
$$
$$
=\epsilon(\sigma\_1)\epsilon(\sigma\_2)\ c\_2\ \mathscr{D}^2
\ \ \left. \prod\_{i=1}^{n} V(i,\sigma\_1(i))\ \prod\_{i=1}^{n} V(i,\sigma\_2(i))\right|\_{V:=0}
$$
where
$$
c\_2=\frac{0!1!}{n!(n+1)!}
$$
and the "propagator" $\mathscr{D}$ is the differential operator
$$
\mathscr{D}={\rm det}(\partial V)=\frac{1}{n!}
\sum\_{a,b}\epsilon(a\_1,\ldots,a\_n)\epsilon(b\_1,\ldots,b\_n)
\frac{\partial}{\partial V(a\_1,b\_1)}\cdots
\frac{\partial}{\partial V(a\_n,b\_n)}\ .
$$
The sum is over all sequences of indices $a\_1,\ldots,a\_n,b\_1,\cdots,b\_n$
in $[n]:=\{1,\ldots,n\}$ and now $\epsilon$ is to be understood as the Levi-Civita tensor.


Then one computes the action of the two propagators $\mathscr{D}\times\mathscr{D}$ on the $2n$ legs
$$
\prod\_{i=1}^{n} V(i,\sigma\_1(i))\ \prod\_{i=1}^{n} V(i,\sigma\_2(i))
$$
as in basic applications of Wick's theorem in quantum field theory, namely by summing over Wick contractions. Here the sum is organized according to subsets $A\subset [n]$
corresponding to the legs in the first group
$$
\prod\_{i=1}^{n} V(i,\sigma\_1(i))
$$
selected by the first propagator $\mathscr{D}$. Let us denote $A=\{i\_1<\cdots<i\_k\}$
and $A^{c}=\{j\_1<\cdots< j\_{n-k}\}$. Then
$$
\mathscr{D}^2
\prod\_{i=1}^{n} V(i,\sigma\_1(i))\ \prod\_{i=1}^{n} V(i,\sigma\_2(i))
=\sum\_{A}
\left\{
\mathscr{D}\ V(i\_1,\sigma\_1(i\_1))\cdots V(i\_k,\sigma\_1(i\_k))\ 
V(j\_1,\sigma\_2(j\_1))\cdots V(j\_{n-k},\sigma\_2(j\_{n-k}))
\right\}
$$
$$
\times \left\{
\mathscr{D}\ V(j\_1,\sigma\_1(j\_1))\cdots V(j\_{n-k},\sigma\_1(j\_{n-k}))\ 
V(i\_1,\sigma\_2(i\_1))\cdots V(i\_{k},\sigma\_2(i\_{k}))
\right\}
$$
$$
=\sum\_{A}
\epsilon(i\_1,\ldots,i\_k,j\_1,\ldots,j\_{n-k})\ 
\epsilon(\sigma\_1(i\_1),\ldots,\sigma\_1(i\_k),\sigma\_2(j\_1),\ldots,\sigma\_2(j\_{n-k}))
$$
$$
\times\ \epsilon(j\_1,\ldots,j\_{n-k},i\_1,\ldots,i\_k)\ 
\epsilon(\sigma\_1(j\_1),\ldots,\sigma\_1(j\_{n-k}),\sigma\_2(i\_1),\ldots,\sigma\_2(i\_k))\ .
$$
The condition imposed on the set $A$ by these epsilon factors is that
$\sigma\_1(A)^{c}=\sigma\_2(A^{c})$ which is equivalent to $\sigma\_1(A)=\sigma\_2(A)$, i.e.,
$\sigma\_2^{-1}\circ\sigma\_1(A)=A$. This means that $A$ must be a union of cycle supports for
$\sigma\_2^{-1}\circ\sigma\_1$. Hence the number of $A$'s is $2$ at the power the number of such cycles, i.e., $2^{n-C}$ where $C$ is the Cayley distance between $\sigma\_1$ and $\sigma\_2$.


Finally all the terms add up with the same sign. Indeed
$$
\epsilon(\sigma\_1(i\_1),\ldots,\sigma\_1(i\_k),\sigma\_2(j\_1),\ldots,\sigma\_2(j\_{n-k}))=\epsilon(\rho)
$$
where (with hopefully understandable notations)
$$
\rho=(\sigma\_1\circ \sigma\_2^{-1}|\_{\sigma\_2(A)}\oplus Id\_{\sigma\_2(A)^c})\circ\sigma\_2\circ \tau
$$
with the $\tau$ denoting the shuffle permutation
$$
\tau=\left(
\begin{array}{cccccc}
1 & \cdots & k & k+1 & \cdots & n \\
i\_1 & \cdots & i\_k & j\_1 & \cdots & j\_{n-k}
\end{array}
\right)\ .
$$
we then have
$$
\epsilon(i\_1,\ldots,i\_k,j\_1,\ldots,j\_{n-k})\ 
\epsilon(\sigma\_1(i\_1),\ldots,\sigma\_1(i\_k),\sigma\_2(j\_1),\ldots,\sigma\_2(j\_{n-k}))
=\epsilon(\sigma\_1\circ \sigma\_2^{-1}|\_{\sigma\_2(A)}\oplus Id\_{\sigma\_2(A)^c})\ \epsilon(\sigma\_2)\ \epsilon(\tau)^2
$$
and likewise
$$
\epsilon(j\_1,\ldots,j\_{n-k},i\_1,\ldots,i\_k)\ 
\epsilon(\sigma\_1(j\_1),\ldots,\sigma\_1(j\_{n-k}),\sigma\_2(i\_1),\ldots,\sigma\_2(i\_k))=
\epsilon(\sigma\_1\circ \sigma\_2^{-1}|\_{\sigma\_2(A^c)}\oplus Id\_{\sigma\_2(A)})\ \epsilon(\sigma\_2)
$$
So the product of four epsilons gives
$$
\epsilon(\sigma\_1\circ \sigma\_2^{-1}|\_{\sigma\_2(A)}\oplus Id\_{\sigma\_2(A)^c})\ 
\epsilon(\sigma\_1\circ \sigma\_2^{-1}|\_{\sigma\_2(A^c)}\oplus Id\_{\sigma\_2(A)})
=\epsilon(\sigma\_1\circ \sigma\_2^{-1})=\epsilon(\sigma\_1)\epsilon(\sigma\_2)\ .
$$


