Matrix Multiplication

easyFREEMatrices & TransformationsLinear AlgebraCV: Mathematical Foundations

Implement matrix multiplication for two matrices A and B. This operation is crucial in linear algebra and computer vision, as it represents the composition of linear transformations.

Given matrices $A$ of size $m \times n$ and $B$ of size $n \times p$ , the product $C = A \times B$ is an $m \times p$ matrix.

Initialize the result matrix $C$ with zeros.
For each element $C_{ij}$ , compute the dot product of row $i$ from $A$ and column $j$ from $B$ . The resulting matrix $C$ represents the composition of the transformations represented by $A$ and $B$ .

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

This technique is widely used in image processing and machine learning applications.

Example

Input

A = [[1, 2], [3, 4]]
B = [[5, 6], [7, 8]]

Output

[[19, 22], [43, 50]]

Reasoning

Inputs: $A$ and $B$ are both $2 \times 2$ . The number of columns of $A$ (2) equals the number of rows of $B$ (2), so the product exists and is $2 \times 2$ .
Entry (row 1, column 1): pair row 1 of $A$ , $(1, 2)$ , with column 1 of $B$ , $(5, 7)$ : $1 \cdot 5 + 2 \cdot 7 = 5 + 14 = 19$ .
Entry (row 1, column 2): row $(1, 2)$ with column $(6, 8)$ : $6 + 16 = 22$ .
Second row: row $(3, 4)$ with $(5, 7)$ gives $15 + 28 = 43$ , and with $(6, 8)$ gives $18 + 32 = 50$ .
Output: $C = \begin{pmatrix} 19 & 22 \\ 43 & 50 \end{pmatrix}$ , i.e. [[19, 22], [43, 50]]. Each entry already has fewer than 4 decimal places, so rounding leaves it unchanged.
Notice: order matters. Swapping the inputs gives $BA = \begin{pmatrix} 23 & 34 \\ 31 & 46 \end{pmatrix}$ , a different matrix, because composing transformations is not commutative.

Constraints

Matrix A has dimensions m×n, Matrix B has dimensions n×p
1 ≤ m, n, p ≤ 100
Elements are floating-point numbers
Round each element of the result to 4 decimal places

Learn this in

Mathematical FoundationsFoundations

More from CV: Mathematical Foundations

Adam Optimizer Stephard Power Iteration for Dominant Eigenvectorhard SVD Image Compressionhard Batch Affine Transform with PyTorchmedium Covariance Matrix from Image Patcheshard

Concept primer

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:

Initialize an $m \times p$ result matrix $C$ with zeros.
For each row $i$ of $A$ :
For each column $j$ of $B$ :
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++).

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.

Create result matrix

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

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]

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).

solution.py

Python 3.13

Test results