# Sampling Haar over two systems

Say $$M$$ is a matrix acting on $$C^r \otimes C^s$$. $$X$$ is the system of dimension $$r$$, and $$Y$$ is the system of dimension $$s$$.

With $$|\psi\rangle$$ sampled from Haar, how can we show that $$\int (I_r \otimes \langle\psi|) A (I_r \otimes |\psi\rangle) \, \mathrm{d}\psi = s^{-1} \, Tr_Y(A)$$

where $$I_r$$ denotes the $$r \times r$$ identity matrix, and $$Tr_Y(\cdot)$$ denotes tracing out the $$Y$$ system.

I would choose to think of $$|\psi\rangle$$ as $$U|0\rangle$$ where $$U$$ is any unitary. But, I can also think of it as $$U'|1\rangle$$, or $$U''|2\rangle,\ldots$$. Hence, I can write this as \begin{align*} \int(I_r\otimes\langle\psi|)A(I_r\otimes|\psi\rangle)d\psi&=\frac{1}{s}\sum_{i=1}^s\int(I_r\otimes\langle i|U^\dagger)A(I_r\otimes U|i\rangle)dU \\ &=\frac{1}{s}\sum_{i=1}^s\int\text{Tr}_Y\left(A(I_r\otimes U|i\rangle)(I_r\otimes\langle i|U^\dagger)\right)dU \\ &=\frac{1}{s}\sum_{i=1}^s\int\text{Tr}_Y\left(A(I_r\otimes U|i\rangle\langle i|U^\dagger)\right)dU \\ &=\frac{1}{s}\int\text{Tr}_Y\left(A(I_r\otimes UIU^\dagger)\right)dU \\ &=\frac{1}{s}\int\text{Tr}_Y\left(A\right)dU \\ &=\frac{1}{s}\text{Tr}_Y\left(A\right) \end{align*}