9,702 views

Four Matrices $M_1, M_2, M_3$ and $M_4$ of dimensions $p \times q, \:\:q \times r, \:\:r \times s$ and $s \times t$ respectively can be multiplied in several ways with different number of total scalar multiplications. For example when multiplied as $((M_1 \times M_2) \times (M_3 \times M_4))$, the total number of scalar multiplications is $pqr + rst + prt$. When multiplied as $(((M_1 \times M_2) \times M_3) \times M_4)$, the total number of scalar multiplications is $pqr + prs + pst$.

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

1.  $248000$
2.  $44000$
3.  $19000$
4.  $25000$

I read @Arjun sir comment of doing it using DP but I didn't believe it can be done in less time. So I tried it using timer and after doing it 2 times I finally endup doing it in less than 2 minutes.

So the conclusion is if you have enough practice, DP is most reliable and it can get you 2 marks within 3 minutes.

p.s :

I was actually looking for such comment so i thought posting it will be helpful for some and clear the things that solving it with DP is effective too.

Peace :)

Is there any way to do this faster?
Practice this one for 7-8 times, and you'll get your own tricks to solve it faster (max. 2.5 minutes) + accuracy. Practice is the key!

Ordering:

• First Multiply  $M_2 \times M_3.$
This requires $100*20*5$ multiplications.
• Then Multiply  $M_1 \times (M_2 \times M_3).$
This requires $10*100*5$ multiplications.
• Then Multiply $(M_1 \times (M_2 \times M_3)) \times M_4.$
This requires $10*5*8$ multiplications.

Total $19000$ Multiplications.

Brute Force approach - anyone can do.

No. of possible ordering for 4 matrices is $C_3$ where $C_3$ is the $3^{rd}$ Catalan number and given by $n=3$ in $\frac{1}{n+1} {}^{2n}C_n = 5.$

So, here we have

1. $(M_1 \times M_2) \times (M_3 \times M_4)$
2. $(M_1 \times (M_2 \times M_3)) \times M_4$
3. $((M_1 \times M_2) \times M_3) \times M_4$
4. $M_1 \times (M_2 \times (M_3 \times M_4))$
5. $M_1 \times ((M_2 \times M_3) \times M_4))$

Each of these would give no. of multiplications required as

1. $pqr + rst + prt$
2. $qrs + pqs + pst$
3. $pqr + prs + pst$
4. $rst + qrt + pqt$
5. $qrs + qst + pst$

The last 2 are having $qt$ terms which are the highest terms by far and hence we can avoid them from consideration $qt = 8000$ multiplied by one other term would be larger than any value in choice. So, just find the value of first 3 terms.

1. $pqr + rst + prt = 20000 + 8000 + 16000 = 44000$
2. $qrs + pqs + pst = 10000 + 5000 + 4000 = 19000$ - smallest value in choice, we can stop here.
3. $pqr + prs + pst$

Dynamic Programming Solution (should know Matrix Chain Ordering algorithm)

Here we have a chain of length 4.

Dynamic programming solution of Matrix chain ordering has the solution

$m[i, j] = \begin{cases} 0 &\text{ if } i=j\\ \displaystyle \min_{i\leq k < j } m[i][k] + m[k+1][j] + p_{i-1}p_{j}p_{k} &\text{ if } i < j\end{cases}$

So, we can fill the following table starting with the diagonals and moving upward diagonally. Here, $k < j$ but $\geq i, m[i,i] = 0.$

$p_0=p = 10, p_1 = q = 100, p_2=r = 20, p_3 = s =5, p_4 = t =80.$
$$\scriptsize \begin{array}{|l|l|l|l|l|} \hline \text{} & \textbf{j=1} & \textbf{j=2} & \textbf{j=3} & \textbf{j=4}\\\hline \textbf{i=1} & \text{0} & \text{p_0p_1p_2} & \min(m[1,1]+m[2,3]+p_0p_1p_3,& \min(m[1,1]+m[2,4]+ p_0p_1p_4, \\ &&=20000&\quad m[1,2]+m[3,3]+p_0p_2p_3 )&\quad m[1,2]+m[3,4]+p_0p_2p_4, \\ &&&=15000&\quad m[1,3]+m[4,4]+p_0p_3p_4)\\&&&& = 19000 \\\hline \textbf{i=2} & \text{} & \text{0} & p_1p_2p_3 = 10000 & \min(m[2,2]+m[3,4]+p_1p_2p_4,\\ &&&&\quad m[2][3]+m[4,4]+p_1p_3p_4)\\ &&&&= \min(160000, 50000)=50000 \\\hline \textbf{i=3} &\text{} & \text{} & \text{0} &p_2p_3p_4 = 8000 \\\hline \textbf{i=4} &\text{} &\text{} & \text{} & \text{0} \\\hline \end{array}$$

