Exercise 2.4.36

Multiplying $\mathit{AB}=(m$ by $n)(n$ by $p)$ needs $\mathit{mnp}$ multiplications. Then $(\mathit{AB})C$ needs $\mathit{mpq}$ more. Multiply $\mathit{BC}=(n$ by $p)(p$ by $q)$ needs $\mathit{npq}$ and then $A(\mathit{BC})$ needs $\mathit{mnq}$.

(a)

If $m,n,p,q$ are $2,4,7,10$ we compare $(2)(4)(7)+(2)(7)(10)=196$ with the larger number $(2)(4)(10)+(4)(7)(10)=360$. So $\mathit{AB}$ first is better, we want to multiply that 7 by 10 matrix by as few rows as possible.

(b)

If $u,v,w$ are $N$ by 1 , then $\left(u^{T}v\right)w^T$ needs $2N$ multiplications but $u^T\left(v{w}^T\right)$ needs $N^2$ to find $v{w}^T$ and $N^2$ more to multiply by the row vector $u^T$. Apologies for using the transpose symbol so early.

(c)

We are comparing $\mathit{mnp}+\mathit{mpq}$ with $\mathit{mnq}+\mathit{npq}$. Divide all terms by $\mathit{mnpq}$. Now we are comparing $q^{-1}+n^{-1}$ with $p^{-1}+m^{-1}$. This yields a simple important rule. If matrices $A$ and $B$ are multiplying $v$ for $\mathit{ABv}$, don’t multiply the matrices first. Better to multiply $Bv$ and then $A(Bv)$.