Simon Willison’s Weblog

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.

1. The elementary transformations (elementary row operations) are reversible
2. 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₁ => S₂ by one elementary transformation and α ∈ Sol(S₁). Thanks to the rule of interchange that states that two equations (or rows of the matrix) can be exchanged α ∈ Sol(S₂)

E_i := CE_i, C != 0 then α ∈ Sol(S₂)

If S₁ => S₂ by E_i := E_i + CE_j then α ∈ Sol(S₂)

In all cases we have α ∈ Sol(S₁) -> α ∈ Sol(S₂)

Thus we get Sol(S₁) c Sol(S₂)

By part 1, S₂ => S₁ thus Sol(S₁) c Sol(S₂)

---

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 E₁ (equation 1) to eliminate x₁ from E₂ and E₃, then use E₂ to eliminate x₂ from E₁ and E₃.

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₁ from rows 2 and 3. We will now repeat this process but with the aim of eliminating x₂ 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₁, the second is x₂ and the third is x₃. 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:

1. Any rows consisting entirely of zeros are grouped at the bottom of the matrix.
2. The first non-zero element of any row is a 1 (apart from all-zero rows). This element is called a Leading 1.
3. 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).
4. 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