Definition
Row · column
Each C[i][j] is a dot product of row i of A with column j of B.
Perform Matrix Multiplication in Python
Overview
What You’ll Learn
Standard matrix multiplication builds each result cell as a row × column dot product: C[i][j] = sum(A[i][k] * B[k][j]), only when inner dimensions match. This tutorial covers the rule, triple nested loops, a live preview, worked Python examples, edge cases, and complexity.
Shape Rule
(m×n)(n×p)
AB exists only when columns of A equal rows of B; result is m×p.
Triple Loop
i, j, k
Outer i/j pick a cell; inner k accumulates products.
Zero Init
Start at 0
Every result cell is a running sum — initialize before adding.
Live Preview
Show 3×3
Run the classic 3×3 sample product in the browser.
Not Hadamard
Not cell×cell
This is true matrix product — not element-wise multiply.
Introduction
Matrix multiplication combines a row from A with a column from B. If A is m × n and B is n × p, then AB is defined and has size m × p, with C[i][j] = sum over k of A[i][k] * B[k][j].
This is not cell-by-cell multiplication (Hadamard product). Order matters: AB is generally not equal to BA.
Why it matters?
It is a classic interview problem that tests 2D indexing, accumulation, and understanding of linear-algebra shape rules.
Key Highlights
Dot Product Cells
Each output entry is one row dotted with one column.
Inner Dimensions
cols(A) must equal rows(B).
Three Loops
i and j pick the cell; k walks the shared dimension.
O(n³) Classic
Square case uses cubic work with the basic algorithm.
In short: if shapes are compatible, zero-init C, then for each i, j accumulate A[i][k] * B[k][j] over k.
Foundation
📝 Problem & Approach
Given compatible matrices A and B, build product C = AB using row–column dot products.
python
# (m x n) * (n x p) -> (m x p)
# C[i][j] = A[i][0]*B[0][j] + A[i][1]*B[1][j] + ...
# Not the same as A[i][j] * B[i][j]Inputs & Outputs
| Item | Type | Description |
|---|---|---|
A, B | list[list[int]] | Compatible matrices: cols(A) == rows(B). |
| Return / print | matrix / text | Product matrix of size rows(A) × cols(B). |
Minimal workflow
Pseudocode
function multiply(A, B):
n <- size
C <- n x n matrix of zeros
for i from 0 to n - 1:
for j from 0 to n - 1:
for k from 0 to n - 1:
C[i][j] <- C[i][j] + A[i][k] * B[k][j]
return CMethod comparison
| Method | Idea | Notes |
|---|---|---|
| Triple nested loops | Accumulate A[i][k]*B[k][j] | Interview default — clear and correct |
| Element-wise (Hadamard) | A[i][j] * B[i][j] | Different operation — same shape required |
NumPy @ / matmul | Library product | Production path; show loops in interviews |
Cheat Sheet
⚡ Quick Reference
| Goal | Pattern |
|---|---|
| Accumulate cell | result[i][j] += a[i][k] * b[k][j] |
| Triple loop | for i / for j / for k |
| Zero-init | [[0 for _ in range(n)] for _ in range(n)] |
| Shape check | len(a[0]) == len(b) (cols A == rows B) |
| Result size | m x p when A is m x n, B is n x p |
| Trace one cell | Top-left 3×3 sample: 1*9 + 2*6 + 3*3 = 30 |
Compare
📋 Matrix Product vs Hadamard vs NumPy
Same word “multiply” — very different meanings.
Matrix product
sum A[i][k]*B[k][j]This page — classic interview style
Hadamard
A[i][j] * B[i][j]Element-wise — needs same shape
NumPy
A @ BFast in apps; show loops in interviews
Interview tip
state shape firstSay (m×n)(n×p)→m×p before coding
Context
When This Problem Shows Up
Reach for true matrix products when rows must combine with columns.
Interview classics
Triple loops plus shape rules are a common warm-up.
After entrywise ops
Natural step up from addition/division in this chain.
Linear transforms
Compose maps, graphics, and simple ML layers.
Teaching accumulation
Practice running sums over a shared index k.
Not for Hadamard
Clarify when the interviewer wants cell-by-cell multiply.
Key benefit: one short problem that locks in indexing, accumulation, and the (m×n)(n×p)→m×p rule.
Interactive
🔮 Live Preview
Uses the same 3×3 matrices as Example 1. Click to display both inputs and the product matrix.
Hands-On
Examples Gallery
Three complete Python programs — classic 3×3 product, easy-to-verify 2×2, and a shape-safe general multiplier. Click View Output to reveal sample console results.
📚 Getting Started
Triple nested loops with a zero-initialized result matrix.
Example 1 — Multiply Two 3×3 Matrices
Classic interview-style implementation with helpers for multiply and display.
python
N = 3
def multiply_matrices(a: list[list[int]], b: list[list[int]]) -> list[list[int]]:
result = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
for j in range(N):
for k in range(N):
result[i][j] += a[i][k] * b[k][j]
return result
def display_matrix(matrix: list[list[int]]) -> None:
for row in matrix:
print("\t".join(str(x) for x in row))
def main() -> None:
first_matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9],
]
second_matrix = [
[9, 8, 7],
[6, 5, 4],
[3, 2, 1],
]
result = multiply_matrices(first_matrix, second_matrix)
print("First Matrix:")
display_matrix(first_matrix)
print("\nSecond Matrix:")
display_matrix(second_matrix)
print("\nResult Matrix:")
display_matrix(result)
if __name__ == "__main__":
main()How It Works
The innermost loop computes one dot product for each result cell: result[i][j] += a[i][k] * b[k][j]. Top-left output is 1*9 + 2*6 + 3*3 = 30.
⚡ Easy Manual Check
Same logic on a smaller matrix so you can verify by hand.
Example 2 — Smaller 2×2 Product
Same triple-loop pattern with values that are easy to dry-run.
python
N = 2
def multiply_matrices(a: list[list[int]], b: list[list[int]]) -> list[list[int]]:
result = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
for j in range(N):
for k in range(N):
result[i][j] += a[i][k] * b[k][j]
return result
def print_matrix(title: str, m: list[list[int]]) -> None:
print(title)
for row in m:
print(*row)
def main() -> None:
a = [[1, 2], [3, 4]]
b = [[5, 6], [7, 8]]
r = multiply_matrices(a, b)
print_matrix("A", a)
print()
print_matrix("B", b)
print()
print_matrix("AB", r)
if __name__ == "__main__":
main()How It Works
Top-left value is 1*5 + 2*7 = 19; top-right is 1*6 + 2*8 = 22. Matching the printed AB confirms the accumulation logic.
⚙️ General Shape Validation
Drop fixed N and enforce cols(A) == rows(B).
Example 3 — Shape-Safe General Product
Checks inner dimensions, then multiplies any compatible m×n by n×p.
python
def can_multiply(a: list[list[int]], b: list[list[int]]) -> bool:
if not a or not b or not a[0] or not b[0]:
return False
cols_a = len(a[0])
rows_b = len(b)
if cols_a != rows_b:
return False
for row in a:
if len(row) != cols_a:
return False
cols_b = len(b[0])
for row in b:
if len(row) != cols_b:
return False
return True
def multiply_safe(a: list[list[int]], b: list[list[int]]) -> list[list[int]] | None:
if not can_multiply(a, b):
return None
m, n, p = len(a), len(a[0]), len(b[0])
result = [[0 for _ in range(p)] for _ in range(m)]
for i in range(m):
for j in range(p):
for k in range(n):
result[i][j] += a[i][k] * b[k][j]
return result
ok = multiply_safe([[1, 2, 3], [4, 5, 6]], [[7, 8], [9, 10], [11, 12]])
bad = multiply_safe([[1, 2], [3, 4]], [[5, 6, 7]])
print(ok)
print(bad)How It Works
First sample is 2×3 times 3×2 → 2×2. Second fails because columns of A (2) do not match rows of B (1).
🧠 How the Algorithm Builds C
1
Check shapes
Require cols(A) == rows(B); result will be rows(A) × cols(B).
Shape
2
Zero-init C
Create an m×p matrix of zeros before accumulation.
Init
3
Triple loop
For each i, j accumulate A[i][k] * B[k][j] over k.
Loops
=
Product matrix ready
C holds every row–column dot product.
Trace
🔎 Worked Walkthrough — Top Row of 3×3
Trace the first row of C for the Example 1 matrices.
| Cell | Dot product | Value |
|---|---|---|
C[0][0] | 1*9 + 2*6 + 3*3 | 30 |
C[0][1] | 1*8 + 2*5 + 3*2 | 24 |
C[0][2] | 1*7 + 2*4 + 3*1 | 18 |
First row of the result is [30, 24, 18] — matching Example 1 output.
Use Cases
Where true matrix multiplication shows up beyond the interview prompt.
1. Interview Warm-Ups
2D indexing plus accumulation over k.
Example: write multiply_matrices(A, B).
2. After Entrywise Ops
Step up from addition/division to products.
Example: compare with Hadamard multiply.
3. Linear Transforms
Compose maps in graphics and simple ML.
Example: apply a 2×2 transform to points.
4. Shape Reasoning
Practice (m×n)(n×p)→m×p checks.
Example: reject incompatible pairs.
5. Complexity Talk
State O(n³) for the classic square case.
Example: mention NumPy for large n.
6. Precursor to Subtract
Next page returns to entrywise ops.
Example: continue the matrix chain.
Pro Tip: open with “(m×n)(n×p)→m×p, C[i][j] is a row–column dot product” before writing loops.
Advantages
Why the classic triple-loop approach works well in interviews.
1. Clear Formula
One rule: C[i][j] = sum of A[i][k] * B[k][j].
2. Easy to Trace
2×2 dry-runs verify understanding in seconds.
3. Forces Shape Thinking
Inner-dimension checks are a natural follow-up question.
4. Maps to Libraries
Same idea as NumPy
@— you just write the loops by hand.
Pro Tip: lead with loops and zero-init; mention NumPy @ only as a production aside.
Usage Tips
Small habits that keep matrix-multiplication solutions interview-ready.
1. State Shapes First
Say (m×n)(n×p)→m×p before writing code.
2. Zero-Init Every Cell
Accumulation requires starting at zero.
3. Keep k as the Shared Index
Always pair
A[i][k]withB[k][j].4. Build Fresh Row Lists
Avoid
[[0]*n]*nshared references.5. State O(n³) / O(mnp)
Square vs rectangular complexity in one sentence.
Pro Tip: dry-run 1*5 + 2*7 = 19 aloud on the 2×2 sample — if that matches, your indexing is correct.
Common Pitfalls
Mistakes that commonly break matrix-multiplication solutions.
1. Inner Dimensions Mismatch
Multiplying when cols(A) ≠ rows(B).
→ Validate shapes before looping.
2. Doing Element-Wise Multiply
Writing
A[i][j] * B[i][j]instead of a dot product.→ Use three loops and the k index.
3. Forgetting Zero Init
Accumulating into uninitialized cells.
→ Start every C[i][j] at 0.
4. Assuming AB = BA
Order usually changes the result (or validity).
→ Multiply in the requested order only.
5. Shared Row Initialization
[[0]*n]*nshares row lists.→ Build each row separately.
Edge Cases
Common beginner mistakes — plus a few more.
Shape
Inner dimensions mismatch
Cannot multiply unless columns of A equal rows of B.
Order
AB is not always BA
Changing order usually changes result, and sometimes makes multiplication invalid.
Logic
Forgetting zero init
If result cells do not start at zero, accumulation gives incorrect values.
Ragged
Uneven rows
Validate every row length before multiplying.
1×1
Single cell
Still a product: C[0][0] = A[0][0] * B[0][0].
Rect
Non-square pairs
Use m, n, p — not a single N — when shapes differ.
Math
⚖️ Facts Worth Knowing
Handy follow-ups interviewers sometimes ask.
- Associative. (AB)C = A(BC) when shapes allow — but not commutative.
- Not commutative. AB is generally not equal to BA.
- Identity. AI = IA = A for the compatible identity matrix I.
- Cost. Classic algorithm is O(n³) for n×n; faster algorithms exist but are advanced.
Drill
🎯 Practice Problems
Try these variations to lock in the pattern.
1. Dry-run 2×2
- Reproduce Example 2 by hand
- Expect [[19, 22], [43, 50]]
2. Trace C[0][0] on 3×3
- Compute 1*9 + 2*6 + 3*3
- Confirm 30 matches Example 1
3. Reject bad shapes
- 2×2 times 3×2 → None or raise
- Assert cols(A) == rows(B)
4. Rectangular product
- Multiply 2×3 by 3×2
- Drop fixed N; use m, n, p
Important
Notes
- Rule:
C[i][j] = sum(A[i][k] * B[k][j]), with compatible dimensions. - Code pattern: initialize result to zeros, then use three loops.
- Complexity: cubic for square matrices with the basic algorithm.
- Non-square matrices use
rowsA,colsA, andcolsBwith the checkcolsA == rowsB.
Quick Takeaway: compatible shapes first, zero-init C, then accumulate A[i][k]*B[k][j] with three nested loops.
Analysis
⏱️ Time and Space Complexity
| Setting | Time | Extra space |
|---|---|---|
Two n × n matrices, classic triple loop | O(n^3) | O(1) beyond output |
m × n by n × p | O(m*n*p) | O(1) beyond output |
| Shape validation | O(m + n) row checks | O(1) |
For large matrices, production code usually switches to optimized libraries; interviews still expect the triple-loop explanation.
🎉 Conclusion
Matrix multiplication builds each result cell as a row–column dot product when inner dimensions match. Zero-init the result, use three nested loops, and distinguish this from element-wise multiplication.
Practice the three examples above, then continue to matrix subtraction for the next entrywise operation.
Compatible shapes first, zero-init C, then C[i][j] += A[i][k] * B[k][j].
Pro Tips
💡 Best Practices
✅ Do
- State (m×n)(n×p)→m×p first
- Zero-init the result matrix
- Use three nested loops with index k
- Dry-run one cell by hand
- State O(n³) or O(mnp) complexity
❌ Don’t
- Multiply incompatible shapes
- Confuse this with Hadamard multiply
- Skip zero initialization
- Assume AB equals BA
- Use shared-row list init
Summary
Key Takeaways
Knowledge Unlocked
Five things to remember about matrix multiplication
Multiply matrices the interview-friendly way.
5
Core concepts 01
Rule
Row · column
Definition 02
Shape
(m×n)(n×p)
Constraint 03
Loops
i, j, then k
Pattern 04
Init
Start at zero
Safety 05
Cost
O(n³) / O(mnp)
Analysis❓ Frequently Asked Questions
A must have as many columns as B has rows. If A is m x n and B is n x p, then AB is defined and its size is m x p.
No. Standard matrix multiplication uses row-column dot products. Cell-by-cell multiplication is a different operation called element-wise or Hadamard multiplication.
One loop chooses result row i, another chooses result column j, and the innermost loop accumulates sum over k: A[i][k] * B[k][j].
Each result cell is a running sum of products. It must start at zero before we add terms.
Python integers are arbitrary precision, so normal integer overflow does not happen. But very large values can increase runtime.
The classic triple-loop algorithm performs O(n^3) arithmetic operations for square matrices.
Not in general. Matrix multiplication is not commutative: AB and BA can differ, and one order may even be undefined.
NumPy uses @ or np.matmul for true matrix products. Interviews usually want the triple-loop version first so you show indexing clearly.
Did you Know? 🔊
Matrix multiplication pairs rows of A with columns of B. If A is m x n and B is n x p, then AB exists and has size m x p.
Continue to Matrix Subtraction
Learn entrywise subtraction with matching dimensions — a simpler return to cell-by-cell ops.
About the author
8 people found this page helpful