Matrix Multiplication

Matrix multiplication is a fundamental operation in linear algebra, essential for tasks ranging from 3D graphics transformations to machine learning algorithms. It combines two matrices into a new matrix by computing the dot product of rows from the first matrix and columns from the second.

How Matrix Multiplication Works

To multiply two matrices, say A and B, to produce a result matrix C, the number of columns in A must equal the number of rows in B. If A is an `n x m` matrix and B is an `m x p` matrix, the resulting matrix C will be an `n x p` matrix.

Each element `C[i][j]` in the result matrix is calculated by taking the dot product of the `i`-th row of matrix A and the `j`-th column of matrix B. This involves summing the products of corresponding elements from that row and column.

Let's consider an example with two 2x2 matrices:

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

Calculating C[0][0]

To determine the element at `C[0][0]`, we multiply the elements of the first row of A by the elements of the first column of B and sum the results. For instance, if `A[0][0]` is 1 and `B[0][0]` is 5, their product is 5. If `A[0][1]` is 2 and `B[1][0]` is 7, their product is 14. `C[0][0]` would then be `5 + 14 = 19`.

Calculating C[0][1]

Next, for `C[0][1]`, we use the first row of A and the second column of B. If `A[0][0]` is 1 and `B[0][1]` is 6, their product is 6. If `A[0][1]` is 2 and `B[1][1]` is 8, their product is 16. `C[0][1]` would be `6 + 16 = 22`.

Calculating C[1][0]

For `C[1][0]`, we use the second row of A and the first column of B. If `A[1][0]` is 3 and `B[0][0]` is 5, their product is 15. If `A[1][1]` is 4 and `B[1][0]` is 7, their product is 28. `C[1][0]` would be `15 + 28 = 43`.

Calculating C[1][1]

Finally, for `C[1][1]`, we use the second row of A and the second column of B. If `A[1][0]` is 3 and `B[0][1]` is 6, their product is 18. If `A[1][1]` is 4 and `B[1][1]` is 8, their product is 32. `C[1][1]` would be `18 + 32 = 50`.

This process continues for all elements in the result matrix C until it is fully populated.

Key takeaways

• Matrix multiplication requires the inner dimensions of the matrices to match.
• Each element `C[i][j]` is a dot product of row `i` from the first matrix and column `j` from the second.
• The resulting matrix has dimensions `n x p` if the input matrices are `n x m` and `m x p`.
• Matrix multiplication is not commutative (A * B != B * A, generally).