# How to prove that the trace of n-qubit matrices satisfies ${\rm Tr}(XY)=2^n\sum_{M\in\{I,X,Y,Z\}^n} x_M y_M$?

It is known that for n-qubit matrices X, Y $$\in \mathbb{C}^{2^{n}\times 2^{n}}$$ (and Pauli matrices $$I, X, Y, Z$$) such that $$X = \sum_{M \in \{I, X, Y, Z\}^{n}} x_{M}M_{1}\otimes ... \otimes M_{n}$$ and $$Y = \sum_{M \in \{I, X, Y, Z\}^{n}} y_{M}M_{1}\otimes ... \otimes M_{n}$$ their trace is $$Tr(XY) = 2^{n} \sum_{M \in \{I, X, Y, Z\}^{n}}x_{M} y_{M}$$ and we can thus use the trace to calculate the coefficients $$x_{M}, y_{M}$$, but how do we know that is true? I understand that for all tensor products where $$M \neq I$$ the trace is zero but where exactly does the $$2^{n}$$ come from, and why is there still a summation in the trace if the tensor product only yields a non-zero trace for one scenario?

Letting $$\sigma_j$$ for $$j \in \{I, X, Y, Z\}$$ denote a Pauli matrix, its easy to verify the identity $$$$\text{Tr}(\sigma_i \sigma_j) = 2 \delta_i^j \tag{1}$$$$

since $$\sigma_i \sigma_j$$ give the identity when $$i=j$$ but gives another non-identity Pauli operator (i.e. traceless) when $$i \neq j$$. Now its straightforward to show \begin{align} \text{Tr}(XY) &= \text{Tr}\left(\sum_{\mathbf{i}\in\{I,X,Y,Z\}^n} x_\mathbf{i} \sigma_{i_1} \otimes \cdots \otimes \sigma_{i_n} \sum_{\mathbf{j}\in\{I,X,Y,Z\}^n} y_\mathbf{j} \sigma_{j_1} \otimes \cdots \otimes \sigma_{j_n}\right)\tag{2} \\&= \sum_{\mathbf{i},\mathbf{j}\in\{I,X,Y,Z\}^n} x_\mathbf{i} y_\mathbf{j} \text{Tr}\left(\sigma_{i_1}\sigma_{j_1} \otimes \cdots \otimes \sigma_{i_n} \sigma_{j_n}\right)\tag{3} \\&= \sum_{\mathbf{i},\mathbf{j}\in\{I,X,Y,Z\}^n} x_\mathbf{i} y_\mathbf{j} \prod_{k=1}^n\text{Tr}\left(\sigma_{i_k}\sigma_{j_k}\right)\tag{4} \\&= \sum_{\mathbf{i},\mathbf{j}\in\{I,X,Y,Z\}^n} x_\mathbf{i} y_\mathbf{j} \left(2^n \prod_{k=1}^n \delta_{i_k}^{j_k} \right)\tag{5} \\&= 2^n \sum_{\mathbf{i},\mathbf{j}\in\{I,X,Y,Z\}^n} x_\mathbf{i} y_\mathbf{j} \delta_\mathbf{j}^\mathbf{i}\tag{6} \\&= 2^n \sum_{\mathbf{i}\in\{I,X,Y,Z\}^n} x_\mathbf{i} y_\mathbf{i} \tag{7} \end{align}

And so the $$2^n$$ comes from $$\text{Tr}(\sigma_I)=2$$ and the fact that every pair of terms between $$X$$ and $$Y$$ is either orthogonal or multiplies to $$I_{2^n} := I \otimes \cdots \otimes I$$ (with trace $$2^n$$). The sum remains because there are actually $$4^n$$ different pairs whose product is $$I_{2^n}$$. For example with three qubits, multiplying $$x_{III} I_8$$ with $$y_{III} I_8$$ results in an operator with nonzero trace, but so too does multiplying $$x_{IXY} (I\otimes X \otimes Y)$$ and $$y_{IXY}(I\otimes X \otimes Y$$), and so on.

where exactly does the $$2^n$$ come from

If you have a term in the product where all the Paulis are the same from both the $$X$$ and the $$Y$$, then you're left with the $$2^n\times 2^n$$ identity matrix. This has trace $$2^n$$.

why is there still a summation in the trace if the tensor product only yields a non-zero trace for one scenario?

When you multiply $$X$$ and $$Y$$, there are two summations (better to use different summation indices to make it super-clear!). The fact that the trace identifies equal terms accounts for one of the summations, leaving your answer with one summation.