Matrix multiplication

From Wikipedia, the free encyclopedia

(Redirected from Matrix product)
Jump to: navigation, search

This article gives an overview of the various ways to perform matrix multiplication.

Contents

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 is an m-by-p matrix denoted by AB (or sometimes A · B). The product is given by

(\mathbf{AB})_{ij} = \sum_{r=1}^n a_{ir}b_{rj} = a_{i1}b_{1j} + a_{i2}b_{2j} + \cdots + a_{in}b_{nj}.

for each pair i and j with 1 ≤ i ≤ m and 1 ≤ j ≤ p. The algebraic system of "matrix units" summarises the abstract properties of this kind of multiplication.

The picture to the left shows how to calculate the (1,2) element and the (3,3) element of AB if A is a 4×2 matrix, and B is a 2×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.

(\mathbf{AB})_{1,2} = \sum_{r=1}^2 a_{1,r}b_{r,2} = a_{1,1}b_{1,2}+a_{1,2}b_{2,2}
(\mathbf{AB})_{3,3} = \sum_{r=1}^2 a_{3,r}b_{r,3} = a_{3,1}b_{1,3}+a_{3,2}b_{2,3}

For example:

\begin{bmatrix} 1 & 0 & 2 \\ -1 & 3 & 1 \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 2 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 \times 3 + 0 \times 2 + 2 \times 1 & 1 \times 1 + 0 \times 1 + 2 \times 0 \\ -1 \times 3 + 3 \times 2 + 1 \times 1 & -1 \times 1 + 3 \times 1 + 1 \times 0 \end{bmatrix} = \begin{bmatrix} 5 & 1 \\ 4 & 2 \end{bmatrix}

This matrix multiplication can also be considered from a slightly different viewpoint : it adds vectors together after being multiplied by different coefficients. If A and B are matrices given by:

\mathbf{A} = \begin{bmatrix} a_{1,1} & a_{1,2} & \dots \\ a_{2,1} & a_{2,2} & \dots \\ \vdots & \vdots & \ddots \end{bmatrix} and \mathbf{B} = \begin{bmatrix} b_{1,1} & b_{1,2} & \dots \\ b_{2,1} & b_{2,2} & \dots \\ \vdots & \vdots & \ddots \end{bmatrix} = \begin{bmatrix} B_1 \\ B_2 \\ \vdots \end{bmatrix}

then

\mathbf{AB} = \begin{bmatrix} a_{1,1} B_1 + a_{1,2} B_2 + \cdots \\\\ a_{2,1} B_1 + a_{2,2} B_2 + \cdots \\ \vdots \end{bmatrix}

The example revisited:

\begin{bmatrix} 1 & 0 & 2 \\ -1 & 3 & 1 \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 2 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 \begin{bmatrix} 3 & 1 \end{bmatrix} + 0 \begin{bmatrix} 2 & 1 \end{bmatrix} + 2 \begin{bmatrix} 1 & 0 \end{bmatrix} \\ -1 \begin{bmatrix} 3 & 1 \end{bmatrix} + 3 \begin{bmatrix} 2 & 1 \end{bmatrix} + 1 \begin{bmatrix} 1 & 0 \end{bmatrix} \end{bmatrix} = \begin{bmatrix} \begin{bmatrix} 3 & 1 \end{bmatrix} + \begin{bmatrix} 0 & 0 \end{bmatrix} + \begin{bmatrix} 2 & 0 \end{bmatrix} \\ \begin{bmatrix} -3 & -1 \end{bmatrix} + \begin{bmatrix} 6 & 3 \end{bmatrix} + \begin{bmatrix} 1 & 0 \end{bmatrix} \end{bmatrix}
= \begin{bmatrix} 5 & 1 \\ 4 & 2 \end{bmatrix}

The rows in the matrix on the left are the list of coefficients. The matrix on the right is the list of vectors. In the example, the first row is [1 0 2], and thus we take 1 times the first vector, 0 times the second vector, and 2 times the third vector.

The equation can be simplified further by using outer products:

\mathbf{A} = \begin{bmatrix} A_1 & A_2 & \dots \end{bmatrix} \implies \mathbf{AB} = \sum_i A_iB_i

