## Systems of Linear Equations |

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.

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 IDEASA 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:

x _{1}+ 2 x _{2}+ 4 x _{3}= 12 2 x _{1}- 3 x _{2}+ x _{3}= 10 x _{1}- 2 x _{2}- 3 x _{3}= -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 x

_{1}= 2, x_{2}= -1, x_{3}= 3 into each equation of the system above, we see that each equation is satisfied. So x_{1}= 2, x_{2}= -1, x_{3}= 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 EQUATIONSOne 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

x _{1}+ 2 x _{2}+ 4 x _{3}= 12 2 x _{1}- 3 x _{2}+ x _{3}= 10 x _{1}- 2 x _{2}- 3 x _{3}= -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 x

_{1}, the second column gives the coefficients of x_{2}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). R_{i}<=> R_{j}means interchange row i and row j.- Multiply an equation by a non-zero constant:

Multiply a row by a non-zero constant (Timy). R_{j}' = a R_{j}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). R_{i}' = R_{i}+ a R_{j}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

...... R _{2}'= R_{2}+ (-2)R_{1}R _{3}'= R_{3}+ (-1)R_{1}

~

1 2 4 | 12 0 -7 -7 | -14 0 -4 -7 | -17

...... R _{2}'= (-1/7)R_{2}......

~

1 2 4 | 12 0 1 1 | 2 0 -4 -7 | -17

R _{1}'= R_{1}+ (-2)R_{2}...... R _{3}'= R_{3}+ 4R_{2}

~

1 0 2 | 8 0 1 1 | 2 0 0 -3 | -9

...... ...... R _{3}'= (-1/3)R_{3}

~

1 0 2 | 8 0 1 1 | 2 0 0 1 | 3

R _{1}'= R_{1}+ (-2)R_{3}R _{2}'= R_{2}+ (-1)R_{3}......

~

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 x

_{1}= 2. The second row of the matrix represents the equation x_{2}= -1. The third row of the matrix represents the equation x_{3}= 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 x _{1}- x _{2}+ x _{3}= 3 x _{1}+ x _{3}= 1 x _{1}- 2 x _{2}- x _{3}= 4 Max's solution:

2 -1 1 | 3 1 0 1 | 1 1 -2 -1 | 4

R _{1}<=> R_{2}...... ......

~

1 0 1 | 1 2 -1 1 | 3 1 -2 -1 | 4

...... R _{2}'= R_{2}+ (-2)R_{1}R _{3}'= R_{3}+ (-1)R_{1}

~

1 0 1 | 1 0 -1 -1 | 1 0 -2 -2 | 3

...... R _{2}'= (-1)R_{2}...... "This is fun Ninetypenny, I like doing this!"

~

1 0 1 | 1 0 1 1 | -1 0 -2 -2 | 3

...... ...... R _{3}'= R_{3}+ 2R_{2}

~

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 x_{1}+ 0 x_{2}+ 0 x_{3}= 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

...... ...... R _{3}<=> R_{4}......

~

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.