Write down an explicit tensor of border rank $r$ in $\mathbb{C}^r \otimes \mathbb{C}^r \otimes \mathbb{C}^r$ with rank greater than $r$

Question

This question is from the text Geometry and Complexity Theory, from J.M. Landsberg. Before start talking about the question, I think it is good to show the definition of border rank. Consider a tensor $T \in \mathbb{C}^r \otimes \mathbb{C}^r \otimes \mathbb{C}^r$. Then the border rank of $T$ is the minimum $r$ such that $T$ can be arbitrarily approximated by tensors of rank $r$.

In this discussion we asume $r > 1$ is integer. In general, the limit of tensors of rank $r$ may not be a tensor of rank $r$. An example is given in the text (I changed a little the notation):

Let $x_i, y_i \in \mathbb{C}^r$ be linearly independent vectors, for $i = 1,2,3$. Then the sequence of rank 2 tensors

$$T_n = n\left( x_1 + \frac{1}{n} y_1 \right) \otimes \left( x_2 + \frac{1}{n} y_2 \right) \otimes \left( x_3 + \frac{1}{n} y_3 \right) - nx_1 \otimes x_2 \otimes x_3 $$

converges to the rank 3 tensor

$$T = x_1 \otimes x_2 \otimes y_3 + x_1 \otimes y_2 \otimes x_3 + y_1 \otimes x_2 \otimes x_3. $$

The author says that $T$ is a rank $3$ tensor with border rank $2$. With this example in mind I tried to come up with the following idea:

Let $x_i, y_i \in \mathbb{C}^r$ be linearly independent vectors, for $i = 1, \ldots, r$. Consider the sequence

$$T_n = n\left( x_1 + \frac{1}{n} y_1 \right) \otimes \left( x_2 + \frac{1}{n} y_2 \right) \otimes \left( x_3 + \frac{1}{n} y_3 \right) - nx_1 \otimes x_2 \otimes x_3 + $$ $$ + n\left( x_2 + \frac{1}{n} y_2 \right) \otimes \left( x_3 + \frac{1}{n} y_3 \right) \otimes \left( x_4 + \frac{1}{n} y_4 \right) - nx_2 \otimes x_3 \otimes x_4 + \ldots$$ $$ \ldots + n\left( x_{\frac{r}{2}} + \frac{1}{n} y_{\frac{r}{2}} \right) \otimes \left( x_{\frac{r}{2}+1} + \frac{1}{n} y_{\frac{r}{2}+1} \right) \otimes \left( x_{\frac{r}{2}+2} + \frac{1}{n} y_{\frac{r}{2}+2} \right) - nx_{\frac{r}{2}} \otimes x_{\frac{r}{2}+1} \otimes x_{\frac{r}{2}+2}$$

for $r$ even. The $T_n$ is a sum of $r$ rank 1 tensor, so $T_n$ has rank $r$. Furthermore, we have that $T_n$ converges to

$$T = x_1 \otimes x_2 \otimes y_3 + x_1 \otimes y_2 \otimes x_3 + y_1 \otimes x_2 \otimes x_3 + $$ $$ + x_2 \otimes x_3 \otimes y_4 + x_2 \otimes y_3 \otimes x_4 + y_2 \otimes x_3 \otimes x_4 + \ldots $$ $$\ldots + x_{\frac{r}{2}-2} \otimes x_{\frac{r}{2}-1} \otimes y_\frac{r}{2} + x_{\frac{r}{2}-2} \otimes y_{\frac{r}{2}-1} \otimes x_\frac{r}{2} + y_{\frac{r}{2}-2} \otimes x_{\frac{r}{2}-1} \otimes x_\frac{r}{2}$$

which is a sum of $3(\frac{r}{2}-2)$ rank 1 tensors, so $T$ has rank $3(\frac{r}{2}-2)$.

I have some concerns about this "solution"., which I'm going to list here.

1) I'm not sure if the tensors $T_n$ really have rank $r$, maybe there is a way to reduce the number of terms which I'm not aware of. The same goes to $T$.

