Matrix Multiplication Article Index for
Matrix 		Shopping
Multiplication 		Website Links For
Matrix 		 

Information About

Matrix Multiplication
  CATEGORIES ABOUT MATRIX MULTIPLICATION
   
matrix theory
   
binary operations
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...





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

: (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 Unit s" summarises the abstract properties of this kind of multiplication.


Calculating directly from the definition


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.

:(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}

:(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}



The coefficients-vectors method


This matrix multiplication can also be considered from a slightly different viewpoint: it adds Vector s together after being multiplied by different Coefficients . If A and '''B''' are matricies given by:

: \mathbf{A} =

\begin{bmatrix}
a_{1,1} & a_{1,2} & \dots \
a_{2,1} & a_{2,2} & \dots \
dots & dots & \ddots
\end{bmatrix}

and \mathbf{B} =

\begin{bmatrix}
b_{1,1} & b_{1,2} & \dots \
b_{2,1} & b_{2,2} & \dots \
dots & dots & \ddots
\end{bmatrix}



then

:
\mathbf{AB}
=
\begin{bmatrix}
a_{1,1} \begin{bmatrix} b_{1,1} & b_{1,2} & \dots \end{bmatrix} + a_{1,2} \begin{bmatrix} b_{2,1} & b_{2,2} & \dots \end{bmatrix} + \cdots \\
a_{2,1} \begin{bmatrix} b_{1,1} & b_{1,2} & \dots \end{bmatrix} + a_{2,2} \begin{bmatrix} b_{2,1} & b_{2,2} & \dots \end{bmatrix} + \cdots \
dots
\end{bmatrix}



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 \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 is the list of coefficients. The matrix on the right is the list of vectors. In the example, the first row is {Link without Title} , and thus we take 1 times the first vector, 0 times the second vector, and 2 times the third vector.


Vector-lists method


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 matricies 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 \
dots & dots & dots & \ddots
\end{bmatrix}
=
\begin{bmatrix}
A_1 \
A_2 \
A_3 \
dots
\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 \
dots & dots & dots & \ddots
\end{bmatrix}
=
\begin{bmatrix} B_1 & B_2 & B_3 & \dots
\end{bmatrix}



where
A

: and ''B''1 is the vector of all elements of the form ''b''''x'',1      ''B''2 is the vector of all elements of the form ''b''''x'',2     etc,

then

:
\mathbf{AB} =

\begin{bmatrix}
A_1 \
A_2 \
A_3 \
dots
\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 \
dots & dots & dots & \ddots

\end{bmatrix}



Properties

Matrix multiplication is not Commutative (that is, ''AB'' ≠ ''BA''), except in special cases. It's easy to see why: you can't expect to switch the proportions with the vectors and get the same result. It's 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 Determinant s 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.

This notion of multiplication is important because if ''A'' and ''B'' are interpreted as Linear Transformation s (which is almost universally done), then the matrix product ''AB'' corresponds to the composition of the two linear transformations, with ''B'' being applied first.


Algorithms


The Complexity of matrix multiplication, if carried out naively, is ''O'' (''n''3), 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''log2(7)) = ''O''(''n''2.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''(''n''2.376). It is based on a similar trick as Strassen's algorithm: a clever way is devised for multiplying two ''k'' × ''k'' matrices with less than ''k''3 multiplications, and this technique is applied recursively.

Since any algorithm for multiplying two ''n'' × ''n'' matrices has to process all ''n''2 entries, it cannot run faster than ''O''(''n''2). Most researchers believe that an optimal algorithm will run in essentially ''O''(''n''2) time (Robinson, 2005).


SCALAR MULTIPLICATION


The scalar multiplication of a matrix ''A'' = (''a''''ij'') and a scalar ''r'' gives a product ''rA'' of the same size as ''A''. The entries of ''rA'' are given by
: (rA)_{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
: (Ar)_{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 Quaternion s, they may be different. For example
:
i\begin{bmatrix}
i & 0 \
0 & j \
\end{bmatrix}
= \begin{bmatrix}
-1 & 0 \
0 & k \
\end{bmatrix}

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



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'')''ij'' = ''a''''ij''''b''''ij''. For instance

:
\begin{bmatrix}
1 & 3 & 2 \
1 & 0 & 0 \
1 & 2 & 2
\end{bmatrix}
\bullet
\begin{bmatrix}
0 & 0 & 2 \
7 & 5 & 0 \
2 & 1 & 1
\end{bmatrix}
=
\begin{bmatrix}
1 \cdot 0 & 3 \cdot 0 & 2 \cdot 2 \
1 \cdot 7 & 0 \cdot 5 & 0 \cdot 0 \
1 \cdot 2 & 2 \cdot 1 & 2 \cdot 1
\end{bmatrix}
=
\begin{bmatrix}
0 & 0 & 4 \
7 & 0 & 0 \
2 & 2 & 2
\end{bmatrix}


Note that the Hadamard product is a Submatrix of the Kronecker product (see below). The Hadamard product is studied by matrix theorists, but it is virtually untouched by linear algebraists. It is discussed in (Horn & Johnson, 1994, Ch. 5).


KRONECKER PRODUCT

''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 \
dots & dots & \ddots & dots \
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 ''V''1 → ''W''1 and ''V''2 → ''W''2, respectively, then ''A'' ''B'' represents the Tensor Product of the two maps, ''V''1 ''V''2 → ''W''1 ''W''2.


COMMON PROPERTIES


All three notions of matrix multiplication are Associative :

A

and Distributive :
A

and
:(''A'' + ''B'')''C'' = ''AC'' + ''BC''
and compatible with scalar multiplication:
c



SEE ALSO



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.

  • Horn, Roger; Johnson, Charles: "Topics in Matrix Analysis", Cambridge, 1994.

  • Robinson, Sarah, ''Toward an Optimal Algorithm for Matrix Multiplication,'' SIAM News 38(9), November 2005.