Return to Answer

Let me try to work this out, along the lines of a similar calculation in the orthogonal (rather than unitary) group.

We need the fourth-order tensor $$\int_{{\rm U}(n)}(U^m)_{ij}(\bar{U}^m)_{kl}\,dU=a_{m}(n)\delta_{ij}\delta_{kl}+b_{m}(n)\delta_{ik}\delta_{jl}+c_{m}(n)\delta_{il}\delta_{jk}$$ so that the required integral takes the form $$\int_{{\rm U}(n)}U^m X(U^\dagger)^m\,dU=a_{m}(n)X+b_{m}(n)\mathbb{1}\,{\rm tr}\,X+c_{m}(n)X^{\rm t} $$ [note: The OP does not have the transpose $X^{\rm t}$, but I don't see a priori why this term will not appear.]

Substitution $X=\mathbb{1}$ gives a first relation $$a_m(n)+nb_m(n)+c_m(n)=1$$ one more relation follows from application of theorem 2.1.b of Diaconis and Evans: $$n^2 a_m(n)+nb_m(n)+nc_m(n)=\int_{{\rm U}(n)}\,({\rm tr}\,U^m)({\rm tr}\,\bar{U}^m)\,dU={\rm min}\,(n,m)$$ [note: in a related MO posting I had $m$ instead of ${\rm min}\,(n,m)$, I have now corrected this oversight and apologize for the confusion it may have caused]

I need a third relation $$na_m(n)+nb_m(n)+n^2 c_m(n)=\int_{{\rm U}(n)}\,{\rm tr}\,(U^m\bar{U}^{m})\,dU$$

To evaluate this integral I write $U^m=V\Lambda^m V^\dagger$, with $\Lambda$ the diagonal matrix of eigenvalues of $U$ and $V\in{\rm U}(n)$ independent of $\Lambda$. I then first average over the $V$ matrices, which is easy because there are just four of them: $$\int_{{\rm U}(n)}\,{\rm tr}\,(V\Lambda^m V^\dagger\overline{V\Lambda^m V^\dagger})\,dV=\frac{1}{n(n+1)}\left[({\rm tr}\,\Lambda^m)({\rm tr}\,\bar{\Lambda}^m)+{\rm tr}\,(\Lambda^m\bar{\Lambda}^m)\right]=\frac{1}{n(n+1)}\left[({\rm tr}\,U^m)({\rm tr}\,\bar{U}^m)+n\right].$$ and then the remaining average can be evaluated using Diaconis and Evans:

$$\int_{{\rm U}(n)}\,{\rm tr}\,(U^m\bar{U}^{m})\,dU =\frac{n+{\rm min}\,(n,m)}{n(n+1)}$$

so now we have three equations with three unknowns and we're done:

$$a_m(n)= \frac{\min(n,m) \left(n (n+1)^2-1\right)-n \left(n^2+n+1\right)}{(n-1) n^2 (n+1) (n+2)}$$ $$b_m(n)= \frac{n \left(n (n+1)^2-1\right)-\min(n,m) \left(n^2+n+1\right)}{(n-1) n^2 (n+1) (n+2)}$$ $$c_m(n)= -\frac{\min(n,m) +n}{n^2 (n+2)}$$

Let me try to work this out, along the lines of a similar calculation in the orthogonal (rather than unitary) group.

We need the fourth-order tensor $$\int_{{\rm U}(n)}(U^m)_{ij}(\bar{U}^m)_{kl}\,dU=a_{m}(n)\delta_{ij}\delta_{kl}+b_{m}(n)\delta_{ik}\delta_{jl}+c_{m}(n)\delta_{il}\delta_{jk}$$ so that the required integral takes the form $$\int_{{\rm U}(n)}U^m X(U^\dagger)^m\,dU=a_{m}(n)X+b_{m}(n)\mathbb{1}\,{\rm tr}\,X+c_{m}(n)X^{\rm t} $$ [note: The OP does not have the transpose $X^{\rm t}$, but I don't see a priori why this term will not appear.]

Substitution $X=\mathbb{1}$ gives a first relation $$a_m(n)+nb_m(n)+c_m(n)=1$$ one more relation follows from application of theorem 2.1.b of Diaconis and Evans: $$n^2 a_m(n)+nb_m(n)+nc_m(n)=\int_{{\rm U}(n)}\,({\rm tr}\,U^m)({\rm tr}\,\bar{U}^m)\,dU={\rm min}\,(n,m)$$ [note: in a related MO posting I had $m$ instead of ${\rm min}\,(n,m)$, I have now corrected this oversight and apologize for the confusion it may have caused]

I need a third relation $$na_m(n)+nb_m(n)+n^2 c_m(n)=\int_{{\rm U}(n)}\,{\rm tr}\,(U^m\bar{U}^{m})\,dU$$

To evaluate this integral I write $U^m=V\Lambda^m V^\dagger$, with $\Lambda$ the diagonal matrix of eigenvalues of $U$ and $V\in{\rm U}(n)$ independent of $\Lambda$. I then first average over the $V$ matrices, which is easy because there are just four of them: $$\int_{{\rm U}(n)}\,{\rm tr}\,(V\Lambda^m V^\dagger\overline{V\Lambda^m V^\dagger})\,dV=\frac{1}{n+1}\left[({\rm tr}\,\Lambda^m)({\rm tr}\,\bar{\Lambda}^m)+{\rm tr}\,(\Lambda^m\bar{\Lambda}^m)\right]=\frac{1}{n+1}\left[({\rm tr}\,U^m)({\rm tr}\,\bar{U}^m)+n\right].$$ and then the remaining average can be evaluated using Diaconis and Evans:

$$\int_{{\rm U}(n)}\,{\rm tr}\,(U^m\bar{U}^{m})\,dU =\frac{n+{\rm min}\,(n,m)}{n+1}$$

so now we have three equations with three unknowns and we're done:

$$a_{m}(n)= \frac{\min(n,m) -1}{n^2-1}=1-nb_{m}(n),\;\;c_m(n)= 0$$

and $c_m(n)$ does in fact turn out to be equal to zero.

Let me try to work this out, along the lines of a similar calculation in the orthogonal (rather than unitary) group.

We need the fourth-order tensor $$\int_{{\rm U}(n)}(U^m)_{ij}(\bar{U}^m)_{kl}\,dU=a_{m}(n)\delta_{ij}\delta_{kl}+b_{m}(n)\delta_{ik}\delta_{jl}+c_{m}(n)\delta_{il}\delta_{jk}$$ so that the required integral takes the form $$\int_{{\rm U}(n)}U^m X(U^\dagger)^m\,dU=a_{m}(n)X+b_{m}(n)\mathbb{1}\,{\rm tr}\,X+c_{m}(n)X^{\rm t} $$ [note: The OP does not have the transpose $X^{\rm t}$, but I don't see a priori why this term will not appear.]

Substitution $X=\mathbb{1}$ gives a first relation $$a_m(n)+nb_m(n)+c_m(n)=1$$ one more relation follows from application of theorem 2.1.b of Diaconis and Evans: $$n^2 a_m(n)+nb_m(n)+nc_m(n)=\int_{{\rm U}(n)}\,({\rm tr}\,U^m)({\rm tr}\,\bar{U}^m)\,dU={\rm min}\,(n,m)$$ [note: in a related MO posting I had $m$ instead of ${\rm min}\,(n,m)$, I have now corrected this oversight and apologize for the confusion it may have caused]

I need a third relation $$na_m(n)+nb_m(n)+n^2 c_m(n)=\int_{{\rm U}(n)}\,{\rm tr}\,(U^m\bar{U}^{m})\,dU$$

To evaluate this integral I write $U^m=V\Lambda^m V^\dagger$, with $\Lambda$ the diagonal matrix of eigenvalues of $U$ and $V\in{\rm U}(n)$ independent of $\Lambda$. I then first average over the $V$ matrices, which is easy because there are just four of them, and then the remaining average over $\Lambda$ can be evaluated using Diaconis and Evans:

$$\int_{{\rm U}(n)}\,{\rm tr}\,(U^m\bar{U}^{m})\,dU =\frac{1}{n+1}+\frac{1}{n(n+1)}\int_{{\rm U}(n)}\,({\rm tr}\,U^m)({\rm tr}\,\bar{U}^{m})\,dU=\frac{n+{\rm min}\,(n,m)}{n(n+1)}$$

so now we have three equations with three unknowns and we're done:

$$a_m(n)= \frac{\min(n,m) \left(n (n+1)^2-1\right)-n \left(n^2+n+1\right)}{(n-1) n^2 (n+1) (n+2)}$$ $$b_m(n)= \frac{n \left(n (n+1)^2-1\right)-\min(n,m) \left(n^2+n+1\right)}{(n-1) n^2 (n+1) (n+2)}$$ $$c_m(n)= -\frac{\min(n,m) +n}{n^2 (n+2)}$$

Let me try to work this out, along the lines of a similar calculation in the orthogonal (rather than unitary) group.

We need the fourth-order tensor $$\int_{{\rm U}(n)}(U^m)_{ij}(\bar{U}^m)_{kl}\,dU=a_{m}(n)\delta_{ij}\delta_{kl}+b_{m}(n)\delta_{ik}\delta_{jl}+c_{m}(n)\delta_{il}\delta_{jk}$$ so that the required integral takes the form $$\int_{{\rm U}(n)}U^m X(U^\dagger)^m\,dU=a_{m}(n)X+b_{m}(n)\mathbb{1}\,{\rm tr}\,X+c_{m}(n)X^{\rm t} $$ [note: The OP does not have the transpose $X^{\rm t}$, but I don't see a priori why this term will not appear.]

Substitution $X=\mathbb{1}$ gives a first relation $$a_m(n)+nb_m(n)+c_m(n)=1$$ one more relation follows from application of theorem 2.1.b of Diaconis and Evans: $$n^2 a_m(n)+nb_m(n)+nc_m(n)=\int_{{\rm U}(n)}\,({\rm tr}\,U^m)({\rm tr}\,\bar{U}^m)\,dU={\rm min}\,(n,m)$$ [note: in a related MO posting I had $m$ instead of ${\rm min}\,(n,m)$, I have now corrected this oversight and apologize for the confusion it may have caused]

I need a third relation $$na_m(n)+nb_m(n)+n^2 c_m(n)=\int_{{\rm U}(n)}\,{\rm tr}\,(U^m\bar{U}^{m})\,dU$$

To evaluate this integral I write $U^m=V\Lambda^m V^\dagger$, with $\Lambda$ the diagonal matrix of eigenvalues of $U$ and $V\in{\rm U}(n)$ independent of $\Lambda$. I then first average over the $V$ matrices, which is easy because there are just four of them: $$\int_{{\rm U}(n)}\,{\rm tr}\,(V\Lambda^m V^\dagger\overline{V\Lambda^m V^\dagger})\,dV=\frac{1}{n(n+1)}\left[({\rm tr}\,\Lambda^m)({\rm tr}\,\bar{\Lambda}^m)+{\rm tr}\,(\Lambda^m\bar{\Lambda}^m)\right]=\frac{1}{n(n+1)}\left[({\rm tr}\,U^m)({\rm tr}\,\bar{U}^m)+n\right].$$ and then the remaining average can be evaluated using Diaconis and Evans:

$$\int_{{\rm U}(n)}\,{\rm tr}\,(U^m\bar{U}^{m})\,dU =\frac{n+{\rm min}\,(n,m)}{n(n+1)}$$

so now we have three equations with three unknowns and we're done:

$$a_m(n)= \frac{\min(n,m) \left(n (n+1)^2-1\right)-n \left(n^2+n+1\right)}{(n-1) n^2 (n+1) (n+2)}$$ $$b_m(n)= \frac{n \left(n (n+1)^2-1\right)-\min(n,m) \left(n^2+n+1\right)}{(n-1) n^2 (n+1) (n+2)}$$ $$c_m(n)= -\frac{\min(n,m) +n}{n^2 (n+2)}$$

Let me try to work this out, along the lines of a similar calculation in the orthogonal (rather than unitary) group.

We need the fourth-order tensor $$\int_{{\rm U}(n)}(U^m)_{ij}(\bar{U}^m)_{kl}\,dU=a_{m}(n)\delta_{ij}\delta_{kl}+b_{m}(n)\delta_{ik}\delta_{jl}+c_{m}(n)\delta_{il}\delta_{jk}$$ so that the required integral takes the form $$\int_{{\rm U}(n)}U^m X(U^\dagger)^m\,dU=a_{m}(n)X+b_{m}(n)\mathbb{1}\,{\rm tr}\,X+c_{m}(n)X^{\rm t} $$ [note: The OP does not have the transpose $X^{\rm t}$, but I don't see a priori why this term will not appear.]

Substitution $X=\mathbb{1}$ gives a first relation $$a_m(n)+nb_m(n)+c_m(n)=1$$ one more relation follows from application of theorem 2.1.b of Diaconis and Evans: $$n^2 a_m(n)+nb_m(n)+nc_m(n)=\int_{{\rm U}(n)}\,({\rm tr}\,U^m)({\rm tr}\,\bar{U}^m)\,dU={\rm min}\,(n,m)$$ [note: in a related MO posting I had $m$ instead of ${\rm min}\,(n,m)$, I have now corrected this oversight and apologize for the confusion it may have caused]

I need a third relation $$na_m(n)+nb_m(n)+n^2 c_m(n)=\int_{{\rm U}(n)}\,{\rm tr}\,(U^m\bar{U}^{m})\,dU$$

as an intermezzo, suppose as in the OP that there is no term $X^{\rm t}$, so $c_{m}=0$. Then $nb_m=1-a_m$ and $a_m= [{\rm min}\,(n,m)-1](n^2-1)^{-1}\equiv p\in[0,1]$ so the inconsistency noted by the OP does not appear; still, I'm don't see why $c_m$ would vanish.

continuing with the required integral:

$$\int_{{\rm U}(n)}\,{\rm tr}\,(U^m\bar{U}^{m})\,dU =\frac{1}{n+1}+\frac{1}{n(n+1)}\int_{{\rm U}(n)}\,({\rm tr}\,U^m)({\rm tr}\,\bar{U}^{m})\,dU=\frac{n+{\rm min}\,(n,m)}{n(n+1)}$$

so now we have three equations with three unknowns and we're done:

$$a_m(n)= \frac{\min(n,m) \left(n (n+1)^2-1\right)-n \left(n^2+n+1\right)}{(n-1) n^2 (n+1) (n+2)}$$ $$b_m(n)= \frac{n \left(n (n+1)^2-1\right)-\min(n,m) \left(n^2+n+1\right)}{(n-1) n^2 (n+1) (n+2)}$$ $$c_m(n)= -\frac{\min(n,m) +n}{n^2 (n+2)}$$

Let me try to work this out, along the lines of a similar calculation in the orthogonal (rather than unitary) group.

We need the fourth-order tensor $$\int_{{\rm U}(n)}(U^m)_{ij}(\bar{U}^m)_{kl}\,dU=a_{m}(n)\delta_{ij}\delta_{kl}+b_{m}(n)\delta_{ik}\delta_{jl}+c_{m}(n)\delta_{il}\delta_{jk}$$ so that the required integral takes the form $$\int_{{\rm U}(n)}U^m X(U^\dagger)^m\,dU=a_{m}(n)X+b_{m}(n)\mathbb{1}\,{\rm tr}\,X+c_{m}(n)X^{\rm t} $$ [note: The OP does not have the transpose $X^{\rm t}$, but I don't see a priori why this term will not appear.]

Substitution $X=\mathbb{1}$ gives a first relation $$a_m(n)+nb_m(n)+c_m(n)=1$$ one more relation follows from application of theorem 2.1.b of Diaconis and Evans: $$n^2 a_m(n)+nb_m(n)+nc_m(n)=\int_{{\rm U}(n)}\,({\rm tr}\,U^m)({\rm tr}\,\bar{U}^m)\,dU={\rm min}\,(n,m)$$ [note: in a related MO posting I had $m$ instead of ${\rm min}\,(n,m)$, I have now corrected this oversight and apologize for the confusion it may have caused]

I need a third relation $$na_m(n)+nb_m(n)+n^2 c_m(n)=\int_{{\rm U}(n)}\,{\rm tr}\,(U^m\bar{U}^{m})\,dU$$

To evaluate this integral I write $U^m=V\Lambda^m V^\dagger$, with $\Lambda$ the diagonal matrix of eigenvalues of $U$ and $V\in{\rm U}(n)$ independent of $\Lambda$. I then first average over the $V$ matrices, which is easy because there are just four of them, and then the remaining average over $\Lambda$ can be evaluated using Diaconis and Evans:

$$\int_{{\rm U}(n)}\,{\rm tr}\,(U^m\bar{U}^{m})\,dU =\frac{1}{n+1}+\frac{1}{n(n+1)}\int_{{\rm U}(n)}\,({\rm tr}\,U^m)({\rm tr}\,\bar{U}^{m})\,dU=\frac{n+{\rm min}\,(n,m)}{n(n+1)}$$

so now we have three equations with three unknowns and we're done:

$$a_m(n)= \frac{\min(n,m) \left(n (n+1)^2-1\right)-n \left(n^2+n+1\right)}{(n-1) n^2 (n+1) (n+2)}$$ $$b_m(n)= \frac{n \left(n (n+1)^2-1\right)-\min(n,m) \left(n^2+n+1\right)}{(n-1) n^2 (n+1) (n+2)}$$ $$c_m(n)= -\frac{\min(n,m) +n}{n^2 (n+2)}$$