Matrix Multiplication Assignment¶
Introduction¶
Matrix multiplication is a fundamental operation in many areas of mathematics and computer science, specifically it's a big deal in machine learning!
It involves taking two matrices and producing a third matrix that is the product of the first two. The multiplication is done by taking the dot product of rows and columns from the two matrices.
For two matrices $A$ and $B$ to be multiplied, the number of columns in $A$ must be equal to the number of rows in $B$. If $A$ is of size $m \times n$ and $B$ is of size $n \times l$, the resulting matrix $C$ will be of size $m \times l$.
Algorithm¶
Here's the algorithm for multiplying matrix $A$ times matrix $B$.
Check Dimensions: Ensure the number of columns in matrix $A$ matches the number of rows in matrix $B$. If $A$ is an $m \times n$ matrix and $B$ is an $n \times l$ matrix, the product $C$ will be an $m \times l$ matrix.
Initialize Result Matrix: Create an $m \times l$ matrix $C$ with all elements initialized to zero.
Multiply and Sum:
- For each element $C[i][j]$ in matrix $C$:
- Compute the sum of products of corresponding elements from the $i$-th row of $A$ and the $j$-th column of $B$: $ C[i][j] = \sum_{k=1}^{n} A[i][k] \times B[k][j] $
- For each element $C[i][j]$ in matrix $C$:
Repeat: Repeat the multiplication and summing process for all $i$ (rows in $A$) and $j$ (columns in $B$).
In summary, each element of the resulting matrix $C$ is the dot product of the corresponding row from $A$ and the corresponding column from $B$.
$$ \overset{4\times 2 \text{ matrix}}{\begin{bmatrix} a_{11} & a_{12} \\ \cdot & \cdot \\ a_{31} & a_{32} \\ \cdot & \cdot \\ \end{bmatrix}} \overset{2\times 3\text{ matrix}}{\begin{bmatrix} \cdot & b_{12} & b_{13} \\ \cdot & b_{22} & b_{23} \\ \end{bmatrix}} = \overset{4\times 3\text{ matrix}}{\begin{bmatrix} \cdot & c_{12} & \cdot \\ \cdot & \cdot & \cdot \\ \cdot & \cdot & c_{33} \\ \cdot & \cdot & \cdot \\ \end{bmatrix}} $$
And the values for $C$ are computed as...
$$ \begin{align} c_{12} & = a_{11} b_{12} + a_{12} b_{22} \\ c_{33} & = a_{31} b_{13} + a_{32} b_{23} . \end{align} $$
Visually¶
Assignment¶
- Write a function
matrix_multiplythat takes two matrices (as lists of lists) and returns their product. - Include checks to ensure the matrices can be multiplied (i.e., the number of columns in the first matrix is equal to the number of rows in the second matrix).
- Test your function with some example matrices.
Instructions¶
Function Definition:
- Define the function
matrix_multiply(A, B)whereAandBare matrices represented as lists of lists.
- Define the function
Matrix Multiplication Logic:
- Ensure the number of columns in
Aequals the number of rows inB. - Calculate the product matrix by taking the dot product of the rows of
Awith the columns ofB.
- Ensure the number of columns in
Examples:
- Provide example matrices and their expected outputs.
Example Code¶
def matrix_multiply(A, B):
...
return C
# Example matrices
A = [
[1, 2, 3],
[4, 5, 6]
]
B = [
[7, 8],
[9, 10],
[11, 12]
]
print(matrix_multiply(A, B))
# Expected output:
# [
# [58, 64],
# [139, 154]
# ]
# Another example
C = [
[2, 3],
[0, 1],
[4, 5]
]
D = [
[1, 2, 3],
[4, 5, 6]
]
print(matrix_multiply(C, D))
# Expected output:
# [
# [14, 19, 24],
# [4, 5, 6],
# [24, 33, 42]
# ]
def dot_product(vector_a, vector_b):
"""
Calculates dotproduct of two vectors, so:
[0, 1, 2] * [3, 4, 5] = 0 * 3 + 1 * 4 + 2 * 5 = 14
"""
assert len(vector_a) == len(vector_b)
total = 0
for i in range(len(vector_a)):
total += vector_a[i] * vector_b[i]
return total
def matrix_multiply(A, B):
# Assert that m is the number of columns in A
# And m is the number of rows in B
assert len(A[0]) == len(B)
l = len(A) # Number of rows in A
m = len(A[0]) # Number of columns in A (and rows in B)
n = len(B[0]) # Number of columns in B
# Get the a_rows, it's just A
a_rows = A
# Get the b_cols, we have to extract them
b_cols = []
for j in range(len(B[0])):
col = []
for i in range(len(B)):
col.append(B[i][j])
b_cols.append(col)
C = []
for i in range(l):
col = []
for j in range(n):
val = dot_product(a_rows[i], b_cols[j])
col.append(val)
C.append(col)
return C
# Example matrices
A = [
[1, 2, 3],
[4, 5, 6]
]
B = [
[7, 8],
[9, 10],
[11, 12]
]
out = matrix_multiply(A, B)
exp = [
[58, 64],
[139, 154]
]
assert out == exp
print(out)
print(exp)
# Another example
C = [
[2, 3],
[0, 1],
[4, 5]
]
D = [
[1, 2, 3],
[4, 5, 6]
]
out = matrix_multiply(C, D)
exp = [
[14, 19, 24],
[4, 5, 6],
[24, 33, 42]
]
assert out == exp
print(out)
print(exp)
[[58, 64], [139, 154]] [[58, 64], [139, 154]] [[14, 19, 24], [4, 5, 6], [24, 33, 42]] [[14, 19, 24], [4, 5, 6], [24, 33, 42]]