Tensor rank of anti-symmetric tensor

Question

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

Answer 1

In a new preprint, we show that the tensor rank of the $n\times n$ determinant is at most the n’th Bell number:

A New Formula for the Determinant and Bounds on Its Tensor and Waring Ranks, Robin Houston, Adam P. Goucher, Nathaniel Johnston

For example, the 4×4 determinant has tensor rank at most 15: if $A$ is a general 4×4 matrix with entries $a_{i,j}$, then

$$\begin{align}\begin{split} \det(A) & = a_{1,1}a_{2,2}a_{3,3}a_{4,4} \\ & \quad - (a_{1,2}+a_{1,3}+a_{1,4})(a_{2,1}+a_{2,3}+a_{2,4})(a_{3,1}+a_{3,2}+a_{3,4})(a_{4,1}+a_{4,2}+a_{4,3}) \\ & \quad + (a_{1,1}+a_{1,2}+a_{1,3}+a_{1,4})(a_{2,3}+a_{2,4})(a_{3,2}+a_{3,4})(a_{4,2}+a_{4,3}) \\ & \quad + (a_{1,3}+a_{1,4})(a_{2,1}+a_{2,2}+a_{2,3}+a_{2,4})(a_{3,1}+a_{3,4})(a_{4,1}+a_{4,3}) \\ & \quad + (a_{1,2}+a_{1,4})(a_{2,1}+a_{2,4})(a_{3,1}+a_{3,2}+a_{3,3}+a_{3,4})(a_{4,1}+a_{4,2}) \\ & \quad + (a_{1,2}+a_{1,3})(a_{2,1}+a_{2,3})(a_{3,1}+a_{3,2})(a_{4,1}+a_{4,2}+a_{4,3}+a_{4,4}) \\ & \quad - a_{1,2}a_{2,1}(a_{3,1}+a_{3,2}+a_{3,3})(a_{4,1}+a_{4,2}+a_{4,4}) \\ & \quad - a_{1,3}(a_{2,1}+a_{2,2}+a_{2,3})a_{3,1}(a_{4,1}+a_{4,3}+a_{4,4}) \\ & \quad - a_{1,4}(a_{2,1}+a_{2,2}+a_{2,4})(a_{3,1}+a_{3,3}+a_{3,4})a_{4,1} \\ & \quad - (a_{1,1}+a_{1,2}+a_{1,3})a_{2,3}a_{3,2}(a_{4,2}+a_{4,3}+a_{4,4}) \\ & \quad - (a_{1,1}+a_{1,2}+a_{1,4})a_{2,4}(a_{3,2}+a_{3,3}+a_{3,4})a_{4,2} \\ & \quad - (a_{1,1}+a_{1,3}+a_{1,4})(a_{2,2}+a_{2,3}+a_{2,4})a_{3,4}a_{4,3} \\ & \quad + 2a_{1,2}a_{2,1}a_{3,4}a_{4,3} \\ & \quad + 2a_{1,3}a_{2,4}a_{3,1}a_{4,2} \\ & \quad + 2a_{1,4}a_{2,3}a_{3,2}a_{4,1}. \end{split}\end{align}$$

The formula leads to some tighter bounds for fields of non-zero characteristic, especially finite fields. The tightest new result we have is that the tensor rank of the 4×4 determinant over the field with two elements is exactly 12: see Appendix B.

Answer 2

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!