GATE CSE 2016 | Set 2 | Question: 38

Question

Let $A_{1}, A_{2}, A_{3}$ and $A_{4}$ be four matrices of dimensions $10 \times 5, 5 \times 20, 20 \times 10$ and $10 \times 5$, respectively. The minimum number of scalar multiplications required to find the product $A_{1}A_{2}A_{3}A_{4}$ using the basic matrix multiplication method is _________.

Comments

Will it work in every case??

Take the example -> M1, M2. M3 and M4 with dimensions 5x10, 10×20, 20×25 and 25×30 respectively. Then the number of minimum multiplication needed to multiply the matrices are______

According to this larger dimension 1st method I am getting ans 22500 while the min no of multiplication is 7250

I am getting 7250 by taking smaller dimensions first So, better to go for tabular method rather than this shortcut tricks.

---

yes @satyabrata27 tabular method ensure accuracy

---

Ans is 1500

Answer 1

The answer is $1500$.

Matrix Parenthesizing :  $A_1 ((A_2 A_3) A_4)$

Check my solution below, using dynamic programming $$\begin{array}{|l|l|}\hline A_{1} &A_{2} & A_{3} &A_{4}\\\hline 10 \times 5 & 5 \times 20 & 20 \times 10 & 10\times 5  \\\hline \end{array}$$

• $A_{12} = 10 \times 5 \times 20 =1000$
• $A_{23} = 5 \times 20 \times 10 =1000$
• $A_{34} = 20 \times 10 \times 5 =1000$

$$A_{13}=min\left\{\begin{matrix} A_{12} + A_{33}+ 5 \times 20 \times 10 = 2000\\ A_{11} + A_{23} + 10 \times 5 \times 10 = 1500 \end{matrix}\right.$$

$$A_{24}=min\left\{\begin{matrix} A_{23} + A_{44}+ 5 \times 10 \times 5 = 1250\\ A_{22} + A_{34} + 5 \times 20 \times 5 = 1500 \end{matrix}\right.$$

$$A_{14}=min\left\{\begin{matrix} A_{11} + A_{24}+ 10 \times 5 \times 5 = 1500\\ A_{12} + A_{34} + 10 \times 20\times 5 \geqslant 2000\\ A_{13}+A_{44} + 10 \times 20\times 5 = 2000 \end{matrix}\right.$$

Answer is 1500.

Comments

I have small doubt here

we found that A12 = A23 = A34 =1000

so at this step don't we proceed and take one of above combination and multiply them , before proceeding to check further?

---

@Akash Kanase, This is the fastest method for matrix chain multiplication.

Thanks for sharing.

---

i am not able to understand pls anyone explain clearly

Answer 2

my answer

Comments

yes it's 1750

---

Does it cover all cases?

---

narainkaarthik

Yes, it does cover all cases and also the proper feel of how recursion is happening...The only problem is it's time consuming

Answer 3

$A_{10\times 5}|A_{5\times 20}|A_{20\times 10}|A_{10\times 5}$

$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)=1000$	$(2,3)=1000$	$(3,4)=1000$	$\times$
$(1,3)=1500$	$(2,4)=1250$	$\times$	$\times$
$(1,4)=1500$	$\times$	$\times$	$\times$

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

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

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

Comments

Perfect.

Answer 4

Minimum number of scalar multiplications required is 1500.

A1((A2A3)A4) is the order, where scalar multiplications are minimum here and is 1500

Comments

plz explain how A1(A2 A3)A4) is the order of paranthesizing?

Answer 5

$A[i,j] = \left\{\begin{matrix} 0;& i = j\\ & min_{i\leq k < j}(A[i,k] + A[k+1,j]+ p_{i-1}p_{k}p_{j});\:\: i < j\end{matrix}\right.$

Comments

this is the best way

---

best method

---

hey can u please please make a clear solution of this ?

---

Lakshman bhaiya op. This should be the best answer, samajh aa gaya. Ye qn aaya exam me (iske jesa) toh 3 min me easily ho jaayega

Answer 6

For Matrix Chain Multiplication : - 

            A1 have P0 = 10 , P1 = 5

            A2 have P1 = 5 , P2 = 20

            A3 have P2 = 20 , P3 = 10

            A4 have P3 = 10 , P4 = 5

According to Rule : - 

                             A11 = A22 = A33 = A44 = 0

In 1st Bracket 1500 is minimum in 2nd bracket 1250 is min in 3rd Bracket 1500 minimum 

Now for bracket down to top we check how to we get minimum elements  

1500 is min which is by  A₁(A₂ to A ₄)   for (A₂ to A₄ ) 1250 is minimum so (A₂ A₃)A₄

Finally (A₁ (( A₂ A₃) A₄)) 

Reference : - https://home.cse.ust.hk/~dekai/271/notes/L12/L12.pdf

Comments

min A12 + A33 + 10x20x10   hona chahiye.....