Welcome to MathOverflow

Question

8

4

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

edited Jul 30 at 7:05

Kaveh
2,187●5●24

asked Jul 18 at 16:25

Klim Efremenko
1,399●4●14

where did you get the upper bound? – unknown (google) Jul 18 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 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 at 10:26

Colin McQuillan · Accepted Answer · 2012-07-30 10:10:03Z UTC

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.

What is the largest tensor rank on matrix.

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.