In Schur-Weyl's duality, why is the commutant of $\pi_k(S_k)$ spanned by $U(d)^{\otimes k}$ matrices?

Question

I'm reading this tutorial paper about quantum state certification. However, I'm confused about the concept of Schur-Weyl duality, explicitly Theorem 35 of the paper. Let $S_k$ denotes the symmetric group and $\pi_k$ its unitary representation, i.e., $$\pi _k:S_k\rightarrow U\left[ \left( \mathbb{C} ^d \right) ^{\otimes k} \right].$$ The action of $\pi_k(\sigma)$ with $\sigma\in S_k$ is defined as $$\pi _k\left( \sigma \right) \left[ |\psi _1\rangle \otimes \cdots \otimes |\psi _k\rangle \right] \equiv |\psi _{\sigma ^{-1}\left( 1 \right)}\rangle \otimes \cdots \otimes |\psi _{\sigma ^{-1}\left( k \right)}\rangle.$$ Then, theorem 35 states that the commutant$^1$ of $\pi _k\left( S_k \right) $ is spanned by all matrices of form $U\left( d \right) ^{\otimes k}$. Here, $U(d)$ is one unitary matrix of dimension $d$. My question is, obviously that any matrix of form $M\left( d \right) ^{\otimes k}$ will commute with $\pi _k\left( S_k \right) $. Here, $M(d)$ means any matrix of dimension $d$ which is not unitary in general! However, I can't see how $M(d)^{\otimes k}$ is a linear combination of $U\left( d \right) ^{\otimes k}$, hence a contradiction of the theorem?

---

_{1. The commutant of a set $\mathcal A$, denoted $\mathrm{comm}(\mathcal A)$, is defined as all matrices commute with each element of $\mathcal A$. In other words, we have $\mathrm{comm}\left( \mathcal{A} \right) \equiv \left\{ B|\left[ A,B \right] =0,\forall A\in \mathcal{A} \right\}.$}

Answer 1

While I agree with Markus Heinrich that the argument is non-trivial, actually it can be presented in familiar quantum computing terms.

The matrix algebra $M(d)^{\otimes n} \cong M(d^k)$ has a self-adjoint basis of generalized multi-Pauli operators, i.e., basis elements such as $Z \otimes X \otimes I \otimes Z \otimes Y$. An arbitrary operator, i.e., an arbitrary linear combination of these basis elements, commutes with $S_k$ if and only if the coefficients are permutation invariant. In other words, the algebra commutant of $S_k$ has a basis of symmetric sums of multi-Pauli terms, for example (written in lex order) $$I \otimes X \otimes Y \otimes Z \otimes Z + I \otimes X \otimes Z \otimes Y \otimes Z + \cdots + Z \otimes Z \otimes Y \otimes X \otimes I.$$

Now I will pass to an opposite point: When you take linear combinations of elements of a matrix Lie group, you can also take limits of those linear combinations, which means that you can take derivatives. For example, if $A \in M(n)$ is some operator, then the powers $A,A^2,A^3,\ldots$ are terms in the power series expansion $$ \exp(tA) = I+tA + \frac{t^2A^2}{2} + \cdots, $$ and you can obtain those terms by taking derivatives at $t=0$, which are then limits of linear combinations of elements of the group $G = \{\exp(tA)\}$. This is a univariate example, but the same point holds in multivariate form. In fact, although you don't need this extra remark for your goal, if $G$ is any connected matrix Lie group, you don't lose anything by putting all of your chips on the derivative trick. In other words, if $G$ is connected, then the powers of the action of the Lie algebra $L$ of $G$ has the same matrix span as the action of $G$.

Finally to put these two points together, consider the diagonal action of $\text{SU}(d)$ acting on $k$ qudits. (Your question is about $\text{U}(d)$, but $\text{SU}(d) \subseteq \text{U}(d)$ suffices.) Then the multivariate derivatives at the identity are proportional to the symmetrized multi-Pauli terms that span the commutant of $S_k$. For example if $d=2$, if you expand $$U^{\otimes k} = \exp(I+ixX+iyY+izZ)^{\otimes k}$$ as a power series in $x$, $y$, and $z$, then you can see directly that the terms are proportional to standard multi-Paulis.

