Search code examples
algorithmdynamic-programmingmatrix-multiplication

Chain Matrix Multiplication Schedule Cost

If I have the matrices M0, M1, M2, M3 with the dimensions 10×1, 1×2, 2×1, 1×10 respectively. I am getting the same cost for two different cases, is this possible or am I doing something wrong?
M03 = (M0x(M1xM2)xM3) = 112
M03 = ((M0xM1)xM2)xM3 = 112

Solution

  • The cost to multiply two matrices i x j and j x k is i * j * k.

    For your first example, the cost is 2 + 10 + 100 = 112. For your second example the cost is (10 * 1 * 2) + (10 * 2 * 1) + (10 * 1 * 10), or 20 + 20 + 100 = 140.

    It's possible that depending on the dimensions, the order would not matter. In this case it does.