Friday, March 23, 2007

Matrix Multiplication

Matrix multiplication can be best understood by understanding how matrices relate to a system of linear equations.

A system of linear of equations is a set of n equations with n variables where the goal is to solve each of the equations. For example, if we had three unknowns: x,y,z, a system of linear equations could consist of the following:

x + 3y - z = 4

3x + 2y - 5z = -2

2x - y + 3z = 8

The first step in moving to matrices is the idea of thinking of each unknown as an element of the same type. From this perspective, rather than thinking of them as x,y, and z, we can just as easily think of them as x1, x2, and x3.

This has the advantage that we could now have 27 unknowns without running out of letters. So, with the new form, the 3 equations become:

x1 + 3x2 - x3 = 4

3x1 + 2x2 - 5x3 = -2

2x1 - x2 + 3x3 = 8

The second step is to separate the values x1, x2, x3 from their coefficients.

This is where matrices come in. It would be really nice for example, if matrix multiplication were defined in such a way that we could think of the above systems of equations as a multplication between two matrices. That is:

Indeed, this is exactly the case. Matrix multiplication is defined so that the coefficients of the system of linear equations can be easily abstracted from the unknowns.

Definition 1: Matrix Multiplication

If A is an m x n matrix and B is an n x p matrix, then C = AB is an m x p matrix where

That is:

ci,j = ai,1*b1,j + ai,2*b2,j + ... + ai,n*bn,j for all i in (1 .. m) and for all j in (1 .. p).

In other words, each element is the sum of the multiplication of each element in a column for A with each element in a row for B. If the first row for A = [1, 1, 1] and the first column of B = [1, 2, 3] then the first element of C = (1*1 + 1*2 + 1*3) = 6 (see the example below).

Matrix multiplication is only defined for the case where the number of columns of the first matrix is equal to the number of rows of the second.

By this definition, it should be clear that while AB may be a meaningful matrix product, BA may very well not be allowed. For example, it is fine to multiply a 2 x 3 matrix with a 3 x 1 matrix. It is not allowed to multiply a 3 x 1 matrix with a 2 x 3 matrix since the number of columns in a 3 x 1 does not match the number of rows in the 2 x 3 one.

Here is an example of multiplying a 2 x 3 matrix with a 3 x 2 matrix to get a 2 x 2 matrix:

References
• Gareth Williams, , Wm. C. Brown Publishers, 1996.