Section 2.

3 Gauss-Jordan Method for General Systems of Equations

Recall that we'd like to use row operations on an augmented matrix to get it into the following form: 1 0 0 0 0 b1 0 1 0 0 0 b2 0 0 1 0 0 b3 0 0 0 1 0 bn1 0 0 0 0 1 bn This is not always possible though. be put into this form. 1 2 0 0 0 0 The following are matrices that cannot

3 7 0 0 0 0

1 0 5 2 0 1 6 3

Recognize that if we cant get our matrix to the desired form, then it wont be as easy to see what the solution to the system of equations will be.

For example, this matrix has a solution that is easy to see, (1, 3, 5), because the matrix is in the final form that we want.

1 0 0 1 0 1 0 3 0 0 1 5

This matrix (on the right) has a solution but is not as clear what the solution is. What we can conclude about the solution, (x, y, z), is that the components x, y, and z must obey the equation x + 2y + 3z = 7. This matrix (on the right) has a solution, but again it is not as clear what it is. What we can conclude about the solution, (x, y, z), is that the components x, y, and z must obey the two equations x + 5z = 2 and y + 6z = 3.

1 2 3 7 0 0 0 0 0 0 0 0
1 0 5 2 0 1 6 3

These last two matrices represent systems that do not have a unique solution. Whenever a matrix does not have a unique solution (if it has infinitely many solutions or no solution at all) we will not be able to get our augmented matrix into the form that we really want. When this happens, we want to at least get our matrix as close as possible to this form that we would really like it to be in. When it is as close as it can possibly get, we say it is in reduced row echelon form.

If a matrix cannot be placed into this desired form (seen below), we still try to get it as close to this form as possible. In doing so, we want to use row operations to get as many of our 1s where we want them going down diagonally from the upper left of the matrix to the bottom right of the matrix. Whenever we get a 1 in such a spot, we want to use row operations to clear out all the other entries (turning them into 0s) in that column, thus getting as many of our 0s where we want them.

1 0 0 0 0 b1 A matrix (any matrix, not just an augmented matrix) is 1 0 to be in reduced b 0 said 0 0 2 true: echelon form if all of the following properties hold 0 0 1 0 0 b3 1. All rows consisting entirely of zeros are grouped at the bottom. 2. The leftmost nonzero number in each row is 1 (called the leading one). 3. The leading 1 of a row is to the right of the previous row's leading 1. are zeros. 4. All entries directly above and below a leading 1 0 0 0 1 0 bn1 0 0 0 0 1 bn

Reduced Row Echelon Form

Ex. 1 Determine which of the following matrices are in reduced row echelon form. 1 0 0 3 (a) 1 0 0 4 (b) (c) 1 0 0 2 0 1 0 5 0 1 0 4 0 0 1 4 0 0 0 0 0 0 1 2 0 1 0 1 0 0 1 5

Reduced Row Echelon Form

1. 2. 3. 4.

Yes, all four properties are there is a row of all the leading one of the third row No, No, true for this matrix. is not zeros which is not at the to the right of the leading one bottom of the matrix.of the second row (notice how when this happens the leading ones do not go down diagonally from top left to bottom right). All rows consisting entirely of zeros are grouped at the bottom. The leftmost nonzero number in each row is 1 (called the leading one). The leading 1 of a row is to the right of the previous row's leading 1. All entries directly above and below a leading 1 are zeros.

Ex. 1 Determine which of the following matrices are in reduced row echelon form.

(d) 1 0 0 0 4 0 0 1 0 5 0 0 0 1 7

(e)

1 0 3 4 0 1 2 1 0 0 0 0

(f)

1 0 3 0 1 2 0 0 0

Yes.

Yes.

Yes.

Reduced Row Echelon Form

1. 2. 3. 4. All rows consisting entirely of zeros are grouped at the bottom. The leftmost nonzero number in each row is 1 (called the leading one). The leading 1 of a row is to the right of the previous row's leading 1. All entries directly above and below a leading 1 are zeros.

Ex. 1 Determine which of the following matrices are in reduced row echelon form.

(g)

1 0 0 2 0 1 0 4

(h) 2 0 0 3 0 1 0 5 0 0 1 7

Yes.

No, the first row does not have a leading one (it has a leading two).

Reduced Row Echelon Form

1. 2. 3. 4. All rows consisting entirely of zeros are grouped at the bottom. The leftmost nonzero number in each row is 1 (called the leading one). The leading 1 of a row is to the right of the previous row's leading 1. All entries directly above and below a leading 1 are zeros.

