Geometric aspects of iterated matrix multiplication

Abstract: This paper studies geometric properties of the Iterated Matrix Multiplication polynomial and the hypersurface that it defines. We focus on geometric aspects that may be relevant for complexity theory such as the symmetry group of the polynomial, the dual variety and the Jacobian loci of the hypersurface, that are computed with the aid of representation theory of quivers.

Review text

Let \(n,q>0\) be integers, and let \(IMM_q^n\) be the polynomial on \(n\)-tuples of \(q\times q\) matrices whose value on \((X_1,\dots,X_n)\) is \(\text{tr}(X_n\cdots X_1)\). Then \(IMM_q^n\) is a homogeneous polynomial in \(nq^2\) variables; if we let \(V\) be the complex vector space of \(n\)-tuples of \(q\times q\) matrices, then we write \(IMM_q^n\in S^{n}V\). In the work under review, some geometric properties of \(IMM_q^n\) are given. The tools used are representation theory and algebraic geometry.NEWLINENEWLINEGeometric Complexity Theory seeks to study polynomials which are characterized by their symmetry group. Recall that \(\text{GL}(V)\) acts on \(S^nV\); the symmetry group \(\mathcal{S}\) of \(IMM_q^n\in S^nV\) is the stabilizer of \(IMM_q^n\) under this action. A main result in this paper is that \(\mathcal{S}\cong \mathcal{S}_0\rtimes D_n\), where \(\mathcal{S}_0\) is the connected component of the identity of \(\mathcal{S}\) and \(D_n\) is the group of symmetries of a regular \(n\)-gon. Alternatively, any polynomial in \(S^nV\) which is stabilized by \(\mathcal{S}_0\) is shown to be a complex multiple of \(IMM_q^n\), hence \(IMM_q^n\) is characterized by its stabilizer.NEWLINENEWLINEThe remainder of the results concerns the hypersurface determined by the polynomial. Let \(\mathcal{I}mm_q^n\) be the hypersurface \(V(IMM_q^n)\subseteq\mathbb{P}V^*\). It is shown that its dual variety \((\mathcal{I}mm_q^n)^{\vee}\) is also a hypersurface in \(\mathbb{P}V^*\). Let \(\mathcal{S}ing_q^n\) denote the singular locus of the affine cone in \(V^*\) over \(V(IMM_q^n)\subseteq\mathbb{P}V^*\). Then a description of the irreducible components of \(\mathcal{S}ing_q^n\) in terms of certain nilpotent representations of the Euclidean equioriented quiver and dimensions are computed; examples are provided for \(n\leq 3\). Finally, let \(\mathcal{W}=V(J)\) where \(J\) is the ideal of \(IMM_q^n\) generated by all \(n-2\) order partial derivatives. The irreducible components of \(\mathcal{W}\) are given, and it is shown that \(\text{dim} \mathcal{W}=\lfloor (5/4)q^2 \rfloor\).

Recommendations

Cites work

Cited in

(19)

Describes a project that uses

Uses Software

Book3264Examples

This page was built for publication: Geometric aspects of iterated matrix multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q298019)