For Boolean matrices, replace numerical addition by logical disjunction and multiplication by logical conjunction. Applied to adjacency matrices, the product records a walk formed by following one segment represented by the first matrix and one represented by the second. For an adjacency matrix on vertices, start from . Repeated squaring then computes reflexive transitive closure once the exponent reaches : the identity entries pad shorter walks, and every reachable pair has a simple path of length at most .
For dimension-compatible matrices, . In coordinates both sides have entry ; distributing and regrouping the finite sums proves equality. This permits accumulating a product left to right even when a recursive algorithm groups the same transformations from the right. It does not permit changing factor order, because matrix multiplication is generally not commutative.
The matrix multiplication algorithm of Volker Strassen using seven half-size block products and quadratically many scalar additions per recursion level. Its recurrence is , giving arithmetic operations by the Master theorem.[ref]
https://staging.sigact.hosting.acm.org/prizes/knuth/2008.html. ACM SIGACT, 2008 Knuth Prize citation, the 1969 matrix-multiplication contribution
For an -by- matrix and an -component column vector , their matrix-vector product is the column vector with entriesEquivalently, it is the linear combination of the columns of with coefficients . This formula uses no complex conjugation, so over the complex numbers it should not be confused with an inner product of a row and . A dense evaluation costs arithmetic operations in Big O notation.
For matrices and , their matrix product is the matrix with entries . The operation producing it is matrix multiplication, representing composition of the corresponding linear maps.
Articles by others on the same topic
Matrix multiplication is a mathematical operation that takes two matrices and produces a third matrix. The multiplication of matrices is not as straightforward as multiplying individual numbers because specific rules govern when and how matrices can be multiplied together. Here are the key points about matrix multiplication: 1. **Compatibility**: To multiply two matrices, the number of columns in the first matrix must equal the number of rows in the second matrix.
Since a matrix can be seen as a linear map , the product of two matrices can be seen as the composition of two linear maps:One cool thing about linear functions is that we can easily pre-calculate this product only once to obtain a new matrix, and so we don't have to do both multiplications separately each time.