Four matrices M_{1}, M_{2}, M_{3} and M_{4} of dimensions p × q, q × r, r × s and s × t respectively can be multiplied in several ways with different number of total scalar multiplications. For example when multiplied as ((M_{1} × M_{2}) × (M_{3} × M_{4})), the total number of scalar multiplications is part rst+ prt. When multiplied as ((M1 × M2) × (M3 )× M4), the total number of scalar multiplications is pqr+ prs + pst .

If p = 10, g = 100, r = 20, s = 5, and t = 80, then the minimum number of scalar multiplications needed is

This question was previously asked in

GATE CS 2011 Official Paper

Option 3 : 19000

The correct answer is **option 3**

__Concept:__

If we multiply two matrices [A]_{l × m} and [B]_{m × n}

Then the number of scalar multiplications required = l × m × n

__Data:__

Given 4 matrix are given with their dimensions

Matrix |
M1 |
M2 |
M3 |
M4 |

Dimension |
p× q |
q× r |
r× s |
s× t |

Dimension | 10×100 | 100×20 | 20×5 | 5×80 |

Calculation:

Total number of ways of multiplication =\(\frac{^{2n}C_n}{n+1}\)

n = 4 - 1 = 3

Total number of ways of multiplication =\(\frac{^{2n}C_n}{n+1}\) =5

There are 5 ways in which we can multiply these 4 matrices.

- (M1M2)(M3M4)
- M1 ((M2M3) M4)
- M1(M2(M3M4))
- ((M1M2)M3)M4
- (M1(M2M3))M4

(M10×100 × M100× 20 )(M20× 5 × M5× 80) | 10×100×20 +20× 5×80 +10×20×80 =44,000 |

M10×100 × ( (M100× 20 × M20× 5 )× M5× 80) | 10×100×80 +100×20×5 +100×5×80 =130,000 |

M10×100 × ( M100× 20 × (M20× 5 × M5× 80)) | 10×100×80 +100×20×80 +20×5×80 = 248,000 |

( (M10×100 × M100× 20 )× M20× 5 )× M5× 80 | 10×100×20 +10×20×5 +10×5×80 =25,000 |

( (M10×100 ×( M100× 20 × M20× 5 ))× M5× 80 |
10×100×5 +100×20×5 +10×5×80 =19,000 |

The minimum number of scalar multiplication can find out using (M1(M2M3))M4

(M1(M2M3))M4 =19,000

__Shortcut Trick__

Frist find scaler multiplication of those which are common in some of the 5 ways of multiplication

then it will become easy to solve

(M1M2) is common in 1 and 4

(M2M3) is common in 2 and 5

(M3M4) is common in 1 and 3