2) In order to have $3(\frac{r}{2} - 2) > r$ we need $r > 12$. This restriction indicates my solution is wrong someway.

3) Finally, to work with $r$ odd I need to add one last term in an artificial way. This also makes me think this whole idea is not good.

Well, I need some directions here. To be honest I'm new in the study of tensors, so any help with nice explanations are very welcome!

Thank you!

Answer 1

One way to prove that the border rank is exactly $r$ and not less is the flattening lower bound. You can see a tensor $T \in A\otimes B\otimes C$ as a linear map $T\colon A^* \to B\otimes C$. If $T$ has tensor rank $\leq r$, than this map also has rank $\leq r$, and we can take the limits to talk about border rank. (Landsberg discusses it in the section "Our first lower bound").

To show that the rank is more than $r$, we need to do something slightly more complicated. Again look at $T\colon A^* \to B\otimes C$. If $T$ has rank $r$, then you can say many things about values $T(\alpha)$ for various $\alpha \in A^*$. Try to construct your tensor in such a way that some of these things cannot hold.

Answer 2

Let $V = \mathbb{C}^r$ have basis $\{x_1,\dotsc,x_r\}$. Consider the tensor $$ \begin{split} T &= x_1^2 x_2 + x_3^3 + x_4^3 + \dotsb + x_r^3 \\ &= x_1 \otimes x_1 \otimes x_2 + x_1 \otimes x_2 \otimes x_1 + x_2 \otimes x_1 \otimes x_1 + x_3 \otimes x_3 \otimes x_3 + \dotsb + x_r \otimes x_r \otimes x_r . \end{split} $$ where I have used polynomial (symmetric tensor) notation, I hope it is clear how to make it correspond with usual tensors.

As a tensor, this is written as a sum involving $r+1$ terms ($3$ for the first $2$ basis elements, plus $r-2$ more for $x_3,\dotsc,x_r$). Therefore $T$ has rank less than or equal to $r+1$.

I claim that $T$ has rank equal to $r+1$ and border rank equal to $r$.

First, $$ T = \lim_{t \to 0} \frac{(x_1+t x_2)^3-x_1^3}{3t} + x_3^3 + \dotsb + x_n^3 $$ (again using polynomial notation for convenience), which shows that $T$ has border rank less than or equal to $r$.

A lower bound for border rank is not too hard. For example there is a lower bound given by flattening rank, see https://mathoverflow.net/questions/280554/is-a-flattening-rank-a-lower-bound-for-the-border-rank. To be a little bit explicit, we get a map from, say, $V^* \otimes V^* \to V$. Say $V^*$ has dual basis $\{y_1,\dotsc,y_r\}$. The induced map $V^*\otimes V^* \to V$ (also denoted $T$ by slight abuse of notation) is given by $$ T(y_i \otimes y_j) = x_1(x_1(y_i)\cdot x_2(y_j)) + x_1(x_2(y_i)\cdot x_1(y_j)) + \dotsb + x_r(x_r(y_i) \cdot x_r(y_j)) . $$ So $T(y_1 \otimes y_2) = x_1$, $T(y_1 \otimes y_1) = x_2$, and for $3 \leq i \leq r$, $T(y_i \otimes y_i) = x_i$. This shows that this induced map is onto. So it has rank $r$. Therefore the tensor $T$ has border rank greater than or equal to $r$, see the linked MO answer for an explanation why.

Here is one idea for how to get a lower bound for the tensor rank of $T$. First observe that the tensor given by the first three terms of $T$ (corresponding to $x_1^2 x_2$) is precisely the first example you started with, so it has rank $3$. (One way to see that it has rank $3$ is here Find the rank of the tensor.) And by a special case of Strassen's conjecture, each time we add a term $x_i \otimes x_i \otimes x_i$, with $x_i$ linearly independent from all the previously used vectors, then we in fact add $1$ to the rank. Unfortunately I am having trouble finding a citation for that at the moment. Please let me know if you're still interested, I will be happy to look again.