Matrix-chain multiplication: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Choose multiplication order with minimum scalar multiplications and reconstruct the parenthesization.

Try every last split of each matrix interval and combine its two optimal subcosts with the boundary-dimension multiplication cost.

Open the 3D visualization

Matrix-chain multiplication example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Matrix-chain multiplication

Choosing multiplication parenthesization before numeric work.

Choosing an alternative

The algorithm changes grouping, not matrix order.

Worked example: input and state changes

Example input

10,30,5,60

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: A single matrix requires no scalar multiplications.

    State at this checkpoint
    {
      "values": [
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0,
        0
      ],
      "active": [],
      "kind": "matrix",
      "columns": 3
    }
  2. Step 1: Interval 0–1: split after 0, candidate 1500, best 1500.

    State at this checkpoint
    {
      "values": [
        0,
        1500,
        0,
        0,
        0,
        0,
        0,
        0,
        0
      ],
      "active": [
        1
      ],
      "kind": "matrix",
      "columns": 3
    }
  3. Step 3: Interval 0–2: split after 0, candidate 27000, best 27000.

    State at this checkpoint
    {
      "values": [
        0,
        1500,
        27000,
        0,
        0,
        9000,
        0,
        0,
        0
      ],
      "active": [
        2
      ],
      "kind": "matrix",
      "columns": 3
    }
  4. Step 4: Interval 0–2: split after 1, candidate 4500, best 4500.

    State at this checkpoint
    {
      "values": [
        0,
        1500,
        4500,
        0,
        0,
        9000,
        0,
        0,
        0
      ],
      "active": [
        2
      ],
      "kind": "matrix",
      "columns": 3
    }
  5. Step 5: Minimum scalar multiplications = 4500; order ((AB)C).

    State at this checkpoint
    {
      "values": [
        0,
        1500,
        4500,
        0,
        0,
        9000,
        0,
        0,
        0
      ],
      "active": [],
      "kind": "matrix",
      "columns": 3,
      "result": 4500,
      "parenthesization": "((AB)C)"
    }

Expected final state

Minimum scalar multiplications = 4500; order ((AB)C).

Complexity and input bounds

Family: Dynamic programming. Time complexity: O(n³).

Space complexity: O(n squared) interval costs and splits.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

2–9 matrix dimensions, each 1–99. Matrix i has dimensions d[i] × d[i+1].

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

A dimension array has one more entry than the number of matrices; multiplication is not generally commutative.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 2–9 positive dimensions ≤ 99. Returns minimum scalar multiplications. output[0] is parenthesization token count; subsequent ASCII codes use matrices A..H and parentheses. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(dims, count, output) {
    let n = count - 1; let dp = Array(256).fill(0); let split = Array(256).fill(0);
    for (let length = 2; length <= n; length++) {
        for (let i = 0; i + length <= n; i++) {
            let j = i + length - 1; dp[i * n + j] = 1000000000;
            for (let k = i; k < j; k++) {
                let cost = dp[i * n + k] + dp[(k + 1) * n + j] + dims[i] * dims[k + 1] * dims[j + 1];
                if (cost < dp[i * n + j]) { dp[i * n + j] = cost; split[i * n + j] = k; }
            }
        }
    }
    let left = Array(256).fill(0); let right = Array(256).fill(0); let type = Array(256).fill(0); let top = 1; let tokens = 0; right[0] = n - 1;
    while (top > 0) {
        top--; let l = left[top]; let r = right[top]; let kind = type[top];
        if (kind == 1) { output[++tokens] = 41; }
        else if (l == r) { output[++tokens] = 65 + l; }
        else {
            output[++tokens] = 40; let k = split[l * n + r];
            left[top] = 0; right[top] = 0; type[top++] = 1;
            left[top] = k + 1; right[top] = r; type[top++] = 0;
            left[top] = l; right[top] = k; type[top++] = 0;
        }
    }
    output[0] = tokens;
    return dp[n - 1];
}

Source

Foundational dynamic-programming paper. It establishes the general method, not the first publication or exact recurrence of this particular teaching example.