Our required answer is given by $m[1,4] = 19000.$

checked all combinations in the exam? any shortcuts?
Use dynamic programming approach. It is standard matrix multiplication problem.
even the dynamic one takes time. how to approach this kind of problem in lesser time??
It is just 5 pairs we have to consider. Dynamic programming is recommended if one has tried it before- then its easy to try for problems. See the solution now.

Values are obtained by the formula: m[i,j] = { 0                                                                                     ,         i==j

min i<=k<j    { m[i,k] + m[k+1,j] + Pi-1.Pk.Pj }       ,        i < j

}

 0 20000 15000 19000 0 10000 50000 0 8000 0

ans: 19000(option C)

How to solve such matrix chain multiplication questions fast in Exam ??
M1×((M2×M3)×M4)) = qrs+qst+pst .......?

it should be  pqt+qrs+qst

Then Multiply (M1×(M2×M3))×M4. This requires 10*5*8 multiplications.

thanks

For those who still doen't understand how multiplication works, very simple.

Only thing is you should not alter the sequence.

For ex, (M1 x M2) = First term X Common Term X Last term

(M1.x M2) = (10 x 100 ) x ( 100 x 20) = 10 x 100 x 20

((M1  x M2 ) x M3) = (10 x 100 x 20) x (20 x 5) = 10 x 20 x 5 ( In this case, we have cancelled all remaining terms except first term, common term and last term)

(((M1  x M2 ) x M3) x M4) = (10 x 20 x 5) x (5 x 80) = 10 x 5 x 80 ( In this case also, we have cancelled all remaining terms except first term, common term and last term)

Finally, addition of all steps will give us result.

Result = (10 x 100 x 20) + (10 x 20 x 5) + (10 x 5 x 80) = 19000

Isn't it simple !

by

25000?
Your summation is wrong. Check it !

$M1_{10\times 100}|M2_{100\times 20}|M3_{20\times 5}|M4_{5\times 80}$

Subscipts for the matrix : $P_{0}\times P_{1}|P_{1}\times P_{2}|P_{2}\times P_{3}|P_{3}\times P_{4}$

 $(1,1)=0$ $(2,2)=0$ $(3,3)=0$ $(4,4)=0$ $(1,2)=20000$ $(2,3)=10000$ $(3,4)=8000$ $\times$ $(1,3)=15000$ $(2,4)=50000$ $\times$ $\times$ $(1,4)=19000$ $\times$ $\times$ $\times$

$A_{13}=min\left\{\begin{matrix} A_{12} + A_{33}+ 10 \times 20 \times 5(P_{0}\times P_{2}\times P_{3}) = 21000\\ A_{11} + A_{23} + 10 \times 100 \times 5(P_{0}\times P_{1}\times P_{3}) = 15000 \end{matrix}\right.$

$A_{24}=min\left\{\begin{matrix} A_{23} + A_{44}+ 100 \times 5 \times 80(P_{1}\times P_{3}\times P_{4}) = 50000\\ A_{22} + A_{34} + 100 \times 20 \times 80(P_{1}\times P_{2}\times P_{4}) = 168000 \end{matrix}\right.$

$A_{14}=min\left\{\begin{matrix} A_{11} + A_{24}+ 10 \times 100 \times 80(P_{0}\times P_{1}\times P_{4}) = 130000\\ A_{12} + A_{34} + 10 \times 20\times 80(P_{0}\times P_{2}\times P_{4}) = 44000\\ A_{13}+A_{44} + 10 \times 5\times 80(P_{0}\times P_{3}\times P_{4}) = 19000 \end{matrix}\right.$

### 1 comment

Nice and preciously presented.

Can you explain this formula in the light of dynamic programming ?

Given M1, M2, M3, M4

first of all we take first three matrix and see which combination is giving minimum number of multiplication.

combination #1:   M1*(M2*M3)   → Here for M2*M3 no. of multiplication is q*r*s  and then we will multiply M1 with the resultant matrix of M2*M3 and no. of multiplication will be p*q*s , so total no. of multiplication in   M1*(M2*M3) is q*r*s + p*q*s = 10000 + 5000 = 15000

combination #2:   (M1*M2)*M3 → Here for M1*M2  no. of multiplication is p*q*r and then we multiply M3 with the resultant matrix of  M1*M2 and no. of multiplication will be p*r*s, so total no. of multiplication in (M1*M2)*M3 is p*q*r + p*r*s = 20000 + 1000 = 21000

Minimum of both combination is 15000 , so we will choose M1*(M2*M3) for further process.

Now only M4 is left, so we will multiply M4 to (M1*(M2*M3)) → (M1*(M2*M3))*M4 no. of multiplication will be p*s*t (10*5*80 = 4000) so the total no. of multiplication will be 15000 + 4000 = 19000