CS Paper Radar

Concise tensors with maximal symmetries

Annika Holtrup, Jeroen Zuiddam

cs.CC math.AGmath.GR ·submitted 2026-09-15 14:54 UTC · v1
theory

Abstract

Conner, Gesmundo, Landsberg and Ventura (2019) determined the largest stabilizer dimension of concise $n\times n \times n$ tensors that are binding, and they determined the corresponding maximizing tensors to be the null algebra tensors. They left as an open problem to extend this to all concise $n \times n \times n$ tensors (i.e. dropping binding). We solve this problem: We prove that the largest stabilizer dimension of concise $n\times n\times n$ tensors is $n^2 + 1$ and the maximizers are the null algebra tensors (as in the binding case) and the skew symmetric tensor $e_1 \wedge e_2 \wedge e_3$. As part of our approach we obtain upper bounds on the stabilizer dimension of matrix tuples under left-right action (generalized Kronecker quiver representations), which we think are of independent interest.

Closest papers

Nearest neighbours by meaning across the whole index.

Identifiability of Nonnegative Tensor Decompositions via Positive Scattering

cs.LG stat.MLmath.COmath.ST ·2026-09-10 ·Haoming Wang, Ming Yuan
theory similarity 0.59
Abstract

Identifiability of tensor decompositions is often established through linear-algebraic conditions on the factor families. For nonnegative decompositions, however, positivity provides additional information that is not captured by dimension and independence alone: nonnegative terms cannot cancel, and their supports constrain competing decompositions. We introduce a positive scattering term that quantifies this additional source of identifiability and combine it with the dimension budget underlying the Lovitz--Petrov generalization of Kruskal's theorem. For every subset of components, we obtain two sufficient conditions: a threshold of $2|S|-2$ guarantees minimality and nonnegative rank, while the stronger threshold $2|S|-1$ guarantees uniqueness among nonnegative decompositions of the same length. The key result is a positive splitting inequality for irreducible exchanges of nonnegative rank-one tensors, which combines the dimension constraint with support-induced geometric rigidity. Although the scattering term is defined through an optimization over intermediate factor spaces, we show that its mode costs are exactly $0$, $1$, or $+\infty$, yielding an exact activation characterization in terms of graph connectivity. The resulting criterion can strictly certify sparse nonnegative tensor decompositions beyond the reach of Kruskal and Lovitz--Petrov conditions, including examples for which those conditions fail even after reshaping. In the matrix case, the two criteria reduce respectively to full-rank factorization and two-sided separability.

0.36

Semidirect sums of tensors and the matrix multiplication exponent

cs.CC cs.DS ·2026-11-03 ·Baitian Li
position similarity 0.59
Abstract · 31 pages, 1 figure

This note is an exposition of the recent preprints from OpenAI that establish the bound $ω\leq 9/4$ on the matrix multiplication exponent. We argue that the heart of these preprints is a new technique, which we formulate as the untwisting lemma for semidirect sums of tensors. This gives a generally applicable method for analyzing tensors. We also discuss further consequences of this method, as well as the relation between the OpenAI proof and previous work.

0.23

Structure and Exact Certification of Nonnegative Tensor Decompositions

cs.DS cs.CCmath.AGmath.CO+1 ·2026-10-23 ·Haoming Wang, Ming Yuan
theory similarity 0.58
Abstract

We study the structure and exact certification of nonnegative tensor decompositions supplied through rational factor matrices. Every failure of minimality or essential uniqueness contains an irreducible positive exchange between $p$ supplied terms and $q$ competing terms. A dimension count based on the Lovitz--Petrov splitting theorem bounds the effective order of such an exchange, the sum over the modes of the joint factor-span dimension minus one, by $p+q-2$, and this bound is attained at every supplied length $R\ge2$. After eliminating ambient-row variables by the Farkas lemma, the resulting semialgebraic systems have fewer than $2R^2$ real variables. For input bit length $L$, this gives a deterministic $G(R)L^{O(R^2)}$-time algorithm that computes the nonnegative rank and an exact minimum-length decomposition, decides minimality and essential uniqueness, and returns exact witnesses when either property fails. The exponent is independent of the tensor order and the mode dimensions. For Lebesgue moment tensors, positive quadrature determines the nonnegative rank and the uniqueness behavior, and some rational length-$R$ inputs force a common field of degree at least $\lfloor R/2\rfloor!$ for any exact minimum-length output. As an illustration, an implementation resolves all 114 instances left inconclusive by earlier positive-scattering criteria, of which 95 are minimal and essentially unique and 19 are minimal but nonunique.

0.12

Disjoint and nearly disjoint sums of matrix multiplication tensors and their centroids

