PaperlayerView exact revision on arXiv

Source-linked AI summary

Abelian Tensors

J. M. Landsberg, Mateusz Michałek

arXiv:1504.03732v2math.AGcs.CC

TL;DR

Determining tensor rank and border rank remains difficult, and the paper examines tensors satisfying Strassen’s equations in the border-rank-m setting. It uses geometric and algebraic results to characterize Coppersmith-Winograd tensors and establish further results on symmetric tensors and rank.

  • Problem

    Tensor rank and border rank are difficult to determine, and the paper focuses on tensors satisfying Strassen’s equations in the border-rank-m case.

    Source: §1 · p. 1

  • Method

    The paper studies Strassen-equation tensors through geometric characterizations and results on genericity, symmetry, and associated commuting-matrix spaces.

    Source: §1 · p. 1, §2.3 · pp. 6–7

  • Results

    The paper gives two geometric characterizations of the Coppersmith-Winograd tensor and proves that 1-generic tensors satisfying Strassen’s equations are isomorphic to symmetric tensors.

    Source: §1 · pp. 1–2

  • Takeaways & Limitations

    The results include explicit examples and new equations, alongside a reduction to studying symmetric tensors under a genericity hypothesis.

    Source: §1 · pp. 1–2

    The authors could not state useful general infinitesimal and scheme-theoretic analogues of the flag condition.

    Source: §2.2 · p. 5

Abstract

from arXiv · show

We analyze tensors in the tensor product of three m-dimensional vector spaces satisfying Strassen's equations for border rank m. Results include: two purely geometric characterizations of the Coppersmith-Winograd tensor, a reduction to the study of symmetric tensors under a mild genericity hypothesis, and numerous additional equations and examples. This study is closely connected to the study of the variety of m-dimensional abelian subspaces of the space of endomorphisms of an m-dimensional vector space, and the subvariety consisting of the Zariski closure of the variety of maximal tori, called the variety of reductions.

1. Introduction

The paper studies tensors satisfying Strassen’s equations, focusing on border rank m under concision and 1A-genericity. It connects this problem to commuting matrices and develops geometric characterizations, rank results, and examples relevant to tensor complexity.

1. Introduction

  • Prior work leaves tensor rank and border rank difficult to determine; this paper studies tensors satisfying Strassen’s equations, especially the border-rank-m case under concision and 1A-genericity.For 1A-generic tensors, Strassen’s equations correspond to an abelian space of endomorphisms.Source: §1 · pp. 1–2
  • The paper geometrically studies tensors used in matrix-multiplication exponent bounds, characterizes the Coppersmith-Winograd tensor in two ways, and gives explicit high-rank examples.It also reports a class for which Strassen’s additivity conjecture holds.Source: §1 · pp. 2–3

1.1. Background and previous work.

  • The background connects tensor rank questions to explicit high-rank examples and to the variety of reductions, the closure of diagonalizable subspaces of commuting matrices.The paper presents results on reductions in tensor language for the tensor community.Source: §1 · p. 2, §1.1 · p. 3

1.2. Organization.

  • The paper’s roadmap covers necessary conditions, rank bounds, additivity, generic tensors beyond minimal border rank, minimal-border-rank classifications, and Coppersmith-Winograd geometry.It includes the result that 1-generic tensors satisfying Strassen’s equations are isomorphic to symmetric tensors.Source: §1.2 · pp. 3–4

1.3. Notation.

  • The notation section defines tensor spaces and isomorphism, and illustrates that a change of basis can make a tensor’s rank and border rank transparent.For the group-algebra structure tensor, the discrete Fourier transform gives a diagonal form of rank and border rank m.Source: §1.3 · p. 4

2. Border rank m equations for tensors in Cm⊗Cm⊗Cm

For tensors of border rank m, the section develops commutativity, flag, and end-closure conditions, connecting them to abelian endomorphism spaces and reductions. It also identifies where these conditions are difficult to express or apply generally.

