Matrix multiplication - Wikipedia
matrix-multiplicationlinear-algebracomputational-complexitystrassen
Abstraction: Definition, properties, and complexity of matrix multiplication
Key points:
- Matrix product AB requires columns of A to equal rows of B; result is m x p for m x n times n x p matrices; first described by Jacques Philippe Marie Binet in 1812
- Matrix multiplication is non-commutative in general; associative; distributive over addition; forms a ring for square n x n matrices
- Naive algorithm is O(n^3); Strassen's 1969 algorithm reduced this to O(n^2.807); as of 2024 best known is O(n^2.371552) by Williams, Xu, Xu, Zhou
- Whether O(n^2+o(1)) multiplication is possible remains open
- Order of matrix chain multiplication affects computation cost dramatically (e.g., 4,500 vs 27,000 multiplications for same result)
- Transpose of a product reverses factor order: (AB)^T = B^T A^T; same for conjugate transpose
Connections: Matrix Multiplication · Strassen Algorithm · Computational Complexity · Linear Algebra · Volker Strassen