Question

A chain of four matrices A₁, A₂, A₃ and A₄, with order 3 X 4, 4 X 2, 2 X 8 and 8 X 7 respectively. Deduce m[1, 4] to find best possible minimum number of multiplication

Answer 1

Method used For multiple matrix multiplication is MATRIX CHAIN MULTIPLICATION (MCM)

As we know matrix multiplication means multiplying all matrix according to their order and get a resultant matrix with desired order . Matrix can be multiplied only by A x B when no.of columns of A = no. of rows of B.

Challenge is to reduce no of multiplications to obtain the answer

Now there are 5

ways to multiply 4 different matrices using different parenthesis i.e

1.((AB)C)D

2.(A(BC))D

3. (AB)(CD)

4. A((BC)D)

5. A(B(CD))

Now calculate no. of multiplications in each case and find minimal of all .

To multiply two matrices of order mxn and nxp we need m*n*p no. of multiplications .

Case 1.

((A1A2)A3)A4

1. Multiply first A1 and A2 so total no.of multiplication will be 3*4*2 =24 resulting in 3x2 matrix

2. Now multiply resultant of step 1 with A3 in 3*2*8=48 resulting in 3x8 matrix

3 . At last Multiply it by A4 in 3*8*7=168

so total no. of multiplication are 24+48+168=240

Case 2

(A(BC))D

1. Multiply first A2 and A3 so total no.of multiplication will be 4*2*8 =64 resulting in 4x8 matrix

2. Now multiply resultant of step 1 with A1 in 3*4*8=96 resulting in 3x8 matrix

3 . At last Multiply it by A4 in 3*8*7=168

so total no. of multiplication are 64+96+168=328

Case 3 .

(AB)(CD)

1. Multiply first A1 and A2 so total no.of multiplication will be 3*4*2 =24 resulting in 3x2 matrix

2. Now multiply A3 and A4of in 2*8*7=112 resulting in 2x7 matrix

3 . Now multiply both resultant of step 1 and 2 with each other in 3*2*7=42

so total no. of multiplication are 24+112+42=178

Now similarly do this for Case 4 and Case 5 and then take minimum of all the multiplication

Once you do you will find that best possible solution is

Optimal Parenthesization is : ((AB)(CD))

Optimal Cost is : 178

Case 2 result in minimum no. of multiplication to multiply A1 A2 A3 A4 forming m[1,4]

Thank You