2.1. Strassen’s commutativity equations.

  • For an invertible slice, Strassen’s equations require the normalized slice space to be abelian, and cofactor maps replace inverses to obtain polynomial equations when slices are singular.The equations are expressed using commutators of normalized slices.Source: §2.1 · pp. 4–5

2.2. The flag condition.

  • Border rank m forces an A-concise tensor’s slice space to meet the rank-one Segre variety and admit a complete flag whose j-dimensional slices lie in the jth secant variety.When the intersection is a single point, the tangent space at that point must also intersect the slice space in at least a line.Source: §2.2 · pp. 5–6
  • The flag conditions are intersection-based and difficult to express polynomially, so the authors use them for tensors with simple expressions where they can be checked.The authors also report that useful general infinitesimal and scheme-theoretic analogs were unavailable to them.Source: §2.2 · pp. 5–6

2.3. Review and clarification of results in [29].

  • The abelian-tensor locus is cut out by Strassen’s equations, and its closure is a component of their zero set; the reduction variety consists of abelian spaces arising from concise border-rank-m tensors.The latter spaces are precisely those in the closure of diagonalizable subspaces.Source: §2.3 · p. 7

2.4. The End-closed condition.

  • For a 1A-generic tensor of border rank m with an invertible slice, the associated endomorphism space is closed under composition; the End-closed equations have degree 2m + 1.The section defines the End-closed locus using the existence of an invertible slice whose associated space is composition-closed.Source: §2.4 · pp. 7–8

3. The Alexeev-Forbes-Tsimerman method for bounding tensor rank

The section presents the substitution method for proving tensor-rank lower bounds and applies it to explicit examples. It also describes a condition under which the method implies additivity and states a limit on its lower bounds for square tensors.

3. The Alexeev-Forbes-Tsimerman method for bounding tensor rank

  • The substitution method represents a tensor as a matrix of linear forms, selects rows and columns, eliminates their nonzero entries, and recurses on the resulting smaller tensor.At each iteration, the rank is bounded below by the selected row and column counts plus the rank of the reduced tensor.Source: §3 · p. 9
  • 15 is the rank lower bound obtained by iterating the substitution method, with successive contributions 8 + 4 + 2 + 1.The example’s rank is stated to equal 15, while its border rank is 8.Source: §3 · p. 9
  • 18 is the rank of the second explicit example, and this construction generalizes to tensors in C^(2k) ⊗ C^(2k) ⊗ C^(2k) with rank 3·2^k − k − 3.The lower-bound argument first contracts four entries and then applies substitution to the resulting tensor.Source: §3 · p. 10
  • For tensors in C^m ⊗ C^m ⊗ C^m, the method’s limiting lower bound is 3(m − 1), achievable only by successively exchanging the roles of A, B, and C.Source: §3 · p. 10

4. A Remark on Strassen’s additivity conjecture

Strassen’s additivity conjecture remains unsettled, and the section gives a condition under which it holds. If the substitution method determines one summand’s rank, then it determines the rank of the direct sum additively.

4. A Remark on Strassen’s additivity conjecture

  • The conjecture remains open-ended in the cited discussion, with experts divided over whether it should hold.Source: §4 · p. 10
  • If the substitution method determines R(T1), then R(T1 ⊕ T2) = R(T1) + R(T2), establishing additivity for that direct sum.The argument reduces T1 to zero while leaving T2 unchanged.Source: §4 · p. 10
  • When any one of A1, B1, or C1 has dimension 2, the section says the theorem gives an easy proof of additivity.The passage notes this case had previously been shown by other methods.Source: §4 · pp. 10–11

5. Abelian tensors in Cm⊗Cm⊗Cm with border rank greater than m

The section gives examples showing that abelian tensors can have border rank greater than m, including when they are End-closed or satisfy other genericity conditions. It also shows that 1-generic abelian tensors admit symmetry reductions and can have high border rank.

