Matrix Chain Multiplication�

• Given a sequence of matrices, find the most efficient way to multiply these matrices together. The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications.
• We have many options to multiply a chain of matrices because matrix multiplication is associative. In other words, no matter how we parenthesize the product, the result will be the same. For example, if we had four matrices A, B, C, and D, we would have:
• (ABC)D = (AB)(CD) = A(BCD) = ....

Amity School of Engineering & Technology

• The matrices have size 4 x 10, 10 x 3, 3 x 12, 12 x 20, 20 x 7. We need to compute M [i,j], 0 ≤ i, j≤ 5. We know M [i, i] = 0 for all i.

Amity School of Engineering & Technology

Amity School of Engineering & Technology

Calculation of Product of 2 matrices:

• 1. m (1,2) = m₁ x m₂ = 4 x 10 x 10 x 3 = 4 x 10 x 3 = 120
• 2. m (2, 3) = m₂ x m₃ = 10 x 3 x 3 x 12 = 10 x 3 x 12 = 360
• 3. m (3, 4) = m₃ x m₄ = 3 x 12 x 12 x 20 = 3 x 12 x 20 = 720
• 4. m (4,5) = m₄ x m₅ = 12 x 20 x 20 x 7 = 12 x 20 x 7 = 1680

Amity School of Engineering & Technology

Amity School of Engineering & Technology

Now product of 3 matrices

Amity School of Engineering & Technology

Now Product of 4 matrices:

Amity School of Engineering & Technology

Now Product of 5 matrices:

Amity School of Engineering & Technology

• So Answer is=

((M₁ x M₂ )x((M₃ x M₄ )x M₅))

​

Amity School of Engineering & Technology

Chain Matrix Multiplication

• A1(3x4) x A2 (4x2) X A3(2x5)x A4(5x6)

Amity School of Engineering & Technology

Problem

• A1(5x4) x A2 (4x6) X A3(6x2)x A4(2x7)

​

Amity School of Engineering & Technology

Answer

• ((A1)x(A2 xA3))xA4

​

​

• A1(4x2) x A2 (2x3) X A3(3x4)x A4(4x5)

​

​

Amity School of Engineering & Technology