The terms of this sum are matrices of the same shape, each describing the effect of one column of A and one row of B on the result. The columns of A can be seen as a coordinate system of the transform, i.e. given a vector x we have \mathbf{A}x=A_1x_1+A_2x_2+\cdots where xi are coordinates along the Ai "axes". The terms AiBi are like Aixi, except that Bi contains the ith coordinate for each column vector of B, each of which is transformed independently in parallel.

The example revisited:

\begin{bmatrix} 1 & 0 & 2 \\ -1 & 3 & 1 \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 2 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix}1 \\ -1\end{bmatrix}\begin{bmatrix}3 & 1\end{bmatrix}+ \begin{bmatrix}0 \\ 3\end{bmatrix}\begin{bmatrix}2 & 1\end{bmatrix}+ \begin{bmatrix}2 \\ 1\end{bmatrix}\begin{bmatrix}1 & 0\end{bmatrix}
= \begin{bmatrix} 1 \cdot 3 & 1 \cdot 1 \\ -1 \cdot 3 & -1 \cdot 1 \end{bmatrix}+ \begin{bmatrix} 0 \cdot 2 & 0 \cdot 1 \\ 3 \cdot 2 & 3 \cdot 1 \end{bmatrix}+ \begin{bmatrix} 2 \cdot 1 & 2 \cdot 0 \\ 1 \cdot 1 & 1 \cdot 0 \end{bmatrix} = \begin{bmatrix} 5 & 1 \\ 4 & 2 \end{bmatrix}

The vectors \begin{bmatrix}3 & 2 & 1\end{bmatrix}^\top and \begin{bmatrix}1 & 1 & 0\end{bmatrix}^\top have been transformed to \begin{bmatrix}5 & 4\end{bmatrix}^\top and \begin{bmatrix}1 & 2\end{bmatrix}^\top in parallel. One could also transform them one by one with the same steps:

\begin{bmatrix} 1 & 0 & 2 \\ -1 & 3 & 1 \end{bmatrix} \cdot \begin{bmatrix} 3 \\ 2 \\ 1 \end{bmatrix} = \begin{bmatrix}1 \\ -1\end{bmatrix}3+ \begin{bmatrix}0 \\ 3\end{bmatrix}2+ \begin{bmatrix}2 \\ 1\end{bmatrix}1 = \begin{bmatrix} 1\cdot 3 \\ -1\cdot 3\end{bmatrix}+ \begin{bmatrix} 0\cdot 2 \\ 3\cdot 2\end{bmatrix}+ \begin{bmatrix} 2\cdot 1 \\ 1\cdot 1\end{bmatrix} = \begin{bmatrix} 5 \\ 4 \end{bmatrix}

The ordinary matrix product can be thought of as a dot product of a column-list of vectors and a row-list of vectors. If A and B are matrices given by:

\mathbf{A} = \begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3} & \dots \\ a_{2,1} & a_{2,2} & a_{2,3} & \dots \\ a_{3,1} & a_{3,2} & a_{3,3} & \dots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} = \begin{bmatrix} A_1 \\ A_2 \\ A_3 \\ \vdots \end{bmatrix} and \mathbf{B} = \begin{bmatrix} b_{1,1} & b_{1,2} & b_{1,3} & \dots \\ b_{2,1} & b_{2,2} & b_{2,3} & \dots \\ b_{3,1} & b_{3,2} & b_{3,3} & \dots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} = \begin{bmatrix} B_1 & B_2 & B_3 & \dots \end{bmatrix}

where

A1 is the vector of all elements of the form a1,x      A2 is the vector of all elements of the form a2,x     etc,
and B1 is the vector of all elements of the form bx,1      B2 is the vector of all elements of the form bx,2     etc,

then

\mathbf{AB} = \begin{bmatrix} A_1 \\ A_2 \\ A_3 \\ \vdots \end{bmatrix} * \begin{bmatrix} B_1 & B_2 & B_3 & \dots \end{bmatrix} = \begin{bmatrix} (A_1 \cdot B_1) & (A_1 \cdot B_2) & (A_1 \cdot B_3) & \dots \\ (A_2 \cdot B_1) & (A_2 \cdot B_2) & (A_2 \cdot B_3) & \dots \\ (A_3 \cdot B_1) & (A_3 \cdot B_2) & (A_3 \cdot B_3) & \dots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix}

Matrix multiplication is not commutative (that is, AB ≠ BA), except in special cases. It is easy to see why: you cannot expect to switch the proportions with the vectors and get the same result. It is also easy to see how the order of the factors determines the result when one knows that the number of columns in the proportions matrix has to be the same as the number of rows in the vectors matrix: they have to represent the same number of vectors.

