## Maths for apps problems class

### Maths for Applications Problem Class (27th September 2002)

#### Theorems

I didn’t quite understand this part of the lecture as we arrived late. These are the notes copied from the board.

- The elementary transformations (elementary row operations) are reversible
- The elementary transformations leave the solution set invariant

#### Proof of 2

If S is a system of equations, let Sol(S) be the set of solutions. Suppose S_{1} => S_{2} by one elementary transformation and α ∈ Sol(S_{1}). Thanks to the rule of interchange that states that two equations (or rows of the matrix) can be exchanged α ∈ Sol(S_{2})

E_{i} := CE_{i}, C != 0 then α ∈ Sol(S_{2})

If S_{1} => S_{2} by E_{i} := E_{i} + CE_{j} then α ∈ Sol(S_{2})

In all cases we have α ∈ Sol(S_{1}) -> α ∈ Sol(S_{2})

Thus we get Sol(S_{1}) c Sol(S_{2})

By part 1, S_{2} => S_{1} thus Sol(S_{1}) c Sol(S_{2})

#### Solving systems of linear equations

Systems of linear equations can be solved by creating an augmented matrix to represent the system and manipulating it using elementary row operations. The method described here is called Gauss Jordan Elimination.

Augmented Matrix x_{1}+ x_{2}+ x_{3}= 2 [ 1 1 1 2 ] 2x_{1}+ 3x_{2}+ x_{3}= 3 [ 2 3 1 3 ] x_{1}- x_{2}- 2_{3}= 6 [ 1 -1 -2 6 ]

The basic idea here is to use E_{1} (equation 1) to eliminate x_{1} from E_{2} and E_{3}, then use E_{2} to eliminate x_{2} from E_{1} and E_{3}.

First we take twice the first row away from the second, then take the first row away from the third.

[ 1 1 1 2 ] [ 1 1 1 2 ] [ 2 3 1 3 ] =>* [ 0 1 -1 -1 ] row 2 := row 2 - 2 x row 1 [ 1 -1 -2 6 ] [ 0 -2 -3 4 ] row 3 := row 2 - row 1

We have carried out two row operations and eliminated x_{1} from rows 2 and 3. We will now repeat this process but with the aim of eliminating x_{2} from all but row 2.

[ 1 1 1 2 ] [ 1 0 2 3 ] row 1 := row 1 - row 2 [ 0 1 -1 -1 ] => [ 0 1 -1 -1 ] [ 0 -2 -3 4 ] [ 0 0 -5 2 ] row 3 := row 2 + 2 x row 2

The next step is to change the -5 in to a 1 using row 3 := row 3 / -5

[ 1 0 2 3 ] [ 1 0 2 3 ] [ 0 1 -1 -1 ] => [ 0 1 -1 -1 ] [ 0 0 -5 2 ] [ 0 0 1 -2/5 ]

Now we clean up the third column with another pair of row operations:

[ 1 0 2 3 ] [ 1 0 0 19/5 ] row 1 := row 1 - 2 x row 3 [ 0 1 -1 -1 ] =>* [ 0 1 0 -7/5 ] row 2 := row 2 + row 3 [ 0 0 1 -2/5 ] [ 0 0 1 -2/5 ]

Note that this final matrix has the identity matrix on the right. This matrix is in *Reduced Echelon Form*. The presence of the identity matrix shows us that there is a single unique solution to the system of equations. We can read the results off by looking at the columns and rows (remember that the first column is x_{1}, the second is x_{2} and the third is x_{3}. From this we can deduce the following results:

x_{1}= 19/5 x_{2}= -7/5 x_{3}= -2/5

The system of equations:

a_{11}x_{1}+ ... + a_{1m}x_{m}= b_{1}. . . a_{n1}x_{n}+ ... + a_{nm}x_{m}= b_{n}

has a coefficient matrix like this:

[ a_{11}... a_{1m}] [ a_{11}... a_{1m}b_{1}] [ . ] and an augmented [ . ] [ . ] matrix like this [ . ] [ . ] [ . ] [ a_{n1}... a_{nm}] [ a_{n1}... a_{nm}b_{n}]

A matrix is in Reduced Echelon Form if:

- Any rows consisting entirely of zeros are grouped at the bottom of the matrix.
- The first non-zero element of any row is a 1 (apart from all-zero rows). This element is called a Leading 1.
- The leading 1 of each row after the first is to the right of the leading 1 of the previous row (this is the
*echelon*part of the name). - All other elements in a column that contains a leading 1 are 0 (this is the
*reduced*idea).

#### Example Matrices

The following matrices are not in reduced echelon form:

[ 2 0 0 1 ] [ 0 0 0 ] [ 0 1 0 ] [ 0 1 0 0 ] [ 1 0 0 ] [ 1 0 0 ] [ 0 0 0 0 ]

These matrices *are* in reduced echelon form:

a) [ 1 0 0 ] b) [ 0 1 0 0 ] c) [ 1 0 0 0 ] [ 0 0 1 ] [ 0 0 1 2 ] [ 0 0 1 0 ] [ 0 0 0 ] [ 0 0 0 1 ] d) [ 1 0 0 0 ] e) [ 1 0 8 ] [ 0 0 1 0 ] [ 0 1 12 ] [ 0 0 0 1 ]

It is *easy* to solve a system of equations if its augmented matrix is in reduced echelon form. Here’s how to do it with the labelled examples above:

a) x_{1}+ 0x_{2}= 0 0x_{1}+ 0x_{2}= 1 0 != 1 so this system has no solution b) x_{2}= 0 x_{3}= 2 x_{1}= anything so this system has many solutions c) The leading 1 in the last column shows this system has no solutions d) The same as (c) e) x_{1}= 8 x_{2}= 12 The identity matrix on the left shows this is a unique solution

## More recent articles

- Understanding GPT tokenizers - 8th June 2023
- Weeknotes: Parquet in Datasette Lite, various talks, more LLM hacking - 4th June 2023
- It's infuriatingly hard to understand how closed models train on their input - 4th June 2023
- ChatGPT should include inline tips - 30th May 2023
- Lawyer cites fake cases invented by ChatGPT, judge is not amused - 27th May 2023
- llm, ttok and strip-tags - CLI tools for working with ChatGPT and other LLMs - 18th May 2023
- Delimiters won't save you from prompt injection - 11th May 2023
- Weeknotes: sqlite-utils 3.31, download-esm, Python in a sandbox - 10th May 2023
- Leaked Google document: "We Have No Moat, And Neither Does OpenAI" - 4th May 2023
- Midjourney 5.1 - 4th May 2023