Question

What is the minimum number of multiplications involved in computing the matrix product PQR? matrix P has 4 rows and 2 columns, matrix Q has 2 rows and 4 columns, and matrix R has 4 rows and 1 column

Answer 1

Given, ${\left[P\right]}_{4x2},{\left[Q\right]}_{2x4},{\left[R\right]}_{4x1}$

Multiplcation can be done only when number of column of the first matrix is equal to the number of rows of the second matrix,

Let, Q = $\left[\begin{array}{cccc}a& b& c& d\\ e& f& g& h\end{array}\right]$

R = $\left[\begin{array}{c}p\\ q\\ r\\ s\end{array}\right]$

Case I: QR = $\left[\begin{array}{cccc}a& b& c& d\\ e& f& g& h\end{array}\right]$ $\left[\begin{array}{c}p\\ q\\ r\\ s\end{array}\right]$

=$\left[\begin{array}{cc}ap+bq+cr+ds& \\ ep+fq+gr+hs& \end{array}\right]$

$\therefore$ Number of multiplication from $\underset{}{{\left[Q\right]}_{2x4}{\left[R\right]}_{4x1}}$ is equal to (2x4x1 = 8).

Similarly, number of multiplication from $\left[P\right]\underset{}{4x2\left[QR\right]}\underset{}{{}_{2x1}}$ is

equal to (4x2x1 =8)

Hence, total number of multiplications

=8 + 8 = 16

Case II: No. of multiplication required in PQ is

4 x 2 x 4 = 32

No. of multiplication required in [PQ] [R] is

4 x 4 x 1 = 16

Total number of multiplications = 32 + 16 = 48.

$\therefore$ Min. number of multiplications = 16. (using case I)