The Gauss-Jordan Elimination Algorithm

1 DefinitionsThe AlgorithmSolutions of Linear SystemsAnswering Existence and Uniqueness questionsThe Gauss-Jordan Elimination AlgorithmSolving Systems of Real Linear EquationsA. HavensDepartment of MathematicsUniversity of Massachusetts, AmherstJanuary 24, 2018A. HavensThe Gauss-Jordan Elimination AlgorithmDefinitionsThe AlgorithmSolutions of Linear SystemsAnswering Existence and Uniqueness questionsOutline1 DefinitionsEchelon FormsRow OperationsPivots2 The AlgorithmDescriptionThe Algorithm in practice3 Solutions of Linear SystemsInterpreting RREF of an Augmented MatrixThe 2-variable case: complete solution4 Answering Existence and Uniqueness questionsThe Big QuestionsThree dimensional systemsA. HavensThe Gauss-Jordan Elimination AlgorithmDefinitionsThe AlgorithmSolutions of Linear SystemsAnswering Existence and Uniqueness questionsEchelon FormsRow Echelon FormDefinitionA matrixAis said to be inrow echelon formif the followingconditions hold1all of the rows containing nonzero entries sit above any rowswhose entries are all zero,2the first nonzero entry of any row, called theleading entryofthat row, is positioned to the right of the leading entry of therow above it,Observe.

2 The above properties imply also that all entries of acolumn lying below the leading entry of some row are HavensThe Gauss-Jordan Elimination AlgorithmDefinitionsThe AlgorithmSolutions of Linear SystemsAnswering Existence and Uniqueness questionsEchelon FormsRow Echelon FormSuch a matrix might look like this: a 0b 0 0 0c 0 0 0 0 0d ,wherea,b,c,d R arenonzeroreals giving the leadingentries, and means an entry can be an arbitrary the staircase-like appearance hence the wordechelon(from french, for ladder/grade/tier).Also note that not every column has a leading entry in HavensThe Gauss-Jordan Elimination AlgorithmDefinitionsThe AlgorithmSolutions of Linear SystemsAnswering Existence and Uniqueness questionsEchelon FormsRow Echelon FormA square matrix in row echelon form is called anupper 1 2 340 5 670 0 890 0 0 10 is a 4 4 upper triangular HavensThe Gauss-Jordan Elimination AlgorithmDefinitionsThe AlgorithmSolutions of Linear SystemsAnswering Existence and Uniqueness questionsEchelon FormsReduced Row Echelon FormDefinitionA matrixAis said to be inreduced row echelon formif it is in rowechelon form, and additionally it satisfies the following twoproperties.

3 1In any given nonzero row, the leading entry is equal to 1,2 The leading entries are the only nonzero entries in will often abbreviate row echelon form to REF and reduced rowechelon form to , we encountered the idea of reduced row echelon form of amatrix when we considered solving a linear system of equationsusing an augmented HavensThe Gauss-Jordan Elimination AlgorithmDefinitionsThe AlgorithmSolutions of Linear SystemsAnswering Existence and Uniqueness questionsRow OperationsConnection to Systems and Row OperationsAn augmented matrix in reduced row echelon formcorresponds to a solution to the corresponding linear , we seek an Algorithm to manipulate matrices toproduce RREF matrices, in a manner that corresponds to thelegal operations that solve a linear already encountered row operations, and these will be thedesired manipulations in building such an our initial goal is to reduce augmented matrices ofthe form Ab arising from a general real linear system, thealgorithms we describe work for any matrixAwith a HavensThe Gauss-Jordan Elimination AlgorithmDefinitionsThe AlgorithmSolutions of Linear SystemsAnswering Existence and Uniqueness questionsRow OperationsThree Elementary Row OperationsDefinitionGiven any matrixAletRiandRjdenote rows ofA, and lets Rbe a nonzero real number.

4 Then the elementary row operations are1We may swap two rows, just as we may write the equations inany order we please. We notate a swap of theith andjthrows of an augmented matrix byRi may replace a rowRiwith the row obtained by scaling theoriginal row by anonzeroreal number. We notate this bysRi7 may replace a rowRiby the difference of that row and amultiple of another row. We notate this byRi sRj7 HavensThe Gauss-Jordan Elimination AlgorithmDefinitionsThe AlgorithmSolutions of Linear SystemsAnswering Existence and Uniqueness questionsRow OperationsRow EquivalenceDefinitionTwo matricesAandBare said to berow equivalentif and only ifthere is a sequence of row operations notion is well defined and anequivalence relation. Inparticular, ifAis row equivalent toBthenBis row equivalent toA, since row operations are invertible.

5 And ifAis row equivalenttoB, andBis row equivalent toC, thenAis row equivalent toC,since we can concatenate sequences of row operations. (And ofcourse, trivially, every matrix is row equivalent to itself.)A. HavensThe Gauss-Jordan Elimination AlgorithmDefinitionsThe AlgorithmSolutions of Linear SystemsAnswering Existence and Uniqueness questionsRow OperationsA PropositionPropositionFor a given matrixA, there is a unique row equivalent matrix inreduced row echelon any matrixA, let s denote the associated reduced row echelonform byRREF(A). Gauss-Jordan Elimination Algorithm !Wait, what s that A. HavensThe Gauss-Jordan Elimination AlgorithmDefinitionsThe AlgorithmSolutions of Linear SystemsAnswering Existence and Uniqueness questionsPivotsLeading Entries and Pivot PositionsDefinitionApivot positionof a matrixAis a location that correspondsto a leading entry of the reduced row echelon form ofA, ,aijis in a pivot position if an only ifRREF(A)ij= column of a matrixAcontaining a pivot position is called apivot entry, or simply, apivotis a nonzero number in apivot position, which may be used to eliminate entries in itspivot column during number of pivot positions in a matrix is a kind ofinvariantofthe matrix, calledrank(we ll define rank differently later in thecourse, and see that it equals the number of pivot positions)

