Simon Willison’s Weblog

Applications

1st October 2002

Applications

Example 1: Traffic Flow

                         20
                _ B <---------
                /| \
           x1  /    \ x2
   10         /      \|     70
----------> A          C -------->
             |\       /
           x4  \     / x3
                \  |/
                  D
                  ^
                  |
                  | 40

The above (badly drawn) ASCII diagram shows a traffic system. Traffic flows from A to B to C to D and back to A again, with new items flowing in to A, B and D at 10, 20 and 40 items per timeunit respectively. Items flow out of the system at point C at the rate of 70 items per timeunit. We assume that the flow in to each of the nodes on the system is equal to the flow out of that node.

This gives rise to the following equations, which can then be rearranged to form a matrix:

A: 10 + x4 - x1 = 0
B: x1 + 20 - x2 = 0
C: x2 - 70 - x3 = 0
D: x3 + 40 - x4 = 0

[ -1   0   0   1  -10 ]
[  1  -1   0   0  -20 ]
[  0   1  -1   0   70 ]
[  0   0   1  -1  -40 ]

We can now use Gauss-Jordan elimination to reduce the above matrix to reduced echelon form and read off the results:

[ 1   0   0  -1   10 ]  x1 = x4 + 10
[ 0   1   0  -1   30 ]  x2 = x4 + 30
[ 0   0   1  -1  -40 ]  x3 = x4 - 40
[ 0   0   0   0    0 ]  x4 = anything

Note that while x₄ can be anything, if we take the one way system in the original diagram in to account we must add an additional constraint stating x₄ ≥ 40

Example 2: Curve Fitting

This will be part of our first piece of Maple coursework.

A polynomial in x of degree n is an expression of the form:

P(x) = a0 + a1x + a2x2 + ... + anxn with a ≠ 0

a₀ ... a_n are coefficients. There are n+1 coefficients for a polynomial of degree n.

Problem

Given n pairs of numbers [x₁, y₁], ... , [x_n, y_n] find the polynomial of degree n-1 that passes exactly through those points. This is useful for plotting graphs.

Solution

Regard the coefficients as unknowns. We have n equations:

a0 + a1x1 + a2x12 + ... + an-1x1n-1 = y1
 ...
a0 + a1xn + a2xn2 + ... + an-1xnn-1 = yn

In matrix form:

[ 1   x1   x12  ...  x1n-1   a0   ] [ a0   ]
[  ...                            ] [ ..   ]
[ 1   xn   xn2  ...  xnn-1   an-1 ] [ an-1 ]

Example

P(1) = 3, P(5) = -2, P(8) = 10

3 points, so polynomial has degree 2:

P(x) = a0 + a1x + a2x2

P(1) = 3  : a0 +  a1 +   a2 = 3
P(5) = -2 : a0 + 5a1 + 25a2 = -2
P(8) = 10 : a0 + 8a1 + 64a2 = 10

3 equations and 3 unknowns, so we can now solve it using Gauss-Jordan elimination.

Matrix Arithmetic

Let ƒ be some field (as defined here). Assume that our matrices have elements in ƒ, meaning we know how to do simple arithmetic on the elements within the matrices.

Addition

Let A and B be two n x m matricies (i.e they have identical dimensions). The notation we will use is:

A = (aij)n x m
B = (bij)n x m

So a_ij means the element at (i, j) in matrix A, and b_ij means the same but for matrix B.

A + B = (aij + bij)n x m

Addition is not defined for matrices of different sizes. Subtraction is identical to addition, but with the—operator instead of the +.

[ 0   1   2 ]   [ 0   0   1 ]   [ 0   1   3 ]
[ 3   4   1 ] + [ 1   1   2 ] = [ 4   5   3 ]

Scalar Multiplication

We will refer to elements of ƒ as scalars. Let c be a scalar and A = (a_ij)_{n x m} be a matrix. Scalar multiplication is defined thus:

cA = (cAij)n x m

e.g
 [ 1   0 ]   [ 2   0 ]
2[ 5   1 ] = [ 10  2 ]

Matrix Multiplication

A = (aij)n x k
B = (bij)k x m

The number of columns in matrix A is equal to the number of rows in matrix B—this is required in order to perform matrix multiplication. AB (the product of the two matrices) will be an nxm matrix where:

      k
Cij = Σ   aiρbρj
      ρ=1

For example:

    [ 1   2   3 ]
A = [ 0   1   1 ]

    [ 1   0 ]
B = [ 0   1 ]
    [ 1   1 ]

AB = [ 1x1 + 2x0 + 3x1   0x1 + 2x1 + 3x1 ] = [ 4   5 ]
     [ 0x1 + 1x0 + 1x1   0x1 + 1x1 + 1x1 ] = [ 1   2 ]

Note that AB ≠ BA but both can be calculated.

The following matrix demonstrates how 2 x 2 matrix multiplication works:

[ a11   a12 ]   [ b11   b12 ]
[ a21   a22 ] x [ b21   b22 ]

 =

[ a11b11 + a12b21   a11b12 + a12b22 ]
[ a21b11 + a22b21   a21b12 + a22b22 ]