How does matrix multiplication work, step by step?

In this article

1. Before you start
2. Why interviewers ask this
3. Matrix multiplication from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

Matrix multiplication is one of the core coding interview questions on grids and loops, and it needs only three ideas.

Why interviewers ask this

Matrix multiplication is a small problem that exposes three habits at once: checking that the inputs fit before computing, writing a clean triple loop, and stating the cost. Interviewers can use it to see whether a candidate reasons about shapes and about running time without being prompted, and it sits close to many grid and linear-algebra exercises.

A weak answer multiplies matching entries, as if the rule were element-wise, or forgets that the shapes must fit. A strong answer states the shape rule first, writes the sum over the shared index, and says the cost is n times m times k multiplications. A Staff-level answer adds what the school method leaves out: the order of the two matrices matters, the order of a chain of matrices changes the cost, and algorithms faster than cubic exist but are rarely what you write on a whiteboard. Stating the cost fluently also helps on grid problems such as prefix sums with a hash map.

Matrix multiplication from first principles

Matrix multiplication

Matrix multiplication is an operation that combines two matrices into a third whose entry in row i and column j is the dot product of row i of the first matrix with column j of the second. It is defined only when the first matrix has as many columns as the second has rows.

Inner dimension

An inner dimension is the size the two matrices share in a product: the column count of the first and the row count of the second. In an n×k times k×m product it is k, and it disappears from the result, whose shape comes from the two outer sizes.

Identity matrix

An identity matrix is a square matrix with ones on its main diagonal and zeros elsewhere that leaves any matrix unchanged when it multiplies it. It plays the role that the value 1 plays for ordinary multiplication.

In plain words

Picture a shop with a price list and an order sheet. Each row of the order sheet lists how many of each product one customer wants. Each column of the price list gives the price of each product at one shop. A customer's bill at a shop is the quantities multiplied by the matching prices and added up. Doing that for every customer and every shop fills a table of bills. That table is the matrix product. The analogy breaks in one place: real bills do not depend on which sheet you read first, while a matrix product does.

In one precise sentence, entry (i, j) of the result is the sum, over the shared index k, of the entry at row i, position k of the first matrix times the entry at position k, column j of the second.

Step 1: Check that the shapes fit

Two matrices can be multiplied only when the inner dimensions match. The NumPy manual states the rule as a signature: an n by k array and a k by m array give an n by m array. Input: the two shapes. Output: yes or no, and the shape of the result.

Take a 2×3 matrix A and a 3×2 matrix B (illustrative). The inner sizes are both 3, so the product exists and has the outer sizes, 2×2.¹ Swap the roles and B times A would be 3×3, a different shape altogether. Two 2×3 matrices cannot be multiplied: the inner sizes are 3 and 2.

You now know whether the product exists and how big it is. Every interview solution should state this check first, because it is the validation step of the function.

Step 2: Compute one entry from a row and a column

Entry (i, j) of the result needs only row i of the first matrix and column j of the second. Multiply them pairwise and add.

Input: one row and one column of equal length k. Output: one number. With the illustrative A with rows (1, 2, 3) and (4, 5, 6), and B with rows (7, 8), (9, 10) and (11, 12), the top-left entry is 1·7 + 2·9 + 3·11 = 7 + 18 + 33 = 58.¹

You now know how one cell is built. The other three cells of this 2×2 result use the same recipe on a different row or column, and nothing else is needed.

Step 3: Swapping the two matrices changes the answer

Matrix multiplication is not commutative: multiplying A by B and B by A usually gives different results. An operation is called commutative when swapping its two inputs leaves the result unchanged, as with ordinary numbers. Input: the same two matrices in two orders. Output: two different products.

Use two small square matrices, P with rows (1, 2) and (3, 4), and Q with rows (0, 1) and (1, 0). P times Q has rows (2, 1) and (4, 3). Q times P has rows (3, 4) and (1, 2).¹ Here Q swaps the columns of P when it sits on the right and swaps the rows when it sits on the left, which is why the answers differ. Only special pairs commute, and the identity matrix is one such partner: the NumPy manual shows a 2×2 identity returning its partner unchanged.