5.1. End −AbelA ⊊AbelA for m ≥5.

  • Leit5 is abelian but not End-closed, with border rank 6 and rank 9; Leit6 is not End-closed, has rank 11, and has border rank 7.Leit5 is also not in DiagA, while Leit6's endomorphism space is not End-closed.Source: §5.1 · pp. 11–13
  • An End-closed example for m=7 has border rank at least 8, while a general element of End−AbelA has border rank at least m²/8.The latter is approximately 3/8 of the maximal border rank of a general tensor in C^m⊗C^m⊗C^m.Source: §5.1 · p. 13
  • Under the stated construction and inequality on k and ℓ, a 1A-generic, abelian, End-closed tensor can have rank greater than m while its contraction space intersects the Segre.The construction uses a direct-sum M⟨1⟩ term and a specified form of T′′.Source: §5.1 · p. 14

5.4. A tensor in End −Abel8 of border rank > 8 via Corollary 2.2.

  • The tensor Leit8 in End−Abel8 has border rank greater than 8; the stated bound reflects that its associated group lacks a rank-one one-parameter subgroup.Source: §5.4 · p. 14

5.5. A-abelian tensors that intersect the Segre and fail to satisfy flag condition.

  • The 1A-generic abelian tensor Ts9 intersects the Segre yet has border rank greater than 9, with the flag condition failing.The stated reason is that no P1 lies inside σ2(Seg(P8 × P8)).Source: §5.5 · p. 14

5.6. An End-closed tensor satisfying the flag condition but not the infinitesimal flag condition. Consider

  • Tflagok is End-closed and satisfies the flag condition, but its infinitesimal flag space meets the Segre only at [X0], and its border rank exceeds 9.Source: §5.6 · p. 15

5.7. 1-generic abelian tensors.

  • For tensors satisfying the A-Strassen equations, 1A- and 1B-genericity yields an isomorphic partially symmetric tensor; 1-genericity yields a fully symmetric one.Source: §5.6 · p. 15, §5.7 · p. 15
  • The section constructs 1-generic abelian tensors in C^4k⊗C^4k⊗C^4k with border rank at least k(k+1).Source: §5.7 · p. 15

6. Tensors of border rank m in Cm⊗Cm⊗Cm

This section studies tensors of border rank m through sufficient conditions for minimal border rank, rank determinations, and examples, including relations between abelian subspaces and limits of diagonalizable algebras. It also treats limiting-space constructions for m = 5, tensors with large gaps between rank and border rank, and parameterized families of non-isomorphic 1-generic tensors of border rank m.

6.1. Centralizers of a regular element.

  • If an m-dimensional abelian subspace contains a regular element, it lies in Red(m); tensors with the stated regular abelian contraction have border rank m.The section also gives tensor-rank values m for a regular semisimple centralizer and 2m −1 for a regular nilpotent centralizer.Source: §6.1 · p. 17

6.2. The flag algebras of [24].

  • The abelian Lie algebras associated to flags lie in Red(m), so their associated tensors have border rank m.These algebras are defined from a partition of size m −1 and its associated Young tableau.Source: §6.2 · p. 18

6.3. Case m = 4.

  • For m = 4, two types containing a non-regular element of Jordan type (3,1) give isomorphic rank 6 tensors; three types containing a nilpotent block of size 3 have rank 7.One of the latter types contains the Coppersmith-Winograd tensor ˜T2,CW.Source: §6.3 · pp. 20–21
  • The other four m = 4 types all have rank 7 and yield three tensor types, whose Segre intersections are two intersecting lines, a smooth quadric, or a plane.The five one-regular types are centralizers of regular elements, with ranks given by Proposition 6.3.Source: §6.3 · pp. 20–21

6.4. Case m = 5.

  • For 5 × 5 matrices, the passage states that, up to transposition, these are the only maximal nilpotent End-abelian 5-dimensional subalgebras, and proves each is in Red(5).Source: §6.4 · p. 21
  • For m = 5, all End-closed tensors in C5⊗C5⊗C5 obtained from 4-dimensional subspaces of (7) have border rank five; S1, S3, and S4 have rank 9, while S2 has rank 10.The conjecture is false for m > 4.Source: §6.4 · pp. 22, 25
  • The spans of S3 and S4 with the identity are each limits of spaces spanned by the constructed matrices.The argument also establishes that the limit gives the matrix corresponding to a.Source: §6.4 · pp. 26–27