Although matrix multiplication is not commutative, the determinants of AB and BA are always equal (if A and B are square matrices of the same size). See the article on determinants for an explanation. However matrix multiplication is commutative when both matrixes are diagonal and of the same dimension.[1]

This notion of multiplication is important because if 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.

Additionally, all notions of matrix multiplication described here share a set of common properties described below.

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", is based on a clever way of multiplying two 2 × 2 matrices which requires only 7 multiplications (instead of the usual 8). Applying this trick recursively gives an algorithm with a cost of O( n^{\log_{2}7}) \approx O(n^{2.807}). In practice, though, it is rarely used since it is awkward to implement and it lacks numerical stability. The constant factor implied in the big O notation is about 4.695.[citation needed]

The algorithm with the lowest known exponent, which was presented by Don Coppersmith and Shmuel Winograd in 1990, has an asymptotic complexity of O(n2.376). It is similar to Strassen's algorithm: a clever way is devised for multiplying two k × k matrices with less than k³ multiplications, and this technique is applied recursively. It improves on the constant factor in Strassen's algorithm, reducing it to 4.537. However, the constant term implied in the O(n2.376) result is so large that the Coppersmith–Winograd algorithm is only worthwhile for matrices that are too big to handle on present-day computers (Knuth, 1998).

Since any algorithm for multiplying two n × n matrices has to process all 2 × n² entries, there is an asymptotic lower bound of Ω(n²) operations. Raz (2002) proves a lower bound of Ω(m2logm) for bounded coefficient arithmetic circuits over the real or complex numbers.

Cohn et al. (2003, 2005) put methods such as the Strassen and Coppersmith–Winograd algorithms in an entirely different, group-theoretic context. They show that if families of wreath products of Abelian with symmetric groups satisfying certain conditions exists, matrix multiplication algorithms with essential quadratic complexity exist. Most researchers believe that this is indeed the case (Robinson, 2005).

The scalar multiplication of a matrix A = (aij) and a scalar r gives a product r A of the same size as A. The entries of r A are given by

(r\mathbf{A})_{ij} = r \cdot a_{ij}. \,

If we are concerned with matrices over a ring, then the above multiplication is sometimes called the left multiplication while the right multiplication is defined to be

(\mathbf{A}r)_{ij} = a_{ij} \cdot 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

i\begin{bmatrix} i & 0 \\ 0 & j \\ \end{bmatrix} = \begin{bmatrix} -1 & 0 \\ 0 & k \\ \end{bmatrix} \ne \begin{bmatrix} -1 & 0 \\ 0 & -k \\ \end{bmatrix} = \begin{bmatrix} i & 0 \\ 0 & j \\ \end{bmatrix}i.

For two matrices of the same dimensions, we have the Hadamard product, also known as the entrywise product and the Schur product. It can be generalized to hold not only for matrices but also for operators. 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)ij = aij bij. For instance

\begin{bmatrix} 1 & 2 \\ 3 & 1 \\ \end{bmatrix} \bullet \begin{bmatrix} 0 & 3 \\ 2 & 1 \\ \end{bmatrix} = \begin{bmatrix} 1\cdot 0 & 2\cdot 3 \\ 3\cdot 2 & 1\cdot 1 \\ \end{bmatrix} = \begin{bmatrix} 0 & 6 \\ 6 & 1 \\ \end{bmatrix} .

Note that the Hadamard product is a submatrix of the Kronecker product (see below). The Hadamard product is studied by matrix theorists, and it appears in lossy compression algorithms such as JPEG, but it is virtually untouched by linear algebraists. It is discussed in (Horn & Johnson, 1994, Ch. 5).

Main article: Kronecker product.

For any two arbitrary matrices A and B, we have the direct product or Kronecker product A ⊗ B defined as

\begin{bmatrix} a_{11}B & a_{12}B & \cdots & a_{1n}B \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1}B & a_{m2}B & \cdots & a_{mn}B \end{bmatrix}.

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

