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
    0 references
    0 references
    0 references
    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
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references