Multiply Two Matrices

Multiplying two matrices is not multiplying matching cells. Each cell of the result comes from a whole row of the first matrix and a whole column of the second: pair the row entries with the column entries, multiply each pair, and add the products. That sum is called a dot product, and C[i][j] is the dot product of row i of A with column j of B.

That is why the sizes must line up. A row of A has as many entries as A has columns, and a column of B has as many entries as B has rows; the pairs only match when those two numbers are equal. An n × m matrix times an m × p matrix gives an n × p result. The visualizer bands the current row of A and column of B so you can see each pairing as the sum grows.

Two loops pick the result cell, and a third walks along the row and down the column, accumulating the sum:

C = new matrix[n][p]
for i in 0 .. n-1:
  for j in 0 .. p-1:
    sum = 0
    for k in 0 .. m-1:
      sum += A[i][k] * B[k][j]
    C[i][j] = sum
return C

The index k is the one that moves along both matrices at once: it is the column index in A and the row index in B. Every result cell costs m multiplications, and there are n × p cells, so the whole product costs n × m × p multiplications, the number the counter above reaches.

A × B and B × A are different products. With the example above, B × A pairs the 2-entry rows of B with the 2-entry columns of A and gives a 3 × 3 result, not a 2 × 2 one. Even for two square matrices of the same size the two products are normally different, which is unlike the numbers you are used to.

The cost also depends on how you group a chain of products. Multiplying (A × B) × C can be many times cheaper or dearer than A × (B × C), and choosing the best order is the classic dynamic-programming problem called matrix chain multiplication.

• Graphics. Every move, scale, rotation and camera projection in 2D and 3D graphics is a matrix product applied to points.
• Machine learning. A layer of a neural network multiplies its inputs by a weight matrix; training and inference are mostly this loop, run on GPUs.
• Graphs. Multiplying an adjacency matrix by itself counts the two-step paths between every pair of nodes.
• Fast recurrences. The n-th Fibonacci number is a power of a 2 × 2 matrix, computed in O(log n) multiplications.

• Multiplying cell by cell. A[i][j] × B[i][j] is a different operation, the element-wise product. It needs equal shapes and is not what matrix multiplication means.
• Writing B[j][k]. The inner index k is the row of B, so the factor is B[k][j].
• Not resetting the sum. sum = 0 belongs inside the j loop, before the k loop, or each cell inherits the previous total.
• Assuming A × B = B × A. It almost never is, and one of them may not exist.

Three nested loops make this the first O(n³) algorithm most people meet. See how that growth compares with the others: Big-O Playground →