On the optimal evaluation of a set of bilinear forms

AbstractAlthough general theories are beginning to emerge in the area of automata based complexity theory, there are very few general methods or even general problem formulations in the area of arithmetic complexity. In this paper we propose and defined a general model for studying bilinear multiplication in order to provide a common framework for discussing a wide class of problems. The problem of minimizing the number of multiplications required to perform a calculation leads to a problem in matrix algebra relating to the expansion of a given set of matrices as linear combinations of rank-one matrices. In this paper we make a systematic attack on this problem and derived some general results which unify and extend numerous known results