5
$\begingroup$

Let $V$ be a vector space of dimension $n$. Let us consider $V^{\otimes n}=V\otimes V \ldots \otimes V$. This vector space contains one dimentional vector space $\wedge^n V$. My question is does it something is known about the tensor rank of the vector $\wedge^n V$?

More formally let $e_1, e_2,\ldots e_n$ be a basis for $V$ than the question is what does it known about the tensor rank of:$$ T=\sum_{\sigma \in S_n}(-1)^{sign(\sigma)} e_{\sigma(1)}\otimes e_{\sigma(2)} \otimes \ldots \otimes e_{\sigma(n)}.$$

The trivial upper bound on the tensor rank of this form is $n!$. Does it know any better uper bound?

As far as I know without $(-1)^{sign(\sigma)}$(i.e. for a symmetric form) it know upper bound of $2^n$.

$\endgroup$
  • 3
    $\begingroup$ What is the tensor rank? $\endgroup$ – Sasha Dec 20 '12 at 5:37
  • $\begingroup$ @Sasha, see here for a definition: its.caltech.edu/~matilde/WeitzMa10Abstract.pdf $\endgroup$ – Qfwfq Dec 20 '12 at 10:01
  • 2
    $\begingroup$ I don't know the answer to your question, but I know that there is quite a lot of work on computing and bounding tensor ranks in the algebraic geometry community. You might try writing to any of M. Catalisano, A.V. Geramita, A. Gimigliano, J.M. Landsberg, and/or Jerzy Weyman and asking them your question. (I don't know that they read MO, so they might not otherwise know about it.) $\endgroup$ – Robert Bryant Dec 21 '12 at 16:59
  • 1
    $\begingroup$ For symmetric tensors, I think your problem is called 'Waring Problem for polynomials'. Specifically, identifying symmetric tensors with polynomials, the Waring problem asks- given a homogeneous polynomial of degree d, what is the minimum number of d-th powers of a linear polynomial that are needed to write the given polynomial. The generic number has been known for a while and is called (i hope i'm remembering correctly) the Alexander-Hirshowitz theorem. The problem of given a monomial, how many dth forms are needed to write it was just solved and is on the arxiv. $\endgroup$ – meh Jan 17 '13 at 17:15
  • $\begingroup$ Here is a link - arxiv.org/abs/1110.0745 . I think the rank of 'detrminant' considered as a symmetric tensor must be known, but I do't know it ! $\endgroup$ – meh Jan 17 '13 at 17:17
2
$\begingroup$

The tensor ranks of determinants and permanents are currently not known. In the $3 \times 3$ case it is known: the $3 \times 3$ determinant has tensor rank $5$ and the $3 \times 3$ permanent has tensor rank $4$. Here, $5$ is better than the naive $n!=3!=6$. Upper bounds are known. An identity due to Derksen shows that the $n \times n$ determinant has tensor rank at most $\left(\dfrac{5}{6}\right)^{\lfloor n/3 \rfloor} n!$, instead of $n!$. An identity due to Glynn shows that the $n \times n$ permanent has tensor rank at most $2^{n-1}$.

To be clear, perhaps I should have said first that the tensor $T$ described in the question can be identified with the determinant of a generic $n \times n$ matrix (each $e_i$ stands for the $i$th column [or $i$th row]). And without the signs, the resulting tensor is known as the "permanent". The original question as I understand it is asking about an upper bound for the tensor rank of the determinant and permanent.

For some context about what is the meaning of tensor ranks of determinant and permanent, and why comparisons between those particular things might be of interest, see for example Landsberg, Geometric complexity theory: an introduction for geometers, 2015 (MR3343444).

Derksen's identity for the $3 \times 3$ determinant is in his article Derksen, On the nuclear norm and the singular value decomposition of tensors, 2016 (MR3494510). It may be interesting to see the identity explicitly here. First of all the $3 \times 3$ determinant, as noted in the original question, is the following tensor in $(\Bbbk^3)^{\otimes 3}$: $$ \begin{multline} e_1 \otimes e_2 \otimes e_3 + e_2 \otimes e_3 \otimes e_1 + e_3 \otimes e_1 \otimes e_2 \\ - e_1 \otimes e_3 \otimes e_2 - e_2 \otimes e_1 \otimes e_3 - e_3 \otimes e_2 \otimes e_1 . \end{multline} $$ (This corresponds to the familiar-to-undergraduates method of computing $3 \times 3$ determinants by adding the "downward" diagonals and subtracting the "upward" diagonals.) Derksen observed that this same tensor is equal to: $$ \begin{multline} \frac{1}{2} \Big( (e_3+e_2) \otimes (e_1-e_2) \otimes (e_1+e_2) + (e_1+e_2) \otimes (e_2-e_3) \otimes (e_2+e_3) \\ + 2 e_2 \otimes (e_3 - e_1) \otimes (e_3 + e_1) + (e_3-e_2) \otimes (e_2+e_1) \otimes (e_2-e_1) \\ + (e_1-e_2) \otimes (e_3+e_2) \otimes (e_3-e_2) \Big). \end{multline} $$ This uses $5$ terms. (I suppose we had better require $2^{-1} \in \Bbbk$.) By Laplace expansion, all $n \times n$ determinants can be expanded using "blocks" of $3 \times 3$ minors, and each "block" has this gain of rank $5$ instead of $6$, resulting in the above mentioned upper bound for tensor rank of determinant.

As of October 2017 this is, to my knowledge, the best known upper bound for tensor rank of the determinant.

It turns out that it has been known for quite some time that the maximum rank of any tensor in $(\Bbbk^3)^{\otimes 3}$ is $5$, which forces the existence of some rank $5$ expression for determinant. So an identity like Derksen's could have been observed a long time ago (decades ago). In stating this I have no intention whatsoever of taking anything away from Derksen, who was the one who finally considered this and found the above explicit expression. (But when I finally understood what Derksen had managed to do, I did spend a frantic week looking at every upper bound for rank I could find, and sadly for me, the upper bound of $5$ in $(\Bbbk^3)^{\otimes 3}$ turned out to be the only meaningful one for determinants or permanents. Oh well.)

The upper bound of $2^{n-1}$ for the tensor rank of permanent is by an identity due to Glynn, in Glynn, The permanent of a square matrix, 2010 (MR2673027). As of October 2017 it is, to my knowledge, the best known upper bound for the tensor rank of the permanent.

The lower bounds for the tensor ranks of the $3 \times 3$ determinant and permanent is in Ilten, Teitler, Product ranks of the $3 \times 3$ determinant and permanent, 2016 (MR3492642). That article presents the results in terms of "product rank" rather than tensor rank, but the article includes an explanation of the relationship between these notions of rank, including showing how to get the results about tensor ranks of determinants and permanents.

So we know the tensor ranks of $3 \times 3$ determinants and permanents (the tensor ranks are $5$ and $4$, respectively). But that's it; for $4 \times 4$ it is open. Glynn's identity shows that the $4 \times 4$ permanent has tensor rank at most $8$, and Derksen's identity shows that the $4 \times 4$ determinant has tensor rank at most $20$ (via Laplace expansion across the top row, into a sum over $4$ determinants of $3 \times 3$ minors, each with rank $5$). I'm not sure what exactly are the current best lower bounds, but I believe they are something like this. A result of Shafiei shows that the $4 \times 4$ permanent has Waring rank at least $\frac{1}{2}\binom{8}{4} = 35$; this bound for Waring rank implies the tensor rank is at least $\lceil \frac{35}{8} \rceil = 5$. A result of Derksen and myself shows that the $4 \times 4$ determinant has Waring rank at least $\binom{8}{4}-\binom{6}{3}=50$, hence tensor rank at least $\lceil \frac{50}{8}\rceil = 7$. (This business with Waring ranks and tensor ranks is explained in my paper with Harm Derksen, and also in my paper with Nathan Ilten, mentioned above.) There do exist other lower bound results, I'm just not sure right now if any of them give stronger bounds in these examples.

In summary, the $4 \times 4$ permanent has tensor rank between $5$ and $8$ (inclusive) and the $4 \times 4$ determinant has tensor rank between $7$ and $20$ (inclusive).

Regarding @aginensky's comment, it's not only the tensor ranks (and product ranks) which are completely up in the air; the Waring ranks, equivalently symmetric ranks when considered as symmetric tensors, are also completely unknown, even for the $3 \times 3$ case!

$\endgroup$
  • $\begingroup$ Small update: Krishna-Makam in arxiv.org/abs/1801.00496 found a similar identity to Derksen's identity, but without using $2^{-1}$; defined over the integers (in fact, all coefficients in $\{1,0,-1\}$). So the $3 \times 3$ determinant has rank $\leq 5$ in all characteristics... even, over any commutative ring, I guess. $\endgroup$ – Zach Teitler Aug 21 '19 at 15:28

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.