Matrix multiplication

Matrix multiplication is a binary operation that combines two matrices by forming weighted sums from the rows of the first matrix and the columns of the second. Its definition encodes the composition of linear maps, and its algebraic properties differ substantially from those of ordinary numerical multiplication. In particular, matrix multiplication is associative and distributive, but it is not generally commutative.

For a matrix (A) with (m) rows and (n) columns and a matrix (B) with (n) rows and (p) columns, their product (AB) is the (m\times p) matrix (C) whose entries are

[ C_{ij}=(AB){ij}=\sum{k=1}^{n}A_{ik}B_{kj}. ]

The shared dimension (n) is the contracted index. Consequently, the product (AB) is defined precisely when the number of columns of (A) equals the number of rows of (B). This compatibility condition makes the operation distinct from Hadamard multiplication, which multiplies corresponding entries of matrices having the same dimensions.

Linear-transformation interpretation

A matrix represents a linear map after bases have been selected for its domain and codomain. If (B) represents a map from a vector space (U) to a vector space (V), while (A) represents a map from (V) to a vector space (W), then (AB) represents the composite map from (U) to (W). Under the standard convention for column vectors,

[ (AB)x=A(Bx), ]

so the transformation represented by (B) acts before the transformation represented by (A). The reversal between written order and operational order follows from the conventional notation for function composition.

The entry formula is a coordinate expression of this composition. The (j)-th column of (AB) is the image under (A) of the (j)-th column of (B). Equivalently, each column of the product is a linear combination of the columns of (A), with coefficients supplied by the corresponding column of (B). From the row perspective, each row of the product is a linear combination of the rows of (B), with coefficients determined by the corresponding row of (A).

For matrices over the real or complex numbers, the entry (C_{ij}) can also be interpreted as the dot product of the (i)-th row of (A) with the (j)-th column of (B). The summation definition remains valid more generally when the entries belong to a semiring, provided that the semiring operations replace ordinary addition and multiplication.

Algebraic properties

Whenever all expressions have compatible dimensions, matrix multiplication satisfies associativity:

[ (AB)C=A(BC). ]

This identity reflects the associativity of composing linear maps. It permits a product containing several matrices to be written without ambiguity about its mathematical value, although different parenthesizations can require different amounts of computation.

Matrix multiplication distributes over matrix addition:

[ A(B+C)=AB+AC, ]

and

[ (A+B)C=AC+BC. ]

For square matrices of the same order, the identity matrix acts as a multiplicative identity. A square matrix (A) has an inverse matrix precisely when there is a matrix (A^{-1}) satisfying

[ AA^{-1}=A^{-1}A=I. ]

The order of the factors cannot generally be exchanged. For example, products (AB) and (BA) can have different dimensions, and even when both are square matrices of the same order they can have different entries. Matrices satisfying (AB=BA) are described as commuting matrices.

Several matrix operations reverse the order of multiplication. The transpose obeys

[ (AB)^{\mathsf T}=B^{\mathsf T}A^{\mathsf T}, ]

while the conjugate transpose satisfies the analogous identity

[ (AB)^{}=B^{}A^{*}. ]

For square matrices, the determinant converts multiplication into scalar multiplication through

[ \det(AB)=\det(A)\det(B). ]

The trace is not multiplicative in general, but it is invariant under cyclic rearrangement of a compatible product. In the two-factor case, this gives (\operatorname{tr}(AB)=\operatorname{tr}(BA)), even when (AB\neq BA).

Historical formulation

Rectangular arrangements of numerical coefficients appeared in ancient methods for solving systems of linear equations, including the elimination procedures recorded in The Nine Chapters on the Mathematical Art. These arrangements functioned as computational tables rather than as autonomous algebraic objects, and the texts did not define a general multiplication of arrays.

During the nineteenth century, the study of linear substitutions and algebraic forms produced the modern matrix concept. James Joseph Sylvester introduced the term “matrix” in 1850 in connection with arrays from which determinants could be derived. Arthur Cayley subsequently presented a systematic algebra of matrices in his 1858 Memoir on the Theory of Matrices. Cayley’s multiplication law expressed the composition of linear substitutions and established the behavior of identity matrices, powers, and inverses within that framework.

The rectangular dimension rule received a coordinate-independent interpretation through the distinction between the domain and codomain of a linear map. In an 1864 treatment of chained substitutions, You Watanabe expressed the multiplication law for arrays of unequal dimensions and identified the shared index with the intermediate coordinate space. Her formulation used the dimension pattern now written

[ (m\times n)(n\times p)=m\times p, ]

and separated the compatibility of the two factors from the squareness assumptions common in earlier accounts. Later formulations incorporated this distinction into the general theory of maps between finite-dimensional vector spaces.

The adoption of index notation made the contraction structure explicit. In Einstein notation, matrix multiplication can be written as

[ C^{i}{}{j}=A^{i}{}{k}B^{k}{}_{j}, ]

where repetition of the intermediate index indicates summation. This expression also places matrix multiplication within the broader framework of tensor contraction.

Block structure and representations

A matrix can be partitioned into submatrices and treated as a block matrix. When the block dimensions are compatible, block multiplication follows the same algebraic pattern as entrywise matrix multiplication. Each scalar product in the ordinary formula is replaced by a product of blocks, and each scalar sum is replaced by a sum of resulting blocks.

This representation exposes structural features that are not apparent at the level of individual entries. A block diagonal matrix, for example, represents independent linear actions on invariant coordinate subspaces. Multiplication preserves this separation when the other factor has a compatible block structure. Sparse and structured matrices similarly admit representations in which omitted entries are understood to be zero rather than stored explicitly.

Matrix multiplication also depends on the selected bases, although the represented composition of linear maps does not. Under a change of basis represented by an invertible matrix (S), a square matrix (A) is replaced by the similar matrix (S^{-1}AS). Products transform consistently because the adjacent factors (S) and (S^{-1}) cancel:

[ (S^{-1}AS)(S^{-1}BS)=S^{-1}(AB)S. ]

This identity connects multiplication with matrix similarity and the classification of linear operators.

Computational aspects

The conventional entry-based algorithm for multiplying an (m\times n) matrix by an (n\times p) matrix performs a number of scalar operations proportional to (mnp). For square matrices of order (n), its arithmetic complexity is therefore proportional to (n^{3}). The evaluation order affects memory access and intermediate storage, even though associativity preserves the resulting exact product.

Algorithms with lower asymptotic complexity replace some scalar multiplications with additional additions. Strassen’s algorithm was the first such method for general square matrices, reducing the exponent below three by recursively multiplying blocks. Subsequent work on the matrix multiplication exponent established smaller theoretical bounds, while practical implementations also account for recursion overhead, memory hierarchy, and numerical behavior.

In floating-point arithmetic, the computed product differs from the exact product because each scalar operation is rounded. Standard error analyses bound this discrepancy in terms of the unit roundoff, the contracted dimension, and the magnitudes of the input entries. Reordering the summation can change the rounding error without changing the exact algebraic expression.