You now know why the order of the two arguments is part of the question and not a detail.

Step 4: Fill every entry and count the work

Repeat step 2 for every row i and every column j, which is a triple loop: over rows of the first matrix, over columns of the second, and over the shared index. Input: the two matrices. Output: the full n by m result and a count of the work.

Each result entry costs k multiplications and k minus 1 additions. With n·m entries, the total is n·m·k multiplications. Multiplying a 2×3 by a 3×2 matrix takes 12 multiplications (2·2·3) and 8 additions.¹ For two square n×n matrices it is n cubed, so the cost grows by a factor of 8 each time n doubles.

1 · Check shapes2 · One entry3 · Order matters4 · Count the workReplay

Step-by-step description

1. Inner sizes match, outer sizes give the result.
2. A row times a column, summed.
3. Swapping the matrices changes the result.
4. Twelve multiplications for this product.

• The inner sizes must match and the outer sizes give the shape of the result.
• The top-left entry is 58, a row multiplied pairwise with a column and summed.
• Swapping the two matrices changes the result.
• Multiplying a 2×3 by a 3×2 matrix takes 12 multiplications.

Worked example

The full product of the illustrative 2×3 matrix A and 3×2 matrix B from Step 1 fills four entries: 58, 64, 139 and 154.¹ The row (1, 2, 3) against the two columns gives 58 and 64; the row (4, 5, 6) gives 139 and 154.

def matmul(a, b):
    n, k, m = len(a), len(b), len(b[0])
    assert len(a[0]) == k, "inner dimensions must match"
    c = [[0] * m for _ in range(n)]
    for i in range(n):          # each row of a
        for j in range(m):      # each column of b
            for t in range(k):  # the shared index
                c[i][j] += a[i][t] * b[t][j]
    return c

print(matmul([[1, 2, 3], [4, 5, 6]], [[7, 8], [9, 10], [11, 12]]))
# [[58, 64], [139, 154]]

The loop is cubic in the sizes: three nested loops of lengths n, m and k run n·m·k times, and the whole function needs no extra memory beyond the n by m result. Calling np.matmul(a, b) on NumPy arrays gives the same result and rejects scalars with a ValueError, as the NumPy manual shows. a @ b is the shorthand for np.matmul(a, b) on NumPy arrays (NumPy manual). For lists of lists in an interview, the loop above is the expected answer; the Python interview questions page covers the language details around it.

Two more hand checks use the same recipe. A matrix times a vector is a matrix times a one-column matrix: the illustrative 2×3 matrix A times the column (1, 0, 2) gives the 2×1 column (7, 16).¹ A 3×3 product takes 27 multiplications; for the illustrative rows (1, 2, 0), (0, 1, 3), (4, 0, 1) times the rows (1, 0, 2), (0, 1, 0), (3, 1, 0), the result has rows (1, 2, 2), (9, 4, 0) and (7, 1, 8).¹

The last two rows apply the formula n cubed to the illustrative sizes 100 and 1,000.¹ At n of 16 the school method needs 4,096 multiplications and the full Strassen recursion needs 2,401.¹

Text description of the diagram

• The school method needs n cubed multiplications for n by n matrices.
• At n of 16 the school method needs 4,096 multiplications and the full Strassen recursion needs 2,401.

Trade-offs and edge cases

The school method is the right default, and six cases change the picture.

Element-wise confusion. The element-wise product multiplies entries in the same position and needs equal shapes. The matrix product sums row-times-column terms and needs matching inner sizes. In NumPy the star operator is the element-wise one, while np.matmul, or its @ shorthand, is the matrix product and np.matmul rejects scalars.

Text description of the diagram

• The element-wise product multiplies matching entries and needs the same shape.
• The matrix product sums row times column and needs matching inner sizes.
• Order does not matter for the element-wise product but changes the matrix product.
• np.matmul rejects scalars.

Order of a chain. Matrix multiplication is associative, meaning the brackets can move without changing the result, but the cost changes. For illustrative shapes 10×30, 30×5 and 5×60, bracketing the first two costs 4,500 multiplications, while bracketing the last two costs 27,000.¹ Choosing the cheapest bracketing is a classic dynamic-programming exercise.

