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 S1 => S2 by one elementary transformation and α ∈ Sol(S1). Thanks to the rule of interchange that states that two equations (or rows of the matrix) can be exchanged α ∈ Sol(S2)
Ei := CEi, C != 0 then α ∈ Sol(S2)
If S1 => S2 by Ei := Ei + CEj then α ∈ Sol(S2)
In all cases we have α ∈ Sol(S1) -> α ∈ Sol(S2)
Thus we get Sol(S1) c Sol(S2)
By part 1, S2 => S1 thus Sol(S1) c Sol(S2)
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 x1 + x2 + x3 = 2 [ 1 1 1 2 ] 2x1 + 3x2 + x3 = 3 [ 2 3 1 3 ] x1 - x2 - 23 = 6 [ 1 -1 -2 6 ]
The basic idea here is to use E1 (equation 1) to eliminate x1 from E2 and E3, then use E2 to eliminate x2 from E1 and E3.
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 x1 from rows 2 and 3. We will now repeat this process but with the aim of eliminating x2 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 x1, the second is x2 and the third is x3. From this we can deduce the following results:
x1 = 19/5 x2 = -7/5 x3 = -2/5
The system of equations:
a11x1 + ... + a1mxm = b1 . . . an1xn + ... + anmxm = bn
has a coefficient matrix like this:
[ a11 ... a1m ] [ a11 ... a1m b1 ] [ . ] and an augmented [ . ] [ . ] matrix like this [ . ] [ . ] [ . ] [ an1 ... anm ] [ an1 ... anm bn ]
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) x1 + 0x2 = 0 0x1 + 0x2 = 1 0 != 1 so this system has no solution b) x2 = 0 x3 = 2 x1 = 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) x1 = 8 x2 = 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