This is a question that stemmed from [fooling around](http://www.cs.mcgill.ca/~akazna/kaznatcheev20100509.pdf) 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](http://www.cs.uwaterloo.ca/~watrous/quant-info/lecture-notes/all-lectures.pdf) (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)



Symmetric subspace of linear operators
The proof below is mostly by [Peter Scholze](https://mathoverflow.net/users/6074/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.


