EXAMPLE 5 Solution to Linear System Show that x=2 is a solution to the linear system +2x2=5 ④ 2x1-x2=0 and that x- 3 is not a solution to linear system (4). Solution To show that is a solution to Equation(4),we substitutex=1 and x2=2 in both equations and check that they are satisfied:1 2(2)=5 and 2(1)-2 =0. The vector x= is not a solution to (4),because x1=3 and x2=1 fail to satisfy 2x1-x2=0. Using matrices can greatly simplify the statement and solution of a system of linear equations.To show how matrices can be used to compactly represent Equation(3),let a11 a12… din 「 「b1 a21 022 d2n 2 b2 A= X= b= .: am2… dn bm Then(3)may be written as Ax b ) Observe that both sides of Equation(5)will be m x 1 matrices (or m x 1 column vec- tors).For the matrix Ax to equal the matrix b (or for the vector Ax to equal the vector b), their corresponding elements must be equal.The first element of Ax is the scalar product of row I of A with x.This may be written as [a11a12 a11x1+a12x2+…+a1mxn This must equal the first element of b(which is bi).Thus,(5)implies that ax+ a2+.+a=b1.This is the first equation of (3).Similarly,(5)implies that the scalar
Show that x is a solution to the linear system x1 2x2 5 (4) 2x1 x2 0 and that x is not a solution to linear system (4). Solution To show that x is a solution to Equation (4), we substitute x1 1 and x2 2 in both equations and check that they are satisfied: 1 2(2) 5 and 2(1) 2 0. The vector x is not a solution to (4), because x1 3 and x2 1 fail to satisfy 2x1 x2 0. Using matrices can greatly simplify the statement and solution of a system of linear equations. To show how matrices can be used to compactly represent Equation (3), let A , x , b Then (3) may be written as Ax b (5) Observe that both sides of Equation (5) will be m 1 matrices (or m 1 column vectors). For the matrix Ax to equal the matrix b (or for the vector Ax to equal the vector b), their corresponding elements must be equal. The first element of Ax is the scalar product of row 1 of A with x. This may be written as [a11 a12 a1n] a11x1 a12x2 a1nxn This must equal the first element of b (which is b1). Thus, (5) implies that a11x1 a12x2 a1nxn b1. This is the first equation of (3). Similarly, (5) implies that the scalar x1 x2 xn b1 b2 bm x1 x2 xn a1n a2n amn a12 a22 am2 a11 a21 am1 3 1 1 2 3 1 1 2 2.2 Matrices and Systems of Linear Equations 21 EXAMPLE 5 Solution to Linear System
product of row i of 4 with x must equal b,and this is just the ith equation of(3).Our dis- cussion shows that(3)and(5)are two different ways of writing the same linear system.We call(5)the matrix representation of(3).For example,the matrix representation of(4)is Sometimes we abbreviate(5)by writing 4b 6 If A is an m x n matrix,it is assumed that the variables in (6)are x1,x2,...,x Then (6)is still another representation of(3).For instance,the matrix [123|2 0 2 1 3 1111 represents the system of equations +2x2+3x3=2 x2+2x3=3 +x2+x3=1 PROBLEM Group A 1 Use matrices to represent the following system of x-x2=4 equations in two different ways: 2x1+x2=6 x1+3x2=8 2.3 The Gauss-Jordan Method for Solving Systems of Linear Equations We develop in this section an efficient method(the Gauss-Jordan method)for solving a system of linear equations.Using the Gauss-Jordan method,we show that any system of linear equations must satisfy one of the following three cases: Case 1 The system has no solution. Case 2 The system has a unique solution. Case 3 The system has an infinite number of solutions. The Gauss-Jordan method is also important because many of the manipulations used in this method are used when solving linear programming problems by the simplex algo- rithm(see Chapter 4). Elementary Row Operations Before studying the Gauss-Jordan method,we need to define the concept of an elemen- tary row operation (ERO).An ERO transforms a given matrix A into a new matrix A' via one of the following operations
product of row i of A with x must equal bi , and this is just the ith equation of (3). Our discussion shows that (3) and (5) are two different ways of writing the same linear system. We call (5) the matrix representation of (3). For example, the matrix representation of (4) is Sometimes we abbreviate (5) by writing Ab (6) If A is an m n matrix, it is assumed that the variables in (6) are x1, x2, . . . , xn. Then (6) is still another representation of (3). For instance, the matrix represents the system of equations x1 2x2 3x3 2 x2 2x3 3 x1 x2 x3 1 PROBLEM Group A 2 3 1 3 2 1 2 1 1 1 0 1 5 0 x1 x2 2 1 1 2 22 CHAPTER 2 Basic Linear Algebra 2.3 The Gauss–Jordan Method for Solving Systems of Linear Equations We develop in this section an efficient method (the Gauss–Jordan method) for solving a system of linear equations. Using the Gauss–Jordan method, we show that any system of linear equations must satisfy one of the following three cases: Case 1 The system has no solution. Case 2 The system has a unique solution. Case 3 The system has an infinite number of solutions. The Gauss–Jordan method is also important because many of the manipulations used in this method are used when solving linear programming problems by the simplex algorithm (see Chapter 4). Elementary Row Operations Before studying the Gauss–Jordan method, we need to define the concept of an elementary row operation (ERO). An ERO transforms a given matrix A into a new matrix A via one of the following operations. 1 Use matrices to represent the following system of equations in two different ways: x1 x2 4 2x1 x2 6 x1 3x2 8
Type 1 ERO A4'is obtained by multiplying any row of A by a nonzero scalar.For example,if [1234 A= 1356 012 then a Type 1 ERO that multiplies row 2 of 4 by 3 would yield [12341 A 391518 0123 Type 2 ERO Begin by multiplying any row of A(say,row i)by a nonzero scalar c.For someji,let row j of 4'=c(row i of 4)+row j of A,and let the other rows of A'be the same as the rows of A. For example,we might multiply row 2 of A by 4 and replace row 3 of A by 4(row 2 of A)+row 3 of A.Then row 3 of A'becomes 4[1356]+[0123]=[4132227刀 and 23 ￥ A 1 3 5 6 4 132227 Type 3 ERO Interchange any two rows of 4.For instance,if we interchange rows 1 and 3 of 4,we obtain [0123] A'=1356 [1234 Type 1 and Type 2 EROs formalize the operations used to solve a linear equation sys- tem.To solve the system of equations +x2=2 ) 2r1+4x2=7 we might proceed as follows.First replace the second equation in(7)by -2(first equa- tion in(7))+second equation in(7).This yields the following linear system: x1+2=2 2x2=3 亿10 Then multiply the second equation in (7.1)by,yielding the system x1+x2=2 2=黄 亿2) Finally,replace the first equation in(7.2)by -1[second equation in(7.2)]+first equa- tion in (7.2).This yields the system
Type 1 ERO A is obtained by multiplying any row of A by a nonzero scalar. For example, if A then a Type 1 ERO that multiplies row 2 of A by 3 would yield A Type 2 ERO Begin by multiplying any row of A (say, row i) by a nonzero scalar c. For some j i, let row j of A c(row i of A) row j of A, and let the other rows of A be the same as the rows of A. For example, we might multiply row 2 of A by 4 and replace row 3 of A by 4(row 2 of A) row 3 of A. Then row 3 of A becomes 4 [1 3 5 6] [0 1 2 3] [4 13 22 27] and A Type 3 ERO Interchange any two rows of A. For instance, if we interchange rows 1 and 3 of A, we obtain A Type 1 and Type 2 EROs formalize the operations used to solve a linear equation system. To solve the system of equations x1 x2 2 (7) 2x1 4x2 7 we might proceed as follows. First replace the second equation in (7) by 2(first equation in (7)) second equation in (7). This yields the following linear system: x1 x2 2 (7.1) 2x2 3 Then multiply the second equation in (7.1) by 1 2 , yielding the system x1 x2 2 (7.2) x2 3 2 Finally, replace the first equation in (7.2) by 1[second equation in (7.2)] first equation in (7.2). This yields the system 3 6 4 2 5 3 1 3 2 0 1 1 4 6 27 3 5 22 2 3 13 1 1 4 4 18 3 3 15 2 2 9 1 1 3 0 4 6 3 3 5 2 2 3 1 1 1 0 2.3 The Gauss–Jordan Method for Solving Systems of Linear Equations 23
亿.3) 2= System (7.3)has the unique solutionx=and x2=.The systems (7),(7.1),(7.2), and(7.3)are equivalent in that they have the same set of solutions.This means thatx= 2and x2=is also the unique solution to the original system,(7). If we view (7)in the augmented matrix form (Ab).we see that the steps used to solve (7)may be seen as Type 1 and Type 2 EROs applied to Ab.Begin with the augmented matrix version of (7): 7) Now perform a Type 2 ERO by replacing row 2 of(7')by -2(row 1 of(7'))+row 2 of (7).The result is [11|2] 023 71) which corresponds to (7.1).Next,we multiply row 2 of(7.1')by (a Type 1 ERO),re- sulting in 0 1232 7.2) which corresponds to(7.2).Finally,perform a Type 2 ERO by replacing row 1 of(7.2') by -1(row 2 of (7.2'))+row 1 of (7.2).The result is 0 0 23-2 亿.3') which corresponds to(7.3).Translating(7.3')back into a linear system,we obtain the sys- temx=and x2=3,which is identical to (7.3). Finding a Solution by the Gauss-Jordan Method The discussion in the previous section indicates that if the matrix A'b'is obtained from Ab via an ERO,the systems Ax b and A'x b'are equivalent.Thus,any sequence of EROs performed on the augmented matrix Ab corresponding to the system Ax b will yield an equivalent linear system. The Gauss-Jordan method solves a linear equation system by utilizing EROs in a system- atic fashion.We illustrate the method by finding the solution to the following linear system: 2x1+2x2+3=9 2x1-x2+2x3=6 ⑧) x1-X2+2x3=5 The augmented matrix representation is 「2 219] 4b=2 -12 6 (8) 1 -125 Suppose that by performing a sequence of EROs on(8')we could transform(8')into
x1 1 2 (7.3) x2 3 2 System (7.3) has the unique solution x1 1 2 and x2 3 2 . The systems (7), (7.1), (7.2), and (7.3) are equivalent in that they have the same set of solutions. This means that x1 1 2 and x2 3 2 is also the unique solution to the original system, (7). If we view (7) in the augmented matrix form (Ab), we see that the steps used to solve (7) may be seen as Type 1 and Type 2 EROs applied to Ab. Begin with the augmented matrix version of (7): (7 ) Now perform a Type 2 ERO by replacing row 2 of (7 ) by 2(row 1 of (7 )) row 2 of (7 ). The result is (7.1 ) which corresponds to (7.1). Next, we multiply row 2 of (7.1 ) by 1 2 (a Type 1 ERO), resulting in (7.2 ) which corresponds to (7.2). Finally, perform a Type 2 ERO by replacing row 1 of (7.2 ) by 1(row 2 of (7.2 )) row 1 of (7.2 ). The result is (7.3 ) which corresponds to (7.3). Translating (7.3 ) back into a linear system, we obtain the system x1 1 2 and x2 3 2 , which is identical to (7.3). Finding a Solution by the Gauss–Jordan Method The discussion in the previous section indicates that if the matrix A b is obtained from Ab via an ERO, the systems Ax b and A x b are equivalent. Thus, any sequence of EROs performed on the augmented matrix Ab corresponding to the system Ax b will yield an equivalent linear system. The Gauss–Jordan method solves a linear equation system by utilizing EROs in a systematic fashion. We illustrate the method by finding the solution to the following linear system: 2x1 2x2 2x3 9 2x1 2x2 2x3 6 (8) x1 2x2 2x3 5 The augmented matrix representation is Ab (8 ) Suppose that by performing a sequence of EROs on (8 ) we could transform (8 ) into 9 6 5 1 2 2 2 1 1 2 2 1 1 2 3 2 0 1 1 0 2 3 2 1 1 1 0 2 3 1 2 1 0 2 7 1 4 1 2 24 CHAPTER 2 Basic Linear Algebra
1 0 0 1 0 0 2 (8) 0 0 1 We note that the result obtained by performing an ERO on a system of equations can also be obtained by multiplying both sides of the matrix representation of the system of equations by a particular matrix.This explains why EROs do not change the set of solu- tions to a system of equations. Matrix(9')corresponds to the following linear system: x1=1 X2=2 (9) X3=3 System(9)has the unique solution x1 =1,x2 =2,x3 =3.Because (9')was obtained from(8')by a sequence of EROs,we know that(8)and(9)are equivalent linear systems. Thus,x1=1,x2=2,x3=3 must also be the unique solution to (8).We now show how we can use EROs to transform a relatively complicated system such as (8)into a relatively simple system like (9).This is the essence of the Gauss-Jordan method. We begin by using EROs to transform the first column of(8')into [1 0 o Then we use EROs to transform the second column of the resulting matrix into o Finally,we use EROs to transform the third column of the resulting matrix into 001 As a final result,we will have obtained (9').We now use the Gauss-Jordan method to solve(8).We begin by using a Type 1 ERO to change the element of(8')in the first row and first column into a 1.Then we add multiples of row 1 to row 2 and then to row 3 (these are Type 2 EROs).The purpose of these Type 2 EROs is to put zeros in the rest of the first column.The following sequence of EROs will accomplish these goals. Step 1 Multiply row 1 of(8')by This Type 1 ERO yields 11 A1b1= -12 6 1-125 Step 2 Replace row 2 of Ab by -2(row 1 of Ab)+row 2 of Ab.The result of this Type 2 ERO is 1支 A2b2=0-31 3 1 -12 5
(9 ) We note that the result obtained by performing an ERO on a system of equations can also be obtained by multiplying both sides of the matrix representation of the system of equations by a particular matrix. This explains why EROs do not change the set of solutions to a system of equations. Matrix (9 ) corresponds to the following linear system: x1 1 x2 2 (9) x3 3 System (9) has the unique solution x1 1, x2 2, x3 3. Because (9 ) was obtained from (8 ) by a sequence of EROs, we know that (8) and (9) are equivalent linear systems. Thus, x1 1, x2 2, x3 3 must also be the unique solution to (8). We now show how we can use EROs to transform a relatively complicated system such as (8) into a relatively simple system like (9). This is the essence of the Gauss–Jordan method. We begin by using EROs to transform the first column of (8 ) into Then we use EROs to transform the second column of the resulting matrix into Finally, we use EROs to transform the third column of the resulting matrix into As a final result, we will have obtained (9 ). We now use the Gauss–Jordan method to solve (8). We begin by using a Type 1 ERO to change the element of (8 ) in the first row and first column into a 1. Then we add multiples of row 1 to row 2 and then to row 3 (these are Type 2 EROs). The purpose of these Type 2 EROs is to put zeros in the rest of the first column. The following sequence of EROs will accomplish these goals. Step 1 Multiply row 1 of (8 ) by 1 2 . This Type 1 ERO yields A1b1 Step 2 Replace row 2 of A1b1 by 2(row 1 of A1b1) row 2 of A1b1. The result of this Type 2 ERO is A2b2 9 2 3 5 1 2 1 2 1 3 1 1 0 1 9 2 6 5 1 2 2 2 1 1 1 1 2 1 0 0 1 0 1 0 1 0 0 1 2 3 0 0 1 0 1 0 1 0 0 2.3 The Gauss–Jordan Method for Solving Systems of Linear Equations 25