ISRO2020-79

Question

Consider product of three matrices $M_1,M_2$ and $M_3$ having $w$ rows and $x$ columns, $x$ rows and $y$ columns, and $y$ rows and $z$ columns. Under what condition will it take less time to compute the product as $(M_1M_2)M_3$ than to compute $M_1(M_2M_3)$ ?

• A. Always take the same time
• B. $(1/x +1/z)<(1/w+1/y)$
• C. $x>y$
• D. $(w+x)>(y+z)$

Comments

option B is correct

Answer 1

$\underline{\textbf{Answer:}\Rightarrow}\;\mathbf{b.}$

$\underline{\textbf{Explanation:}\Rightarrow}$

$\mathrm{M_{1_{w\times x}} M_{2_{x\times y}} M_{3_{y\times z}}}$

$\text{Cost of } \;\mathrm{(M_1M_2)M_3\; = wxy+ wyz}$

while $\text{Cost of } \; \mathrm{M_1(M_2M_3)\; = xyz + wxz}$

Now, The time taken by $(M_1M_2)M_3$ will be less than $\mathrm{M_1(M_2M_3)}$, when

$\mathrm{wxy + wyz < xyz + wxz}$

Divide both sides with $\mathbf{wxyz}$, we will get:

$\mathrm{\dfrac{1}{z}+ \dfrac{1}{x} < \dfrac{1}{w}+ \dfrac{1}{y} }$

Answer 2

Option b is correct

---

Number of multiplication for $(M{_{1}}M{_{2}})M{_{3}}= wxy+wyz$

Number of multiplication for

$M{_{1}}(M{_{2}}M{_{3}})= xyz+wxz$

According to question:

$wxy+wyz < xyz+wxz$

Divide by $wxyz$ on both the sides we get

$\frac{1}{z} +\frac{1}{x} < \frac{1}{w} + \frac{1}{y}$

Answer 3

Option B will correct Answer