Polynomials and the exponent of matrix multiplication

The exponent of matrix multiplication is the smallest constant o such that two nxn matrices may be multiplied by performing O(n^(o+e)) arithmetic operations for every e>0. Determining the constant o is a central question in both computer science and mathematics. Strassen showed that o is also governed by the tensor rank of the matrix multiplication tensor. We define certain symmetric tensors, i.e., cubic polynomials, and our main result is that their symmetric rank also grows with the same exponent o, so that o can be computed in the symmetric setting, where it may be easier to determine. In particular, we study the symmetrized matrix multiplication tensor SMn defined on an nxn matrix A by SMn(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 o.