1 3 11 Ex. 2 Put the matrix A 3 4 6 into reduced row echelon form. 2 7 17 1 3 Well, we are going to proceed as we did before when we were 11 3 4 solving systems of equations. Same process, GaussJordan 6 elimination process using the PIVOT program, the only difference 2 7 17 is we might not be able to get the final matrix into the form of the 1 3 following matrix (but we will get as close to this form as we can 11 0 13 this is precisely what 2reduced row echelon form is): 39 R2 3R1R 1 0 0 0 0 b1 0 13 39 R3 2R1R3 0 1 0 0 0 b2 1 3 11 0 0 1 0 0 b3 1 3 /13 R2R2 0 1 0 13 39 bn1 1 0 1 0 2 R1 3R2R1 0 0 0 0 0 0 Reduced row echelon form has been bn 0 1 reached! 0 1 3 0 0 0 R3 + 13R2R3

The Calculator And The PIVOT Program.

To enter matrices press the MATRX button then select the EDIT menu.
Once you press the MATRX button you should see a screen that looks something like this one. There are three menus at the top.

To create a matrix and store it in the calculators memory, we need to select a matrix from the EDIT menu. (It doesnt really matter which matrix you select, as long as you remember the name of the one you selected. To make things easier on myself, I always choose matrix [A]).

The Calculator And The PIVOT Program.

After you select [A] from the EDIT menu you should see a screen somewhat similar to this one. The top right hand corner of the screen has the dimensions (number of rows and columns) for the current matrix.
Lets enterin the number of the previous example to the calculator. First type the matrix from rows, followed by the enter button, followed by11 number of 1 3 the columns, followed by the 4 6 button again. A 3 enter (So the button sequence for this matrix is 2 7 17 3, ENTER, 3, ENTER.) Next, start typing in the entries for the matrix, hitting enter after you type in each entry. When you finish typing in the values, your screen should look something like this:

The Calculator And The PIVOT Program.

Now we are done creating the matrix, so exit out of the matrix editor (press quit located at the top left of the calculator). You will now be at the home screen.

We want to begin the PIVOT program and use it to put our matrix [A] into reduced row echelon form. First let me describe what the PIVOT program is going to do. Pivoting is a process that uses elementary row operations to change a matrix. If we want to pivot on row i, column j, that means we want to use elementary row operations to scale down/up whatever number was in that spot into a one, then use elementary row operations to clear out the other numbers in that column (turning these other numbers into zeros).

The Calculator And The PIVOT Program. The following sequence of matrices shows how we converted column 3 in the first matrix into having a one in the third row and zeros elsewhere. We can do all three of the required elementary row operation involved here with one pivot command. If we want to place a one in the third row, third column (and clear out zeros elsewhere in the column) then we will say we want to pivot on the third row and third column.
1 0 3 8 0 1 2 8 0 0 2 9 1 0 3 8 0 1 2 8 9 0 0 1 Pivoting R3R3 2 on row 3, column 3. 1 0 3 8 0 1 0 1 R2 + 2R3R2 0 0 1 9 2 1 0 0 11 2 R1 3R3R1 0 1 0 1 9 0 0 1 2

The Calculator And The PIVOT Program.

Ok, now back to the calculator and its PIVOT program.

We want to start this program, and see how it will place our matrix [A] in reduced row echelon form quickly through a series of pivot commands. While on the home screen, press the PRGM button. You should see a screen somewhat similar to the following.

This is a list of all the programs on the calculator (Your calculator may have more programs on it. Each program on your calculator is listed here). We want to select the PIVOT program (use the up/down arrows to highlight PIVOT then push ENTER).

The Calculator And The PIVOT Program.

This pasted the command to run the PIVOT program into the home screen (see the screen shot on the right). Now we must hit ENTER one more time to execute this command.

Once you hit ENTER the program begins. Basically, while you are in the PIVOT program you will want to follow the directions given on the screen.

The Calculator And The PIVOT Program.

First we will choose matrix [A] (since that is where we put our matrix earlier).

The Calculator And The PIVOT Program.

Next tell the calculator where you want to pivot. (In putting our matrix into reduced row echelon form we first need to concentrate on the first column, so we begin by pivoting on row one column one.)

Now we see our matrix after the first pivot. Notice that the first column is looking good, so next we will pivot in the second column.

The Calculator And The PIVOT Program.

Once we pivot on the 2nd row, 2nd column we see that the process is done (the matrix is now in reduced row echelon form).

The Calculator And The PIVOT Program.

To exit the program we follow the direction at the bottom of the screen.

1 3 11 Ex. 3 Use the calculator to put the matrix A 3 4 6 into reduced row echelon form. 2 7 17 1 3 11 3 4 6 2 7 17
This is what we just did in the last several screens.

