Matrix multiplication

Matrix multiplication is defined when the number of columns in the first matrix equals the number of rows in the second. If A has dimensions m × n and B has dimensions n × p, their product AB has dimensions m × p, with entry (AB)_ij = Σ_k=1ⁿ a_ikb_kj.¹

The shared dimension is consumed in each dot product: row i of A meets column j of B. This explains why a 2 × 3 matrix can multiply a 3 × 4 matrix, but not a 2 × 4 matrix. Unlike entrywise multiplication, the product mixes multiple entries and generally changes when the factors are reversed.

Viewed geometrically, matrices represent linear maps, and AB represents applying B first and then A. This interpretation accounts for both the dimension rule and the reversed order of composition.²

The product is associative and distributive, but it is generally not commutative. Whenever the products are defined, (AB)C = A(BC), and multiplication distributes over matrix addition; however, AB and BA may have different dimensions or different values.¹

Square matrices of a fixed size form an algebra with addition and multiplication. Its identity matrix leaves a compatible matrix unchanged, while a zero matrix absorbs multiplication. A square matrix may have an inverse, but only when it is nonsingular; invertibility is equivalent to having full rank and a nonzero determinant.

Products encode repeated transformations, simultaneous linear equations, coordinate changes, and powers of a transition matrix. In graph theory, powers of an adjacency matrix count walks of specified lengths when ordinary arithmetic is used; with Boolean arithmetic, related products can instead record reachability.

The direct algorithm computes every output entry by forming one dot product, requiring O(mnp) scalar multiplications and additions for an m × n matrix times an n × p matrix. For two n × n matrices, this is the familiar cubic O(n³) method.

Implementation order matters even though the mathematical result does not: arranging loops to reuse contiguous data can greatly improve cache behavior. Scientific software commonly delegates dense products to the Basic Linear Algebra Subprograms, or BLAS, whose level-3 routines include general matrix multiplication.³ Parallel CPUs, GPUs, and specialized accelerators divide the operation into blocks or tiles.

Algorithms can reduce the arithmetic count. Strassen's algorithm uses seven recursive multiplications of subblocks instead of eight and has asymptotic complexity O(n^log₂7), although extra additions, memory demands, numerical stability, and crossover size affect practical use.⁴ Floating-point implementations therefore balance speed against rounding error.

Matrix multiplication has useful variants that preserve the same structural idea while changing the coefficient system or the data pattern. Entries may belong to a finite field, a Boolean algebra, or another ring rather than the real or complex numbers; the dot-product formula then uses that system's addition and multiplication.

Sparse matrices can be multiplied without visiting every stored zero, but the product may become much denser, a phenomenon called fill-in. In numerical linear algebra, sparsity patterns and ordering strategies are therefore as important as arithmetic count. A product can also be formed implicitly: matrix-free methods compute its action on a vector without storing all entries, which is valuable in large eigenvalue and optimization problems.

Matrix multiplication is closely related to higher-order tensor contraction, and fast algorithms are studied through the tensor rank of the multiplication map. These connections link ordinary products to computational complexity theory, while batched multiplication supports applications ranging from machine learning to simulations.⁵

Compatible matrices

Matrices whose inner dimensions match, making their product defined.

Identity matrix

A square matrix with ones on the main diagonal and zeros elsewhere; it acts as the multiplicative identity.

Sparse matrix

A matrix in which most entries are zero, allowing storage or computation methods that exploit that pattern.

Matrix-free method

A computational method that obtains a matrix's action on a vector without explicitly storing the full matrix.