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

Tuesday, March 20, 2007

Introduction to Matrices

A matrix is a rectangular array of elements; it can be composed from any set of elements arranged evenly into rows and columns. While these elements can themselves be matrices, for purposes of this blog, I will assume that the elements are numbers.

Definitition 1: Matrix

A matrix is an ordering of elements into rows and columns. A matrix M that is an r x c matrix consists of r rows and c columns.

For example, a 2 x 3 matrix contains 6 elements ordered into 2 rows and 3 columns.

I will refer to a matrix as a capital letter and the elements that make up a matrix as a lowercase letter followed by a subscript that specifies row and column.

For example, a 2 x 3 matrix M consists of the following elements: m1,1, m1,2, m1,3, m2,1, m2,2, m2,3 that would look like this:



So that we have, M = [ mi,j ]2 x 3

Definition 2: Matrix Equality

If A is an m x n matrix and B is a p x q matrix, then A = B if and only if m=p and n=q and ai,j = bi,j for all i in (1 .. m) and for all j in (1 .. n).

In other words, two matrices are equal if they consist of the same number of rows and columns and all their elements are equal.

Definition 3: Matrix Addition

If A, B are two matrices of the same dimensions m x n, then the sum C = A + B is given by:

ci,j = ai,j + bi,j for all i in (1 .. m) and all j in (1 .. n)

where C is also an m x n matrix.

For example:



Matrices can be only be added together when they consist of the same number of rows and columns.

Definition 4: Scalar

A scalar is any element of a matrix which is a number.

In this blog, I have made the assumption that all the elements of a matrix are scalar.

I will represent a scalar value as a lowercase letter that does not have a subscript.

Definition 5: Scalar Multiplication

If a is a scalar and B is an m x n matrix, then C = aB is also an m x n matrix such that:

ci,j = a*bi,j for all i in (1..m) and for all j in (1 .. n).

For example:



In my next blog, I will review matrix multiplication.

References