Question

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

Let

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

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)

Answer 1

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.

Answer 2

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.

Answer 3

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$.