Our aim is not to compete with the numerous books that cover this basic material. If you are really not familiar with
the subject we suggest that you consult a book on this subject for more details.
SCENE 1: A luxury hotel in Melbourne.
|
"Hello Jim! So, the rumours of the retirement
of the famous Linear spy, Jim Bonza, are not true eh?"
"Maximus? Maximus Bond? Have a martini, Max? Shaken,
not ......."
.....some time later:
" Have you got the details of the secret meeting Jim?"
"Well Max, I haven't finished decoding the message yet, but
I've got it down to some simple systems of linear equations.
You'll be able to finish it off. I think z gives the date
and you may need to use 1 is code for a, 2 for b and so
on."
"Ah Ha, the old 1 is code for a, 2 for b and so on trick,
eh? No problem at all Jim. Nice to visit you again in good old
Melbourne, I hear its a great place to live."
|
|
SCENE 2: Back at Linear Spy headquarters:
|
"Ninetypenny, Ninetypenny, I can hardly remember what an
equation is, what are systems and how do I solve them?"
"Don't worry Max, its easy. Read this quick summary of the
main ideas and how I solve them."
And she pivoted out of the room.
|
FUNDAMENTAL IDEAS
A SYSTEM of equations is a set of equations that we want to
solve simultaneously. The following is an example of a system of linear
equations:
| x1 | + | 2 x2 | + |
4 x3 | = | 12 |
| 2 x1 | - | 3 x2 | +
|
x3 | = | 10 |
| x1 | - | 2 x2 | - |
3 x3 | = | -5 |
|
To solve the system means to find ALL possible solutions to
the system. A SOLUTION to the system is a set of values of the
variables such that all equations of the system are satisfied by
that set of values.
e.g. If we substitute x1 = 2, x2 = -1,
x3 = 3 into each equation of the system above,
we see that each equation is satisfied. So x1 = 2, x2
= -1,
x3 = 3 is a solution of this system.
As we shall see later, no matter how many variables or how
many equations we have (even if the number of variables is
different from the number of equations), there are three
things that can happen. There may be
- EXACTLY ONE SOLUTION to the system
- NO SOLUTIONS to the system
- INFINITELY MANY SOLUTIONS to the system.
A system of equations is called CONSISTENT if it has one or more solutions and INCONSISTENT otherwise.
SOLVING SYSTEMS OF EQUATIONS
One way of solving systems of equations is to successively
produce new systems that have the same solution as the
original system, that is we produce EQUIVALENT SYSTEMS.
Our aim is to create a system where it is easy to see
the solution.
We can produce equivalent systems by using the following familiar
operations:
- Interchange two equations.
- Multiply an equation by a non-zero constant.
- Add a multiple of one equation to another equation.
We will now introduce a streamlined, systematic method for doing this
using row operations.
If you have not already done so you should look at the
Row Operations page for information on the
Dream Team.
We can solve any system of linear equations using these row
operations and the method that we now describe can be applied to
any size system.
Scene: Still at Linear Spy headquarters:
|
"How are you finding it so far Max?"
"Reading it ANNNND loving it Ninetypenny. "
"Well keep going Max."
|
STREAMLINING THE PROCESS
SHORTHAND NOTATION
To help streamline the process, instead of writing all the
equations in detail we simply write the coefficients in a matrix
array. For example
| x1 | + | 2 x2 | + |
4 x3 | = | 12 |
| 2 x1 | - | 3 x2 | +
|
x3 | = | 10 |
| x1 | - | 2 x2 | - |
3 x3 | = | -5 |
|
is written as
| 1 | 2 | 4 | |
| 12 |
| 2 | -3 | 1 | |
| 10 |
| 1 | - 2 | -3 | | | -5 |
|
This is called an augmented matrix. You must be careful to keep
the coefficients in their correct columns. The first column gives the
coefficients of x1, the second column gives the coefficients
of x2
and so on.
Augmented matrices are called ROW EQUIVALENT if they are
augmented matrices of equivalent systems. We use the symbol ~. Row
equivalent matrices are obtained only by using row operations.
So for our earlier example we can, for instance add -2 times row 1 to
row 2,
and add -1 times row 1 to row 3. This gives the equivalent augmented
matrix:
| 1 | 2 | 4 | |
| 12 |
| 0 | -7 | -7 | | | -14 |
| 0 | -4 | -7 | | | -17 |
|
It should be emphasised that these matrices are NOT equal, just
row equivalent.
OPERATIONS
Operations that we are used to using with equations translate as
follows:
- Interchange two equations:
Interchange two rows (Changy). Ri <=> Rj
means interchange row i and row j.
- Multiply an equation by a non-zero constant:
Multiply a row by a non-zero constant (Timy). Rj' = a
Rj means multiply row j by a to give a new row j.
- Add a multiple of one equation to another equation:
Add a multiple of one row to another row (Addy). Ri' =
Ri + a Rj means add a times row j to row i to
give a new row i.
THE PROCESS : GAUSS-JORDAN ELIMINATION
We work systematically on the columns from left to right to try and
get as close as we can to an identity matrix (with the same number of
rows as we have equations in the system) in the left hand section
of the augmented matrix.
For a fuller explanation of why this process works refer to an
elementary linear algebra text book.
Now we'll do the example above using the new notation, showing
how we set it out. Notice that the row operation used to go from one augmented
matrix to the next equivalent augmented matrix is always stated on the right,
next to the row that will be changed by that operation.
| |
| 1 | 2 | 4 | |
| 12 |
| 2 | -3 | 1 | |
| 10 |
| 1 | -2 | -3 | | | -5 |
| |
| ...... |
| R2'= R2 + (-2)R1 |
| R3'= R3 + (-1)R1 |
|
| ~ |
| 1 | 2 | 4 | |
| 12 |
| 0 | -7 | -7 | | | -14 |
| 0 | -4 | -7 | | | -17 |
| |
| ...... |
| R2'= (-1/7)R2 |
| ...... |
|
| ~ |
| 1 | 2 | 4 | |
| 12 |
| 0 | 1 | 1 | |
| 2 |
| 0 | -4 | -7 | | | -17 |
| |
| R1'= R1 + (-2)R2 |
| ...... |
| R3'= R3 + 4R2 |
|
| ~ |
| 1 | 0 | 2 | |
| 8 |
| 0 | 1 | 1 | |
| 2 |
| 0 | 0 | -3 | |
| -9 |
| |
| ...... |
| ...... |
| R3'= (-1/3)R3 |
|
| ~ |
| 1 | 0 | 2 | |
| 8 |
| 0 | 1 | 1 | |
| 2 |
| 0 | 0 | 1 | |
| 3 |
| |
| R1'= R1 + (-2)R3 |
| R2'= R2 + (-1)R3 |
| ...... |
|
| ~ |
| 1 | 0 | 0 | |
| 2 |
| 0 | 1 | 0 | |
| -1 |
| 0 | 0 | 1 | |
| 3 |
|
|
We have finished reducing the augmented matrix. Now we translate back
into equations. The first row of the matrix represents the equation x1 = 2.
The second row of the matrix represents the equation x2 = -1.
The third row of the matrix represents the equation x3 = 3, and
we have the solution, as verified earlier.
THINGS TO NOTE
- This method is called GAUSS-JORDAN ELIMINATION.
- The process of applying row operations to get equivalent augmented
matrices is called row reduction.
- This same basic idea can be used no matter how many equations and how
many variables we have, we just need to learn how to interpret some different cases.
- Notice that our friend Pivorrratti (in charge of pivoting) could have joined in too here.
See the discussion on the Dream Team if you are not familiar with this operation. In this case the solution
would be as follows:
| |
| 1 | 2 | 4 | |
| 12 |
| 2 | -3 | 1 | |
| 10 |
| 1 | -2 | -3 | | | -5 |
| |
| Pivot (1, 1) |
| ...... |
| ...... |
|
| ~ |
| 1 | 2 | 4 | |
| 12 |
| 0 | -7 | -7 | | | -14 |
| 0 | -4 | -7 | | | -17 |
| |
| ...... |
| Pivot (2, 2) |
| ...... |
|
| ~ |
| 1 | 0 | 2 | |
| 8 |
| 0 | 1 | 1 | |
| 2 |
| 0 | 0 | -3 | |
| -9 |
| |
| ...... |
| ...... |
| Pivot (3, 3) |
|
| ~ |
| 1 | 0 | 0 | |
| 2 |
| 0 | 1 | 0 | |
| -1 |
| 0 | 0 | 1 | |
| 3 |
|
|
VARIATIONS ON THE THEME
|
"My head is spinning Ninetypenny, but I think I know what is going on.
Just don't tell me there is more to it."
"I will give you an example to do Max, and we will discuss what happens
here. There is a little more to it."
"I asked you not to tell me that!"
Ninetypenny's Example for Max:
Find all solutions of the following system of equations, or explain why
there are no solutions: |
| 2 x1 | - | x2 | + |
x3 | = | 3 |
| x1 | + | | |
x3 | = | 1 |
| x1 | - | 2 x2 | - |
x3 | = | 4 |
|
Max's solution:
| |
| 2 | -1 | 1 | |
| 3 |
| 1 | 0 | 1 | |
| 1 |
| 1 | -2 | -1 | | | 4 |
| |
|
| ~ |
| 1 | 0 | 1 | |
| 1 |
| 2 | -1 | 1 | |
| 3 |
| 1 | -2 | -1 | | | 4 |
| |
| ...... |
| R2'= R2 + (-2)R1 |
| R3'= R3 + (-1)R1 |
|
| ~ |
| 1 | 0 | 1 | |
| 1 |
| 0 | -1 | -1 | | | 1 |
| 0 | -2 | -2 | | | 3 |
| |
| ...... |
| R2'= (-1)R2 |
| ...... |
|
"This is fun Ninetypenny, I like doing this!"
| ~ |
| 1 | 0 | 1 | |
| 1 |
| 0 | 1 | 1 | |
| -1 |
| 0 | -2 | -2 | | | 3 |
| |
| ...... |
| ...... |
| R3'= R3 + 2R2 |
|
| ~ |
| 1 | 0 | 1 | |
| 1 |
| 0 | 1 | 1 | |
| -1 |
| 0 | 0 | 0 | |
| 1 |
|
|
"But I can't go any further, there's no way I can get anything but those
zeros on the bottom, using the valid row operations, unless I mess up what I've already done."
"That's excellent so far Max, but I told you there was a bit more to it.
- You can always convert any augmented matrix back to equations and see
what they tell you.
- The clue here is the bottom row where we have all zeros in the left
section of the matrix.
If we convert this back to an equation it gives
0 x1 + 0 x2 + 0 x3 = 1.
In other words 0 = 1.
- Now we know this is not true, so our original system of equations is
inconsistent, and this system has
no solution."
"That's very Smart Ninetypenny. Can we start doing Jim's message now?"
The first system of equations given to Max by Jim Bonza is:
| w | + | 5 x | + | 5 y |
| | = | 164 |
| -4 w | + | x | | |
| | = | -51 |
| -7 w | + | 7 x | + | 5 y
| | | = | 62 |
| | | | | y | -
| 21 z | = | -17 |
|
"I think there will be some really nasty arithmetic in this Ninetypenny."
"Why don't you use tutOR's Mercyless Equator, Max?"
Max's solution:
| |
| 1 | 5 | 5 | 0 | | | 164 |
| -4 | 1 | 0 | 0 | | | -51 |
| -7 | 7 | 5 | 0 | | | 62 |
| 0 | 0 | 1 | -21 | | | -17 |
| |
| Pivot (1, 1) |
| ...... |
| ...... |
| ...... |
|
| ~ |
| 1 | 5 | 5 | 0 | | | 164 |
| 0 | 21 | 20 | 0 | | | 605 |
| 0 | 42 | 40 | 0 | | | 1210 |
| 0 | 0 | 1 | -21 | | | -17 |
| |
| ...... |
| Pivot (2, 2) |
| ...... |
| ...... |
|
| ~ |
| 1 | 0 | 5 / 21 | 0 | | | 419 / 21 |
| 0 | 1 | 20 / 21 | 0 | | | 605 / 21 |
| 0 | 0 | 0 | 0 | | | 0 |
| 0 | 0 | 1 | -21 | | | -17 |
| |
| ...... |
| ...... |
| R3 <=> R4 |
| ...... |
|
| ~ |
| 1 | 0 | 5 / 21 | 0 | | | 419 / 21 |
| 0 | 1 | 20 / 21 | 0 | | | 605 / 21 |
| 0 | 0 | 1 | -21 | | | -17 |
| 0 | 0 | 0 | 0 | | | 0 |
| |
| ...... |
| ...... |
| Pivot (3, 3) |
| ...... |
|
| ~ |
| 1 | 0 | 0 | 5 | | | 24 |
| 0 | 1 | 0 | 20 | | | 45 |
| 0 | 0 | 1 | -21 | | | -17 |
| 0 | 0 | 0 | 0 | | | 0 |
|
|
Translating back to equations:
| w | + | 5 z | = | 24 |
| x | + | 20 z | = | 45 |
| y | - | 21 z | = | -17 |
| | | 0 | = | 0 |
|
"Here is what I got using the Mercyless Equator place Ninetypenny. As
you can see, I've translated the last augmented matrix back to equations but I still can't see what is going on."
"OK, here's how we reason from here Max."
- The last equation tells us nothing! We can just discard it and
rearrange the remaining three equations:
| w | = | 24 | - | 5 z |
| x | = | 45 | - | 20 z |
| y | = | -17 | + | 21 z |
|
- Now if we think of putting in some real number for z, say we put z = 3,
we'll get the solution
w = 9, x = -15, y = 46, z = 3, which satisfies all the equations of the
original system.
In fact, we can put in ANY REAL NUMBER for z and we'll get a solution.
- Thus we see that in fact this system has an INFINITE NUMBER OF SOLUTIONS.
- Suppose we call the real number that we put in for z, t. We then have
that the solution of the system is
w = 24 - 5t, x = 45 - 20t, y = -17 + 21t, z = t, where t is any real
number.
This tells you how you can generate ALL solutions of the system.
If you want to see more about the particular case of Max's problem from
Jim Bonza read on.
SCENE 3: Max is working feverishly to find out
about the secret meeting.
|
According to Jim Bonza, the solutions need to be translated into letters
of the alphabet according to the code: 1 = a, 2 = b, 3 = c and so on. This means that 0 < w, x, y < = 26, and
that w, x, y must be integers.
So we only want some of the solutions. In particular we only want those
with t = 1 and t = 2, since it turns out that
other values of t will give negative solutions or fractions.
If t = 1, we get w = 19, x = 25, y = 4, z = 1. This translates to SYD, z = 1 (remember Jim thought z gave the date).
If t = 2, we get w = 14, x = 5, y = 25, z = 2. This translates to NEY, z =
2.
So the secret meeting is in SYDNEY on 1st of February or 2nd of January or
...?
Hopefully when Max solves the other systems that Jim gave him, he'll be
able to work it out.
In other modules to do with linear programming, we'll see how these
methods of solving systems of
linear equations can be adapted to problems where instead of = we have < =
or > =, and even to cases where we only
want integer solutions.
|