Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
    
where did you get the upper bound? –  J.A 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
2  
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
add comment

1 Answer 1

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 http://arxiv.org/abs/0909.4262v4 so that is probably the best known upper bound.

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

Your Answer

 
discard

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.