tensor decompositiontensor-ranktensors
What is the largest possible rank of a tensor in the space $F^n\otimes …\otimes F^n$ where we have $k$ copies of $F^n$? It is quite easy to see that it is at most $n^{k-1}$ (I have commented the proof for this). For $k=2$ this bound is in fact tight. What about for $k\geq2$?
In particular, I'm looking for a tighter bound, or an example of a tensor with rank $n^{k-1}$ in these spaces. If this is too much, the spaces with $k=3,4$ would suffice.
These questions can be answered in the case of real spaces, which is enough for my purposes. Anyone interested can check the article Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem - Vin de Silva and Lek-Heng Lim.
The first one is the lemma 3.5. This answers the first question positively.
Lemma 3.5. For $\ell=1 \ldots k$, let $x_1^{(\ell)}, \ldots, x_r^{(\ell)} \in \mathbb{R}^{d_\ell}$ be linearly independent. Then the tensor defined by $$ \sum_{j=1}^r x_j^{(1)} \otimes x_j^{(2)} \otimes \ldots \otimes x_j^{(k)}$$ has rank $r$.
The second one is the proposition 4.6, which I partially reproduce below. This answers the second question negatively.
Proposition 4.6. Let $x_1, y_1 \in \mathbb{R}^{d_1}, x_2,y_2 \in \mathbb{R}^{d_2}$, and $x_3, y_3 \in \mathbb{R}^{d_3}$ be vectors such that each pair $x_i,y_i$ is linearly independent. Then the tensor $$x_1 \otimes x_2 \otimes y_3 + x_1 \otimes y_2 \otimes x_3 + y_1 \otimes x_2 \otimes x_3$$ has rank 3.
The tensor has rank 3 but in the decomposition we use $x_1$ as the first factor two times, so it's not necessary to have linearly independent factors in $\mathbb{R}^{d_1}$. The same goes for the other positions.
Claim: Let $e_1 = (1, 0 ) \in \mathbb{R}^2$ and $e_2 = (0,1) \in \mathbb{R}^2$. Then all of the following are instances of the counterexample you were looking for (ordered in lexicographical order):
$$ \begin{array}{rcccl} e_1 \otimes e_1 \otimes e_1 & + & e_1 \otimes e_2 \otimes e_2 & + & e_2 \otimes e_1 \otimes e_2 \\ e_1 \otimes e_1 \otimes e_1 & + & e_1 \otimes e_2 \otimes e_2 & + & e_2 \otimes e_2 \otimes e_1\\ e_1 \otimes e_1 \otimes e_1 & + & e_2 \otimes e_1 \otimes e_2 & + & e_2 \otimes e_2 \otimes e_1 \\ e_1 \otimes e_1 \otimes e_2 & + & e_1 \otimes e_2 \otimes e_1 & + & e_2 \otimes e_1 \otimes e_1 \\ e_1 \otimes e_1 \otimes e_2 & + & e_1 \otimes e_2 \otimes e_1 & + & e_2 \otimes e_2 \otimes e_2 \\ e_1 \otimes e_1 \otimes e_2 & + & e_2 \otimes e_1 \otimes e_1 & + & e_2 \otimes e_2 \otimes e_2 \\ e_1 \otimes e_2 \otimes e_1 & + & e_2 \otimes e_1 \otimes e_1 & + & e_2 \otimes e_2 \otimes e_2 \\ e_1 \otimes e_2 \otimes e_2 & + & e_2 \otimes e_1 \otimes e_2 & + & e_2 \otimes e_2 \otimes e_1 \end{array} $$
Sub-Claim 1: All of these tensors have canonical/CP rank $3$.
Sub-Claim 2: All of these tensors have multilinear rank $(2,2,2)$.
Proof of sub-claim 1: Given a tensor
$$u_1 \otimes u_2 \otimes u_3 + v_1 \otimes v_2 \otimes v_3 + w_1 \otimes w_2 \otimes w_3 $$
where $u_1, u_2 , u_3, v_1, v_2, v_3, w_1, w_2, w_3 \in \{e_1, e_2\}$, the following three constraints need to be satisfied in order for the tree terms to be minimal and thus the tensor rank equal to $3$:
Given a value for $u_1 \otimes u_2 \otimes u_3$, there is exactly one tensor where all three tensor factors are different, e.g. $e_2 \otimes e_1 \otimes e_2$ compared to $e_1 \otimes e_2 \otimes e_1$.
If constraint one is satisfied with a $v_1 \otimes v_2 \otimes v_3$ where all three tensor factors are different from $u_1 \otimes u_2 \otimes u_3$, then it is impossible to simultaneously satisfy both constraint 2 and constraint 3 because of the pigeonhole principle. This is because then $w_1 \otimes w_2 \otimes w_3$ would have to have exactly two different tensor factors compared to $u_1 \otimes u_2 \otimes u_3$ (in order to satisfy constraint 2) (because there is only one tensor with exactly three tensor factors different compared to $u_1 \otimes u_2 \otimes u_3$), so then by the pigeonhole principle $v_1 \otimes v_2 \otimes v_3$ would have to have at least two tensor factors in common with $w_1 \otimes w_2 \otimes w_3$, which would make it possible to combine those terms and decrease the tensor rank.
Therefore, it is possible to satisfy all three constraints simultaneously, then $v_1 \otimes v_2 \otimes v_3$ must differ from $u_1 \otimes u_2 \otimes u_3$ in exactly two tensor factors.
For the analogous reasons, if the second constraint is satisfied with $w_1 \otimes w_2 \otimes w_3$ with exactly three tensor factors different from $u_1 \otimes u_2 \otimes u_3$, since there is only one such tensor, constraint one would then have to be satisfied with a $v_1 \otimes v_2 \otimes v_3$ with exactly two tensor factors different from $u_1 \otimes u_2 \otimes u_3$. But the constraint three would not be satisfiable, since if $v_1 \otimes v_2 \otimes v_3$ differs from $u_1 \otimes u_2 \otimes u_3$ in two tensor factors, and $w_1 \otimes w_2 \otimes w_3$ differs from $u_1 \otimes u_2 \otimes u_3$ in three tensor factors, then $v_1 \otimes v_2 \otimes v_3$ and $w_1 \otimes w_2 \otimes w_3$ must have two tensor factors in common due to the pigeonhole principle and therefore it would be possible to combine them.
Therefore if it is possible to satisfy all three constraints simultaneously, then $w_1 \otimes w_2 \otimes w_3$ must differ from $u_1 \otimes u_2 \otimes u_3$ in exactly two tensor factors.
Also due to the pigeonhole principle, we have the following "transitivity" property: if $y_1 \otimes y_2 \otimes y_3$ differs from $x_1 \otimes x_2 \otimes x_3$ by exactly two tensor factors, and $z_1 \otimes z_2 \otimes z_3$ differs from $y_1 \otimes y_2 \otimes y_3$ in exactly two tensor factors, then either $x_1 \otimes x_2 \otimes x_3 = z_1 \otimes z_2 \otimes z_3$, or $z_1 \otimes z_2 \otimes z_3$ differs from $x_1 \otimes x_2 \otimes x_3$ in exactly two tensor factors.
(Because we change one tensor factor back to its original value for $x_1 \otimes x_2 \otimes x_3$, change a tensor factor that had been the same in $y_1 \otimes y_2 \otimes y_3$ compared to $x_1 \otimes x_2 \otimes x_3$ to something which is now different from $x_1 \otimes x_2 \otimes x_3$, and leave alone one of the two tensor factors in $y_1 \otimes y_2 \otimes y_3$ which was different from $x_1 \otimes x_2 \otimes x_3$, leading to two tensor factors total which are now different from $x_1 \otimes x_2 \otimes x_3$.)
Thus, if constraint one is satisfied with a $v_1 \otimes v_2 \otimes v_3$ with exactly two tensor factors different from $u_1 \otimes u_2 \otimes u_3$, and constraint two is satisfied with a $w_1 \otimes w_2 \otimes w_3$ with exactly two tensor factros different from $u_1 \otimes u_2 \otimes u_3$, then automatically we have that $v_1 \otimes v_2 \otimes v_3$ differs from $w_1 \otimes w_2 \otimes w_3$ in exactly two tensor factors, so that the third constraint is automatically satisfied.
By the arguments above, this also the only way to solve all three constraints simultaneously.
Since there are only eight possible values for $u_1 \otimes u_2 \otimes u_3$, the above arguments lead to exactly the eight combinations shown above for CP rank $3$ and order $3$ tensors whose factors are all $e_1$ or $e_2$. $\square$
Proof of sub-claim 2: The general idea is that for every relevant matricization of each one of these tensors, at least one of the first tensor factors will be $e_1$, at least one of the first tensor factors will be $e_2$, and then the remaining first tensor factor will be either $e_1$ or $e_2$, such that either way we get a rank $2$ matrix instead of a rank $3$ matrix. This is best probably illustrated with an example.
Consider the first example given above:
$$e_1 \otimes e_1 \otimes e_1 + e_1 \otimes e_2 \otimes e_2 + e_2 \otimes e_1 \otimes e_2 \,. $$
The mode $1$ matricization$\renewcommand{\vec}{\operatorname{vec}}$ is:
$$\begin{array}{rl} & e_1 \otimes \vec(e_1 \otimes e_1) + e_1 \otimes \vec(e_2 \otimes e_2) + e_2 \otimes \vec (e_1 \otimes e_2) \\ = & e_1 \otimes ( \vec(e_1 \otimes e_1) + \vec(e_2 \otimes e_2)) + e_2 \otimes \vec(e_1 \otimes e_2) \,. \end{array}$$
The mode $2$ matricization is:
$$\begin{array}{rl} & e_1 \otimes \vec(e_1 \otimes e_1) + e_2 \otimes \vec(e_1 \otimes e_2) + e_1 \otimes \vec(e_2 \times e_2) \\ = & e_1 \otimes (\vec(e_1 \otimes e_1) + \vec(e_2 \otimes e_2)) + e_2 \otimes \vec(e_1 \otimes e_2) \,. \end{array}$$
The mode $3$ matricization is:
$$\begin{array}{rl} & e_1 \otimes \vec(e_1 \otimes e_1) + e_2 \otimes \vec (e_1 \otimes e_2) + e_2 \otimes \vec(e_2 \otimes e_1) \\ = & e_1 \otimes \vec(e_1 \otimes e_1) + e_2 \otimes (\vec(e_1 \otimes e_2) + \vec(e_2 \otimes e_1)) \,. \end{array} $$
Clearly, all three of the matricizations above are matrices with rank $2$. The rank of the mode $1$ matricization is the same as the $1$-rank of the tensor, the rank of the mode $2$ matricization is the same as the $2$-rank of the tensor, and the rank of the mode $3$ matricization is the same as the $3$-rank of the tensor. Therefore, since all of those (matrix) ranks are equal to $2$, it follows that the multilinear rank of the tensor is $(2,2,2)$. So even though all of the multilinear ranks are equal, none of them equal the tensor/CP/canonical rank (which was shown above to be $3$).
A similar analysis holds for all of the other $7$ remaining tensors, which can be verified fairly easily by looking at them, but writing out the detailed proofs as the above is left as an exercise, for no other reason than it would take me a really long time to type them all out.
Note: You said you were also interested in counterexamples for even higher order tensors. Look at tensor $Q$ of p. 177 of Diaz, Lutoborski, Polynomial Foldings and Rank of Tensors, 2016.
Specifically, given vector spaces $U, V, W ,X$, with basises $\{u_1, u_2\}, \{v_1, v_2 \}, \{w_1, w_2\}, \{x_1, x_2 \}$, i.e. they're all two-dimensional. Then the tensor $Q$ is defined to be:
$$ Q = u_1 \otimes v_1 \otimes w_1 \otimes x_1 + u_2 \otimes v_2 \otimes w_2 \otimes x_2 + u_1 \otimes v_2 \otimes w_1 \otimes x_2 \,.$$
Then the multilinear rank of $Q$ is $(2,2,2,2)$. Also, the tensor rank of $Q$ is clearly bounded above by $3$ (since it was defined in terms of a three term sum of elementary tensors). Now the multiplex ranks of size $2$ of that tensor (defined in that tensor, see also many papers by Lek Heng Lim for definitions of multiplex rank) are $(3,2,3,3,2,3)$. Using Proposition 2.16 of that paper, where the tensor/CP/canonical rank is lower bounded by any component of any multiplex rank, we also see that the tensor rank of this tensor is greater than or equal to $3$. And of course, since it is both greater than or equal to and less than or equal to $3$, its tensor rank is $3$. Even though all of its multilinear ranks are equal and equal $2$, with $2 \not=3$. (One can also probably more directly show that $Q$ has tensor rank $3$ more directly using a combinatorial argument like I gave above.) Anyway this is a counterexample for a $4$th order tensor. I actually found the counterexamples for third order tensors above by trying to modify this counterexample from Diaz, Lutoborski.
Unfortunately I don't know of, nor have thought of, an algorithm for constructing counterexamples for any order, or how to systematically use counterexamples from lower orders to construct counterexamples for higher orders. But anyway considering how all of these counterexamples are for such low-dimensional spaces, it is certainly very suggestive of the possibility that such counterexamples exist generally, but again I don't know how to verify that or even whether it's actually true.
Best Answer
Note that to get the bound $\textrm {rank}\left(t\right)\leq n^{k-1}$ for $t\in F^n\otimes ...\otimes F^n$, suppose that $$t=\sum _{i=1}^r u_i \otimes v_i$$ with $u_1,...,u_r\in F^n\otimes ...\otimes F^n$ themselves rank-one with $k-1$ copies of $F^n$, and $v_1,...,v_r\in F^n$. Suppose that $r$ is the minimal number for such a decomposition. We will show that $u_1,...,u_r$ is linearly independent, and hence that $r\leq n^{k-1}$.
Suppose for contradiction that $u_1,...,u_r$ is linearly dependent $$\sum _{i=1}^r a_iu_i=0$$ without loss of generality, assume that $a_r\neq 0$ and hence we may assume $a_r= -1$. We have $$t=\sum _{i=1}^r u_i \otimes v_i$$ $$=\sum _{i=1}^{r-1} u_i \otimes v_i+u_r \otimes v_r$$ $$=\sum _{i=1}^{r-1} u_i \otimes v_i+\sum _{i=1}^{r-1} a_iu_i \otimes v_r$$ $$=\sum _{i=1}^{r-1} u_i \otimes \left(v_i+a_iv_r\right)$$ but this contradicts the minimality of $r$. Hence, $u_1,...,u_r$ is linearly independent, thus $\textrm {rank}\left(t\right)\leq n^{k-1}$.