# What is the largest tensor rank of $n \times n \times n$ tensor?

The tensor rank of a three dimensional array $M[i,j,k], i,j,k\in [1,\ldots,n]$ is the minimal number of vectors $x_i,y_i,z_i$, such that $M=\sum_{i=1}^d x_i\otimes y_i\otimes z_i$. From dimension argument it easily follows that there exists a tensor of tensor rank at least $\frac{1}{3}n^2$. One can also easily show that every tensor is of tensor rank at most $n^2$.

So I know that the maximal tensor rank is between $\frac{1}{3}n^2$ and $n^2$. Does any one know what is the maximal tensor rank?

p.s. As far as I understand maximal border rank is $\frac{1}{3}n^2$.

• where did you get the upper bound? Jul 18, 2012 at 17:39
• unknown: we can write the $n\times n\times n$ tensor $M$ in the form $\sum_1^n e_i\otimes M_i$ where $\{e_i\}$ is a basis and $M_i$ are $n\times n$ matrices. Each term $e_i\otimes M_i$ has rank at most $n$, so $M$ has rank at most $n^2$. Jul 30, 2012 at 9:43
• Oh, the question should really specify whether this is over $\mathbb{R}$ or $\mathbb{C}$ (I assumed $\mathbb{C}$). Jul 30, 2012 at 10:26

The lower bound can be improved slightly to $n^3/(3n-2)$ by noting that in $x\otimes y\otimes z$ one can assume $|y|=|z|=1$. See also Chapter 20, "Typical Tensorial Rank", in the book Algebraic Complexity Theory, by Peter Bürgisser, Michael Clausen, and Mohammad Amin Shokrollahi.
An upper bound of $n^2−n−1$ is shown in http://arxiv.org/abs/0909.4262v4 so that is probably the best known upper bound.
For tensors in $\mathbb{R}^3 \otimes \mathbb{R}^3 \otimes \mathbb{R}^3$ or in $\mathbb{C}^3 \otimes \mathbb{C}^3 \otimes \mathbb{C}^3$, the maximum rank is $5$. See Bremner, Hu, On Kruskal's theorem that every $3 \times 3 \times 3$ array has rank at most $5$, 2013 (MR3089693). (Their proof in the complex case also works for any algebraically closed field of characteristic not equal to $2$. Interestingly, over the field with two elements there are $3 \times 3 \times 3$ tensors of rank $6$.)
For tensors in $\mathbb{R}^n \otimes \mathbb{R}^n \otimes \mathbb{R}^n$ or in $\mathbb{C}^n \otimes \mathbb{C}^n \otimes \mathbb{C}^n$, for $n \geq 4$, the maximum rank is at most $\binom{n+1}{2}$. See Atkinson, Lloyd Bounds on the ranks of some 3-tensors, 1980 (MR0570374). (They state the result only over $\mathbb{C}$, but say that "however, many of our techniques remain valid for arbitrary fields of characteristic zero". I have not tried to figure out if their proof works over $\mathbb{R}$.) Alternatively, see Theorem 1 and Theorem 3 of Sumi, Miyazaki, Sakata, About the maximal rank of $3$-tensors over the real and the complex number field, 2010 (MR2652318). (Theorem 4 of this paper also gives the upper bound $5$ in the $n=3$ case.)
I think it is still open what the actual maximal rank is for $n \geq 4$, but this narrows down the range to be between $n^3/(3n-2)$ and $\binom{n+1}{2}$.