One final point: At least some representation theory gurus think of this as the more explicit half of Schur-Weyl duality. The other half, that the commutant of the diagonal action of $\text{SU}(d)$ is spanned by permutations, then follows from the magic of the double commutant theorem.

Answer 2

The goal is to prove that the subspace spanned by $U^{\otimes n}$ for all $d\times d$ unitary matrices $U$ includes $M^{\otimes n}$ for every $d\times d$ matrix $M$. Here's my attempt to make this as elementary as possible. I'm afraid it's a bit long but hopefully each step is simple enough.

We can first reduce the problem to diagonal matrices, which allows it to be translated to an analogous question for vectors in place of matrices. For a given matrix $M$, consider a singular value decomposition $M = V D W$ where $D$ is diagonal and $V$ and $W$ are unitary. If $D^{\otimes n}$ is contained in the subspace spanned by all $E^{\otimes n}$, where $E$ ranges over all diagonal unitary matrices, then it follows that $M^{\otimes n} = (V D W)^{\otimes n}= V^{\otimes n} D^{\otimes n} W^{\otimes n}$ is contained in the subspace spanned by all $V^{\otimes n} E^{\otimes n} W^{\otimes n} =(V E W)^{\otimes n}$, again as $E$ ranges over all diagonal unitary matrices. Because $VEW$ is always unitary, this establishes the required fact.

We therefore only need to worry about diagonal matrices — so we might as well think about $d$ dimensional vectors instead. Let $\mathbb{T} = \{\alpha\in\mathbb{C}\,:\,\vert\alpha\vert = 1\}$ denote the set of complex units, which are the possible diagonal entries of a diagonal unitary matrix. What we'll prove is that the set $\{u^{\otimes n}\,:\,u\in\mathbb{T}^d\}$ spans the entire symmetric subspace $(\mathbb{C}^d)^{\vee n}$, which includes every vector $v\in(\mathbb{C}^d)^{\otimes n}$ that is invariant under every permutation of its tensor factors (i.e., the action of $\pi_n(\sigma)$ for every $\sigma\in S_n$). This includes every vector of the form $w^{\otimes n}$, and from this we can conclude what we need about diagonal matrices.

Consider an arbitrary symmetric vector $v\in(\mathbb{C}^d)^{\vee n}$, and suppose that $v \perp \{u^{\otimes n}\,:\,u\in\mathbb{T}^d\}$, meaning that $\langle v, u^{\otimes n}\rangle = 0$ for every $u\in\mathbb{T}^d$. We'll show that $v$ must be the zero vector, and that's all we need — for if $\{u^{\otimes n}\,:\,u\in\mathbb{T}^d\}$ spanned a proper subspace of $(\mathbb{C}^d)^{\vee n}$ then there would have to exist a nonzero symmetric vector perpendicular to it.