I do want to mention here what kind of work is expected to be shown (when using the PIVOT program) to justify your answers on an exam. Whenever you use this program you will need to show the first matrix you typed into the calculator, then the final matrix that the calculator produced before you exit the program.

1 0 0 1 0 0

2 3 0

Ex. 4 Solve the following system. Then draw a graph of this system and its solution. x + y = 11 3x 4y = 6 2x 7y = 17 There are no solutions to this system because this system consists of equations for three lines which do not all 11 1 1 First, we will take the augmented matrix for this intersect at one common point. 3 4 6 system and put it into reduced row echelon form (via the calculator with its PIVOT program). 2 7 17
11 1 1 0 7 39 0 9 39 1 0 0 1 0 0 39 7 78 7
38 7

The result of pivoting on row 1, column 1.

The result of pivoting on row 2, column 2. This first row states that 1x + 0y = 0 (i.e. x = 0). The second row states that 0x + 1y = 0 (i.e. y = 0). So it seems that the solution is x = 0 and y = 0. The resultlastpivoting onthat 0x + 0y = 1. This is impossible! But the of row states row 3, column 3. No values of x and y can satisfy this equation. Thus, there are no values for x and y that solve our system of equations. (This system has no solution.)

1 0 0 0 1 0 0 0 1

Ex. 5 Solve the following system of equations.

3x1 2x2 3x3 = 16 2x1 + 4x2 + x3 = 15 x1 7x2 + x3 = 8

3 2 3 2 4 1 1 7 1 1 0 0
2 16 3 3 3 5 9

16 15 8
16

1 3 2
8

19

The result of pivoting on row 1, column 1. 77 3 8 3

3 8

1 0 0 1 0 0

16 16

89

77 16 445 16
17

The result of pivoting on row 2, column 2.

1 0 0 0 1 0 0 0 1

1 2 5

The resultOurpivoting on (1, 2, 5) of solution is row 3, column 3.

Ex. 6 Solve the following system of equations.

1 4 7 2 9 4 1 3 17 1 4 7 0 1 10 0 1 10 1 0 47 0 1 10 0 0 0

3 7 2

3 1 1 Alright. These equations indicate that if we know what the value ofouris, then is in reduced rowthe value form. and we can Well, x3 matrix we can compute echelon of x1 All that is 1 computedo isvalue of x2.what the solution is. left to the figure out The 1st row states that 1x1 + 0x2 + 47x3 = 1. 1 So picknd row states that, 0x1 +call this k.3 = 1. The 2 any value for x3 lets 1x2 + 10x 0 Then 3rd = k, states 1 47k, +and +x0x 1 10k. The x3 row x1 = that 0x1 0x2 2 = = 0. 3 Well, the last row just tells us that 0 = 0. That information is We have infinitely manyfigure out to this system.So, ignore it. useless when trying to solutions our solution. The solutions have the parametric form of (1 47k, 1 10k, k).

x1 4x2 + 7x3 = 3 2x1 + 9x2 4x3 = 7 x1 3x2 + 17x3 = 2 So, the only information we have for our solution (x1, x2, x3) is x1 + 47x3 = 1 x2 + 10x3 = 1. Notice that we can easily solve these equations for x1 and x2 : x1 = 1 47x3 x2 = 1 10x3.

Ex. 6 Solve the following system of equations. x1 4x2 + 7x3 = 3 (A graph of this system is given below.) 2x1 + 9x2 4x3 = 7 x1 3x2 + 17x3 = 2 Here's one view of the three planes: Here's a side view of the three planes:

Recall that solutions with two variables have graphs that are lines slicing through Systems of equations to systems of equations correspond to intersection points on the dimensional space. Systems on this line (embedded in 3D space). the two graph. So, every single point of equationscorresponds to a solution graphs Now note that a line is a one dimensional objectwith three variables havetoThis can that are planes slicing through three has of our solution: points on it, are seeing besystem of equations. Since this line dimensional space. Thats what we10k,are seen by observing the parametric form infinitely many (1 47k, 1 there k). infinitely many solutions to the system. here. We have three equations, so there are three planes the one dimension This parametric form has one parameter (corresponding toin the graph. The for the intersection the graph of the solution). line, which is of these three planes form a line (shown in pink).

Ex. 7 Solve the following system of equations.

x1 2x2 + 3x3 = 4 2x1 + 4x2 6x3 = 8 3x1 6x2 + 9x3 = 12

1 2 3 2 4 6 3 6 9 1 2 3 0 0 0 0 0 0 4 0 0

