MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $n,d_1,\ldots,d_n > 1$ be integers, and $V_1, \ldots, V_n$ be inner product spaces over $\mathbb C$, having dimensions $d_1, \ldots, d_n$ respectively. We consider the ways in which we may decompose vectors $$\Psi \in \mathbf V := V_1 \otimes \cdots \otimes V_n$$ into a sum of product vectors, $$ \Psi = \sum_{t=1}^M s_t \Bigl(\psi^{(1)}_t \otimes \cdots \otimes \psi^{(n)}_t\Bigr)\;,$$ for $s_t \in \mathbb C$, where $\psi^{(j)}_t \in V_j$ are unit vectors for each $1 \leqslant j \leqslant n$ and $1 \leqslant t \leqslant M$. I'm specifically interested in the conditions in which we can bound $M$ from above for all $\Psi$.

  1. Let $\alpha \geqslant 0$ be a function of $n$ such that $1/(1 - \alpha)$ increases at most polynomially with $n$. Suppose that for each $1 \leqslant j \leqslant n$ and for all $1 \leqslant t,u \leqslant M$, we require that $$\Bigl\langle \psi^{(j)}_t , \psi^{(j)}_u \Bigr\rangle\Bigl\langle \psi^{(j)}_u , \psi^{(j)}_t \Bigr\rangle \ \in\ [0,\alpha] \cup \{1\} \ .$$ What is the smallest value of $M$ for which all vectors in $\mathbf V$ have such a decomposition?

  2. What is the smallest such value of $M$ if we set $\alpha := 0$ for all $n$? Equivalently: if for each $1 \leqslant j \leqslant n$ and for all $1 \leqslant t,u \leqslant M$, we require that $\psi^{(j)}_t$ and $\psi^{(j)}_u$ are either equal or orthogonal?

For the second question above, in the case $n = 2$ we may set $M = \min \{ d_1, d_2 \}$ (and as a corollary restrict each scalar $s_t$ to be a non-negative real); this is just the Schmidt decomposition. And we may always bound $M$ from above by $M \leqslant d_1 d_2 \cdots d_n$ by simply chosing an orthonormal basis $\mathbf B$ for $\mathbf V$ consisting of a tensor product of orthonormal bases for each space $V_j$, and decomposing $\Psi$ with respect to that basis. Are there any good upper bounds on $M$ for $n > 2$, for either for $\alpha = 0$, $\alpha > 0$ some constant, or for some function $\alpha \in 1 - \Omega(1/\mathrm{poly}(n))$?

share|cite|improve this question
I asked a different but related question here:… – Jess Riedel Sep 26 '13 at 18:19

Your Answer


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

Browse other questions tagged or ask your own question.