The moment polytope of matrix multiplication is not maximal
Maxim van den Berg, Matthias Christandl, Vladimir Lysikov, Harold Nieuwboer, Michael Walter, Jeroen Zuiddam · 2025
Read The moment polytope of matrix multiplication is not maximal by Maxim van den Berg, Matthias Christandl, Vladimir Lysikov, Harold Nieuwboer, Michael Walter, Jeroen Zuiddam (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-22633.txt.
Introduction
Maxim van den Berg and co-authors prove that a shape tied to matrix multiplication falls short of its outer bound, in a 2025 paper. The shape is the moment polytope, a convex body that sums up a tensor's hidden symmetries. Such shapes serve quantum theory, where they chart entanglement, and complexity theory, where they frame how fast matrices can multiply.
The team pulls the multiplication tensor's shape apart from the unit tensor's shape. That gap proves the first sits strictly inside the Kronecker polytope, so it is not maximal. The same gap kills a hoped-for test that would read shape inclusion off long-run behavior of tensors. Iterated multiplication inherits the shortfall. The proof sorts which uniform points lie in such shapes and ties them to polynomial multiplication through the rank of matrix spaces. A side gain is a fresh proof of the best known bound on border subrank.
Catalog record
| CREATOR | Maxim van den Berg, Matthias Christandl, Vladimir Lysikov, Harold Nieuwboer, Michael Walter, Jeroen Zuiddam |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-22633
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The moment polytope of matrix multiplication is not maximal Maxim van den Berg, Matthias Christandl, Vladimir Lysikov, Harold Nieuwboer, Michael Walter, Jeroen Zuiddam Abstract Moment polytopes of tensors, the study of which is deeply rooted in invariant theory, representation theory and symplectic geometry, have found relevance in numerous places, from quantum information (entanglement polytopes) and algebraic complexity theory (GCT program and the complexity of matrix multiplication) to optimization (scaling algorithms). Towards an open problem in algebraic complexity theory, we prove separations between the moment polytopes of matrix multiplication tensors and unit tensors. As a consequence, we find that matrix multiplication moment polytopes are not maximal, i.e. are strictly contained in the corresponding Kronecker polytope. As another consequence, we obtain a no-go result for a natural operational characterization of moment polytope inclusion in terms of asymptotic restriction. We generalize the separation and non-maximality to moment polytopes of iterated matrix multiplication tensors. Our result implies that tensor networks where multipartite entanglement structures beyond two-party entanglement are allowed can go beyond projected entangled-pair states (PEPS) in terms of expressivity. Our proof characterizes membership of uniform points in moment polytopes of tensors, and establishes a connection to polynomial multiplication tensors via the minrank of matrix subspaces. As a result of independent interest, we extend these techniques to obtain a new proof of the optimal border subrank bound for matrix multiplication. 1 Introduction Moment polytopes of tensors, the study of which is deeply rooted in invariant theory, representation theory and symplectic geometry [ NM84 , Bri87 ] , have found relevance in numerous places, from algebraic complexity theory (in particular, the geometric complexity program [ BI11 , BCI11 ] and asymptotic spectra [ Str05 , CVZ21 , WZ22 ] ) and quantum information (quantum marginals and entanglement polytopes [ CM06 , Kly04 , CHM07 , WDGC13 , SOK14 , Wal14 ] ) to optimization (scaling algorithms [ BFG+18 , BFG+19 ] ). These polytopes admit various descriptions, notably in terms of the types of irreducible representations that appear in the Schur–Weyl decomposition of powers of the tensor and in terms of quantum marginals of elements in the orbit closure of the tensor. Bürgisser and Ikenmeyer [ BI11 , Problem 7.3] , motivated by questions in algebraic complexity and quantum information, posed as a central open problem to determine the moment polytopes of the matrix multiplication tensors and the unit tensors (diagonal tensors). A construction of Bürgisser, Christandl and Ikenmeyer [ BCI11 , Theorem 1] implies that the moment polytope of the unit tensor contains all points which are uniform on two of the three subsystems. However, no further progress has been made on this problem since then. We prove separations between moment polytopes of matrix multiplication and unit tensors of varying sizes. As a consequence, we find that the moment polytope of matrix multiplication is not equal to the maximal moment polytope (i.e. the Kronecker polytope). We extend this to separations and non-maximality for iterated matrix multiplication tensors, and derive implications for the expressivity of tensor network representations of quantum states (which has seen much recent interest, e.g. [ CLVW20 , CLS+24 , LQY12 , BDLG22 ] ). We summarize our main results here and discuss these in more detail in the rest of the paper: • We prove a range of separations between moment polytopes of tensors, namely for matrix multiplication and unit tensors (diagonal tensors). These in particular imply strictness of inclusions of matrix multiplication moment polytopes in Kronecker polytopes. This constitutes the first progress towards an open problem of Bürgisser and Ikenmeyer [ BI11 , Problem 7.3] , going beyond previous constructions of moment polytope points of Bürgisser, Christandl and Ikenmeyer [ BCI11 , Theorem 1] . • As a central ingredient for the above we further develop minrank of tensors and polynomial multiplication tensors. We use these ingredients to give a new proof of the optimal border subrank upper bound for matrix multiplication tensors that was previously obtained using geometric rank [ Str87 , KMZ23 ] . • As another consequence, we rule out an, a priori natural, asymptotic characterization of moment polytope inclusion in terms of asymptotic restriction, which originates from the study of matrix multiplication algorithms [ Str87 , CVZ21 ] . • In the context of quantum information theory, as a consequence of the above, we show there exist joint marginals realizable by pure multipartite quantum states, which are not realizable (even approximately) by matrix product states (MPS) with certain bond dimensions. This implies that projected entangled-pair states (PEPS) become more expressive when allowing genuine multipartite entanglement structures beyond the standard choice of two-party maximally entangled states. Moment polytopes of tensors Let V=\mathbb{C}^{a}\otimes\mathbb{C}^{b}\otimes\mathbb{C}^{c} be the space of a\times b\times c tensors. The product of general linear groups \mathrm{GL}=\mathrm{GL}_{a}\times\mathrm{GL}_{b}\times\mathrm{GL}_{c} naturally acts on V by local basis transformations. 1 1 1 We may leave a,b,c implicit when clear from the context and just refer to \mathrm{GL} . To every T\in V are naturally associated linear maps T_{1}\colon\mathbb{C}^{a}\to\mathbb{C}^{b}\otimes\mathbb{C}^{c} , T_{2}\colon\mathbb{C}^{b}\to\mathbb{C}^{a}\otimes\mathbb{C}^{c} and T_{3}\colon\mathbb{C}^{c}\to\mathbb{C}^{a}\otimes\mathbb{C}^{b} from which we obtain positive semidefinite matrices T_{1}\!^{*}T_{1}\in\mathbb{C}^{a\times a} , T_{2}\!^{*}T_{2}\in\mathbb{C}^{b\times b} and T_{3}\!^{*}T_{3}\in\mathbb{C}^{c\times c} . Let \displaystyle\mu_{i}\colon T\mapsto\frac{T_{i}\!^{*}T_{i}}{\Tr(T_{i}\!^{*}T_{i})}. (1.1) The moment map \mu\colon\mathbb{C}^{a}\otimes\mathbb{C}^{b}\otimes\mathbb{C}^{c}\setminus\{0\}\to\mathbb{C}^{a\times a}\times\mathbb{C}^{b\times b}\times\mathbb{C}^{c\times c} is defined by \displaystyle\mu(T)\coloneqq\big(\mu_{1}(T),\mu_{2}(T),\mu_{3}(T)\big). (1.2) Note that \Tr(T_{i}^{*}T_{i})=\lVert T\rVert^{2} does not depend on i . For any positive semidefinite matrix M\in\mathbb{C}^{n\times n} , let \spec(M)=(\lambda_{1},\lambda_{2},\ldots,\lambda_{n})\in\mathbb{R}^{n} , where \lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}\geq 0 , denote the eigenvalues of M , non-increasingly ordered. Define \spec(\mu(T))\coloneqq\big(\spec(\mu_{1}(T))\mid\spec(\mu_{2}(T))\mid\spec(\mu_{3}(T))\big)\in\mathbb{R}^{a}\times\mathbb{R}^{b}\times\mathbb{R}^{c}, where \mid separates the three components of \mathbb{R}^{a}\times\mathbb{R}^{b}\times\mathbb{R}^{c} . Definition 1.1 . For any irreducible algebraic variety W\subseteq\mathbb{C}^{a}\otimes\mathbb{C}^{b}\otimes\mathbb{C}^{c} that is closed under the action of \mathrm{GL} , the moment polytope of W is defined as \Delta(W)\coloneqq\big\{\spec(\mu(S))\mid S\in W\setminus\{0\}\big\}\subseteq\mathbb{R}^{a}\times\mathbb{R}^{b}\times\mathbb{R}^{c}.\, In the context of quantum information theory, the moment polytopes is also called the entanglement polytope of W [ WDGC13 ] . Note that because \mathrm{GL} can scale elements of \mathbb{C}^{a}\otimes\mathbb{C}^{b}\otimes\mathbb{C}^{c} , any algebraic variety W that is closed under \mathrm{GL} is an (algebraic) cone. Because \mu is invariant under scaling, we may equivalently work in projective space. This is the viewpoint of Ness, Mumford and Brion. We state their result in our setting. Theorem 1.2 ( [ NM84 , Bri87 , WDGC13 ] 2 2 2 To be able to apply the theorem of Mumford–Ness and Brion, we furthermore need to show show that irreducibility of a variety W that is a cone is equivalent to irreducibility of the projective variety \mathbb{P}(W)\subseteq\mathbb{P}(V) consisting of the lines through W , which is not hard to do. ) . Let W\subseteq\mathbb{C}^{a}\otimes\mathbb{C}^{b}\otimes\mathbb{C}^{c} be an irreducible algebraic variety that is closed under the action of \mathrm{GL} . Then \Delta(W) is a (bounded convex) polytope with rational vertices. For any tensor T\in\mathbb{C}^{a}\otimes\mathbb{C}^{b}\otimes\mathbb{C}^{c} , let \mathrm{GL}\cdot T denote its \mathrm{GL} -orbit and \overline{\mathrm{GL}\cdot T} the closure in the Euclidean topology (which is the same as the Zariski-closure 3 3 3 This is because the orbit is constructible [ Bor12 , Section AG.1.3, Corollary AG.10.2] . ). The orbit closure \overline{\textnormal{GL}\cdot T} is also irreducible 4 4 4 The group GL is irreducible as it is connected [ Bor12 , Proposition I.1.2] , which implies that \overline{\textnormal{GL}\cdot T} is irreducible as well. . The moment polytope of T is then defined as \Delta(T)\coloneqq\Delta\bigl(\overline{\mathrm{GL}\cdot T}\bigr). There is a second description of