16
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ where did you get the upper bound? $\endgroup$
    – Turbo
    Jul 18, 2012 at 17:39
  • 1
    $\begingroup$ 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$. $\endgroup$ Jul 30, 2012 at 9:43
  • 2
    $\begingroup$ Oh, the question should really specify whether this is over $\mathbb{R}$ or $\mathbb{C}$ (I assumed $\mathbb{C}$). $\endgroup$ Jul 30, 2012 at 10:26

2 Answers 2

13
$\begingroup$

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.

$\endgroup$
0
11
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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