Geometric aspects of iterated matrix multiplication. (English) Zbl 1352.14032
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.
Geometric 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.
The 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\).
Geometric 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.
The 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\).
Reviewer: Alan Koch (Decatur)
MSC:
| 14L40 | Other algebraic groups (geometric aspects) |
| 15A86 | Linear preserver problems |
| 16G20 | Representations of quivers and partially ordered sets |
Keywords:
iterated matrix multiplication; symmetry group of a polynomial; Jacobian loci of hypersurfacesSoftware:
Book3264ExamplesReferences:
| [1] | Abeasis, S.; Del Fra, A., Degenerations for the representations of an equioriented quiver of type \(A_m\), Boll. Un. Mat. Suppl. Algebra Geom., 157-171 (1980) · Zbl 0449.16024 |
| [2] | Abeasis, S.; Del Fra, A., Degenerations for the representations of a quiver of type \(A_m\), J. Algebra, 93, 376-412 (1985) · Zbl 0598.16030 |
| [3] | Abeasis, S.; Del Fra, A.; Kraft, H., The geometry of the representations of \(A_m\), Math. Ann., 256, 3, 401-418 (1981) · Zbl 0477.14027 |
| [4] | Assem, I.; Simson, D.; Skowroński, A., Elements of Representation Theory and Associative Algebras, vol. 1: Techniques of Representation Theory, London Mathematical Society Student Texts, vol. 65 (2006), Cambridge University Press · Zbl 1092.16001 |
| [5] | Ben Or, M.; Cleve, R., Computing algebraic formulas using a constant number of registers, SIAM J. Comput., 21, 54-58 (1992) · Zbl 0743.68062 |
| [6] | Bermudez, H.; Garibaldi, S.; Larsen, V., Linear preservers and representations with 1-dimensional ring of invariants, Trans. Amer. Math. Soc., 366, 9, 4755-4780 (2014) · Zbl 1296.15012 |
| [7] | Bürgisser, P.; Ikenmeyer, C., Explicit lower bounds via geometric complexity theory, (Proceedings of the 45th Annual ACM Symp. on Th. of Comp. (New York, NY, USA), STOC ’13 (2013)), 141-150 · Zbl 1293.68138 |
| [8] | Bläser, M., Complete problems for Valiant’s class of qp-computable families of polynomials, (Wang, Jie, Computing and Combinatorics. Computing and Combinatorics, Lecture Notes in Computer Science, vol. 2108 (2001), Springer: Springer Berlin, Heidelberg), 1-10 · Zbl 0991.68027 |
| [9] | Bürgisser, P.; Landsberg, J. M.; Manivel, L.; Weyman, J., An overview of mathematical issues arising in the geometric complexity theory approach to \(V P \neq V N P\), SIAM J. Comput., 40, 4, 1179-1209 (2011) · Zbl 1252.68134 |
| [10] | Brion, M., Lectures on the geometry of flag varieties (2003), Lecture Notes |
| [11] | Dvir, Z.; Malod, G.; Perifel, S.; Yehudayof, A., Separating multilinear branching program formulas, (Proc. of the 44th Annual ACM Symp. on Th. of Comp. (New York), STOC ’12 (2012)), 615-624 · Zbl 1286.68131 |
| [12] | Eisenbud, D.; Harris, J., 3264 and All That - A Second Course in Algebraic Geometry (2016), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1341.14001 |
| [13] | Fulton, W.; Harris, J., Representation Theory: A First Course, Graduate Texts in Mathematics, vol. 129 (1991), Springer-Verlag: Springer-Verlag New York · Zbl 0744.22001 |
| [14] | Fournier, H.; Limaye, N.; Malod, G.; Srinivasan, S., Lower bounds for depth 4 formulas computing iterated matrix multiplication, (Proc. of the 46th Annual ACM Symp. on Th. of Comp. (New York), STOC ’14 (2014)), 128-135 · Zbl 1315.68137 |
| [15] | Gelfand, I. M.; Kapranov, M. M.; Zelevinsky, A. V., Discriminants, Resultants, and Multidimensional Determinants, Mathematics: Theory & Applications (1994), Birkhäuser: Birkhäuser Boston · Zbl 0827.14036 |
| [16] | Landsberg, J. M., Tensors: Geometry and Applications, Graduate Studies in Mathematics, vol. 128 (2012), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 1238.15013 |
| [17] | Landsberg, J. M., Geometric complexity theory: an introduction for geometers, Ann. Univ. Ferrara, 61, 1, 65-117 (2015) · Zbl 1329.68128 |
| [18] | Landsberg, J. M., An introduction to geometric complexity theory, Eur. Math. Soc. Newsl., 99 (2016) · Zbl 1358.68108 |
| [19] | Landsberg, J. M.; Manivel, L.; Ressayre, N., Hypersurfaces with degenerate duals and the geometric complexity theory program, Comment. Math. Helv., 88, 2, 469-484 (2013) · Zbl 1292.14033 |
| [20] | Mulmuley, K. D.; Sohoni, M., Geometric complexity theory. II. Towards explicit obstructions for embeddings among class varieties, SIAM J. Comput., 38, 3, 1175-1206 (2008) · Zbl 1168.03030 |
| [21] | Procesi, C., Lie Groups: An Approach through Invariants and Representations, Universitext (2007), Springer: Springer New York · Zbl 1154.22001 |
| [22] | Riedtmann, C., Degenerations for representations of quivers with relations, Ann. Sci. Éc. Norm. Supér., 19, 2, 275-301 (1986) · Zbl 0603.16025 |
| [23] | Schiffmann, O., Quivers of type \(A\), flag varieties and representation theory, (Representations of Finite-Dimensional Algebras and Related Topics in Lie Theory and Geometry. Representations of Finite-Dimensional Algebras and Related Topics in Lie Theory and Geometry, Fields Instit. Comm., vol. 40 (2004)), 453-479 · Zbl 1134.16301 |
| [24] | Zwara, G., Degenerations for modules over representation-finite algebras, Proc. Amer. Math. Soc., 127, 1313-1322 (1999) · Zbl 0927.16008 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