cs.CC math.AGmath.ACmath.RA ·2026-08-27 ·Martin Kassabov, J. M. Landsberg, Victor Souza, Philip Speegle
theory similarity 0.58
Abstract · 52 pages, 3 figures

This paper addresses centroids, which are fundamental invariants of tensors. Our main results are as follows: (i) The construction of explicit tensors with very large centroids, whereas previously it had been conjectured that none such exist. (ii) An upper bound on the dimension of the centroid that is essentially attained by our examples. (iii) The development of a geometric technique to write down border rank decomposition of tensors using centroids and "extended centroids". (iv) The technique is applied to tensors of this paper to prove they are of minimal border rank. The technique is versatile and enables us to geometrically derive and improve upon previous ad hoc decompositions. (v) The construction of symmetric tensors with large centroids and proof that they are wild in the sense of Buczyńska-Buczyński. Our results also pave the way for new upper bounds on the exponent of matrix multiplication. The geometric technique also constructs new "better" tensors for Strassen's laser method from old, and we apply this to the tensors of Strassen and Schönhage to get better tensors in the sense that they give better upper bounds on the exponent than the original tensors.

0.46

Tensor value and the 9/4 bound for matrix multiplication

cs.CC math.RT ·2026-11-06 ·Mahmut Levent Doğan, Vladimir Lysikov, Keiya Sakabe, Michael Walter
theory similarity 0.58
Abstract

We give an exposition of OpenAI's recent result that the exponent of matrix multiplication is at most 9/4 valid over every field. Our main tool is a fractional symmetrized variant of the tensor value introduced by Coppersmith and Winograd, used in place of spectral points (tensor characters) in the original proof. We prove a superadditivity inequality for a power of this value on partially direct sums, whose summands share one tensor factor and occupy independent subspaces in the other two. Together with the degenerations of polynomial multiplication tensors from the OpenAI proof, this inequality yields the bound.

0.08

A Lower Bound of 21 for $3\times3$ Matrix Multiplication over $\mathbb{F}_2$

cs.CC cs.DS ·2026-09-06 ·Chengu Wang
theory similarity 0.56
Abstract

We prove that $3\times3$ matrix multiplication over $\mathbb{F}_2$ has bilinear complexity at least $21$, improving the previous lower bound of $20$. Lower bounds for restrictions of the first input constrain how many first factors of a decomposition can lie in each subspace. For a hypothetical $20$-term decomposition, the strengthened restriction bounds force all first factors of matrix rank at least two into a single coset of a three-dimensional rank-one subspace. An exhaustive computation finds no admissible first-factor profile with $20$ terms. We also prove that $2\times3$ by $3\times3$ matrix multiplication over $\mathbb{F}_3$ has rank exactly $15$: three profiles with $14$ terms survive the corresponding computation up to symmetry, and short restriction arguments exclude them. We combine Wang's automated framework for tensor-rank lower bounds with D'Ambrosio's capacity-and-profile strategy. Our computational contributions are rank-one-span searches that strengthen the subspace lower-bound table and a direct, symmetry-reduced profile enumerator that enforces all subspace capacities simultaneously.

0.28

Polynomial Separation of a Shared Tensor Leg and Matrix Multiplication in Arbitrary Characteristic

cs.CC ·2026-10-12 ·Houxi Lü
theory similarity 0.56
Abstract

We improve the shared-leg separation construction in Proposition 3.1 of OpenAI, *An Upper Bound of $9/4$ for the Matrix Multiplication Exponent* (October 2, 2026). If $M$ tensor blocks have a common first space and independent matched sectors on their other two spaces, then $M+n-1$ copies of their matched sum degenerate to the full direct sum of the blocks, each tensored with an $n$-dimensional dot product. For $n=M$, this reduces the number of source copies from $5M$ to $2M-1$. The construction uses polynomial interpolation and truncated local substitution, with no roots of unity or factorial denominators. It works over every field containing enough distinct elements. We verify that the remaining spectral and discrete-growth arguments of the cited preprint are independent of characteristic. Over an algebraic closure, the replacement therefore gives $ω\leq9/4$ in every characteristic.

0.46

Border rank=rank for Kruskal tensors and a Kruskal's theorem for skew decompositions

cs.DS math.AG ·2026-08-21 ·Alexander Taveira Blomenhofer, Benjamin Lovitz
theory similarity 0.55
Abstract · 33 pages

We show that border rank is equal to rank for Kruskal tensors. We also give an analogous Kruskal condition for alternating tensors, which certifies uniqueness of skew rank decompositions. Furthermore, we show that border skew rank is equal to skew rank for alternating Kruskal tensors, and we give an algorithm to find the minimum skew rank decomposition of alternating Kruskal tensors.

0.49