6.5. Examples with large gaps between rank and border rank.

  • The tensor Tbiggap has border rank 12 and rank at least 25; further tensoring Tgap yields rank-to-border-rank ratios converging to at least 13/6.Tgap itself has border rank 6 and rank 12, and is also a counterexample to [4, Conjecture 0].Source: §6.5 · pp. 28–30
  • For m = 2k + 1, the constructed tensors have rank 5k and border rank at most 2(m − 1), so their rank-to-border-rank ratio tends to 5/2.The theorem generalizes the earlier construction Tbiggap,5.Source: §6.5 · p. 30

6.6. There are parameters worth of non-isomorphic 1-generic border rank m tensors in Cm⊗Cm⊗Cm.

  • For p ≥ 4 and n ≥ 2, equivalently m ≥ 7, the family gives non-isomorphic tensors, and (TLeit, τ) = m.For p = 4 and n = 2, there is a one-parameter family of non-isomorphic tensors.Source: §6.6 · p. 31

7. Coppersmith-Winograd value

The section examines tensors used to bound the matrix-multiplication exponent, focusing on geometric features of the Coppersmith-Winograd tensor. It reviews their border ranks and ranks, then gives geometric characterizations of the Coppersmith-Winograd tensor.

7. Coppersmith-Winograd value

  • A tensor’s Coppersmith-Winograd value depends on its presentation, and estimating it even in a fixed presentation involves choices of decomposition, tensor power, and block estimates.The paper studies geometric aspects of such tensors in hopes of finding others that could enable further exponent bounds.Source: §7 · p. 32

7.1. Sch¨onhage’s tensors.

  • Schönhage’s tensors give ω < 2.55, with no gain from tensor powers because the two matrix multiplications are already disjoint.The tensors are formed from a tensor product of two matrix multiplication tensors.Source: §7.1 · p. 32, §7 · p. 32

7.2. The Coppersmith-Winograd tensors.

  • Both Coppersmith-Winograd tensors have border rank q + 2; their ranks are 2q + 1 and 2q + 3, respectively.The rank formulas are for Tq,CW and ˜Tq,CW, respectively.Source: §7.2 · pp. 32–33

7.3. Strassen’s tensor.

  • Strassen’s tensor has border rank q + 1 and rank 2q; its cyclic tensor-product construction has rank at most (q + 1)^3.The tensor is obtained from the Coppersmith-Winograd tensor by setting c0 = 0.Source: §7.3 · pp. 33–34

7.4. Extremal tensors.

  • A curve general to order m gives a tensor whose A-slice space is the centralizer of a regular nilpotent element, hence lies in the closure of diagonalizable algebras.The explicit closure conclusion follows from the identification with that centralizer.Source: §7.4 · p. 34
  • For border rank m > 2, a unique Segre point whose tangent space contains the slice space implies the tensor is not 1A-generic.The condition in Proposition 7.3 is that the tangent space at the unique point contains the projectivized slice space.Source: §7.4 · p. 34
  • A 1A-generic tensor with a unique Segre point and an m − 2 dimensional tangent intersection is isomorphic to the Coppersmith-Winograd tensor.The theorem’s hypotheses also require that the tensor slice space intersect the Segre variety at that single point.Source: §7.4 · p. 35

7.5. A second geometric characterization of the Coppersmith-Winograd tensors.

  • Among 1-generic, maximally symmetric compressible tensors of minimal border rank, the only one is ˜Tm−2,CW.The theorem classifies the 1-generic maximally symmetric compressible symmetric tensors; the stated uniqueness is the minimal-border-rank case.Source: §7.5 · pp. 35–36
Loading 1504.03732v2…