Matrix Multiplication

Matrix multiplication: A(m×n) · B(n×p) = C(m×p)

Matrix multiplication is the core operation of linear algebra: each entry of the product is the dot product of a row of A with a column of B — C[i][j] = Σ A[i][k]·B[k][j]. The number of columns of A must equal the number of rows of B; the result has the rows of A and the columns of B. Example: A = [[1,2],[3,4]] and B = [[5,6],[7,8]] give C = [[19,22],[43,50]]. The product is not commutative: in general A·B ≠ B·A. Multiplying by the identity matrix I leaves a matrix unchanged: A·I = A. The naive algorithm is O(n³); Strassen brought it down to O(n^2.81) and Coppersmith–Winograd and its successors to around O(n^2.37) — Williams recently pushed this to roughly 2.371. In practice, BLAS libraries and GPU tensor cores (NVIDIA H100, Apple M3 Neural Engine) provide enormous speedups.

Applications

Composing linear transformations (a 3D graphics pipeline chains rotation × scale × translation as one matrix product), neural networks (every layer is essentially a matrix multiplication followed by a non-linearity), Markov chains (state_{t+1} = P · state_t), solving linear systems Ax = b via matrix inverses, computer vision (camera projection matrices), and statistics (covariance and least-squares regression).

FAQ

Why must the inner dimensions match? Because each output entry is a dot product of a row of A with a column of B — they must have the same number of elements, i.e. cols(A) = rows(B).

Is matrix multiplication associative? Yes: (A·B)·C = A·(B·C). It is also distributive over addition. It just isn't commutative.

When is A·B = B·A? Only in special cases, e.g. when both matrices are diagonal, when one is the identity or a scalar multiple of it, or when the matrices share an eigenbasis.