## Applications

1st October 2002

### Applications

#### Example 1: Traffic Flow

20 _ B <--------- /| \ x_{1}/ \ x_{2}10 / \| 70 ----------> A C --------> |\ / x_{4}\ / x_{3}\ |/ 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 + x_{4}- x_{1}= 0 B: x_{1}+ 20 - x_{2}= 0 C: x_{2}- 70 - x_{3}= 0 D: x_{3}+ 40 - x_{4}= 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 ] x_{1}= x_{4}+ 10 [ 0 1 0 -1 30 ] x_{2}= x_{4}+ 30 [ 0 0 1 -1 -40 ] x_{3}= x_{4}- 40 [ 0 0 0 0 0 ] x_{4}= anything

Note that while x_{4} 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_{4} ≥ 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) = a_{0}+ a_{1}x + a_{2}x^{2}+ ... + a_{n}x^{n}with a ≠ 0

a_{0} ... a_{n} are coefficients. There are n+1 coefficients for a polynomial of degree n.

#### Problem

Given n pairs of numbers [x_{1}, y_{1}], ... , [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:

a_{0}+ a_{1}x_{1}+ a_{2}x_{1}^{2}+ ... + a_{n-1}x_{1}^{n-1}= y_{1}... a_{0}+ a_{1}x_{n}+ a_{2}x_{n}^{2}+ ... + a_{n-1}x_{n}^{n-1}= y_{n}In matrix form: [ 1 x_{1}x_{1}^{2}... x_{1}^{n-1}a_{0 }] [ a_{0 }] [ ..._{ }] [ .._{ }] [ 1 x_{n}x_{n}^{2}... x_{n}^{n-1}a_{n-1}] [ a_{n-1}]

#### Example

P(1) = 3, P(5) = -2, P(8) = 10 3 points, so polynomial has degree 2: P(x) = a_{0}+ a_{1}x + a_{2}x^{2}P(1) = 3 : a_{0}+ a_{1}+ a_{2}= 3 P(5) = -2 : a_{0}+ 5a_{1}+ 25a_{2}= -2 P(8) = 10 : a_{0}+ 8a_{1}+ 64a_{2}= 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 = (a_{ij})_{n x m}B = (b_{ij})_{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 = (a_{ij}+ b_{ij})_{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 = (cA_{ij})_{n x m}e.g [ 1 0 ] [ 2 0 ] 2[ 5 1 ] = [ 10 2 ]

#### Matrix Multiplication

A = (a_{ij})_{n x k}B = (b_{ij})_{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 C_{ij}= Σ a_{iρ}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:

[ a_{11}a_{12}] [ b_{11}b_{12}] [ a_{21}a_{22}] x [ b_{21}b_{22}] = [ a_{11}b_{11}+ a_{12}b_{21}a_{11}b_{12}+ a_{12}b_{22}] [ a_{21}b_{11}+ a_{22}b_{21}a_{21}b_{12}+ a_{22}b_{22}]

## More recent articles

- Weeknotes: GPT-4o mini, LLM 0.15, sqlite-utils 3.37 and building a staging environment - 19th July 2024
- Imitation Intelligence, my keynote for PyCon US 2024 - 14th July 2024
- Give people something to link to so they can talk about your features and ideas - 13th July 2024
- Weeknotes: a livestream, a surprise keynote and progress on Datasette Cloud billing - 2nd July 2024
- Open challenges for AI engineering - 27th June 2024
- Building search-based RAG using Claude, Datasette and Val Town - 21st June 2024
- Weeknotes: Datasette Studio and a whole lot of blogging - 19th June 2024
- Language models on the command-line - 17th June 2024
- A homepage redesign for my blog's 22nd birthday - 12th June 2024
- Thoughts on the WWDC 2024 keynote on Apple Intelligence - 10th June 2024