4 We will again take the augmented matrix for this system and The only 8 put it intoinformation we have for our solution (x1, x2, x3) is reduced row echelon form (via the calculator). x1 x2 + 3x3 = 4 12
Notice row states that 1x solve + 3x3 = 4. The 1st that we can easily 1 2x2this equation for x1: x1 states that 0x The 2nd row = 4 + x2 3x31. + 0x2 + 0x3 = 0. The 3rd row states that 0x1 + 0x2 + 0x3 = 0. This equation indicates that if we know what the value of x2 The last two rows can compute the value and x3 are, then wejust tells us that 0 = 0. of x1. Useless information. Ignore any So pickit. value for x2 and x3, lets call the value we pick for x2 to be j and the value we pick for x3 to be k. Then x2 = j, x3 = k, and x1 = 4 + 2j 3k. We have infinitely many solutions to this system. The solutions have the parametric form of (4+2j3k, j, k).

Ex. 7 Solve the following system of equations. x1 2x2 + 3x3 = 4 (A graph of this system is given below.) 2x1 + 4x2 6x3 = 8 3x1 6x2 + 9x3 = 12 Here's one view of the three planes: Here's a side view of the three planes:

We have three equations, and there really are three planes in the graph. Youre only seeing one because all three planes are exactly the same. The intersection of these three identical planes form a plane (naturally), which is a two dimensional object (embedded in 3D space). This could be seen from our the parametric form of the solution to the system of equations: (4+2j3k, j, k). This parametric form has two parameters (corresponding to the two dimensions for the plane, which is the graph of the solution).

Ex. 8 Solve the following system of equations. 3x1 + 11x2 3x3 = 17 4x1 2x2 3x3 = 8 11x1 + 7x2 9x3 = 10

3 11 3 17 4 2 3 8 11 7 9 10 1 0 0
11 3 3 3 39 3

Again we take the augmented matrix for this system and put it into reduced row echelon form (via the calculator).

1 1 2
50

50

100

44 3 157 3
17 3

1 0 0 1 0 0 1 0 0 1 0 0

50

0
39 3 50

50

22 25 23 One only needs to look at the last row to determine the solution to this system of equations. The last row states: 0 0x1 + 0x2 + 0x3 = 1. 0 Since no values of x1, x2, and x3 can make this equation work 1 we must conclude that there is no solution for this system.
61 25

Ex. 8 Solve the following system of equations. 3x1 + 11x2 3x3 = 17 (A graph of this system is given below.) 4x1 2x2 3x3 = 8 11x1 + 7x2 9x3 = 10

We have three equations, so there are three planes in the graph. Any two of the planes intersect in a line, but the three planes do not all intersect at the same point (there is no point which happens to be on each plane). Since there is no common intersection point, there is no solution to the system.

Ex. 9 Solve the following system of equations.

2x1 + 4x2 x3 = 0 4x1 + 8x2 + 5x3 = 14 3x1 + x2 9x3 = 5

2 4 1 4 8 5 3 1 9 1 2 0 0 0 5 1 2 0 5 0 0 1 0 0 1 0 0
3 1 2

0 14 5 0 14 5 0 5 14 2 1 14

7
15 1 2

2 2

15

7
7 2

Again we take the augmented matrix for this system and put it into reduced row echelon form (via the calculator). Ok. At this point in the PIVOT program we want to pivot on the element in the 2nd row and 2nd column. The calculator wont let us though since that element is a zero. What we need to do when this happens is think about what we would do without the calculator. What elementary row operation would we use at this point to proceed to put the matrix in reduced row echelon form? Swapping rows! Swap rows 2 and 3 so that a nonzero number appears in the 2nd row and 2nd column, then we can put a leading one in this spot with further elementary row operations. 1 0 0 5 This system has a unique solution Since is what we would do without the calculator, thisof this is exactly0what we want to(2, with the calculator. The PIVOT 1 0 2 do 1, 14). 0 0 1 2 program has an option for switching rows. Use this option here.

Ex. 10 A contractor builds houses, duplexes, and apartment units. He has financial backing to build 250 units. He makes a profit of $4,500 on each house, $4,000 on each duplex, and $3,000 on each apartment unit. Each house requires 10 man-months of labor, each duplex requires 12 man-months, and each apartment requires 6 man-months. How many of each should the contractor build if he has 2050 man-months of labor available and wishes to make a total profit of $875,000? Let x1 = the number of houses to build x2 = the number of duplexes to build x3 = the number of apartment units to build x1 + x2 + x3 = 250 4500x1 + 4000x2 + 3000x3 = 875000 10x1 + 12x2 + 6x3 = 2050

1 1 1 4500 4000 3000 10 12 6

250 875000 2050

1 0 0 40 0 1 0 65 0 0 1 145

The contractor should build 40houses, 65 duplexes, and 145 apartment units.