Matrix Multiplication

Matrix multiplication combines two matrices by taking dot products of rows of $A$ with columns of $B$. For $A$ of size $m \times n$ and $B$ of size $n \times p$, the result $C$ is an $m \times p$ matrix where each entry $C_{ij}$ is the sum of elementwise products along the shared dimension $n$:

$$C_{ij} = \sum_{k=1}^{n} A_{ik} \cdot B_{kj}.$$

Conceptually, each row of $A$ represents coefficients, and each column of $B$ represents a vector being combined by those coefficients.

In computer vision and linear algebra, matrix multiplication encodes linear transformations (like rotation, scaling, projection). Applying a transformation to a vector is just multiplying a matrix by that vector. Composing multiple transformations (e.g., rotate then translate in homogeneous coordinates) corresponds to multiplying their matrices in sequence, which is why understanding the order and shape rules of matrix multiplication is important.

---

1. Background Knowledge (Key Concepts)

• Shape compatibility

• $A$: $m \times n$

• $B$: $n \times p$

• $C = A B$: $m \times p$

• The inner dimensions must match (both equal $n$). The outer dimensions give the result’s shape.

• Entry-wise definition For each output entry:

$$C_{ij} = \sum_{k=1}^{n} A_{ik} \cdot B_{kj}$$

• Index $i$: which row of $A$ / $C$

• Index $j$: which column of $B$ / $C$

• Index $k$: runs along the shared dimension (columns of $A$, rows of $B$).

• Interpretation as dot products

• $C_{ij} =$\text{dot}$($\text{row }$i$\text{ of }$A,$\text{column }$j$\text{ of }$B)$.

---

2. Algorithm / Approach

For this easy-level problem, you use the classical triple-loop algorithm:

1. Initialize an $m \times p$ result matrix $C$ with zeros.
2. For each row $i$ of $A$:
3. For each column $j$ of $B$:
4. Compute $C_{ij}$ by looping over $k = 0 \dots n-1$ and accumulating:

$$C_{ij} \mathrel{+}= A_{ik} \times B_{kj}$$

This is the standard dense matrix multiplication used in many implementations when dimensions are small or moderate.

---

3. Step-by-Step Strategy

Assume inputs are 2D arrays (e.g., lists of lists in Python or vectors of vectors in C++).

1. Read dimensions

• Let A be size m x n.
• Let B be size n x p.
• Optionally, assert/check that A’s column count equals B’s row count.

2. Create result matrix

• Allocate C with size m x p.
• Initialize all entries to 0 (or the numeric zero of your type).

3. Nested loops

• Outer loop over rows of A:

for i in range(m): # row index in A and C

• Middle loop over columns of B:

for j in range(p): # column index in B and C

• Inner loop over shared dimension n to accumulate the dot product:

for k in range(n): # shared dimension
C[i][j] += A[i][k] * B[k][j]

4. Return or print C in the format the problem expects.

Tiny Python-like sketch (for intuition, not a full solution):

def matmul(A, B):
 m, n = len(A), len(A)
 n2, p = len(B), len(B)
 # assume n == n2
 C = [[0 for _ in range(p)] for _ in range(m)]
 for i in range(m):
 for j in range(p):
 s = 0
 for k in range(n):
 s += A[i][k] * B[k][j]
 C[i][j] = s
 return C

---

4. Common Pitfalls

• Dimension mismatch

• Forgetting to check A_cols == B_rows before multiplying.

• Mixing up m, n, p and indexing incorrectly.

• Index order mistakes

• Using B[j][k] instead of B[k][j] in the inner loop.

• Writing to C[k][j] instead of C[i][j].

• Incorrect initialization

• Not resetting the accumulator s to 0 for each new (i, j).

• Not initializing C to zeros, causing garbage values to be added.

• Off-by-one errors

• Using <= instead of < in loops.

• Confusing 0-based indices (common in code) with 1-based notation in math.

---

5. Time & Space Complexity

• Time complexity

• Three nested loops over:

• $i = 1 \dots m$

• $j = 1 \dots p$

• $k = 1 \dots n$

• Total operations: $O(m \cdot n \cdot p)$.

• Space complexity

• Input storage: $O(mn)$ for $A$, $O(np)$ for $B$.

• Output storage: $O(mp)$ for $C$.

• Extra (auxiliary) space beyond inputs and output: $O(1)$ (just a few scalars like i, j, k, s).