# Symmetric subspace of linear operators

This is a question that stemmed from fooling around with unitary t-designs.

Let

$$\mathbb{V} = \mathrm{span} \{\; U^{\otimes t}\; |\; U \in \mathrm{U}(d)\}$$

Where $\mathrm{U}(d)$ is the unitary group acting on $\mathbb{C}^d$.

What can we say about $\dim \mathbb{V}$? What tools can I use to figure out the dimension or good lower bounds for it?

I've read (p. 162) about the analogous question for $\mathbb{U} = \mathrm{span}\{|\psi\rangle^{\otimes t}\;|\; |\psi\rangle \in \mathbb{C}^d\}$. In particular, we can show that $\dim \;\mathbb{U} = {d + t - 1 \choose t - 1}$. To use that approach, we need to change $\mathrm{U}(d)$.

If we change $\mathrm{U}(d)$ to $\mathbb{C}^{d\times d}$ (i.e. all the matrices on $\mathbb{C}^d$) then is it obvious that the resulting space is the same as $\mathbb{V}$? If they are the same, then the question becomes easier, since then we have the space of all linear operators that are invariant under permutations of the $t$ registers and we can just use the formulate for $\dim \mathbb{U}$ thinking of the operators as row vectors.

(I am not sure of the tags for this, so feel free to change them)

-
Your definition of $\mathbb V$ involves taking the span of a set where? –  Mariano Suárez-Alvarez Oct 25 '10 at 5:27
@Mariano I am not sure if I understand your question exactly. The field I have in mind is $\mathbb{C}$ and $\mathbb{V}$ is a subspace of $(C^{d \times d})^{\otimes t}$. So the span is taken there. –  Artem Kaznatcheev Oct 25 '10 at 6:30
So you are asking whether the unitary matrices are Zariski-dense in the $\mathbb C$-vector space $\mathrm{M}_n\left(\mathbb C\right)$. Interesting question. –  darij grinberg Dec 6 '10 at 12:41
Why no one pointed out that in the answer the lower t-1 should be t ? –  user4245 Mar 1 '11 at 10:00

The proof below is mostly by Peter Scholze, so no point in voting it up.

1° I claim that $\dim \mathbb V=\binom{d^2+t-1}{t-1}$. In order to prove this, I will show that the subset $\mathrm{U}_d$ (this is what you call $\mathrm{U}\left(d\right)$ and is defined as the set of all $d\times d$ unitary matrices) is Zariski-dense as a subset of the $\mathbb C$-vector space $\mathrm{M}_d$ (which is short for $\mathrm{M}_d\left(\mathbb C\right)$).

