|
This article gives an overview of the various ways to multiply matrices.
The Einstein summation convention is
used throughout.
Ordinary matrix product
By far the most important way to multiply matrices is the usual matrix multiplication. It is defined between two matrices only
if the number of columns of the first matrix is the same as the number of rows of the second matrix. If A is an
m-by-n matrix and B is an n-by-p matrix, then their product
AB is an m-by-p matrix given by
- (AB)ij = AirBrj = ai1 *
b1j + ai2 * b2j + ... +
ain * bnj
for each pair i and j.
The following picture shows how to calculate the (AB)12 element of AB if A is a
2×4 matrix, and B is a 4×3 matrix. Elements from each matrix are paired off in the direction of the
arrows; each pair is multiplied and the products are added. The location of the resulting number in AB corresponds to
the row and column that were considered.
-
-
Example
-
-
This notion of multiplication is important because A and B are interpreted as linear transformations (which is almost universally done), then
the matrix product AB corresponds to the composition of the two linear transformations, with B being applied
first. In general, matrix multiplication is not commutative; that is, AB is
not equal to BA.
The complexity of matrix
multiplication, if carried out naively, is O(n³), but
more efficient algorithms do exist. Strassen's algorithm,
devised by Volker Strassen in 1969 and often referred to as "fast matrix multiplication", uses a mapping of bilinear combinations to reduce
complexity to O(nlog2(7)) (approximately O(n2.807...)). In
practice, though, it is rarely used since it is awkward to implement, lacking numerical stability. The constant factor involved
is about 4.695 asymptotically; Winograd's method improves on this slightly by reducing it to an asymptotic 4.537.
The best algorithm currently known, which was presented by Don
Coppersmith and S. Winograd in
1990, has an asymptotic complexity of O(n2.376). It has been
shown that the leading exponent must be at least 2.
Hadamard product
For two matrices of the same dimensions, we have the Hadamard product or entrywise product. The Hadamard product of two m-by-n matrices A and
B, denoted by A · B, is an m-by-n matrix given by
(A·B)[i,j]=A[i,j] * B[i,j]. For instance
-
Note that the Hadamard product is a submatrix of the Kronecker product (see
below). Hadamard product is studied by matrix theorists, but it is virtually untouched by linear algebraists.
Kronecker product
For any two arbitrary matrices A=(aij) and B, we have the direct product or
Kronecker product A B defined
as
-
(the HTML entity ⊗ (⊗) represents the direct product, but is not supported on older browsers)
Note that if A is m-by-n and B is p-by-r then A B is an mp-by-nr matrix. Again this multiplication is not
commutative.
For example
-
.
If A and B represent linear transformations V1 → W1 and
V2 → W2, respectively, then A
B represents the tensor product of the two maps,
V1 V2 → W1
W2.
Common properties
All three notions of matrix multiplication are associative
- A * (B * C) = (A * B) * C
and distributive:
- A * (B + C) = A * B + A * C
and
- (A + B) * C = A * C + B * C
and compatible with scalar multiplication:
- c(A * B) = (cA) * B = A * (cB)
Scalar multiplication
The scalar multiplication of a matrix A=(aij) and a scalar r gives the product
- rA=(r aij).
If we are concerns with matrices over a ring, then the
above multiplicaion is sometimes called the left multiplication while the right multiplication is defined to
be
- Ar=(aij r).
When the underlying ring is commutative, for example, the real or complex
number field, the two multiplications are the same. However, if the ring is not commutative, such as the quaternions, they may be different. For example
-
External links
References
- Strassen, Volker, Gaussian Elimination is not Optimal, Numer. Math. 13, p. 354-356, 1969
- Coppersmith, D., Winograd S., Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9, p. 251-280,
1990
|