2 Chapter One.Linear Systems ments C,H,N,and O in turn gives this system. 7x=7z 8x+1y=5z+2w 1y=3z 3y=6z+1w To finish each of these examples requires solving a system of equations.In each,the equations involve only the first power of the variables.This chapter shows how to solve any such system. I.1 Gauss'Method 1.1 Definition A linear equation in variables x1,r2,...,In has the form a1T1+a2t2 a373++anIn =d where the numbers a1,...,an ER are the equation's coefficients and dER is the constant.An n-tuple (s1,s2,...,sn)ERm is a solution of,or satisfies, that equation if substituting the numbers s1,...,sn for the variables gives a true statement:a1s1 a2s2+...+ansn d. A system of linear equations a1,1x1+a1,2x2+…+a1,nEn=d1 a2,1T1+a2,2T2+…+a2,nxn=d2 am,1t1+am,2t2+·…+am,nxn=dm has the solution (s1,s2,...,sn)if that n-tuple is a solution of all of the equa- tions in the system. 1.2 Example The ordered pair(-1,5)is a solution of this system. 3x1+2x2=7 -x1+r2=6 In contrast,(5,-1)is not a solution. Finding the set of all solutions is solving the system.No guesswork or good fortune is needed to solve a linear system.There is an algorithm that always works.The next example introduces that algorithm,called Gauss'method.It transforms the system,step by step,into one with a form that is easily solved
2 Chapter One. Linear Systems ments C, H, N, and O in turn gives this system. 7x = 7z 8x + 1y = 5z + 2w 1y = 3z 3y = 6z + 1w To finish each of these examples requires solving a system of equations. In each, the equations involve only the first power of the variables. This chapter shows how to solve any such system. I.1 Gauss’ Method 1.1 Definition A linear equation in variables x1, x2, . . . , xn has the form a1x1 + a2x2 + a3x3 + · · · + anxn = d where the numbers a1, . . . , an ∈ R are the equation’s coefficients and d ∈ R is the constant. An n-tuple (s1, s2, . . . , sn) ∈ R n is a solution of, or satisfies, that equation if substituting the numbers s1, . . . , sn for the variables gives a true statement: a1s1 + a2s2 + . . . + ansn = d. A system of linear equations a1,1x1 + a1,2x2 + · · · + a1,nxn = d1 a2,1x1 + a2,2x2 + · · · + a2,nxn = d2 . . . am,1x1 + am,2x2 + · · · + am,nxn = dm has the solution (s1, s2, . . . , sn) if that n-tuple is a solution of all of the equations in the system. 1.2 Example The ordered pair (−1, 5) is a solution of this system. 3x1 + 2x2 = 7 −x1 + x2 = 6 In contrast, (5, −1) is not a solution. Finding the set of all solutions is solving the system. No guesswork or good fortune is needed to solve a linear system. There is an algorithm that always works. The next example introduces that algorithm, called Gauss’ method. It transforms the system, step by step, into one with a form that is easily solved
Section I.Solving Linear Systems 3 1.3 Example To solve this system 3x3=9 x1+5x2-2x3=2 5x1+2x2 =3 we repeatedly transform it until it is in a form that is easy to solve. 3T1+2x2 =3 swap row 1 with row 3 r1+5x2-2x3=2 3x3=9 x1+6x2 =9 multiply row 1 by 3 x1+5x2-2x3=2 3x3=9 r1+6x2 =9 add-1 times row 1 to row 2 -x2-2xg=-7 3xg=9 The third step is the only nontrivial one.We've mentally multiplied both sides of the first row by -1,mentally added that to the old second row,and written the result in as the new second row. Now we can find the value of each variable.The bottom equation shows that z3=3.Substituting 3 for r3 in the middle equation shows that z2=1. Substituting those two into the top equation gives that z1=3 and so the system has a unique solution:the solution set is [(3,1,3)}. Most of this subsection and the next one consists of examples of solving linear systems by Gauss'method.We will use it throughout this book.It is fast and easy.But,before we get to those examples,we will first show that this method is also safe in that it never loses solutions or picks up extraneous solutions. 1.4 Theorem (Gauss'method)If a linear system is changed to another by one of these operations (1)an equation is swapped with another (2)an equation has both sides multiplied by a nonzero constant (3)an equation is replaced by the sum of itself and a multiple of another then the two systems have the same set of solutions. Each of those three operations has a restriction.Multiplying a row by 0 is not allowed because obviously that can change the solution set of the system. Similarly,adding a multiple of a row to itself is not allowed because adding-1 times the row to itself has the effect of multiplying the row by 0.Finally,swap- ping a row with itself is disallowed to make some results in the fourth chapter easier to state and remember (and besides,self-swapping doesn't accomplish anything)
Section I. Solving Linear Systems 3 1.3 Example To solve this system 3x3 = 9 x1 + 5x2 − 2x3 = 2 1 3 x1 + 2x2 = 3 we repeatedly transform it until it is in a form that is easy to solve. swap row 1 with row 3 −→ 1 3 x1 + 2x2 = 3 x1 + 5x2 − 2x3 = 2 3x3 = 9 multiply row 1 by 3 −→ x1 + 6x2 = 9 x1 + 5x2 − 2x3 = 2 3x3 = 9 add −1 times row 1 to row 2 −→ x1 + 6x2 = 9 −x2 − 2x3 = −7 3x3 = 9 The third step is the only nontrivial one. We’ve mentally multiplied both sides of the first row by −1, mentally added that to the old second row, and written the result in as the new second row. Now we can find the value of each variable. The bottom equation shows that x3 = 3. Substituting 3 for x3 in the middle equation shows that x2 = 1. Substituting those two into the top equation gives that x1 = 3 and so the system has a unique solution: the solution set is { (3, 1, 3) }. Most of this subsection and the next one consists of examples of solving linear systems by Gauss’ method. We will use it throughout this book. It is fast and easy. But, before we get to those examples, we will first show that this method is also safe in that it never loses solutions or picks up extraneous solutions. 1.4 Theorem (Gauss’ method) If a linear system is changed to another by one of these operations (1) an equation is swapped with another (2) an equation has both sides multiplied by a nonzero constant (3) an equation is replaced by the sum of itself and a multiple of another then the two systems have the same set of solutions. Each of those three operations has a restriction. Multiplying a row by 0 is not allowed because obviously that can change the solution set of the system. Similarly, adding a multiple of a row to itself is not allowed because adding −1 times the row to itself has the effect of multiplying the row by 0. Finally, swapping a row with itself is disallowed to make some results in the fourth chapter easier to state and remember (and besides, self-swapping doesn’t accomplish anything)
Chapter One.Linear Systems PROOF.We will cover the equation swap operation here and save the other two cases for Exercise 29. Consider this swap of row i with row j. a1,1t1+a1,2x2+·a1,nxn=d1 a1,1T1+a1,2t2+…a1,ntn=d1 di,171+di,272+.di.nIn=di aj.11+aj,2x2+...aj.nIn dj → aj,171+aj.272+...aj.nIn=dj di,171+ai,272+...di,nIn=di am,11 am,272+.am,nIn dm am,1T1+am,22+..am,nIn dm The n-tuple (s1,...,sn)satisfies the system before the swap if and only if substituting the values,the s's,for the variables,the x's,gives true statements: a1,151+a1,2s2+…+a1,n5n=d1and..ai,151+a,2s2+…+a,nsn=dand aj.181+aj,252+...+aj:nsn dj and...am,151+am,252+...+am,nsn dm. In a requirement consisting of statements and-ed together we can rearrange the order of the statements,so that this requirement is met if and only if a1.1s1+ a1.282+...+a1.nSn d1 and ..aj.1s1+aj,282+...+aj:nsn dj and... ai,181+ai,252++ai,nsn di and...am.151 am,282+...+am,nsn dm. This is exactly the requirement that (s1,...,sn)solves the system after the row swap. QED 1.5 Definition The three operations from Theorem 1.4 are the elementary reduction operations,or row operations,or Gaussian operations.They are swapping,multiplying by a scalar or rescaling,and pivoting. When writing out the calculations,we will abbreviate row i'by 'pi'.For instance,we will denote a pivot operation by kp:+pj,with the row that is changed written second.We will also,to save writing,often list pivot steps together when they use the same pi. 1.6 Example A typical use of Gauss'method is to solve this system. x+y=0 2x-y+3z=3 x-2y-z=3 The first transformation of the system involves using the first row to eliminate the x in the second row and the z in the third.To get rid of the second row's 2x,we multiply the entire first row by -2,add that to the second row,and write the result in as the new second row.To get rid of the third row's x,we multiply the first row by-1,add that to the third row,and write the result in as the new third row. x+y=0 -2p1十P2 -3y+3z=3 -P1+P3 -3y-2=3
4 Chapter One. Linear Systems Proof. We will cover the equation swap operation here and save the other two cases for Exercise 29. Consider this swap of row i with row j. a1,1x1 + a1,2x2 + · · · a1,nxn = d1 . . . ai,1x1 + ai,2x2 + · · · ai,nxn = di . . . aj,1x1 + aj,2x2 + · · · aj,nxn = dj . . . am,1x1 + am,2x2 + · · · am,nxn = dm −→ a1,1x1 + a1,2x2 + · · · a1,nxn = d1 . . . aj,1x1 + aj,2x2 + · · · aj,nxn = dj . . . ai,1x1 + ai,2x2 + · · · ai,nxn = di . . . am,1x1 + am,2x2 + · · · am,nxn = dm The n-tuple (s1, . . . , sn) satisfies the system before the swap if and only if substituting the values, the s’s, for the variables, the x’s, gives true statements: a1,1s1+a1,2s2+· · ·+a1,nsn = d1 and . . . ai,1s1+ai,2s2+· · ·+ai,nsn = di and . . . aj,1s1 + aj,2s2 + · · · + aj,nsn = dj and . . . am,1s1 + am,2s2 + · · · + am,nsn = dm. In a requirement consisting of statements and-ed together we can rearrange the order of the statements, so that this requirement is met if and only if a1,1s1+ a1,2s2 + · · · + a1,nsn = d1 and . . . aj,1s1 + aj,2s2 + · · · + aj,nsn = dj and . . . ai,1s1 + ai,2s2 + · · · + ai,nsn = di and . . . am,1s1 + am,2s2 + · · · + am,nsn = dm. This is exactly the requirement that (s1, . . . , sn) solves the system after the row swap. QED 1.5 Definition The three operations from Theorem 1.4 are the elementary reduction operations, or row operations, or Gaussian operations. They are swapping, multiplying by a scalar or rescaling, and pivoting. When writing out the calculations, we will abbreviate ‘row i’ by ‘ρi ’. For instance, we will denote a pivot operation by kρi + ρj , with the row that is changed written second. We will also, to save writing, often list pivot steps together when they use the same ρi . 1.6 Example A typical use of Gauss’ method is to solve this system. x + y = 0 2x − y + 3z = 3 x − 2y − z = 3 The first transformation of the system involves using the first row to eliminate the x in the second row and the x in the third. To get rid of the second row’s 2x, we multiply the entire first row by −2, add that to the second row, and write the result in as the new second row. To get rid of the third row’s x, we multiply the first row by −1, add that to the third row, and write the result in as the new third row. −2ρ1+ρ2 −→ −ρ1+ρ3 x + y = 0 −3y + 3z = 3 −3y − z = 3
Section I.Solving Linear Systems 5 (Note that the two pi steps-2p1 +p2 and-P1+p3 are written as one opera- tion.)In this second system,the last two equations involve only two unknowns. To finish we transform the second system into a third system,where the last equation involves only one unknown.This transformation uses the second row to eliminate y from the third row. E+y=0 -P2+P3 -3y+3z=3 -4z=0 Now we are set up for the solution.The third row shows that z=0.Substitute that back into the second row to get y=-1,and then substitute back into the first row to get x =1. 1.7 Example For the Physics problem from the start of this chapter,Gauss' method gives this. 40h+15c=1005/ApP40h+ 15c=100 -50h+25c=50 (175/4)c=175 So c=4,and back-substitution gives that h=1.(The Chemistry problem is solved later.) 1.8 Example The reduction Z+y+z=9 x+y+2=9 2x+4g-3z=1 -2p1+p2 2y-52=-17 3x+6y-5z=0 -3p1+P3 3y-8z=-27 -3/2e+pa x+y+ z=9 2y- 5z= -17 -(1/2)z=-(3/2) shows that z =3,y=-1,and x 7. As these examples illustrate,Gauss'method uses the elementary reduction operations to set up back-substitution. 1.9 Definition In each row,the first variable with a nonzero coefficient is the row's leading variable.A system is in echelon form if each leading variable is to the right of the leading variable in the row above it (except for the leading variable in the first row). 1.10 Example The only operation needed in the examples above is pivoting. Here is a linear system that requires the operation of swapping equations.After the first pivot x-y =0 T-y =0 2x-2y+z+2w=4-2p1±P2 z+2w=4 y+0=0 y+w=0 2z+w=5 2z+w=5
Section I. Solving Linear Systems 5 (Note that the two ρ1 steps −2ρ1 + ρ2 and −ρ1 + ρ3 are written as one operation.) In this second system, the last two equations involve only two unknowns. To finish we transform the second system into a third system, where the last equation involves only one unknown. This transformation uses the second row to eliminate y from the third row. −ρ2+ρ3 −→ x + y = 0 −3y + 3z = 3 −4z = 0 Now we are set up for the solution. The third row shows that z = 0. Substitute that back into the second row to get y = −1, and then substitute back into the first row to get x = 1. 1.7 Example For the Physics problem from the start of this chapter, Gauss’ method gives this. 40h + 15c = 100 −50h + 25c = 50 5/4ρ1+ρ2 −→ 40h + 15c = 100 (175/4)c = 175 So c = 4, and back-substitution gives that h = 1. (The Chemistry problem is solved later.) 1.8 Example The reduction x + y + z = 9 2x + 4y − 3z = 1 3x + 6y − 5z = 0 −2ρ1+ρ2 −→ −3ρ1+ρ3 x + y + z = 9 2y − 5z = −17 3y − 8z = −27 −(3/2)ρ2+ρ3 −→ x + y + z = 9 2y − 5z = −17 −(1/2)z = −(3/2) shows that z = 3, y = −1, and x = 7. As these examples illustrate, Gauss’ method uses the elementary reduction operations to set up back-substitution. 1.9 Definition In each row, the first variable with a nonzero coefficient is the row’s leading variable. A system is in echelon form if each leading variable is to the right of the leading variable in the row above it (except for the leading variable in the first row). 1.10 Example The only operation needed in the examples above is pivoting. Here is a linear system that requires the operation of swapping equations. After the first pivot x − y = 0 2x − 2y + z + 2w = 4 y + w = 0 2z + w = 5 −2ρ1+ρ2 −→ x − y = 0 z + 2w = 4 y + w = 0 2z + w = 5
Chapter One.Linear Systems the second equation has no leading y.To get one,we look lower down in the system for a row that has a leading y and swap it in. T-y =0 P2二g3 y+w=0 z+2D=4 2z+w=5 (Had there been more than one row below the second with a leading y then we could have swapped in any one.)The rest of Gauss'method goes as before. T-y =0 -2ps十P4 y+w=0 z+20=4 -3w=-3 Back-substitution gives w=1,z=2,y=-1,and x=-1. Strictly speaking,the operation of rescaling rows is not needed to solve linear systems.We have included it because we will use it later in this chapter as part of a variation on Gauss'method,the Gauss-Jordan method. All of the systems seen so far have the same number of equations as un- knowns.All of them have a solution,and for all of them there is only one solution.We finish this subsection by seeing for contrast some other things that can happen. 1.11 Example Linear systems need not have the same number of equations as unknowns.This system x+3y=1 2x+y=-3 2x+2y=-2 has more equations than variables.Gauss'method helps us understand this system also,since this x+3y=1 -2p1+P2 -5y=-5 -2p1+p3 -4y=-4 shows that one of the equations is redundant.Echelon form -(4/5)e2+ps 3y=1 -5y=-5 0=0 gives y=1 and x=-2.The 0=0'is derived from the redundancy. That example's system has more equations than variables.Gauss'method is also useful on systems with more variables than equations.Many examples are in the next subsection
6 Chapter One. Linear Systems the second equation has no leading y. To get one, we look lower down in the system for a row that has a leading y and swap it in. ρ2↔ρ3 −→ x − y = 0 y + w = 0 z + 2w = 4 2z + w = 5 (Had there been more than one row below the second with a leading y then we could have swapped in any one.) The rest of Gauss’ method goes as before. −2ρ3+ρ4 −→ x − y = 0 y + w = 0 z + 2w = 4 −3w = −3 Back-substitution gives w = 1, z = 2 , y = −1, and x = −1. Strictly speaking, the operation of rescaling rows is not needed to solve linear systems. We have included it because we will use it later in this chapter as part of a variation on Gauss’ method, the Gauss-Jordan method. All of the systems seen so far have the same number of equations as unknowns. All of them have a solution, and for all of them there is only one solution. We finish this subsection by seeing for contrast some other things that can happen. 1.11 Example Linear systems need not have the same number of equations as unknowns. This system x + 3y = 1 2x + y = −3 2x + 2y = −2 has more equations than variables. Gauss’ method helps us understand this system also, since this −2ρ1+ρ2 −→ −2ρ1+ρ3 x + 3y = 1 −5y = −5 −4y = −4 shows that one of the equations is redundant. Echelon form −(4/5)ρ2+ρ3 −→ x + 3y = 1 −5y = −5 0 = 0 gives y = 1 and x = −2. The ‘0 = 0’ is derived from the redundancy. That example’s system has more equations than variables. Gauss’ method is also useful on systems with more variables than equations. Many examples are in the next subsection