\begin{bmatrix} 1 & 2 \\ 3 & 1 \\ \end{bmatrix} \otimes \begin{bmatrix} 0 & 3 \\ 2 & 1 \\ \end{bmatrix} = \begin{bmatrix} 1\cdot 0 & 1\cdot 3 & 2\cdot 0 & 2\cdot 3 \\ 1\cdot 2 & 1\cdot 1 & 2\cdot 2 & 2\cdot 1 \\ 3\cdot 0 & 3\cdot 3 & 1\cdot 0 & 1\cdot 3 \\ 3\cdot 2 & 3\cdot 1 & 1\cdot 2 & 1\cdot 1 \\ \end{bmatrix} = \begin{bmatrix} 0 & 3 & 0 & 6 \\ 2 & 1 & 4 & 2 \\ 0 & 9 & 0 & 3 \\ 6 & 3 & 2 & 1 \end{bmatrix} .

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.

Wikibooks

All three notions of matrix multiplication are associative:

\ \mathbf{A} ( \mathbf{B C} ) = ( \mathbf{A B} ) \mathbf{C}

and distributive:

\ \mathbf{A} ( \mathbf{B} + \mathbf{C} ) = \mathbf{A B} + \mathbf{AC}

and

\ ( \mathbf{A} + \mathbf{B} ) \mathbf{C} = \mathbf{A C} + \mathbf{B C}.

and compatible with scalar multiplication:

\ c ( \mathbf{A B} ) = ( c \mathbf{A} ) \mathbf{B}
\ ( \mathbf{A} c ) \mathbf{B} = \mathbf{A} ( c \mathbf{B} )
\ ( \mathbf{A B} ) c = \mathbf{A} ( \mathbf{B} c )

Note that these three separate couples of expressions will be equal to each other only if the multiplication and addition on the scalar field are commutative, i.e. the scalar field is a commutative ring. See Scalar multiplication above for a counter-example such as the scalar field of quaternions.

The Frobenius inner product, sometimes denoted A:B is the component-wise inner product of two matrices as though they are vectors. In other words, it is the sum of the entries of the Hadamard product, that is,

\mathbf{A}:\mathbf{B}=\sum_i\sum_j A_{ij} B_{ij} = \operatorname{trace}(\mathbf{A}^T \mathbf{B}) = \operatorname{trace}(\mathbf{A} \mathbf{B}^T).

This inner product induces the Frobenius norm.

  • Henry Cohn, Robert Kleinberg, Balazs Szegedy, and Chris Umans. Group-theoretic Algorithms for Matrix Multiplication. arXiv:math.GR/0511460. Proceedings of the 46th Annual Symposium on Foundations of Computer Science, 23-25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379–388.
  • Henry Cohn, Chris Umans. A Group-theoretic Approach to Fast Matrix Multiplication. arXiv:math.GR/0307321. Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 11-14 October 2003, Cambridge, MA, IEEE Computer Society, pp. 438–449.
  • Coppersmith, D., Winograd S., Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9, p. 251-280, 1990.
  • Horn, Roger; Johnson, Charles: "Topics in Matrix Analysis", Cambridge, 1994.
  • R. Raz. On the complexity of matrix product. In Proceedings of the thirty-fourth annual ACM symposium on Theory of computing. ACM Press, 2002.
  • Robinson, Sara, Toward an Optimal Algorithm for Matrix Multiplication, SIAM News 38(9), November 2005. PDF
  • Strassen, Volker, Gaussian Elimination is not Optimal, Numer. Math. 13, p. 354-356, 1969.
  • Knuth, D.E., The Art of Computer Programming Volume 2: Seminumerical Algorithms. Third Edition, 1998. pp 501.
  1. ^ Matrix Multiplication

Retrieved from "http://en.wikipedia.org/wiki/Matrix_multiplication"
Advanced Search
Included Web Search Engines


Safe Search

close

Top Matching Results

Occasionally Search.com will highlight specialized results that are based on the context of your query. Examples of specialized results include specific links to news, images, or video.

Top Matching Results may highlight information from other Search.com pages, content from the CNET Network of sites, or third party content. The listings are based purely on relevance. Search.com does not receive payment for listings in this section but our partners that provide this data may get paid for listing these products.

Sponsored Links

This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.

Search Results

Search.com sends your search query to several search engines at one time and integrates the results into one list which has been sorted by relevance using Search.com's proprietary algorithm. You can customize the list of search engines included in your metasearch from the preferences.

The search engines that are used in your metasearch may allow companies to pay to have their Web sites included within the results. To view the Paid Inclusion policy for a specific search engine, please visit their Web site. Search.com does not accept payment or share revenue with any search engine partner for listings in this section.