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

Informal solution:

To get min no of multiplications(pqr), multiply matrix with largest common dimension first so that it doesn’t appear in pqr again. multiply A2 x A3 which gives 5x10 matrix. pqr = 1000

then multiply A2xA3 to eliminate next largest common dimmension 10. (A2xA3)xA4 => (5x10)x(10x5). pqr = 250

lastly, multiply A1x((A2xA3)xA4) = (10x5)x(5x5) => pqr = 250. thus total = 1500.

---

Does anyone have any trick other than the brute-force parenthesizing / tabular method?

P.s. This is that question, which must be attempted at last.

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

Is there any short method for finding multiplication as it is very length procedure & consumes a lot more time to solve it & moreover it is difficult to find out whether the calculation done is not wrong when asked in integer type question

---

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.

Answer 2

my answer

Comments

explain sir

---

@hera_thakur :  check B it will be (1000+500+250) = 1750 not 1850 ..

---

yes it's 1750

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?