Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)

share|improve this question
    
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
add comment

3 Answers

up vote 4 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
show 2 more comments

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

share|improve this answer
    
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
3  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.