Why is this enough? Because let us consider the tensor product $\otimes^t \mathrm{M}_d$. Let $\left(\otimes^t \mathrm{M}_d\right)_{\mathrm{symm}}$ be the subspace of this tensor product containing only the symmetric tensors (= tensors invariant under the canonical action of $S_t$ on $\otimes^t \mathrm{M}_d$). Physicists like to call $\otimes^t \mathrm{M}_d$ the "$t$-th symmetric power" of $\mathrm{M}_d$; for us mathematicians it is just canonically isomorphic to the $t$-th symmetric power of $\mathrm{M}_d$. Anyway, let $D:\mathrm{M}_d\to \left(\otimes^t \mathrm{M}_d\right)_{\mathrm{symm}}$ be the map given by $D\left(A\right)=A\otimes A\otimes ...\otimes A$ for every $A\in\mathrm{M}_d$. This map is polynomial, and the images of $\mathrm{M}_d$ and $\mathrm{U}_d$ under this map are $\left(\otimes^t \mathrm{M}_d\right)_{\mathrm{symm}}$ and $\left\lbrace U^{\otimes t}\mid U\in\mathrm{U_d}\right\rbrace$, respectively (for $\mathrm{M}_d$, this is known (look up "polarization" and "full restitution"), and for $\mathrm{U}_d$, this is clear). Hence, once we can show that $\mathrm{U}_d$ is Zariski-dense in $\mathrm{M}_d$, it will follow that $\left\lbrace U^{\otimes t}\mid U\in\mathrm{U_d}\right\rbrace$ is Zariski-dense in $\left(\otimes^t \mathrm{M}_d\right)_{\mathrm{symm}}$, so that $\left(\otimes^t \mathrm{M}_d\right)_{\mathrm{symm}}$ must be the span of $\left\lbrace U^{\otimes t}\mid U\in\mathrm{U_d}\right\rbrace$. In other words, $\left(\otimes^t \mathrm{M}_d\right)_{\mathrm{symm}}=\mathbb V$, so that $\dim\mathbb V = \dim \left(\otimes^t \mathrm{M}_d\right)_{\mathrm{symm}} = \binom{d^2+t-1}{t-1}$.` This is what we want to prove.

So it just remains to show that $\mathrm{U}_d$ is Zariski-dense in $\mathrm{M}_d$.

2° Assume the contrary. Then there is a polynomial $P$ on $\mathrm{M}_d$ such that $P$ is not identically zero, but $P\left(U\right)=0$ for every $U\in \mathrm{U}_d$.

3° A lemma from complex analysis: If $V$ is an $\mathbb R$-vector space, and if some holomorphic function $f: V\otimes\mathbb C\to\mathbb C$ is identically zero on the subset $V\otimes \mathbb R$ of $V\otimes \mathbb C$, then $f$ is zero everywhere. (This is easily deduced from the one-dimensional case $V=\mathbb R$, which is a basic fact.)

4° Consider the Lie algebra $\mathfrak{u}_d\in \mathrm{M}_d$. This Lie algebra is an $\mathbb R$-subspace and not a $\mathbb C$-vector subspace of $\mathrm{M}_d$; its $\mathbb C$-span is actually the whole $\mathrm{M}_d$ (because $\mathfrak{u}_d$ consists of all anti-Hermitian matrices). We can even say a bit more: There is an isomorphism $\mathrm{M}_d\cong \mathrm{u}_d\otimes \mathbb C$ as $\mathbb C$-vector spaces, and this isomorphism maps the subset $\mathrm{u}_d$ of $\mathrm{M}_d$ to the subset $\mathrm{u}_d\otimes \mathbb R$ of $\mathrm{M}_d\cong \mathrm{u}_d\otimes \mathbb C$. (Explicitly, this isomorphism is given by $M\mapsto \frac{M-M^{\ast}}{2}\otimes 1 + \frac{M+M^{\ast}}{2}\otimes i$.)

Now we know (from 3°) that if a holomorphic function $\mathrm{u}_d\otimes \mathbb C\to\mathbb C$ is identically zero on the subset $\mathrm{u}_d\otimes \mathbb R$, then it is zero everywhere. Thus, due to the above isomorphism, if a holomorphic function $\mathrm{M}_d\to \mathbb C$ is identically zero on the subset $\mathrm{u}_d$, then it is zero everywhere.

Consider the mapping $\exp:\mathrm{M}_d\to\mathrm{M}_d$. This mapping is holomorphic on the whole $\mathrm{M}_d$. For every $u\in\mathfrak{u}_d$, we have $\exp u\in \mathrm{U}_d$ (since $\mathfrak{u}_d$ is the Lie algebra of $\mathrm{U}_d$) and thus $P\left(\exp u\right)=0$.

The function $P\circ\exp:\mathrm{M}_d\to\mathbb C$ is holomorphic (since so are $P$ and $\exp$) and is identically zero on the subset $\mathrm{u}_d$. According to our above results, it thus is zero everywhere, so that $P$ is zero on $\exp\mathrm{M}_d$. But the set $\exp\mathrm{M}_d$ is Zariski-dense in $\mathrm{M}_d$ (in fact, it is $\mathrm{GL}_d$, but I guess it is easier to prove its Zariski-density by different means), so that $P$ must be zero everywhere, contradicting our assumption on $P$. Qed.

Addendum: The above proof is now complete, but it has the disadvantage of not being constructive. The culprit is the $\exp$ mapping, being non-algebraic. Fortunately, we can amend this by replacing the $\exp$ mapping by a different mapping, namely the mapping $T:\mathrm{M}_d\dashrightarrow \mathrm{M}_d$ given by

$T\left(A\right)=\left(I_d+A\right)\left(I_d-A\right)^{-1}$.

Note that this mapping $T$ is not a total mapping, but it is a dominant rational partial mapping, and all that we have used about holomorphic mappings holds for rational partial mappings as well. Instead of the result "for every $u\in\mathfrak{u}_d$, we have $\exp u\in \mathrm{U}_d$" we now must use "for every $u\in\mathfrak{u}_d$ for which $T\left(u\right)$ is defined, we have $T\left( u\right)\in \mathrm{U}_d$" (which is an easy calculation); note that $T\left(u\right)$ is defined for "most" elements $u\in\mathfrak{u}_d$ (in other words, the set of all $u\in\mathfrak{u}_d$ for which $T\left(u\right)$ is defined is a Zariski-closed subset of the set $\mathfrak{u}_d$). Otherwise the proof remains pretty much the same.

-
thank you for this proof! I think I understand the basic idea, but I will have to look at the argument more closely to really understand it, since it uses some technology that I am not familiar with. I will accept this answer since it was the first one to answer the question I had. –  Artem Kaznatcheev Dec 17 '10 at 10:21

Here is another proof of the same result (it is probably the same as the one given by darij grinberg but I do not understand all the words. It has perhaps more his place as a comment, but I do not know how to write comments). In the case $t=2$, it is Claim 1 in Lemma 1.3.2 of http://arxiv.org/pdf/1002.4595v2

Denote by $P : M_d(\mathbb C)^{\otimes t} \to M_d(\mathbb C)^{\otimes t}$ the linear map such that $P(A_1 \otimes \dots \otimes A_t) = 1/t!\sum A_{\sigma(1)} \otimes \dots \otimes A_{\sigma(t)}$, where the sum os over all permutations of $\{1,\dots ,t\}$. $P$ is the natural projection on the symmetric tensors.

Let $(H_k)$ be the assertion "$\mathbb V$ contains the space $F_k$ spanned by $P(h_1 \otimes h_2 \otimes \dots \otimes h_t)$ for any hermitian matrices $h_1,...,h_t$ with $h_{k+1} = h_{k+2} = \dots h_t=1$" ($1$ is the identity matrix).

By polarity, $(H_k)$ is equivalent to the assertion "$\mathbb V$ contains $P(h_1 \otimes h_2 \otimes \dots \otimes h_t)$ for any hermitian matrices $h_1,...,h_t$ with $h_1 = h_2 = \dots =h_k$ and $h_{k+1} = h_{k+2} = \dots h_t=1$".

Prove $(H_k)$ by induction on $k$. Take indeed a symmetric matrix $h$, and consider $f(x) = \exp(ixh)^{\otimes t}$ and develop $f$ in power series: $f(x) = \sum_n x^n a_n$. Then $a_n$ belongs to $\mathbb V$ for all $n$. For example $a_1 = i t P(h\otimes 1 \ \dots \otimes 1)$ which proves $(H_1)$.

One moment of thinking gives you that you can write $a_k=i^k C(t,k) P(h\otimes \dots h \otimes 1 \dots \otimes 1) +$something in $F_{k-1}$, where $C(t,k)$ is the binomial coefficient and there are $k$ $h$'s and $(t-k)$ $1$'s in $h\otimes \dots h \otimes 1 \dots \otimes 1$. This allows to proceed by induction.

Thus for $k=t$, and using that $M_d(\mathbb C)$ is the linear span of the hermitian matrices, you get that $\mathbb V$ is the whole space of symmetric tensors.

-
I think one needs 50 experi... reputation points to write comments. Quite an annoying hurdle, but the idea is probably that otherwise 50% of the comments would be about V14gr4. –  darij grinberg Dec 16 '10 at 17:02
Nice proof, by the way. –  darij grinberg Dec 16 '10 at 17:05
One thing: I think that as soon as you prove $(H_1)$, i. e. as soon as you show that $P(h\otimes 1\otimes ...\otimes 1\right)$ lies in $\mathbb V$, you should pass from Hermitian $h$ to any general matrix $h$. This makes the "polarity" argument sound (I don't claim that it is not sound the way it is right now, but I can't follow it). –  darij grinberg Dec 16 '10 at 17:09
The latex failure should be $P(h\otimes 1\otimes ...\otimes 1)$. –  darij grinberg Dec 16 '10 at 17:09
Well, maybe the term polarity is not appropriate. What I had in mind was the following. If $h_1,...,h_k$ are hermitian, consider, for $h=h(X_1,...,X_k) = X_k h_k+ ... X_k h_k$. Then $P(h \otimes \dots h \otimes 1 \dots 1)$ is a polynomial in $X_1,...,X_k$ and the coefficient of $X_1 X_1 ... X_k$ is precisely (a multiple?) of $P(h_1\otimes \dots h_k\otimes 1\dots)$. –  Mikael de la Salle Dec 16 '10 at 17:16

I am not sure if my interpretation of your question is correct or not, but any $n \times n$ complex matrix can be written as a linear combination of unitary matrices: For $n=1$, this is almost obvious, and for arbitrary $n$, use the singular value decomposition (or $KAK$ decomposition) to decompose $A$ as $A=U_1 D U_2$ where $U_i$ is unitary for $i=1,2$ and $D$ is diagonal with real non-negative entries. So, the problem reduces to diagonal matrices with non-negative real entries, which in turn reduces to $n=1$ by induction. Now, in my interpretation of the problem, this solves the problem for arbitrary $t$.

-
In any C*-algebra, any element can be written as a linear combination of unitary elements (in fact, by at most four such elements). Do you want to say something about linear independence in this answer? –  Jon Bannon Oct 25 '10 at 11:28
No. My point (if I understand the question correctly) is that the span of the unitary matrices is the same as the space of all $M_n(C)$. So the dimension of the tensor power is the same as the one for $M_n(C)$ which is given in the problem. By the way, re your comment,I do not think four or any other bound would work, since the norm of a unitary element is one, and any finite sum has a norm bounded by the number of summands. Am I missing something? –  Keivan Karai Oct 25 '10 at 11:53
I agree that any matrix can be written as a linear combination of unitaries (in fact as each matrix can be written as a linear combination of just two unitaries). This definitely solves the question for the case of $t = 1$, but that is not really the difficult case. Just because the unitaries span $\mathbb{C}^{d \times d}$ does not mean we can replace $U \in mathrm{U}(d)$ by $U \in \mathbb{C}^{d \times d}$ on the condition side of the definition of our spanning set --- at least not without proof because it is not obvious that the tensor will behave nicely. –  Artem Kaznatcheev Oct 25 '10 at 22:25