# Nonnegativity of an integral over the unitary group

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). 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, 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).

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

• WHat is the measure you use on the Unitary group to define the integral? – Mark Fischler May 7 at 18:46
• @MarkFischler The Haar measure, normalized so that $\int_{U(n)}dU=1$. – MTyson May 7 at 18:53
• for the record, when $n=2$ the integrals are $1/3$ for $\sigma=\{1,2\}$ and $1/6$ for $\sigma=\{2,1\}$. – Carlo Beenakker May 10 at 6:34
• also for the record, I checked that the integral is positive for all combinations of permutations for $n=2,3,4$; for $n=3$ the integrals take one of the three values $11/6!,19/6!,41/6!$, for $n=4$ the integrals take one of the five values $13/5040,17/20160,5/4032,41/6720,19/13440$. – Carlo Beenakker May 11 at 13:55
• @CarloBeenakker, what permutations are $\sigma = \{1, 2\}$ and $\sigma = \{2, 1\}$? Does the first map $1 \mapsto 1$ and $2 \mapsto 2$ and the second $1 \mapsto 2$ and $2 \mapsto 1$? – LSpice May 11 at 21:06

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?

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

• Thank you! Creutz 1978 has some nice pictures of the graphical calculus, if anyone is interested. Can this method also handle the nonnegativity of the $w_{\sigma_1}\bar w_{\sigma_2}$ terms, or do you think the degree-$n^2$ integrand will be too massive to evaluate? – MTyson May 13 at 20:25
• No thank You. As I explained in my two answers to the linked MO question about Schur-Weyl duality, and as you saw, one can indeed find a similar expression in the $w\bar{w}$ case. However, the price to pay via Cramer's rule is that each $\bar{U}$ now gives birth to $n-1$ new $U$'s and one has to compute the result of acting with $({\rm det}(\partial V))^n$ on an integrand of degree $n$. It might be doable with methods a la Creutz, e.g., if one can show the result is a sum of squares. Using these methods, Clebsch in 1861 did just that for $({\rm det}(\partial V))^n({\rm det}(V))^n$. – Abdelmalek Abdesselam May 14 at 14:50
• BTW computing $({\rm det}(\partial V))^n({\rm perm}(V))^n$ and showing it is nonzero for $n$ even, is a major open problem which in my opinion is what stands in the way of the geometric complexity program, see my MO answer: mathoverflow.net/questions/277408/… – Abdelmalek Abdesselam May 14 at 14:54
• I meant to say "on an integrand of degree $n^2$" not $n$. – Abdelmalek Abdesselam May 14 at 15:14
• this "sharing thing" is mighty generous and unexpected; – Carlo Beenakker May 14 at 20:12

This is not the requested proof, but it may give an indication how to arrive at one. As discussed in the OP, the unknown part of the expression is the integral $$I_{\sigma_1,\sigma_2}=\int_{U(n)} w_{\sigma_1}w_{\sigma_2}\,dU,\;\;w_\sigma=(-1)^\sigma\det(U^*)\prod_{i=1}^n U_{i,\sigma(i)}.$$ I have evaluated this for $$n$$ up to 5, using the intU package, and based on that data I surmise $$I_{\sigma_1,\sigma_2}= \frac{2^n}{2^{C}n!(n+1)!},$$ with $$C$$ the Cayley distance between $$\sigma_1$$ and $$\sigma_2$$ (the minimal number of transpositions needed to convert $$\sigma_1$$ into $$\sigma_2$$).

For example, when $$n=5$$ and $$\sigma_1=\{1,2,3,4,5\}$$, $$\sigma_2=\{2, 3, 4, 5, 1\}$$, one has $$C=4$$ and $$I=\frac{1}{43200}$$. For $$\sigma_2=\{1, 2, 3, 5, 4\}$$ one has $$C=1$$ and $$I=\frac{1}{5400}$$.

As a check, one should be able to verify that $$\sum_{\sigma_1,\sigma_2}I_{\sigma_1,\sigma_2}=\int_{U(n)}(\det U^\ast \det U)^2\,dU=1.$$

The number of permutations at Cayley distance $$C\in\{0,1,2,\ldots,n-1\}$$ from $$\{1,2,3,\ldots n\}$$ equals $$|s_{n,n-C}|$$, the absolute value of the Stirling number of the first kind. [Thank you, Martin Rubey.] So let us calculate $$\sum_{\sigma_1,\sigma_2}I_{\sigma_1,\sigma_2}=n!\sum_{C=0}^{n-1}\frac{2^n}{2^{C}n!(n+1)!}|s_{n,n-C}|,$$ which equals unity as far as I can check. So it all works out.

I find it remarkable that the integral of $$w_{\sigma_1}w_{\sigma_2}$$ has such a simple explicit expression, while the integral of $$w_{\sigma_1}\bar{w}_{\sigma_2}$$ has only an implicit expression in terms of a Weingarten function.

I don't understand the matrix integrals, but the sum in the last paragraph is easy to deal with. Here is a story to visualize the permutation groups. Imagine $$n$$ couples lined up in two lines in a hall, perhaps to dance. A permutation in $$C$$ permutes each line within itself, breaking up partnerships. A permutation in $$R$$ makes some couple switch places with each other. Note that every permutation in $$R$$ is an involution.

Let's first prove positivity. Let $$\tau_s$$ switch $$k_s$$ pairs of couples. If we are to have $$\tau_1 \sigma \tau_2 \in C$$, then each person who switches under $$\tau_1$$ must switch again until $$\tau_2$$ to get back to their original line. So $$k_1 = k_2$$ and $$(-1)^{\tau_1} = (-1)^{\tau_2}$$. This implies that $$(-1)^{\pi} = (-1)^{\tau_1 \sigma \tau_2}$$ and thus $$(-1)^{\sigma \pi}=1$$.

Now, let's compute the sum. Let $$T_s$$ be the set of indices $$k$$ for which $$\tau_s(k) = k+n$$. In order to have $$\tau_1 \sigma \tau_2 \in C$$, each person must cross the hall under $$\tau_1$$ if and only if they do under $$\tau_2$$. Looking at the people who start on the $$\{1,2,\ldots, n \}$$ side of the hall, we must have $$\sigma_2(T_1) = T_2$$. Looking at the people who start on the other side, we must also have $$\sigma_1(T_1) = T_2$$. Thus $$\sigma_1^{-1} \sigma_2 (T_1) = T_1$$. So $$T_1$$ is a union of orbits of $$\sigma_1^{-1} \sigma_2$$. Each such union of orbits has a unique compatible $$T_2$$, by the equation $$\sigma_1(T_1) = T_2$$, and each such $$(\tau_1, \tau_2)$$ determines a unique $$\pi$$ by $$\pi = \tau_1 \sigma \tau_2$$. So the number of nonzero terms is the number of subsets of orbits of $$\sigma_1^{-1} \sigma_2$$. The number of orbits is $$n-\ell_T(\sigma_1^{-1} \sigma_2)$$ where $$\ell_T$$ is the length with respect to the set of all reflections, so the sum is $$2^{n-\ell_T(\sigma_1^{-1} \sigma_2)}$$ as requested.