Gauss-Jordan EliminationAugust 29, 2007IGoal: Given a system E of linear equations, find thesolution set S(E).IMethod: Find an equivalent system E0which is easy toanalyze. Since E and E0are equivalent, S(E) = S(E0). FindE0by combining equations to eliminate variables.ITechnique: Streamline the computation by writing theequations in matrix form, in which rows correspond toequations. Operations on the equations correspond to rowoperations on the matrix. The goal is to find E0in reducedrow echelon form.DefinitionsIA matrix is a rectangular array of numbers.IAn m × n matrix has m rows and n columns.IIf A is a matrix, the ijth entry aijof A is the entry in the ithrow and jth column.IA row vector is a matrix with just one row.IA column vector is a matrix with just one column.ISometimes we just say “vector” when we mean “columnvector.”A system of m linear equations in n unknowns can beabbreviated by an m × (n + 1) (augmented) matrix.Reduced row echelon formIA matrix is said to be zero if all its entries are zero.IIf R = (a1, . . . , an) is a nonzero row vector, its leading entryis its first nonzero entry, and its leading index ` is the placewhere this leading entr y occurs. Thus a`6= 0 and ai= 0 fori < `.IFor example, the leading entry of0 1 2 3 4is 1 andits leading index is 2.DefinitionA matrix A is in reduced row echelon form if it satisfies thefollowing conditions:1. All the nonzero rows are above all the zero rows.2. The leading entry of every nonzero row lies to the left ofthe leading entries of the nonzero rows below it.3. Every leading entry of ever y nonzero row is 1.4. Every leading entry is the only nonzero entry in the columncontaining it.A description in index notation.DefinitionAn m × n matr ix A is in reduced row echelon form if it satisfiesthe following conditions:1. Let r be the number of nonzero rows of A (so that0 ≤ r ≤ m). Then the first r rows of A are nonzero and theremaining rows are zero.2. Let `ibe the leading index of the ith row. Then`1< `2· · · < `r.3. For 1 ≤ i ≤ r, ai`i= 1.4. For 1 ≤ i ≤ r and 1 ≤ i0≤ m and i06= i, ai0,`i= 0.The solution set of a system in reduced row echelonform.Let E be a system of m equations in n unknowns. Suppose thecorresponding m × (n + 1) matrix is in reduced row echelonform. We can describe the solution set as follows.IIf the leading entry of the last nonzero row of A is in thelast column, the equations are inconsistent and there areno solutions.IThe variables (x`1, x`2, · · · , x`r) corresponding to theleading index columns are fixed, and the remainingvariables are free.IMore precisely, for 1 ≤ i ≤ r , the ith row of A correspondsto an equation which expresses x`iin terms of the freevariables.IThus, if the equations are not inconsistent, there are r fixedvariables and n − r free variables. Thus the solution sethas n − r “degrees of freedom.”Row operationsTheoremLet A be an m × n matrix.IThere is sequence of elementary row operations whichtransform A into a matrix A0in reduced row echelon form.IThe systems of equations E and E0corresponding to A andA0are equivalent, i.e, they have the same solution set.There are three kinds of elementary row operations:IAdd a multiple of some row to some other row.IMultiply a row by some nonzero number.IInterchange two rows.Notice that each of these operations can be undone by anoperation of the same type. Verify that the correspondingoperation on systems of equations does not alter the solutionset.SummaryTo solve a system E of m equations in n unknowns:IWrite the corresponding m × (n + 1)-matrix A.IPerform a sequence of row operations to obtain a matrix A0in reduced row echelon form.ILet E0be the system of equations corresponding to A0.Then E0and E have the same solution set, and E0can beeasily described.RemarkIn fact there is a well-defined algorithm that a computer (or you)can use to go from a matrix A to a matrix in reduced rowechelon form. Thus we can write rref (A), meaning that rref (A)is a well-defined function of A. But in fact more is true; anysequence of elementary row operation which yields a matrix inreduced row echelon form when applied to A will give the sameanswer. More precisely:TheoremLet A, A0, and A00be matrices. Assume that A0and A00are inreduced row echelon form and that both A0and A00can beobtained from A by a sequence of elementary row operations.Then A0= A00.pause The proof of this is theorem is not in the book. I mayhave time to explain it
View Full Document
Unlocking...