The Polynomial Set Associated with a Fixed Number of Matrix-Matrix Multiplications

Abstract. We consider the problem of computing matrix polynomials [Formula: see text], where [Formula: see text] is a large dense matrix, with as few matrix-matrix multiplications as possible. More precisely, let [Formula: see text] represent the set of polynomials computable with [Formula: see text] matrix-matrix multiplications, but with an arbitrary number of matrix additions and scaling operations. We characterize this set through a tabular parameterization. By deriving equivalence transformations of the tabular representation, we establish new methods that can be used to construct elements of [Formula: see text] and determine general properties of the set. The transformations allow us to eliminate variables and prove that the dimension is bounded by [Formula: see text], which is subsequently proven to be sharp, i.e., [Formula: see text]. Consequently, we have identified a parameterization that, to the best of our knowledge, is the first minimal parameterization. We also conduct a study using computational tools from algebraic geometry to determine the largest degree [Formula: see text] such that all polynomials of that degree belong to [Formula: see text] or its closure. In many cases, the computational setup is constructive in the sense that it can also be used to determine a specific evaluation scheme for a given polynomial.