To this end let us think about the entries of $u$ as variables $Z_1,\ldots,Z_d$. The entries of $u^{\otimes n}$ are therefore monomials in these variables having total degree $n$. When we take the inner product of $v$ with $u^{\otimes n}$ we obtain a multivariate polynomial $P(Z_1,\ldots,Z_d)$ in the variables $Z_1,\ldots,Z_d$, which happens to be a sum of monomials having total degree $n$ (but all we really need is that it's a polynomial). This polynomial is zero when $Z_1,\ldots,Z_d$ all range independently over $\mathbb{T}$ by the assumption that $v \perp \{u^{\otimes n}\,:\,u\in\mathbb{T}^d\}$.

However, the only way that can happen is that $P$ is the zero polynomial. Here's one way to see this. We can write $$ P(Z_1,\ldots,Z_d) = \sum_{k=0}^n Q_k(Z_1,\ldots,Z_{d-1}) Z_d^k $$ for polynomials $Q_0,\ldots,Q_n$ in the first $d-1$ variables $Z_1,\ldots,Z_{d-1}$. For every $(\alpha_1,\ldots,\alpha_{d-1}) \in \mathbb{T}^{d-1}$ we find that $P(\alpha_1,\ldots,\alpha_{d-1},Z_d)$ is a univariate polynomial in the variable $Z_d$, and our assumption is that this polynomial takes the value zero everywhere on $\mathbb{T}$. But nonzero univariate polynomials can only have finitely many roots, so this must be the zero polynomial. This implies that the polynomials $Q_0,\ldots,Q_n$ are always equal to zero on $\mathbb{T}^{d-1}$. By applying this argument recursively, effectively eliminating the variables one at a time, we can conclude that $Q_0,\ldots,Q_n$ are all the zero polynomial, and therefore so is $P$.

Finally, because the vector $v$ is symmetric, we know that a lot of its entries must be equal (in general). In particular, if we think of the entries of $v$ as being indexed by tuples $(a_1,\ldots,a_n)$, where $1\leq a_1,\ldots,a_n\leq d$, then we must have $$ v(a_1,\ldots,a_n) = v\bigl(a_{\sigma(1)},\ldots,a_{\sigma(n)}\bigr) $$ for every $\sigma\in S_n$. This means that the entry $v(a_1,\ldots,a_n)$ depends only on the number of times each index $1,\ldots,d$ appears in the tuple — or in other words it depends only on the multiset $\{a_1,\ldots,a_n\}$. We can naturally associate the multiset $\{a_1,\ldots,a_n\}$ with the monomial $Z_{a_1}\cdots Z_{a_n}$, and when we take the inner product of $v$ with $u^{\otimes n}$, we're always multiplying these same values that occur as entries of $v$ to the same corresponding monomial appearing as an entry of $u^{\otimes n}$. We've already concluded that our polynomial $P$ is the zero polynomial, and so it follows that every entry of $v$ must be equal to zero. We've shown that $v = 0$ so the argument is complete.

Answer 3

$M(d)^{\otimes k}$ is a linear combination of $U(d)^{\otimes k}$, this is what theorem 35 implies, yes. It's not obvious.

In fact, the next theorem 36 gives the description of the span of $U(d)^{\otimes k}$.

When $k=2$ it says that the subspaces $H_{sym^2}$ and $H_{\land^2}$ are the irreducible components of $(\mathbb{C}^d)^{\otimes 2}$ under the action of the representation $U^{\otimes 2} \cdot \pi_2(\mathcal{S_2})$ of the group $U(d) \times \mathcal{S_2}$ and that this action is multiplicity free. The same should be true just for the representation $U^{\otimes 2}$ of $U(d)$ in this case (because the two Specht modules are one-dimensional).

The representation theory then says that $$ {\rm span}[ U^{\otimes 2}] = \{ A_{H_{sym^2}} \oplus A_{H_{\land^2}} \}, $$ where each $A_{S}$ can be any operator that acts only on the subspace $S \subset H$, $A_S:S\rightarrow S$.

In general for $k>2$ the factors $W_\lambda \otimes S_\lambda$ are invariant for all $U^{\otimes k}$ (as well as for $U^{\otimes k} \cdot \pi_k(\mathcal{S_k}))$, but the action of $U^{\otimes k}$ on them may not be multiplicity-free. In fact, $W_\lambda \otimes |v\rangle$ is invariant under $U^{\otimes k}$ for any $|v\rangle \in S_\lambda$ and the actions of $U^{\otimes k}$ on each ${W_\lambda \otimes |v\rangle}$ are unitarily equivalent (for same $\lambda$). So, $S_\lambda$ is a kind of multiplicity factor (multiplicity space) for $W_\lambda$.

This means that $$ {\rm span}[ U^{\otimes k}] \simeq \{ \oplus_\lambda (\oplus_{i_\lambda=1}^{\dim S_\lambda}A_{\lambda})\}, $$ where each $A_{\lambda}$ (there are ${\dim S_\lambda}$ copies) acts on $W_\lambda \otimes |i_\lambda\rangle$.