6 A. HavensThe Gauss-Jordan Elimination AlgorithmDefinitionsThe AlgorithmSolutions of Linear SystemsAnswering Existence and Uniqueness questionsPivotsPivoting DownWe are ready to describe the procedure forpivoting downward:DefinitionLetaijdenote the entry in theith row andjth column of anm nmatrixA. Supposeaij6= 0. Topivot downwardon the (i,j)thentryaijofAis to perform the following operations:(i.)1aijRi7 Ri,(ii.) For each integerk>i,Ri+k ai+k,jRi7 Ri+ more simply, make the nonzero entryaijinto a 1, and use this1 to eliminate (make 0) all other entries directly below the (i,j) HavensThe Gauss-Jordan Elimination AlgorithmDefinitionsThe AlgorithmSolutions of Linear SystemsAnswering Existence and Uniqueness questionsPivotsPivoting UpIn the Algorithm , we ll first pivot down, working from theleftmost pivot column towards the right, until we can nolonger pivot we ve finished pivoting down, we ll need topivot procedure is analogous to pivoting down, and works fromthe rightmost pivot column towards the left.

7 Simply apply rowoperations to use the pivot entries to eliminate entries in eachpivot column above the pivots. This is an algorithmic way toaccomplish back-substitution while working with HavensThe Gauss-Jordan Elimination AlgorithmDefinitionsThe AlgorithmSolutions of Linear SystemsAnswering Existence and Uniqueness questionsDescriptionOverview of the Algorithm - Initialization and Set-UpWe present an overview of the Gauss-Jordan Elimination algorithmfor a matrixAwith at least one nonzero : SetB0andS0equal toA, and setk= 0. Input the pair(B0,S0) to the forward phase, step (1).Important: we will always regardSkas a sub-matrix ofBk, androw manipulations are performed simultaneously on the sub-matrixSkand on its parent HavensThe Gauss-Jordan Elimination AlgorithmDefinitionsThe AlgorithmSolutions of Linear SystemsAnswering Existence and Uniqueness questionsDescriptionOverview of the steps - Forward Phase1 Given an input (Bk,Sk), search for the leftmost nonzerocolumn ofSk.

8 If there is none orSkis empty, proceed to thebackwards phase, step (5), with finding a nonzero column, exchange rows ofBkasnecessary to bring the first nonzero entry up to the top row ofSk(Any exchanges in this step alter bothBkandSk). Labelthe corresponding nonzero entry inBkbypk(for pivot).3 Pivot downwards onpkinBkto form matrixBk+ scope to the sub-matrixSk+1ofBk+1consisting ofentries strictly to the right and strictly belowpk. Repeat theprocedures in steps (1)-(3) with input (Bk+1,Sk+1).A. HavensThe Gauss-Jordan Elimination AlgorithmDefinitionsThe AlgorithmSolutions of Linear SystemsAnswering Existence and Uniqueness questionsDescriptionCompleting the Forward PhaseSo, one loops over the first four steps until all pivot columns havebeen located and pivoting down has occurred in each pivot matrixBkis in row echelon form, with leading 1s in eachpivot completes theforward phase.

9 And so thebackwards phasecommences with, step (5).A. HavensThe Gauss-Jordan Elimination AlgorithmDefinitionsThe AlgorithmSolutions of Linear SystemsAnswering Existence and Uniqueness questionsDescriptionOverview of the steps - Backwards Phase5 Start at the rightmost pivot ofBkand pivot up. Call theresultBk+ left to the next pivot column ofBk+1and pivot , and repeat this step until there are no matrixBkreturned by the previous step upon terminationis the outputRREF(A).A. HavensThe Gauss-Jordan Elimination AlgorithmDefinitionsThe AlgorithmSolutions of Linear SystemsAnswering Existence and Uniqueness questionsThe Algorithm in practiceA familiar 3 4 ExampleWe ll work with the augmented matrixA= 11161 2 364 5 612 from last entrya11= 1, so we can pivot down, using the rowoperationsR2 R17 R2andR3 4R17 R3.

10 Thistransforms the matrix into the row equivalent matrixB1= 11160 3 200 9 2 12 .A. HavensThe Gauss-Jordan Elimination AlgorithmDefinitionsThe AlgorithmSolutions of Linear SystemsAnswering Existence and Uniqueness questionsThe Algorithm in practiceA familiar 3 4 Example2 Ignoring the first row and column, we look to the 2 3sub-matrixS1= 3 20 9 2 12 .The top entry is nonzero, and so we may pivot first have to scale this entry to make it 1. In the matrixB1we would apply the row operation 13R27 R2. Then weeliminate the 9 below our pivot usingR3+ 9R27 R3. Theresult is the matrixB2= 1 1160 1 2/300 0 4 12 ,which is row equivalent HavensThe Gauss-Jordan Elimination AlgorithmDefinitionsThe AlgorithmSolutions of Linear SystemsAnswering Existence and Uniqueness questionsThe Algorithm in practiceA familiar 3 4 Example3We now consider the sub-matrixS2= 4 12.