Step 3 Replace row 3 of 42b2 by -1(row 1 of 42b2 row 3 of 42b2.The result of this Type 2 ERO is [1 1立 A3b3=0-31 3 0-22 The first column of (8')has now been transformed into 0 o By our procedure,we have made sure that the variablex occurs in only a single equation and in that equation has a coefficient of 1.We now transform the second column of 43b3 into fo] 1 We begin by using a Type 1 ERO to create a 1 in row 2 and column 2 of A3b3.Then we use the resulting row 2 to perform the Type 2 EROs that are needed to put zeros in the rest of column 2.Steps 4-6 accomplish these goals. Step 4 Multiply row 2 of 43b byThe result of this Type 1 ERO is [1 11 A4b4= 0 1 1 3 0-2 Step 5 Replace row 1 of A4b4 by -1(row 2 of A4b4)+row 1 of A4b4.The result of this Type 2 ERO is 0 A5b5= 0 1 1 0 -2 Step 6 Replace row 3 of Asbs by 2(row 2 of As bs)+row 3 of Asbs.The result of this Type 2 ERO is [1 0 6 A6b6= 01 1-3 1 00 Column 2 has now been transformed into [o 10 Observe that our transformation of column 2 did not change column 1. To complete the Gauss-Jordan procedure,we must transform the third column of 46b6 into u
Step 3 Replace row 3 of A2b2 by 1(row 1 of A2b2 row 3 of A2b2. The result of this Type 2 ERO is A3b3 The first column of (8 ) has now been transformed into By our procedure, we have made sure that the variable x1 occurs in only a single equation and in that equation has a coefficient of 1. We now transform the second column of A3b3 into We begin by using a Type 1 ERO to create a 1 in row 2 and column 2 of A3b3. Then we use the resulting row 2 to perform the Type 2 EROs that are needed to put zeros in the rest of column 2. Steps 4–6 accomplish these goals. Step 4 Multiply row 2 of A3b3 by 1 3 .The result of this Type 1 ERO is A4b4 Step 5 Replace row 1 of A4b4 by 1(row 2 of A4b4) row 1 of A4b4. The result of this Type 2 ERO is A5b5 Step 6 Replace row 3 of A5b5 by 2(row 2 of A5b5) row 3 of A5b5. The result of this Type 2 ERO is A6b6 Column 2 has now been transformed into Observe that our transformation of column 2 did not change column 1. To complete the Gauss–Jordan procedure, we must transform the third column of A6b6 into 0 0 1 0 1 0 7 2 1 5 2 5 6 1 3 5 6 0 1 0 1 0 0 7 2 1 1 2 5 6 1 3 3 2 0 1 2 1 0 0 9 2 1 1 2 1 2 1 3 3 2 1 1 2 1 0 0 0 1 0 1 0 0 9 2 3 1 2 1 2 1 3 2 1 3 2 1 0 0 26 CHAPTER 2 Basic Linear Algebra
We first use a Type 1 ERO to create a 1 in the third row and third column of 46b6.Then we use Type 2 EROs to put zeros in the rest of column 3.Steps 7-9 accomplish these goals. Step 7 Multiply row 3 of b by The result of this Type 1 ERO is [10 Ab7=01 1 00 3 3 Step 8 Replace row 1 of b7 by(row 3 of 47b7)+row 1 of 47b7.The result of this Type 2 ERO is [10 0 1 01 00 1 3 Step 9 Replace row 2 of Asbs by (row 3 of As bs)+row 2 of Asbs.The result of this Type 2 ERO is [100 1 =0 1 0 2 0013 4bo represents the system of equations =1 =2 a 3=3 Thus,(9)has the unique solution x1=1,x2 =2,x3 =3.Because(9)was obtained from (8)via EROs,the unique solution to (8)must also be x1=1,x2=2,x3=3. The reader might be wondering why we defined Type 3 EROs(interchanging of rows). To see why a Type 3 ERO might be useful,suppose you want to solve 2x2+x3=6 +x2-3=2 (10) 21+x2+x3=4 To solve (10)by the Gauss-Jordan method,first form the augmented matrix [02161 Ab=11-1 2 21 1 4 The 0 in row 1 and column 1 means that a Type 1 ERO cannot be used to create a 1 in row 1 and column 1.If,however,we interchange rows 1 and 2(a Type 3 ERO),we obtain [11-121 02 6 (10') 211 4 Now we may proceed as usual with the Gauss-Jordan method
We first use a Type 1 ERO to create a 1 in the third row and third column of A6b6. Then we use Type 2 EROs to put zeros in the rest of column 3. Steps 7–9 accomplish these goals. Step 7 Multiply row 3 of A6b6 by 6 5 . The result of this Type 1 ERO is A7b7 Step 8 Replace row 1 of A7b7 by 5 6 (row 3 of A7b7) row 1 of A7b7. The result of this Type 2 ERO is A8b8 Step 9 Replace row 2 of A8b8 by 1 3 (row 3 of A8b8) row 2 of A8b8. The result of this Type 2 ERO is A9b9 A9b9 represents the system of equations x1x2x3 1 x1x2x3 2 (9) x1x2x3 3 Thus, (9) has the unique solution x1 1, x2 2, x3 3. Because (9) was obtained from (8) via EROs, the unique solution to (8) must also be x1 1, x2 2, x3 3. The reader might be wondering why we defined Type 3 EROs (interchanging of rows). To see why a Type 3 ERO might be useful, suppose you want to solve 2x2 x3 6 x1 x2 x3 2 (10) 2x1 x2 x3 4 To solve (10) by the Gauss–Jordan method, first form the augmented matrix Ab The 0 in row 1 and column 1 means that a Type 1 ERO cannot be used to create a 1 in row 1 and column 1. If, however, we interchange rows 1 and 2 (a Type 3 ERO), we obtain (10 ) Now we may proceed as usual with the Gauss–Jordan method. 2 6 4 1 1 1 1 2 1 1 0 2 6 2 4 1 1 1 2 1 1 0 1 2 1 2 3 0 0 1 0 1 0 1 0 0 1 1 3 0 1 3 1 0 1 0 1 0 0 7 2 1 3 5 6 1 3 3 0 1 0 1 0 0 2.3 The Gauss–Jordan Method for Solving Systems of Linear Equations 27
Special Cases:No Solution or an Infinite Number of Solutions Some linear systems have no solution,and some have an infinite number of solutions.The following two examples illustrate how the Gauss-Jordan method can be used to recognize these cases. EXAMPLE 6 Linear System with No Solution Find all solutions to the following linear system: x+2x2=3 () 2x1+4x2=4 Solution We apply the Gauss-Jordan method to the matrix We begin by replacing row 2 of b by -2(row 1 of Ab)+row 2 of b.The result of this Type 2 ERO is 0副 (12) We would now like to transform the second column of(12)into 「0 but this is not possible.System(12)is equivalent to the following system of equations: x1+2x2=3 (12') 0x1+0x2=-2 Whatever values we give to x and x2,the second equation in(12')can never be satisfied. Thus,(12')has no solution.Because(12')was obtained from(11)by use of EROs,(11) also has no solution. Example 6 illustrates the following idea:If you apply the Gauss-Jordan method to a lin- ear system and obtain a row of the form [0..Oc](c +0),then the original lin- ear system has no solution. EXAMPLE 7 Linear System with Infinite Number of Solutions Apply the Gauss-Jordan method to the following linear system: 1+x2 =1 x2+x3=3 (13) x1+2x2+x3=4 Solution The augmented matrix form of(13)is [11 0 1 Ab=01 3 121 4
Special Cases: No Solution or an Infinite Number of Solutions Some linear systems have no solution, and some have an infinite number of solutions. The following two examples illustrate how the Gauss–Jordan method can be used to recognize these cases. Find all solutions to the following linear system: x1 2x2 3 (11) 2x1 4x2 4 Solution We apply the Gauss–Jordan method to the matrix Ab We begin by replacing row 2 of Ab by 2(row 1 of Ab) row 2 of Ab. The result of this Type 2 ERO is (12) We would now like to transform the second column of (12) into but this is not possible. System (12) is equivalent to the following system of equations: x1 2x2 3 (12 ) 0x1 0x2 2 Whatever values we give to x1 and x2, the second equation in (12 ) can never be satisfied. Thus, (12 ) has no solution. Because (12 ) was obtained from (11) by use of EROs, (11) also has no solution. Example 6 illustrates the following idea: If you apply the Gauss–Jordan method to a linear system and obtain a row of the form [0 0 0c] (c 0), then the original linear system has no solution. Apply the Gauss–Jordan method to the following linear system: x1 x2 1 x2 x3 3 (13) x1 2x2 x3 4 Solution The augmented matrix form of (13) is Ab 1 3 4 0 1 1 1 1 2 1 0 1 0 1 3 2 2 0 1 0 3 4 2 4 1 2 28 CHAPTER 2 Basic Linear Algebra EXAMPLE 7 Linear System with Infinite Number of Solutions EXAMPLE 6 Linear System with No Solution
We begin by replacing row 3(because the row 2,column 1 value is already 0)of b by -1(row 1 of b)+row 3 of 4b.The result of this Type 2 ERO is [11011] Ab1=0113 (14 0113 Next we replace row 1 of 41b by -1(row 2 of Ab)+row 1 of 41b.The result of this Type 2 ERO is [1 0 -1 2 A2b2= 01 3 01 1 3 Now we replace row 3 of 42b2 by -1(row 2 of 42b2)+row 3 of 42b2.The result of this Type 2 ERO is 0 -1 -2 43 b3 0 1 1 3 0 0 01 0 We would now like to transform the third column of A3b3 into [01 0 but this is not possible.The linear system corresponding to 43b3 is XI -3=-2 (14.1) x2+x3=3 (14.2) 0x1+0x2+0x3=0 (14.3) Suppose we assign an arbitrary value k to x3.Then (14.1)will be satisfied if x=-2, orx=k-2.Similarly,(14.2)will be satisfied if x2 +k=3,or x2=3 -k.Of course, (14.3)will be satisfied for any values ofx,x2,and x3.Thus,for any number,x=k-2, x2=3-k,x3=k is a solution to (14).Thus,(14)has an infinite number of solutions (one for each number k).Because (14)was obtained from (13)via EROs,(13)also has an infinite number of solutions.A more formal characterization of linear systems that have an infinite number of solutions will be given after the following summary of the Gauss-Jordan method. Summary of the Gauss-Jordan Method Step 1 To solve Ax b,write down the augmented matrix Ab Step 2 At any stage,define a current row,current column,and current entry (the entry in the current row and column).Begin with row 1 as the current row,column 1 as the cur- rent column,and a as the current entry.(a)If a(the current entry)is nonzero,then use EROs to transform column 1 (the current column)to [1 0 : 0
We begin by replacing row 3 (because the row 2, column 1 value is already 0) of Ab by 1(row 1 of Ab) row 3 of Ab. The result of this Type 2 ERO is A1b1 (14) Next we replace row 1 of A1b1 by 1(row 2 of A1b1) row 1 of A1b1. The result of this Type 2 ERO is A2b2 Now we replace row 3 of A2b2 by 1(row 2 of A2b2) row 3 of A2b2. The result of this Type 2 ERO is A3b3 We would now like to transform the third column of A3b3 into but this is not possible. The linear system corresponding to A3b3 is 0x1 0x2 0x3 2 (14.1) 0x1 0x2 0x3 3 (14.2) 0x1 0x2 0x3 0 (14.3) Suppose we assign an arbitrary value k to x3. Then (14.1) will be satisfied if x1 k 2, or x1 k 2. Similarly, (14.2) will be satisfied if x2 k 3, or x2 3 k. Of course, (14.3) will be satisfied for any values of x1, x2, and x3. Thus, for any number k, x1 k 2, x2 3 k, x3 k is a solution to (14). Thus, (14) has an infinite number of solutions (one for each number k). Because (14) was obtained from (13) via EROs, (13) also has an infinite number of solutions. A more formal characterization of linear systems that have an infinite number of solutions will be given after the following summary of the Gauss–Jordan method. Summary of the Gauss–Jordan Method Step 1 To solve Ax b, write down the augmented matrix Ab. Step 2 At any stage, define a current row, current column, and current entry (the entry in the current row and column). Begin with row 1 as the current row, column 1 as the current column, and a11 as the current entry. (a) If a11 (the current entry) is nonzero, then use EROs to transform column 1 (the current column) to 1 0 0 0 0 1 2 3 0 1 1 0 0 1 0 1 0 0 2 3 3 1 1 1 0 1 1 1 0 0 1 3 3 0 1 1 1 1 1 1 0 0 2.3 The Gauss–Jordan Method for Solving Systems of Linear Equations 29
Then obtain the new current row,column,and entry by moving down one row and one column to the right,and go to step 3.(b)If a(the current entry)equals 0,then do a Type 3 ERO involving the current row and any row that contains a nonzero number in the current column.Use EROs to transform column 1 to 1 0 .: 0 Then obtain the new current row,column,and entry by moving down one row and one column to the right.Go to step 3.(c)If there are no nonzero numbers in the first column, then obtain a new current column and entry by moving one column to the right.Then go to step 3. Step 3 (a)If the new current entry is nonzero,then use EROs to transform it to 1 and the rest of the current column's entries to 0.When finished,obtain the new current row, column,and entry.If this is impossible,then stop.Otherwise,repeat step 3.(b)If the current entry is 0,then do a Type 3 ERO with the current row and any row that con- tains a nonzero number in the current column.Then use EROs to transform that cur- rent entry to 1 and the rest of the current column's entries to 0.When finished,obtain the new current row,column,and entry.If this is impossible,then stop.Otherwise,re- peat step 3.(c)If the current column has no nonzero numbers below the current row, then obtain the new current column and entry,and repeat step 3.If it is impossible,then stop. This procedure may require "passing over"one or more columns without transform- ing them (see Problem 8). Step 4 Write down the system of equations A'x =b'that corresponds to the matrix 4'b' obtained when step 3 is completed.Then A'x =b'will have the same set of solutions as Ax b. Basic Variables and Solutions to Linear Equation Systems To describe the set of solutions to A'x b'(and Ax b),we need to define the concepts of basic and nonbasic variables. DEFINITION■ After the Gauss-Jordan method has been applied to any linear system,a variable that appears with a coefficient of I in a single equation and a coefficient of 0 in all other equations is called a basic variable(BV). Any variable that is not a basic variable is called a nonbasic variable(NBV). Let BIbe the set of basic variables for A'x=b'and NBV be the set of nonbasic vari- ables for A'x b'.The character of the solutions to A'x b'depends on which of the following cases occurs. Case 1 A'x b'has at least one row of form [0 0..0c](c0).Then Ax b has no solution (recall Example 6).As an example of Case 1,suppose that when the Gauss-Jordan method is applied to the system Ax b,the following matrix is obtained:
Then obtain the new current row, column, and entry by moving down one row and one column to the right, and go to step 3. (b) If a11 (the current entry) equals 0, then do a Type 3 ERO involving the current row and any row that contains a nonzero number in the current column. Use EROs to transform column 1 to Then obtain the new current row, column, and entry by moving down one row and one column to the right. Go to step 3. (c) If there are no nonzero numbers in the first column, then obtain a new current column and entry by moving one column to the right. Then go to step 3. Step 3 (a) If the new current entry is nonzero, then use EROs to transform it to 1 and the rest of the current column’s entries to 0. When finished, obtain the new current row, column, and entry. If this is impossible, then stop. Otherwise, repeat step 3. (b) If the current entry is 0, then do a Type 3 ERO with the current row and any row that contains a nonzero number in the current column. Then use EROs to transform that current entry to 1 and the rest of the current column’s entries to 0. When finished, obtain the new current row, column, and entry. If this is impossible, then stop. Otherwise, repeat step 3. (c) If the current column has no nonzero numbers below the current row, then obtain the new current column and entry, and repeat step 3. If it is impossible, then stop. This procedure may require “passing over” one or more columns without transforming them (see Problem 8). Step 4 Write down the system of equations A x b that corresponds to the matrix A b obtained when step 3 is completed. Then A x b will have the same set of solutions as Ax b. Basic Variables and Solutions to Linear Equation Systems To describe the set of solutions to A x b (and Ax b), we need to define the concepts of basic and nonbasic variables. DEFINITION ■ After the Gauss–Jordan method has been applied to any linear system, a variable that appears with a coefficient of 1 in a single equation and a coefficient of 0 in all other equations is called a basic variable (BV). ■ Any variable that is not a basic variable is called a nonbasic variable (NBV). ■ Let BV be the set of basic variables for A x b and NBV be the set of nonbasic variables for A x b . The character of the solutions to A x b depends on which of the following cases occurs. Case 1 A x b has at least one row of form [0 0 0c] (c 0). Then Ax b has no solution (recall Example 6). As an example of Case 1, suppose that when the Gauss–Jordan method is applied to the system Ax b, the following matrix is obtained: 1 0 0 30 CHAPTER 2 Basic Linear Algebra