## Maths for apps problems class

30th September 2002

### 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

- Weeknotes: datasette-enrichments, datasette-comments, sqlite-chronicle - 8th December 2023
- Datasette Enrichments: a new plugin framework for augmenting your data - 1st December 2023
- llamafile is the new best way to run a LLM on your own computer - 29th November 2023
- Prompt injection explained, November 2023 edition - 27th November 2023
- I'm on the Newsroom Robots podcast, with thoughts on the OpenAI board - 25th November 2023
- Weeknotes: DevDay, GitHub Universe, OpenAI chaos - 22nd November 2023
- Deciphering clues in a news article to understand how it was reported - 22nd November 2023
- Exploring GPTs: ChatGPT in a trench coat? - 15th November 2023
- Financial sustainability for open source projects at GitHub Universe - 10th November 2023
- ospeak: a CLI tool for speaking text in the terminal via OpenAI - 7th November 2023