Exercise 25

Matrix multiplication is performed often on computers. Researchers trying to understand its performance, and improve on it, count the number of operations that it takes.

• Definition 2.3 gives $p_{i,j}=g_{i,1}h_{1,j}+g_{i,2}h_{2,j}+\dots+g_{i,r}h_{r,j}$. How many real number multiplications are in that expression? Using it, how many do we need for the product of a $m\!\times\!r$ matrix and a $r\!\times\!n$ matrix?

• Matrix multiplication is associative, so in computing $H_{1}H_{2}H_{3}H_{4}$ we can expect to get the same answer no matter where we put the parentheses. The cost in number of multiplications, however, varies. Find the association requiring the fewest real number multiplications to compute the matrix product of a $5\!\times\!10$ matrix, a $10\!\times\!20$ matrix, a $20\!\times\!5$ matrix, and a $5\!\times\!1$ matrix. Use the same formula as in the prior part.

• (Very hard.) Find a way to multiply two $2\!\times\!2$ matrices using only seven multiplications instead of the eight suggested by the prior approach.