What is the largest tensor rank on matrix. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T10:12:34Z http://mathoverflow.net/feeds/question/102559 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/102559/what-is-the-largest-tensor-rank-on-matrix What is the largest tensor rank on matrix. Klim Efremenko 2012-07-18T16:25:47Z 2012-07-30T10:10:03Z <p>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$. </p> <p>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> <p>p.s. As far as I understand maximal border rank is $\frac{1}{3}n^2$.</p> http://mathoverflow.net/questions/102559/what-is-the-largest-tensor-rank-on-matrix/103506#103506 Answer by Colin McQuillan for What is the largest tensor rank on matrix. Colin McQuillan 2012-07-30T10:10:03Z 2012-07-30T10:10:03Z <p>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 <i>Algebraic Complexity Theory</i>, by Peter Bürgisser, Michael Clausen, and Mohammad Amin Shokrollahi.</p> <p>An upper bound of $n^2−n−1$ is shown in <a href="http://arxiv.org/abs/0909.4262v4" rel="nofollow">http://arxiv.org/abs/0909.4262v4</a> so that is probably the best known upper bound.</p>