Geometric Aspects of Iterated Matrix Multiplication

Notation.

• IMM is the degree-n polynomial on n-tuples of q × q matrices that evaluates to trace(Xn · · · X1).The matrices represent cyclically composed maps between q-dimensional vector spaces.Source: §1 · p. 1, Notation · p. 3

1. Introduction

• For q = 3, IMM is VPe-complete; for q = n, it is VQP-complete.The paper presents these complete instances as motivation for studying IMM’s geometric properties.Source: §1 · p. 1
• The paper determines IMM’s symmetry group and proves that the polynomial is characterized by its stabilizer.The introduction identifies these results as motivation for the subsequent geometric study.Source: §1 · pp. 1–2
• The dual variety of the IMM hypersurface is itself a hypersurface, so dual degeneracy cannot provide complexity lower bounds in this setting.The paper also determines the dimension of the dual variety and describes the singular locus and the (n −2)-nd Jacobian locus.Source: §1 · pp. 1–2
• The singular locus’s irreducible components are characterized using nilpotent representations of the Euclidean equioriented quiver eAn, with formulas for their dimensions.The paper also gives explicit component decompositions for small q and n.Source: §1 · p. 2
• The (n −2)-nd Jacobian locus is studied through its dimension and number of irreducible components.It is the zero locus of partial derivatives of order n −2.Source: §1 · p. 2

2. The symmetry group of IMMn

• The connected stabilizer is obtained by identifying the Lie algebra annihilating IMM with the image of dΦ.The homomorphism Φ comes from the actions of GL(Uα) on adjacent matrix spaces, with a common-scalar kernel.Source: §2 · pp. 4–5
• The normalizer’s outer automorphisms must preserve the set of marked Dynkin diagrams of the representations occurring in V, restricting them to Dn.The cyclic permutation and reversal-with-transposition realize the dihedral symmetries in GL(V).Source: §2 · pp. 6, 8
• The stabilizer of IMM is S0 ⋊ Dn, where Dn acts by cyclically permuting the matrices and by reversal with transposition.The connected component S0 is the image of the product of the GL(Uα) groups under Φ, whose kernel consists of common scalar matrices.Source: §2 · pp. 4, 7, 8
• Every degree-n polynomial stabilized by S0 is a scalar multiple of IMM, so the connected stabilizer already characterizes the polynomial.The proof uses the multidegree decomposition and the fact that the identity tensor is the only stabilized tensor in the (1, . . . , 1) component.Source: §2 · p. 8

• For a general polynomial f, dual degeneracy means that the dual of V(f) is not a hypersurface.Source: §3 · p. 8
• The determinant hypersurface had previously been used to obtain lower bounds on the permanent’s determinantal complexity.Source: §3 · p. 9
• A nonsingular Hessian at a point of Immn_q implies a nonsingular Hessian at a general point by semicontinuity, yielding the hypersurface conclusion.Source: §3 · pp. 9, 11
• At the selected point, where each Xα equals a diagonal matrix, the Hessian is nonsingular.The chosen differential-operator orderings give the Hessian a convenient block structure; the constructed matrix C is its inverse.Source: §3 · pp. 9–11
• For every n ≥ 1 and q ≥ 2, the dual variety (Immn_q)∨ is a hypersurface in PV*.Source: §3 · pp. 9, 11

4. The singular locus of IMMn

• The irreducible components of Sing^n_q correspond exactly to isomorphism classes of maximal (n−1)-nilpotent representations of eA_n, with each component given by the corresponding orbit closure.The maximality orders by rank, degeneration, and elementary operations are equivalent.Source: §4 · p. 14
• Each component admits a desingularization as a vector bundle over a product of flag varieties, and its dimension is computed from the bundle and rank data.The matrix Rk(M) records ranks of maps along quiver paths; the dimension is the dimension of the base plus the fiber dimension.Source: §4 · pp. 14–15

Examples

• For n=1, IMMn is a smooth hyperplane of traceless elements, while for n=2 it is a maximal-rank quadric whose only singular point is the origin.Thus Sing^2_q is the origin for every q.Source: Examples · p. 15

Case n = 3.

• For n=3, the number of irreducible components is 3(q−1)/2 for odd q and 1+3q/2 for even q; for even q, dim Sing^3_q = 2q^2.For a component indexed by the stated maximal representation, the dimension is q^2 + 2ℓ(q−ℓ).Source: Case n = 3 · p. 16

Case q = 2

• A maximal representation of dimension vector (2n), for n ≥ 4, has at most four indecomposable summands.Source: Case q = 2 · p. 16
• For exactly two distinct indecomposable summands, every choice of two vertices provides such a maximal representation, and the associated component has codimension 8 in V*.Source: Case q = 2 · p. 17
• For exactly three distinct indecomposable summands, the corresponding irreducible components have codimension 6 for every n.Every choice of three vertices provides such a maximal representation.Source: Case q = 2 · p. 17
• For exactly four distinct indecomposable summands, the corresponding irreducible components have codimension 6 for every n.Every choice of four vertices provides two such maximal representations.Source: Case q = 2 · p. 17

5. The (n −2)-nd Jacobian locus of Immn q

• Points of the locus have at most two consecutive nonzero matrices, whose product must be zero.The locus is defined by the partial derivatives of order n −2 of IMMn_q.Source: §5 · p. 17
• Each Wα,r is irreducible, with dimension q² + r(q −r), and these varieties describe the locus’s components.Wα,r imposes rank bounds r and q −r on the consecutive matrices, whose product is zero.Source: §5 · pp. 18–19
• A Grassmannian vector-bundle construction desingularizes Z and establishes its irreducibility, supporting the component analysis.The lift records an r-plane E with Im X ⊆ E ⊆ ker Y; its projection is one-to-one when rk X = r and rk Y = q −r.Source: §5 · p. 19
• The locus has nq irreducible components, and its dimension is attained by a component with r = ⌊q/2⌋.The only repeated component descriptions are Wα−1,0 = Wα,q.Source: §5 · pp. 18–19