Rank and border rank of Kronecker powers of tensors and Strassen's laser method (Q2062866)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Rank and border rank of Kronecker powers of tensors and Strassen's laser method |
scientific article |
Statements
Rank and border rank of Kronecker powers of tensors and Strassen's laser method (English)
0 references
3 January 2022
0 references
Given \(A\simeq B \simeq C \simeq \mathbb C^{q+1}\) complex vector spaces with basis \((a_i),(b_i),(c_i)\) respectively, one defines the little Coppersmith-Winograd tensor \[ T_{cw,q} := \sum_{j=1}^q a_0\otimes b_j\otimes c_j + a_j\otimes b_0 \otimes c_j + a_j\otimes b_j \otimes c_0 \ \in \left(\mathbb C^{q+1}\right)^{\otimes 3} \ . \] This tensor was used for upper bounds via Strassen's laser method of the exponent of matrix multiplication \(\omega\). In this work, the authors give results on the border rank of the Kronecker square \(T_{cw,q}^{\boxtimes 2}\) for \(q> 2\) and of the Kronecker cube \(T_{cw,q}^{\boxtimes 3}\) for \(q>4\): their main result (Theorem 1.4) negatively answers the question of wheter these Kronecker powers can lead to providing the upper bound \(\omega <2.3\). In order to overcome this barrier, the authors introduce a skew-symmetric version of \(T_{cw,q}\) (for \(q\) even), that is \[ T_{skewcw,q} := \sum_{j=1}^q a_0\otimes b_j \otimes c_j + \sum_{j=1}^q a_j\otimes b_0 \otimes c_j + \sum_{\xi =1}^{\frac{q}{2}}\left( a_{\xi}\otimes b_{\xi+\frac{q}{2}}-a_{\xi+\frac{q}{2}}\otimes b_{\xi}\right)\otimes c_0 \ \in \left( \mathbb C^{q+1}\right)^{\otimes 3} \ , \] and they show (Proposition 2.2) that \(T_{skewcw,q}\) could potentially be used to prove \(\omega=2\). After determining (Proposition 3.2) a lower bound for the border rank of \(T_{skewcw,q}\), the authors specialize to the case \(q=2\): they show (Lemma 2.8) that \(T_{skewcw,2}^{\boxtimes 2}\) is isomorphic to the determinant polynomial \(\det_3\in \mathbb C^9 \otimes \mathbb C^9 \otimes \mathbb C^9\), and prove (Theorem 1.6) new upper bounds for the Waring rank and Waring border rank of the latter.
0 references
matrix multiplication complexity
0 references
tensor rank
0 references
asymptotic rank
0 references
laser method
0 references
0 references
0 references
0 references