4.2 RowReduction and Echelon Forms 45 Add 5/2 times row 2 to row 3, and add 3/2 times row 2 to row 4. 14 5-9-7 0 2 4-6 -6 0 0000 ® 0 0 0-5 0 ‘The matrix in (2) is different from any encountered in Section 1.1. There is no way to create a leading entry in coluran 3! (We can’t use row 1 or 2 because doing so would destroy the echelon arrangement of the leading entries already produced.) However, if ‘we interchange rows 3 and 4, we can produce a leading entry in column 4. Pivot Lod. 5 2h 0 2 4-6 \-6 0 0 0-40 General form: 0 0 00 0 Pivot columns cone ones ‘The matrix is in echelon form and thus reveals that columns 1,2, and 4 of A are pivot columns, = ; Pivot positions 0-3 |-6 4) 9 -1 2-103) 1 AS 2 3 ors 2 cei ReaD) 7 tit __t —_— pivor columns . A pivot, as illustrated in Example 2, is a nonzero number in a pivot position that is used as needed to create zeros via row operations. The pivots in Example 2 were 1,2, + 4=5, Notice that these numbers are not the same as the actual elements of A in the lighted pivot positions shown in (3). ‘ith Example 2 as a guide, we are ready to describe an efficient procedure for transforming a matrix into an echelon or reduced echelon matrix. Careful study and mastery of this procedure now will pay rich dividends later in the course. The Row Reduction Algorithm ‘The algorithm that follows consists of four steps, and it produces a matrix in echelon form. A fifth step produces a matrix in reduced echelon form, We illustrate the algorithm by an example. EXAMPLE 3 Apply elementary row operations to transform the following matrix first into echelon form and then into reduced echelon form: 03-66 4 -5 , (957 8-38 9 339 12-9 6 Is SOLUTION STEP 4 Begin with the leftmost nonzero column, This position is at the top, is a pivot column. The pivot4g CHAPTER 4 Linear Equations in Linear Algebra ee er 3-9 12-9 6 45 3 ee ee ees LL Pivot column STEP 2 Select a nonzero entry inthe pivot coluran as a pivot, p neg, rows {0 move this entry into the pivot position, essary, Geacaeasaiaerauemensnammimseees Mae STEP 3 Use row replacement operations to create 2eos inal Positions below ‘ low iva. As a preliminary step, we could divide the top row by the i Pivot, 3, column 1, itis just as easy to add —1 times row Ito row 9 oh PU Wis pret 12 ~9 6 15 OED SE ta eg Det Sebo 4k ‘STEP 4 Cover (or ignore) the row containin above it, Apply ‘steps 1-3 to the submatrix that remains, Repeat the process url there are no more nonzero rows to modify, ' the pivot position and cove alrows ify, With row 1 covered, step 1 shows that column 2 is the next pivot column se Select as a pivot the “top” entry in that column, Pit 3-9 je 9 6 15 0 2 4 2-6 0 3 6 6 4-5 {_ Now pivot column at ing the “tp” 109 OT For step 3, we could insert an optional step of dividing to the ow belo the pivot, 2. Instead, we add —3/2 times the “top” row 3-9 2-9 68 Ona ts 0. .0....0—.14.2 Row Reduction and Echelon Forms 47 ‘When we cover the row containing the second pivot position for step 4, we are left with ‘@ new submatrix having only one row: 3-9 12-9 6 15 0 2-4 4 2-6 0 0 0 0 144 a Steps 1-3 require no work for thi 4 for this submatrix, and we have reached an echelon form of the full matrix. If we want the reduced echelon form, we perform one more step. STEP 5 pertain com ate With the rightmost pivot and working upward and to the left, create © each pivot. Ifa pivot is not 1, make it 1 by a scaling operation. The ri vot isi 6 aan Biot is in row 3. Create zeros above it, adding suitable multiples of row 3-9 12 -9 0 =9] +Row1+(-6)-row3 0 2-4 4 0-14] + Row2+4(-2)-row3 0 0 00 1 4 The next pivot is in row 2, Scale this row, dividing by the pivot. 3-9 12-9 0 -9 0 1-2 2 0-7] Row scaled by } GO eS 1 oe Create a zero in column 2 by adding 9 times row 2 to row 1. 30-6 9 0-727) —Row1+(9)-r0w2 0. 8 2208 a7 Orie vou 4 Finally, scale row 1, dividing by the pivot, 3. 10-2 3 0 -24] Row scaled by } o 1-2 2.0 -7 OO Ugly ‘This is the reduced echelon form of the original matrix. . The combination of steps 1-4 is called the forward phase of the row reduction algorithm. Step 5, which produces the unique reduced echelon form, is called the back- ward phase. NUMERICAL NOES? oa] 2 above, a computer program usually selects as a pivot the entry in a he largest absolute value. This strategy, called partial pivoting, rs in the calculations. In step column having #! is used because it reduces roundoffAlgebra 418 CHAPTER 4 Linear Equations in Linear Algebs Solutions of Linear Systems ‘The row reduction algorthit leads directly to an ex; lit description of is appli the i tert When the algorithm is applied to the. augmented ai, oT ato arstvadigl, ton Gp sugmented matrix of liner ont changed into the equivalent reduced echelon form * pen < NOs ay a oO 114 | 000 0 | There ae thee variables because the augmented matix be fou associated system of equations is ina " -3n=4 a+ xe | oe : The variables xy and '2 corresponding to variables? The other variable, xs, is calle Whenever a system is consistent, a explicitly by solving Pivot columng in the i the reduced system | the free variables, Thi | | i imatix da free variable, “reset ig sin (4), the solution se can Of equations forthe basic a ha is operation is possible because the ne felon Fong gach basic variable in one and only one equating 1 (4), solve the st eiiaign { andthe second fr a (Ignores thintequnton offers Ho restriction ome t= 14525 satay 6 | is free \ ‘The statement “x is free” 1 i Y Value for 35, Oa alues for xy and x3, For instance, wien »the solution is (6,3,1), Ech life Of the system, ad every solain of +0); when x3 = choice of xs determines a (diffrent) solution stem is determined by a choice of xy EXAMPLE 4 Fing the general solution of the linear system whose tix has been reduced to NS es ao a eee 08 22g 7h 3 [S109 2-8 0 OO gegen og 9 0.0 0 f 0 Le eat a Flo $k eet Sloat 4 0 OD Oe a o 9,0 Some texts use ig espond tothe columns the tem leading variables because they correspond entces,4.2 Row Reduction and Echelon Forms 19 ‘There are five Variables because the augmented matrix has six columns. The associated system now is x1 +6x2 +3x4 =0 mode = 5 © =7 The pivot columns of the matrix are 1,3, nd 5,0 the basic variables are x),x3, and x5. ‘The remaining variables, x2 and x4, must be free, Solve for the basic variables to obtain the general solution: [ey = ~6x2 — 3x4 2 is free xy = S+ 4x5 a x4 is free ws =7 Note Whgt the value of x is already fixed by the third equation in system (6). “ Parametric Descriptions of Solution Sets ‘The descriptions in (5) and (7) are parametric descriptions of solution sets in which the free variables act as parameters. Solving a system amounts to finding a parametric description of the solution set or determining that the solution set is empty. Whenever a system is consistent and has free variables, the solution set has many parametric descriptions. For instance, in system (4), we may add 5 times equation 2 to equation 1 and obtain the equivalent system mt5e2 9 =21 mtxys 4 We could treat x2 as a parameter and solve for x; and x3 in terms of x2, and we would have an accurate description of the solution set. However, to be consistent, we make the (arbitrary) convention of always using the free variables as the parameters for describing a solution set. (The answer section at the end of the text also reflects this convention.) ‘Whenever a system is inconsistent, the solution set is empty, even when the system has free variables. In this case, the solution set has 1o parametric representation. Back-Substitution Consider the following system, whose augmented matrix in reduced echelon form: xt — 7x2 + 2x3 — Sag + 8x5 = 10 xy — 3x3 + 3xy4+ x5 =-5 a-ase 4 in echelon formn but is not ‘A computer program would solve this system by baek-substitution, rather than by com- puting the reduced echelon form. That is, the program would solve equation 3 for xs in orme of xs and substitute the expression for 2x4 into equation 2, solve equation 2 for x25 fand then substitute the expressions for x2 and x4 into equation 1 and solve for 21 ‘Our matrix format for the backward phase of row reduction, which produces the re- duced echelon form, has the same number of arithmetic operations as buck-substitution, But the discipline of the matrix format substantially reduces the likelihood of errorsi i erg 20 CHAPTER 4 Linear Equations in Linear Algebre hhand computations. The best strategy is to use cg system The Study Guide that accompanies suggestions for performing row operations accurately a only the 1 W this tet ind rapial luce, Shey Offer oy yt vent NUMERICAL NOTE In genera, the forward phase of row reduction takes ugh, backward phase, An algorithm for solving a system is usual’ PEt, (or floating point operons). A flop is one arithmeie Me yt on two real floating point numbers For an nx (n mao tn to echelon form can take 2n*/3 + 17/2 ~7n/6 flops Gwhion 2 te on 2n3/3 flops when n is moderately his a Targe—say, n > 39), 4, 5 *PPtoxi reduction to reduced echelon form needs at most 1? flops. futhey Existence and Uniqueness Questions Although & nonreduced echelon form is a just the tight device for answering two fundamental questions Poor tool for solvin, 'S & system, tis j Posed in Sesion 1° EXAMPLE 5 Determine the existence and ‘uniqueness of the solutions io the sian 3X2 — 6x3 + 6x4 + 4xs = ~5 3x1 — Tea + 8x5 — Sku + Br, 3x1 — 9x2 + 123 — 9x4 + 6x5 = 15 SOLUTION The augmented matrix of this system was row reduced in Bxample3i) 3-9 12-9 6 15 0 2 -4.4 2-6 a [20-020 0, dnd The basic Variables are x), x2, and 2x5; the free variables are x and xy, Theeism equation such as 0 = 1 that would indicate an inconsistent system, so we cud ut back-substitution to find a solution, But the existence of a solution is already st (8). Also; the solution is not unique because there are free variables. Each cite d i i 5 aint choice of x3 and x4 determines «different solution. Thus the system has infinite " solutions. wi When a systemis in echelon form and contain no equation ofthe » nonzero, every nonzero equation contains a basic variable with anoti Either the basic variables are completely determined (with no free . fre vt one of the basic variables may be expressed in terms of on€ OF MAA Tiny a the former case, there is a unique solution; in the latter case solutions (one for each choice of values for the free variables). ‘These remarks justify the following theorem. joractian OO and sl ja ecause addition of Traditionally, a flop was only a multiplication oF divisiun, beea! rameter Ae a ‘time and could nored. The definition of flop given here is pret (pati 1, 2nd ee ( Computer urchitecture. See Golub and Van Loan, Matrix Computation Hopkins Press, 1989), pp. 19-20.4.2 RowReduction and Echelon Forms 24. THEOREM 2 Existence and Uniqueness Theorem A linear system is consistent if and only if the rightmost column of the ‘augmented matrix is nor a pivot column—that is, if and only if an echelon form of the ‘augmented matrix has no row of the form (0. F 5] withb nonzero Ifa linear system is consistent, then the solution set contains either (}) a unique solution, when there are ng free variables, ot (ii) infinitely many solutions, when there ig at least one free variable, ‘The following procedure outlines how to find and describe all solutions of a linear system, iy USING ROW REDUCTION TO SOLVE A LINEAR SYSTEM 1, Write the augmented matrix of the system, 2, Use the row reduetion algorithm to obtain an equivalent augmented matrix in echelon form. Decide whether the system is consistent, If there is no solution, stop; otherwise, go to the next step, 3. Continue row reduction to obtain the reduced echelon form. 4, Write the system of equations corresponding to the matrix obtained in step 3, §. Rewrite each nonzero equation from step 4 so that its one basic variable is ‘expressed in terms of any fiee variables appeering in the equation. PRACTICE PROBLEMS 1. Find the general solution of the linear system whose augmented matrix is 1-3-5 0 o 1-1-1 2. Find the general solution of the system xy 2x, — xy + 3x4 0 H2x; + 4a + Say — Seq = 3 3x, = 6x2 = 6x5 + 8x4 = 2 Suppose a 4 x 7 coefficient matrix for a system of equations has 4 pivots Is the e system consistent? If the system is consistent, how many solutions are there? Sn 1,2 EXERCISES ne ————— In Bxercisen 1 and 2, determine which matrices are in reduced ‘echelon form and which others are only in echelon form. 10 0 0 ee ° ia O40 Op be[O oo kd oa eo-o coma4 Linear Equations in Linear Algebra ‘22. CHAPTER 4 10° 8 fetes Oael 0 ooo iets Cas tae Before og 0 0 100 0 i 10 0 elo 1.1 0 oo! lt gt too Jel 00212 8 ayo 0 0 0 3 0000 0 ‘Row reduce the matrices in Exercises 3 and 4 to reduced echelon form, Circle the pivot positions in the final matrix and in the nd lst the pivot columns. Tas 4 1594155, a[4 5 67 4/3 5 7 9 67 8 9. is ee ey: 5, Describe the possible echelon formis of @ nonzero 2x2 matrix. Use the symbols ®, », and 0, as in the first part of Example 1 6, Repeat Exercise 5 for a nonzero 3 x 2 matrix. Find the general solutions of the systems whose augmented ma- trices are given in Exercises 7-14, 40007 7 010 13 45g 4113 fe 1 a1 os “ »[ L243 ] M5672 2] the system is consiste the solution is unique. ss a fo 0 . 0 0 8 blo o [? § ef a | O mw « H, %., 2 Battie eg be 10 0 m 4 Oo - no & In Exercises 17 and 18, determine ‘mattis is the augmented matcix taco thay, eas 1 ei SAP Gch desc, 18, i - 3] 2 Jn Exercises 19 and 20, choos end ksh €@)n0 solution, (2) a unique solution and) nay separate answers for each part, lt, thea i W. mth =2 20, 4x, + 8m =k M+ 3y=2 Iu thse Jn Exercises 21 and 22, mark each statement True ore jj each answers " 21. a. In some cases, a matrix may be row reduel ome than one matrix in reduced echelon form, wig ies sequences of row operations. bb. The row reduction algorithm applies only to agers Plies ony toa ‘matrices for a linear system. ¢. A basic variable in a linear system is a vari te + corresponds. a pivot column inthe costes mu #" Finding a parametric description of the solution tlt Jinear system is the same as solving the system. ©. Tfone row in an echelon form ofan augmented ms is[0 0 0 5 0}, them the associated lew se" inconsistont, The echelon opm of amatrixis unique; '. The pivot positions in a matrix depend ov iE interchanges are used in th ow ein , Reducing a matrix to echelon forms el Phase ofthe row reduction PO igs d. Whenever a system has free varibles contains many solutions, - ©. A general solution of a system is an os of all solutions of the system. jena a an fora 300 23. Suppose a 3 x 5 eaefficient matrix 10 A a hy pivot columns, Is the system consistent jus bas 03 X50, 24. Suppose a sysiem of Tinear equations hn 181 ‘matrix whose fifth column is a piv consistent? Why (or wiy not)? Tyee many ‘Truefalse questions ofthis type will ppest MPa fect li vers wate dacrBed wxtast BO ion Lt it a