Polynomials and the exponent of matrix multiplication Academic Article uri icon

abstract

  • 2018 London Mathematical Society The exponent of matrix multiplication is the smallest constant such that two nn matrices may be multiplied by performing O(n + ) arithmetic operations for every >0. Determining the constant is a central question in both computer science and mathematics. Strassen [Linear Algebra Appl. 52/53 (1983) 645685] showed that is also governed by the tensor rank of the matrix multiplication tensor. We define certain symmetric tensors, that is, cubic polynomials, and our main result is that their symmetric rank also grows with the same exponent , so that can be computed in the symmetric setting, where it may be easier to determine. In particular, we study the symmetrized matrix multiplication tensor sM n defined on an nn matrix A by sM n (A)=trace(A 3 ). The use of polynomials enables the introduction of additional techniques from algebraic geometry in the study of the matrix multiplication exponent .

published proceedings

  • BULLETIN OF THE LONDON MATHEMATICAL SOCIETY

altmetric score

  • 1.25

author list (cited authors)

  • Chiantini, L., Hauenstein, J. D., Ikenmeyer, C., Landsberg, J. M., & Ottaviani, G.

citation count

  • 12

complete list of authors

  • Chiantini, Luca||Hauenstein, Jonathan D||Ikenmeyer, Christian||Landsberg, Joseph M||Ottaviani, Giorgio

publication date

  • June 2018

publisher