AlgoVerse

Matrix multiplication

Multiply an n×m matrix by an m×p one: each cell of the product is the dot product of a row of A and a column of B.

If A is n×m and B is m×p, the product C = A·B is n×p and

Read the full explanation ↓
Input:
A 2×3 · B 3×2PDF export

A is 2×3 and B is 3×2; the product is 2×2 and each cell is a sum of three products.

  1. def matrix_multiply(A, B):
  2. n, m, p = len(A), len(B), len(B[0])
  3. if len(A[0]) != m:
  4. return None
  5. C = [[0] * p for _ in range(n)]
  6. for i in range(n):
  7. for j in range(p):
  8. total = 0
  9. for k in range(m):
  10. total = total + A[i][k] * B[k][j]
  11. C[i][j] = total
  12. return C

Invariant: The cells of C filled so far are all correct, and each depends only on one row of A and one column of B.

Start

i—
j—
total—

A

123
456

B

78
910
1112

C

The table is still empty.

Local variables

Orange = changed in this step

A list

[1, 2, 3][4, 5, 6]

B list

[7, 8][9, 10][11, 12]

Call stack

  1. matrix_multiply()line 1
Step 1 of 50
Black = cell · Orange = key stepadd: 0/12 · cell: 0/4
    Explanation

    The idea

    If A is n×m and B is m×p, the product C = A·B is n×p and

    C[i][j] = Σ A[i][k] · B[k][j]   for k = 1 … m

    that is, the dot product of row i of A and column j of B. The number of columns of A must equal the number of rows of B.

    Cost

    For each of the n·p cells, m multiplications: O(n·m·p); O(n³) for square matrices. Strassen's method uses 7 multiplications instead of 8 at each split and reaches O(n^2.81).

    Notes

    • Matrix multiplication is not commutative: usually A·B ≠ B·A.
    • The order in which several matrices are multiplied changes the cost (see "matrix-chain multiplication").

    What to watch in the trace

    • The three tables sit side by side; for each cell of C, see which row of A and column of B are read.