Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 62 ยท Matrices

Matrix Multiplication

Learn matrix multiplication: the row-by-column rule, shape compatibility, why AB is not BA, the difference between @ and *, associativity and the cost of products.

Adding matrices is easy because it works entry by entry. Multiplying them is where linear algebra gets its power. The product of two matrices is not the product of matching entries. It is a carefully designed operation that makes the product AB mean "do B first, then A". That design is why matrices can describe rotations, data pipelines and neural network layers.

This lesson gives you the row-by-column rule, the shape check that tells you whether a product exists, the famous fact that AB and BA usually differ, the NumPy difference between @ and *, and a look at the cost of multiplying big matrices.

The row-by-column rule

Let A be an m by n matrix and B an n by p matrix. Their product C = AB is an m by p matrix. The entry in row i and column j of C is the dot product of row i of A with column j of B:

TEXT
C[i, j] = A[i, 0]*B[0, j] + A[i, 1]*B[1, j] + ... + A[i, n-1]*B[n-1, j]

A small example:

TEXT
[1 2]   [5 6]   [1*5+2*7  1*6+2*8]   [19 22]
[3 4] * [7 8] = [3*5+4*7  3*6+4*8] = [43 50]

To get the top-left entry you pair the first row [1, 2] with the first column [5, 7]. To get the top-right entry you pair the same row with the second column [6, 8].

Python The rule written out by hand

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Shapes decide everything

For AB to exist, the number of columns of A must equal the number of rows of B. The inner sizes must match, and the outer sizes give the shape of the result:

TEXT
(m by n) times (n by p) = (m by p)

Check the shapes first

Inner sizes match Columns of A equal rows of B.
Outer sizes remain The result has rows of A and columns of B.

(2 by 3) times (3 by 4) gives (2 by 4).

1 / 2

A 2 by 3 matrix times a 3 by 4 matrix is fine and gives 2 by 4. Reverse the order and the inner sizes are 4 and 2, so BA does not exist at all.

Python Shape rules in practice

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

AB is usually not BA

Even when both products exist, they normally give different answers. Multiplication of matrices is not commutative. A quick example:

TEXT
A = [1 2]   B = [0 1]
    [3 4]       [1 0]

Multiplying on the right by B swaps the columns of A, while multiplying on the left swaps its rows. These are different results. Because order matters, we say "multiply A on the left by B" or "on the right", and never just "multiply them".

There are special cases where AB = BA, for instance when one matrix is the identity or when both are diagonal. Do not rely on this in general.

Python Order matters

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Matrix times vector

A vector can be treated as a matrix with one column, so A @ x follows the same rule: each entry of the result is a row of A dotted with x. The next lesson, Three Ways to See Matrix-Vector Products, looks at this special case from three angles. A 2 by 3 matrix times a vector of length 3 gives a vector of length 2.

@ versus *

This is the most common beginner mistake in NumPy. The * operator multiplies entry by entry (the Hadamard or elementwise product) and needs matching or broadcastable shapes. The @ operator is true matrix multiplication, and np.matmul and np.dot do the same for 2D arrays.

Python Two very different products

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The rules that do hold

Although AB is not BA, several useful rules remain, whenever the shapes allow the products:

  • Associative: (AB)C = A(BC), so you can leave out the parentheses.
  • Distributive: A(B + C) = AB + AC and (A + B)C = AC + BC.
  • Scalars slide through: c(AB) = (cA)B = A(cB).
  • Identity: AI = A and IA = A.
  • Zero divisors exist: AB = 0 does not imply that A or B is zero.

Associativity is a gift, but it has a practical side effect on cost, shown next.

Cost: how many operations?

Multiplying an m by n matrix with an n by p matrix needs m * n * p multiplications, because each of the m * p output entries is a dot product with n terms. For two square matrices of size n that is about n^3 operations. Doubling the size makes the product roughly eight times more expensive.

Associativity lets you pick the cheaper grouping. Take A of shape 100 by 2, B of shape 2 by 100 and a vector x of length 100. The product (A B) x forms a 100 by 100 matrix first, while A (B x) only ever builds small vectors.

Python Counting multiplications

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For programmers: fast powers, Strassen and chain order

