Math 2331 { Linear Algebra

1 echelon FormsMath 2331 Linear Row Reduction and echelon FormsJiwen HeDepartment of Mathematics, University of jiwenhe/math2331 Jiwen He, University of HoustonMath 2331, Linear Algebra1 / echelon FormsDefinition Reduction Solution Row Reduction and echelon FormsEchelon form and Reduced echelon FormUniqueness of the Reduced echelon FormPivot and Pivot ColumnRow Reduction AlgorithmReduce to echelon form (Forward Phase)then to REF (Backward Phase)Solutions of Linear SystemsBasic Variables and Free VariableParametric Descriptions of Solution SetsFinal Steps in Solving a Consistent Linear SystemBack-SubstitutionGeneral SolutionsExistence and Uniqueness TheoremUsing Row Reduction to Solve Linear SystemsConsistency QuestionsJiwen He, University of HoustonMath 2331, Linear Algebra2 / echelon FormsDefinition Reduction Solution TheoremEchelon FormsEchelon form (orRow echelon form )1 All nonzero rows are above any rows of all entry( left most nonzero entry) of a row is ina column to the right of the leading entry of the row above entries in a column below a leading entry are ( echelon forms)(a) 0 00 0 0 000 0 0 0 (b) 0 00 000 (c)

2 0 00 0 00 00 00 000 0 0 00 000 0 00 Jiwen He, University of HoustonMath 2331, Linear Algebra3 / echelon FormsDefinition Reduction Solution TheoremReduced echelon FormReduced echelon FormAdd the following conditions to conditions 1, 2, and 3 above:4. The leading entry in each nonzero row is Each leading 1 is the only nonzero entry in its (Reduced echelon form ) 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 Theorem (Uniqueness of the Reduced echelon form )Each matrix is row-equivalent to one and only one reduced He, University of HoustonMath 2331, Linear Algebra4 / echelon FormsDefinition Reduction Solution TheoremPivotsImportant Termspivot position:a position of a leading entry in an echelonform of the :a nonzero number that either is used in a pivotposition to create 0 s or is changed into a leading 1, which inturn is used to create 0 column.

3 A column that contains a pivot position.(See the Glossary at the back of the textbook.)Jiwen He, University of HoustonMath 2331, Linear Algebra5 / echelon FormsDefinition Reduction Solution TheoremReduced echelon form : ExamplesExample (Row reduce to echelon form and locate the pivots) 0 3 649 1 2 131 2 303 1145 9 7 Solutionpivot 145 9 7 1 2 131 2 303 10 3 649 pivot column 145 9 7024 6 60510 15 150 3 649 Possible Pivots:Jiwen He, University of HoustonMath 2331, Linear Algebra6 / echelon FormsDefinition Reduction Solution TheoremReduced echelon form : Examples (cont.)Example (Row reduce to echelon form (cont.)) 1 4 5 9 70 2 4 6 60 0 0000 0 0 50 1 4 5 9 70 2 4 6 60 0 0 500 0 000 Original Matrix: 0 3 649 1 2 131 2 303 1145 9 7 pivot columns:124 NoteThere is no more than one pivot in any row.

4 There is no morethan one pivot in any He, University of HoustonMath 2331, Linear Algebra7 / echelon FormsDefinition Reduction Solution TheoremReduced echelon form : Examples (cont.)Example (Row reduce to echelon form and then to REF) 03 66 4 53 78 5 893 912 9 615 Solution: 03 66 4 53 78 5 893 912 9 615 3 912 9 6153 78 5 8903 66 4 5 3 912 9 61502 44 2 603 66 4 5 Jiwen He, University of HoustonMath 2331, Linear Algebra8 / echelon FormsDefinition Reduction Solution TheoremReduced echelon form : Examples (cont.)Example (Row reduce to echelon form and then to REF (cont.))Cover the top row and look at the remaining two rows for theleft-most nonzero column. 3 912 9 61502 44 2 603 66 4 5 3 912 9 61501 22 1 303 66 4 5 3 912 9 61501 22 1 30000 14 ( echelon form )Jiwen He, University of HoustonMath 2331, Linear Algebra9 / echelon FormsDefinition Reduction Solution TheoremReduced echelon form : Examples (cont.)

5 Example (Row reduce to echelon form and then to REF (cont.))Final step to create the reduced echelon form :Beginning with the rightmost leading entry, and working upwardsto the left, create zeros above each leading entry and scale rows totransform each leading entry into 1. 3 912 9 0 901 22 0 70000 14 3 0 6 9 0 720 1 2 2 0 70 00 0 14 1 0 2 3 0 240 1 2 2 0 70 00 0 14 Jiwen He, University of HoustonMath 2331, Linear Algebra10 / echelon FormsDefinition Reduction Solution TheoremSolutions of Linear SystemsImportant Termsbasic variable:any variable that corresponds to a pivotcolumn in the augmented matrix of a variable:all nonbasic (Solutions of Linear Systems) 1 6 03 0 00 0 1 8 0 50 0 00 1 7 x1+6x2+3x4= 0x3 8x4= 5x5= 7pivot columns:basic variables:free variables:Jiwen He, University of HoustonMath 2331, Linear Algebra11 / echelon FormsDefinition Reduction Solution TheoremSolutions of Linear Systems (cont.)

6 Final Step in Solving a Consistent Linear SystemAfter the augmented matrix is inreducedechelon form and thesystem is written down as a set of equations,Solve each equationfor the basic variable in terms of the free variables (if any) in (General Solutions of Linear Systems)x1+6x2+3x4= 0x3 8x4= 5x5= 7 x1= 6x2 3x4x2is freex3= 5 + 8x4x4is freex5= 7(general solution)WarningUse only the reduced echelon form to solve a He, University of HoustonMath 2331, Linear Algebra12 / echelon FormsDefinition Reduction Solution TheoremGeneral Solutions of Linear SystemsGeneral SolutionThegeneral solutionof the system provides a parametricdescription of the solution set. (The free variables act asparameters.)Example (General Solutions of Linear Systems (cont.))x1= 6x2 3x4x2is freex3= 5 + 8x4x4is freex5= 7 The above system hasinfinitely many He, University of HoustonMath 2331, Linear Algebra13 / echelon FormsDefinition Reduction Solution TheoremExistence and Uniqueness QuestionsExample (Existence and Uniqueness Questions) 3x2 6x3+6x4+4x5= 53x1 7x2+8x3 5x4+8x5= 93x1 9x2+12x3 9x4+6x5= 15 In an earlier example, we obtained the echelon form .

7 3 912 9 61502 44 2 60000 14 (x5= 4)No equation of the form 0 =c,wherec6= 0, so the system systemwith free variables= infinitely many He, University of HoustonMath 2331, Linear Algebra14 / echelon FormsDefinition Reduction Solution TheoremExistence and Uniqueness QuestionsExample (Existence and Uniqueness Questions)3x1+4x2= 32x1+5x2=5 2x1 3x2=1 34 3255 2 31 3 4 30 130 00 3x1+ 4x2= 3x2= 3 Consistent system,no free variables= unique He, University of HoustonMath 2331, Linear Algebra15 / echelon FormsDefinition Reduction Solution TheoremExistence and Uniqueness TheoremTheorem (Existence and Uniqueness)1A Linear system is consistent if and only if the rightmostcolumn of the augmented matrix is not a pivot column, , ifand only if an echelon form of the augmented matrix has norow of the form [ ](wherebis nonzero).

8 2If a Linear system is consistent, then the solution containseithera unique solution (when there are no free variables) orinfinitely many solutions (when there is at least one freevariable).Jiwen He, University of HoustonMath 2331, Linear Algebra16 / echelon FormsDefinition Reduction Solution TheoremUsing Row Reduction to Solve Linear SystemsUsing Row Reduction to Solve Linear Systems1 Write the augmented matrix of the the row reduction algorithm to obtain an equivalentaugmented matrix in echelon form . Decide whether thesystem is consistent. If not, stop; otherwise go to the row reduction to obtain the reduced echelon the system of equations corresponding to the matrixobtained in step the solution by expressing each basic variable in termsof the free variables and declare the free He, University of HoustonMath 2331, Linear Algebra17 / echelon FormsDefinition Reduction Solution TheoremConsistency QuestionsExample (a)What is the largest possible number of pivots a 4 6 matrix canhave?

9 Why?Example (b)What is the largest possible number of pivots a 6 4 matrix canhave? Why?Jiwen He, University of HoustonMath 2331, Linear Algebra18 / echelon FormsDefinition Reduction Solution TheoremConsistency Questions (cont.)Example (c)How many solutions does a consistent Linear system of 3 equationsand 4 unknowns have? Why?Example (d)Suppose the coefficient matrix corresponding to a Linear system is4 6 and has 3 pivot columns. How many pivot columns does theaugmented matrix have if the Linear system is inconsistent?Jiwen He, University of HoustonMath 2331, Linear Algebra19 / 19