Matrix multiplication order

Updated October 2026

Matrix multiplication is associative, so (AB)C and A(BC) give the same answer. They do not cost the same.

Counting the work

Multiplying an m×n matrix by an n×p matrix with the ordinary algorithm takes m * n * p scalar multiplications. Take A of shape 10×100, B of shape 100×5, and C of shape 5×50.

The same result costs ten times more in the second order, and the intermediate matrix is 100×50 rather than 10×5, so memory use differs as well.

The everyday case

The most common version involves a vector. For n×n matrices A and B and a vector v:

(A @ B) @ v   # about n^3 + n^2 operations
A @ (B @ v)   # about 2 * n^2 operations

Python evaluates A @ B @ v from left to right, so it takes the expensive route unless you add brackets. With n = 1,000 that is roughly five hundred times the work.

Letting the library choose

For a chain of k matrices, the best order can be found with dynamic programming in O(k³) time, which is negligible next to the products themselves. NumPy exposes this directly:

import numpy as np

result = np.linalg.multi_dot([A, B, C])

The same idea applies to tensor contractions, where the number of possible orders grows much faster. np.einsum(..., optimize=True) searches for a cheap contraction path, and the difference on a large expression can decide whether it finishes at all.

When counting is not the whole story

These counts ignore sparsity and structure. If B is diagonal or sparse, a product can be far cheaper than the formula suggests, and the best order may change. Optimised libraries also run some shapes faster than others. The count is a good first model, and timing the real workload settles anything close.

← Memory layout  ·  Automatic differentiation →