Faster algorithms exist. Strassen's 1969 paper, Gaussian elimination is not optimal, began the search for algorithms faster than the school method. Its one-level form uses seven block products where the school method uses eight (Brandão et al., 2023). Applied all the way down, 7 products per halving gives 7 to the power log₂ n, about n to the 2.807.¹ The saving costs extra additions (22 per level in the form shown by Brandão et al., 2023), so Strassen only pays off for large matrices, and libraries mostly use a tuned cubic method.

Fawzi et al. (2022) report a computer-found algorithm that multiplies 4×4 matrices over a finite field with 47 multiplications instead of the 49 of Strassen's two-level method, the first such gain in about 50 years. The best proven exponent for square matrices is below 2.372 (version 3 of Alman et al. gives 2.371177, as of October 2026), a theoretical bound on growth, not a faster routine for ordinary sizes.

Transpose rule. The transpose of a matrix swaps its rows and columns. The transpose of a product reverses the order: (AB)ᵀ = BᵀAᵀ. For the illustrative A and B above, both sides give rows (58, 139) and (64, 154).¹

Memory access order. The three loops can be reordered without changing the n·m·k work. Running the shared index in the middle (order i, k, j) lets the inner loop walk along rows of both the second matrix and the result, which suits row-major memory and the processor cache. Blocking the loops into small tiles goes further. Tuned libraries rely on this, and it is a good Staff-level remark.

Parallel hardware. The n·m result entries are independent, so they can be computed side by side; parallel processing explains how that splits work.

How to answer it in an interview

The spoken structure: say the shape rule, say what one entry is, give the cost, then add the order and the chain.

Common mistakes

• "I multiply the entries in the same positions." (wrong) That is the element-wise product. (right) "Each entry is a row times a column, summed over the shared index."
• "Any two matrices can be multiplied." (wrong) The inner sizes must match. (right) "A 2×3 times a 3×2 works; a 2×3 times a 2×3 does not."
• "A times B equals B times A." (wrong) The earlier pair P and Q gives two different results. (right) "Matrix multiplication is not commutative, so I keep the order."
• "The best possible cost is n cubed." (wrong) Strassen's method and later work beat the cubic exponent in theory. (right) "The school method is cubic; faster methods exist but are rarely used on a whiteboard."

Follow-up questions

How do you multiply matrices?

Check that the inner sizes match, then for each row of the first matrix and each column of the second, multiply pairwise and add. The results fill the output grid in the same row and column order.

Is matrix multiplication commutative?

No. Multiplying P by Q and Q by P above gives two different matrices, and the two orders can even have different shapes. It is associative, so brackets may move, but the arguments may not swap.

Can you multiply a 2×3 matrix by another 2×3 matrix?

No, because the inner sizes are 3 and 2. Transposing the second one into a 3×2 matrix makes the product exist and gives a 2×2 result.

What is the time complexity of matrix multiplication?

For an n by k and a k by m matrix, the school method needs n·m·k multiplications, which is O(n³) for square matrices. Faster algorithms lower the exponent, as in the section on trade-offs above.

What is the fastest matrix multiplication algorithm?

For square matrices, the best known exponent is below 2.372, from a theoretical line of work (Alman et al.). For small sizes, the plain triple loop or a library routine is usually what you use.

In what order should you multiply a chain of matrices?

Pick the bracketing that minimizes total multiplications; for the illustrative shapes above it is 4,500 against 27,000. Dynamic programming over sub-chains finds it.

Sources

1. numpy.matmul (NumPy manual, stable) — NumPy project, 26 Oct 2026
2. Gaussian elimination is not optimal — Numerische Mathematik 13 (Strassen), 1 Aug 1969
3. Discovering faster matrix multiplication algorithms with reinforcement learning — Nature 610 (Fawzi et al.), 5 Oct 2022
4. More Asymmetry Yields Faster Matrix Multiplication (arXiv 2404.16349) — arXiv (Alman et al.), 19 Aug 2026
5. Updates on Practical Strassen's Algorithms (BLIS Retreat 2023 slides) — UT Austin FLAME group (Brandão et al.), 1 Jan 2023