GATE CSE 2011 | Question: 38

Question

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

• A.  $248000$
• B.  $44000$
• C.  $19000$
• D.  $25000$

Comments

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!

---

@Manu Thakur

dp[2][4] → (M2, M3, M4)

1. (M2M3)M4(M2 M3) M4(M2M3)M4
   = 10000 + (100×5×80 = 40000) = 50000
2. M2(M3M4)M2 (M3 M4)M2(M3M4)
   = 8000 + (100×20×80 = 160000) = 168000 

---

I think fastest way is either by practicing enough to solve it fast Or by applying some aptitude,

Here what I did is, first simply substituted the values in given equation

By which I got the answers as 44000 and 25000

Now it means that Opt. A is out of context  and  now they are asking minimum so

it will be eiher Opt. C or Opt. D   

 

Now I went through the values and from that I got to know that the their is definately a way to reduce further

And hence, Opt. C is the right one

Answer 1

$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.$

Comments

Nice and preciously presented.

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

Answer 2

Answer is C.

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*80$ 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.$

Comments

i am not getting how in second multiplication 10*100*5 came?m2*m3=100*20*5 now this adding to m1 that is 10*100*20*5 so why 20 removed @Shaik Masthan 

---

I didn't get your doubt. You may refer new best answer. Tag me on that answer with your doubt incase you still not getting it.

---

min of (160000,50000) is incorrect it should be min(168000,50000) correct me if wrong

 

Answer 3

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 !

Comments

25000?

---

Plz aad total no

---

Your summation is wrong. Check it !

Answer 4

Nice — exam-ready, fast-memory tricks coming up. I’ll keep it short, practical and exam-friendly so you can do it in 30–60 seconds.

 Always write just the dimension list

For four matrices:

\[
M_1\,(p \times q),\quad M_2\,(q \times r),\quad M_3\,(r \times s),\quad M_4\,(s \times t)
\]

Write:

\[
[p,\,q,\,r,\,s,\,t]
\]

This is the only data you need.

For 4 matrices — there are only 5 possible parenthesizations}

Memorize the 5 cost formulas — each is a sum of three scalar products:

\begin{align*}
((M_1 M_2) M_3) M_4 &:\quad pqr + prs + pst \\
(M_1 (M_2 M_3)) M_4 &:\quad qrs + pqs + pst \\
M_1 ((M_2 M_3) M_4) &:\quad qrs + qst + pqt \\
M_1 (M_2 (M_3 M_4)) &:\quad rst + pqr + pqt \\
(M_1 M_2)(M_3 M_4) &:\quad pqr + rst + prt
\end{align*}

You can get these by expanding the three multiplications needed in each order.

Plug numbers and pick the smallest

 

Only 5 quick multiplications — each is a sum of three products.

Practice computing each line fast by grouping multiplications.  

For example: do \(10 \times 100 = 1000\), then \(\times 20 = 20{,}000\).  

With practice, you'll evaluate all 5 in under a minute.

Example:  

Given dimensions:

\[
[10,\,100,\,20,\,5,\,80]
\]

Evaluate each cost:

\begin{align*}
((M_1 M_2) M_3) M_4 &:\quad 10 \times 100 \times 20 + 10 \times 20 \times 5 + 10 \times 5 \times 80 = 25{,}000 \\
(M_1 (M_2 M_3)) M_4 &:\quad 100 \times 20 \times 5 + 10 \times 100 \times 5 + 10 \times 5 \times 80 = 19{,}000 \\
M_1 ((M_2 M_3) M_4) &:\quad 100 \times 20 \times 5 + 20 \times 5 \times 80 + 10 \times 80 \times 5 = 130{,}000 \\
M_1 (M_2 (M_3 M_4)) &:\quad 20 \times 5 \times 80 + 100 \times 20 \times 80 + 10 \times 100 \times 80 = 248{,}000 \\
(M_1 M_2)(M_3 M_4) &:\quad 10 \times 100 \times 20 + 20 \times 5 \times 80 + 10 \times 20 \times 80 = 44{,}000
\end{align*}

Answer:

\[
\boxed{19{,}000}
\]

 

Answer 5

Here it is :

Answer 6

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