Made Easy FLT

Question

 

Assume Am × n, Bn × p and Cp × q are matrices where m > n > p > q. How many minimum number of multiplications are required to perform the following operation?

                              Am × n × Bn × p × Cp × q [= (A B C)m × q]

a) mnp+npq

b) mnp+mpq

c)mnq+npq

d) mnq+mpq

Answer 1

There are two possible to ways to do it :

(A*B)*C or A*(B*C)

In first case   T1 = mnp + mpq = mp(n+q)

In second case T2 = npq + mnq = nq(m+p)

Let q = x , p = x+1 , n = x+2 , m = x+3

After substitution

T1 = (x+3)(x+1)(x+2+x) = 2(x+3)(x+1)(x+1)

T2 = (x+2)x(x+3+x+1) = 2(x+2)x(x+2)

T1 - T2 = 2x^2 + 6x + 3

as x >= 1  so T1-T2 > 0

hence  T1 > T2

T2 requires less multiplications so the answer is  c)

Comments

How did you get the expression T2?

---

Multiplying B*C = R first we get  npq multiplications and then we multiple A with the R which is mnq