Matrix multiplication

This article gives an overview of the various ways to multiply matrices.

Contents

1 Ordinary matrix product 1.1 The proportions-vectors method 2 Hadamard product 3 Kronecker product 4 Common properties 5 Scalar multiplication 6 See also 7 External links 8 References

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 A×B is an m-by-p matrix given by

<math> (A\times B)_{ij} = \sum_{r=1}^n a_{ir}b_{rj} = a_{i1}b_{1j} + a_{i2}b_{2j} + \cdots + a_{in}b_{nj}. <math>

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

The following picture shows how to calculate the (AB)₁₂ element of A×B 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.

<math>(A\times B)_{12} = \sum_{r=1}^4 a_{1r}b_{r2} = a_{11}b_{12}+a_{12}b_{22}+a_{13}b_{32}+a_{14}b_{42}

<math>

The proportions-vectors method

There is a simpler concept for multiplying matrices. Suppose you want to mix vectors together in different proportions. The matrix on the left is the list of proportions. The matrix on the right is the list of vectors. Here's how it works :

<math>

 \begin{bmatrix}
    1 & 0 & 2 \\ 
    -1 & 3 & 1
 \end{bmatrix}

\times

 \begin{bmatrix} 
   3 & 1 \\ 
   2 & 1 \\ 
   1 & 0
 \end{bmatrix}

<math>

Use vector notation :

<math>

= \begin{matrix}

 \begin{bmatrix}
     1 & 0 & 2 \\ 
    -1 & 3 & 1
 \end{bmatrix}
 \begin{matrix}
     (Mix_1) \\
     (Mix_2)
 \end{matrix}
 &
 \times
 &
 \begin{bmatrix} 
   \begin{pmatrix} 3 & 1 \end{pmatrix} \\ 
   \begin{pmatrix} 2 & 1 \end{pmatrix} \\ 
   \begin{pmatrix} 1 & 0 \end{pmatrix}
 \end{bmatrix}
 \begin{matrix}
     (\vec{v_1}) \\
     (\vec{v_2}) \\
     (\vec{v_3})
 \end{matrix}

\end{matrix} <math>

The first proportion in each mix tells how much of the first vector to use and so on :

<math>

= \begin{bmatrix} \;\;1 \cdot \begin{pmatrix} 3 & 1 \end{pmatrix} & + & 0 \cdot \begin{pmatrix} 2 & 1 \end{pmatrix} & + & 2 \cdot \begin{pmatrix} 1 & 0 \end{pmatrix} \\

  -1 \cdot \begin{pmatrix} 3 & 1 \end{pmatrix} & + & 3 \cdot \begin{pmatrix} 2 & 1 \end{pmatrix} & + & 1 \cdot \begin{pmatrix} 1 & 0 \end{pmatrix}

\end{bmatrix} \begin{matrix}

   (Mix_1) \\
   (Mix_2)

\end{matrix} <math>

Simplify :

<math>

= \begin{bmatrix}

   \begin{pmatrix} 5 & 1 \end{pmatrix} \\
   \begin{pmatrix} 4 & 2 \end{pmatrix}

\end{bmatrix} \begin{matrix}

   (Mix_1) \\
   (Mix_2)

\end{matrix} <math>

Remove the vector notation :

<math>

= \begin{bmatrix}

   5 & 1 \\
   4 & 2

\end{bmatrix} <math>

Matrix multiplication is not commutative (A×B = B×A), 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 why 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.

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.

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(n^log₂(7)) (approximately 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 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

<math>

 \begin{bmatrix}
   1 & 3 & 2 \\ 
   1 & 0 & 0 \\ 
   1 & 2 & 2
 \end{bmatrix}

\cdot

 \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}

<math>

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

<math>

 \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}.

<math>

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

<math>

 \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}

<math>.

If A and B represent linear transformations V₁ → W₁ and V₂ → W₂, respectively, then A B represents the tensor product of the two maps, V₁ V₂ → W₁ W₂.

Common properties

All three notions of matrix multiplication are associative

A(BC) = (AB)C

and distributive:

A(B + C) = AB + AC

and

(A + B)C = AC + BC

and compatible with scalar multiplication:

c(AB) = (cA)B = A(cB)

Scalar multiplication

The scalar multiplication of a matrix A=(a_ij) and a scalar r gives the product

rA=(r 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=(a_ij 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

<math>

 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

<math>

See also

• Coppersmith-Winograd algorithm
• Strassen algorithm

External links

• WIMS Online Matrix Multiplier (http://wims.unice.fr/~wims/en_tool~linear~matmult.html)

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.fr:Multiplication des matrices

he:כפל מטריצות nl:Matrixvermenigvuldiging pl:Mnożenie macierzy