# A convex combination of unitary transforms converts any matrix to identity

## Question

Show that there exists a set of unitary matrices $$\{U_i\}$$, and probability $$\{p_i\}$$, such that for any $$n \times n$$ matrix $$A$$ $$$$\tag{1} \sum_{i} p_i U_i A U^{\dagger}_i = \text{tr}(A) \frac{I}{n}$$$$

## Attempts

For $$n=2$$, it is easy to show $$$$\frac{1}{4} ( \sigma^x A \sigma^x + \sigma^y A \sigma^y + \sigma^z A \sigma^z + I A I ) = \text{tr}(A) I / 2$$$$ where $$\sigma^{x,y,z}$$ are Pauli sigma matrices. The idea comes from kraus operator sum representation.

We can then generalize to dimension $$n = 2^m$$, where $$U_i$$ can be taken as the tensor products of these basis, but not arbitrary dimension.

In indices, Eq.(1) is equivalent to $$$$\sum_i p_i (U_i)_{ab} (U_i^*)_{dc} = \delta_{bc} \delta_{ad} / n$$$$ This looks like the identity from the finite dimensional irreducible unitary representation of finite group, see Peter-Weyl theorem. But again this only works when group $$G$$ has irreducible representation at dimension $$n$$, and all $$p_i$$ in this case are equal.

I feel that "right proof" should not utilize these additional structures.

• It may help to observe that the Choi matrix of your operator is given by $$C_{\Phi} = \frac 1n I_n \otimes I_n$$ since the desired decomposition is a Kraus decomposition, the matrices $U_i$ must satisfy $$\sum_{i}p_i \operatorname{vec}(U_i)\operatorname{vec}(U_i)^{\dagger} = C_{\Phi} = \frac 1n I_n \otimes I_n$$ – Omnomnomnom Mar 20 at 19:00
• An educated guess: I think that $U_i = W^i$ should work, where $W$ is the $n \times n$ DFT matrix, with all $p_i = \frac 1n$ – Omnomnomnom Mar 20 at 19:07
• Never mind, my guess fails. The $U_i$ must span the set of all $n \times n$ matrices, which my guess fails to do. Notably, the $U_i$ cannot be simultaneously diagonalizable. – Omnomnomnom Mar 20 at 19:10
• Perhaps it helps though to know that you're looking for a set of unitary matrices $U_i$ whose span is $\Bbb C^{n \times n}$ – Omnomnomnom Mar 20 at 19:31
• @Omnomnomnom, yes problem solved if you find a basis for matrix. – anecdote Mar 21 at 20:56

An attempted proof of existence that doesn't actually construct the spanning set and distribution.

First, we note that the set of unitary matrices spans $$\Bbb C^{n \times n}$$; we could prove this nicely using polar decomposition. From there, we note that there must exist a basis of $$\Bbb C^{n \times n}$$ $$\{U_1,U_2,\dots,U_{n^2}\}$$ consisting of unitary matrices.

It follows that the vectors $$\operatorname{vec}(U_1),\dots,\operatorname{vec}(U_{n^2})$$ span $$\Bbb C^{n^2}$$.

The argument below is incorrect

(Thus, there necessarily exist (positive) $$p_k$$ such that $$\frac 1n I_{n^2} = \sum_{i} p_i \operatorname{vec}(U_i)\operatorname{vec}(U_i)^\dagger$$ We correspondingly find that these $$U_i$$ satisfy $$\sum_{i} p_i U_iA U_i^\dagger = \frac 1n \operatorname{tr}(A) I$$, as desired.)

Some clarification:

First of all, the linear span bit. Let $$\langle \cdot, \cdot \rangle$$ denote the Frobenius (Hilbert-Schmidt) inner product. Suppose that $$A$$ lies in the orthogonal complement of the span of the unitary matrices. Let $$A = UP$$ be a polar decomposition. Then we have $$0 = \langle U, A \rangle = \operatorname{trace}(U^\dagger A) = \operatorname{trace}(U^\dagger UP) = \operatorname{trace}(P)$$ but $$P$$ is positive semidefinite, so $$\operatorname{trace}(P) = 0$$ implies that $$P = 0$$. Thus, $$A$$ must be zero.

So, the span of the unitary matrices is all $$\Bbb C^{n \times n}$$.

Another obsrevation:

Let $$\mathcal C_U$$ denote the convex cone generated by the set $$\{uu^* : u = \operatorname{vec}(U) \text{ for some unitary } U \}$$. Showing that $$\sum_{i} p_i \operatorname{vec}(U_i)\operatorname{vec}(U_i) = I$$ can be achieved with non-negative coefficients $$p_i$$ means that we're trying to show that $$I \in \mathcal C_U$$.

One orthogonal basis for $$\Bbb C^{n \times n}$$ consisting of unitary matrices is as follows: let $$X = \pmatrix{0&&&&1\\1&0\\&1&0\\&&\ddots\\&&&1}, Z = \pmatrix{1\\ & \omega \\ && \ddots \\ &&& \omega^{n-1}}$$ Then the matrices $$\{Z^j X^k : 0 \leq j,k \leq n-1\}$$ form our orthogonal basis.

• I am a bit slow here... Can you show how to get the linear span from the polar decomposition? – anecdote Mar 22 at 3:17
• About the resolution identity: let me write $\text{vec}(U_i)$ as $v_i$. Now $\{ v_i \}$ is a set of basis, if $I = n \sum_i p_i v_i v_i^{\dagger}$, then $G_{ij} = n G_{ik} p_k G_{kj}$ where $G_{ij}$ is the Gram matrix. Then how do we show that $p_k$ exist? I thought $v_i$ here are not necessarily orthogonal. – anecdote Mar 22 at 3:21
• I clarified the polar decomposition argument. It seems clear that I'm wrong about that second argument though. Nevertheless, I have a feeling that the fact that the unitaries "are a large enough set" will somehow be enough here. – Omnomnomnom Mar 22 at 13:46
• Following the argument in proposition 2.2 of this paper, I can show that there exist real coefficients $a_i$ and unitary matrices $U_i$ such that $$\sum_{i} a_i \operatorname{vec}(U_i)\operatorname{vec}(U_i)^\dagger = \frac 1n I$$ That being said, what we would need is a way to guarantee that the coefficients $a_i$ are non-negative, which I haven't been able to come up with. – Omnomnomnom Mar 22 at 14:00
• @anecdote Let me rephrase the argument: define $W \subseteq \Bbb C^{n \times n}$ to be the subspace spanned by the unitary matrices. What I show is that if $A \in W^\perp$, then $A = 0$. It follows that $W = \Bbb C^{n \times n}$ – Omnomnomnom Mar 22 at 16:19