Suppose I want to compute a quantity of the type:

$\mathbb{E}\mathrm{tr}(AUBU^{\ast})$

where averaging is over Haar measure on the unitary group $\mathcal{U}(n)$ (one can of course consider higher order polynomials or other matrix ensembles etc.) and $A$, $B$ are some fixed matrices. Is there any standard technique for computing such averages? I'd guess people in random matrix theory or free probability compute such traces all the time, but I've been unable to find a reference. If it makes matters easier, I'm really interested in computing something for random projections (e.g. something of the form $\mathbb{E}\mathrm{tr}(APBP)$, where $P$ is a projection onto a random subspace), which of course reduces to computation of polynomials in $U$.

`$\mathbb E tr(A U B U^*)=tr(A) tr(B)/n$`

. Indeed, from the property of Haar measure, $\mathbb E(U B U^*)$ is a matrix that commutes with every unitary matrix, so that it a multiple of the identity matrix. It has the same as $B$, so $\mathbb E(U B U^*) = tr(B)/n 1$. – Mikael de la Salle May 15 '12 at 16:54