MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

A tensor rank of tree dimentional matrix $M[i,j,k], i,j,k\in [1,\ldots,n]$ is a 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 matrix of tensor rank at least $\frac{1}{3}n^2$. One can also easily show that every matrix is of tensor rank at most $n^2$.

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

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

share|cite|improve this question
where did you get the upper bound? – Turbo Jul 18 '12 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$. – Colin McQuillan Jul 30 '12 at 9:43
Oh, the question should really specify whether this is over $\mathbb{R}$ or $\mathbb{C}$ (I assumed $\mathbb{C}$). – Colin McQuillan Jul 30 '12 at 10:26
up vote 7 down vote accepted

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 so that is probably the best known upper bound.

share|cite|improve this answer
Thanks for an answer. – Klim Efremenko Jul 30 '12 at 11:29

Your Answer


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

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