Matrix multiplication shows up in programming problems far from geometry. Three ideas are worth having in your toolbox.

Matrix exponentiation for recurrences

A linear recurrence like Fibonacci, F(n) = F(n-1) + F(n-2), can be written as one matrix step:

TEXT
[F(n+1)]   [1 1] [F(n)  ]
[F(n)  ] = [1 0] [F(n-1)]

Applying it n times means multiplying by M^n, and repeated squaring computes M^n with only about logโ‚‚ n multiplications instead of n: to find M^13, square repeatedly to get Mยฒ, Mโด, Mโธ, then combine Mโธ ยท Mโด ยท Mยน. With integers that can grow huge, programmers usually work modulo a number (such as 10โน + 7) so entries stay small. The same trick handles any recurrence with constant coefficients: for Tribonacci, T(n) = T(n-1) + T(n-2) + T(n-3), use a 3 ร— 3 matrix. A recurrence of order k needs a k ร— k matrix, and the cost is about kยณ log n. The matrix is the companion matrix of the recurrence, and its eigenvalues explain the growth rate.

Strassen's algorithm

Ordinary multiplication of two n ร— n matrices takes nยณ scalar multiplications. In 1969 Volker Strassen noticed that two 2 ร— 2 matrices can be multiplied with 7 multiplications instead of 8, at the cost of more additions. Applied recursively to blocks (see block matrices), this gives O(n^logโ‚‚7) โ‰ˆ O(n^2.81). For 2 ร— 2:

TEXT
M1 = (A11 + A22)(B11 + B22)     M5 = (A11 + A12) B22
M2 = (A21 + A22) B11            M6 = (A21 โˆ’ A11)(B11 + B12)
M3 = A11 (B12 โˆ’ B22)            M7 = (A12 โˆ’ A22)(B21 + B22)
M4 = A22 (B21 โˆ’ B11)

C11 = M1 + M4 โˆ’ M5 + M7         C12 = M3 + M5
C21 = M2 + M4                   C22 = M1 โˆ’ M2 + M3 + M6

In practice Strassen pays off only for very large matrices, and optimized libraries with cache-friendly ordinary multiplication usually win for small and medium sizes.

Matrix chain multiplication

Matrix multiplication is associative but the cost depends on the grouping. Multiply A (10 ร— 30), B (30 ร— 5) and C (5 ร— 60). (AB)C costs 10ยท30ยท5 + 10ยท5ยท60 = 4500 multiplications, but A(BC) costs 30ยท5ยท60 + 10ยท30ยท60 = 27000. For a long chain you want the cheapest parenthesization, which dynamic programming finds in O(nยณ) time: let cost[i][j] be the cheapest way to multiply matrices i through j, and try every split point k.

Python Fast Fibonacci, Strassen and the cheapest chain order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Fibonacci of 10^18 takes about 60 matrix squarings instead of a quintillion additions. Strassen uses 7 multiplications where the ordinary method uses 8, and the saving compounds at each recursion level (n = 16 needs 2,401 instead of 4,096). The chain optimizer confirms that (AB)C is the cheap order for the three-matrix example, with 4,500 multiplications.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A has shape (3, 5) and B has shape (5, 2). What is the shape of AB?

    The inner sizes are both 5, so the product exists and keeps the outer sizes: 3 by 2.
  2. 2. In NumPy, what does A * B do for two 2D arrays of the same shape?

    The * operator is elementwise. Use @ for the matrix product.
  3. 3. Which statement about matrix multiplication is always true when the shapes allow it?

    Multiplication is associative. It is not commutative, and non-zero matrices can multiply to zero.
  4. 4. How many scalar multiplications does a (m, n) times (n, p) product need?

    Each of the m * p output entries is a dot product with n terms, giving m * n * p multiplications.

Summary

  • Entry (i, j) of AB is row i of A dotted with column j of B.
  • The inner sizes must match; the result keeps the outer sizes.
  • AB and BA usually differ, and one of them may not even exist.
  • In NumPy, @ is the matrix product and * is elementwise.
  • Multiplication is associative and distributive, with the identity matrix as the neutral element.
  • A product costs m * n * p multiplications, so the grouping of a chain matters.

Next: Three Ways to See Matrix-Vector Products.