Algebra 54 - Gaussian Elimination

Hello. I'm Professor Von Schmohawk and welcome to Why U. In the last several lectures, we saw how augmented matrices allow us to represent systems of linear equations in a compact, easy-to-manipulate form. We also introduced the three elementary row operations "swap" , "scale", and "pivot" which are used to simplify augmented matrices. The process of matrix simplification using these elementary row operations is sometimes referred to as "row reduction". In this lecture, we will introduce a process of row reduction called "Gaussian elimination" named in honor of the German mathematician, Carl Friedrich Gauss. Using Gaussian elimination, the augmented matrix is reduced to "row echelon form". This simplified form of the augmented matrix corresponds to a simpler system of equations with the same solutions as the original system. These simpler equations can then be easily solved using a substitution process which we will see later in this lecture called "back substitution". But before we introduce Gaussian elimination let's see what it means for an augmented matrix to be in row echelon form. Matrices in row echelon form must satisfy several requirements. The first requirement is that the left-most nonzero entry in each row called the row's "leading entry" must be "one". The entries to the right of the leading entry can have any value, zero or otherwise. The second requirement is that each row's leading entry must lie to the right of the leading entry in the row above it. And the third requirement is that any rows which contain all zeros must be positioned at the bottom of the matrix. Some Algebra texts do not include the requirement that leading entries must be "one" in order for a matrix to be in row echelon form. However, in these lectures we will follow the convention that in row echelon form all leading entries must be "one". Since in row echelon form each leading entry must lie to the right of the leading entry above it the zeros below the leading entries will typically form a stair-step pattern at the bottom of the matrix. Let's take a look at some examples of matrices in row-echelon form and see why this happens. Since a leading entry is the left-most non-zero entry in its row all entries which lie to the left of the leading entry must be zero. And since in row echelon form each leading entry lies to the right of the leading entry above it the zeros below the leading entries typically form a stair-step pattern at the bottom of the matrix. Because of this, all the entries below each leading entry will be zero. Since augmented matrices can have different dimensions the zeros may step down in different ways. Once a matrix has been put in row echelon form no column will contain more than a single leading entry although some columns may contain no leading entries. This means that it is possible for some leading entries to be positioned more than one column to the right of the leading entry above. However, in this lecture we will be working with matrices where each leading entry will fall one column to the right of the leading entry above it. Now that we have seen what matrices in row echelon form look like let's see how the process of Gaussian elimination works. So let's start with a system of linear equations and create the augmented matrix which represents this system. We will now use Gaussian elimination to reduce this augmented matrix to row echelon form. In the process of Gaussian elimination we work from left to right starting with column one and modify the entries in each column working from top bottom until the matrix is in row echelon form. So to reduce this matrix to row echelon form we start with the top entry of column one and using elementary row operations, change this entry to a "one". When we do this, keep in mind that there are usually a number of different ways to use row operations to accomplish the same result but some ways may be easier than others. For example, one way to make this entry a "one" would be to use a scale operation to multiply row one by one-half. Or we could use a pivot operation to add negative one times row three to row one replacing row one with the sum. Or we could use a pivot operation to add one-third times row two to row one. However, since the bottom entry of the first column is a one we can simply use a swap operation to exchange rows one and three. As we saw in the previous lecture we notate that we are swapping rows one and three by writing "R subscript one" and "R subscript three" separated by a double-headed arrow. It is a good practice to notate each step so that later we can remember the sequence of steps used to accomplish the matrix transformation. Now that the leading entry of row one is a "one" we need to change the entries below that entry to zeros. Starting with the entry in row two we can zero this entry by using a pivot operation to add three times row one to row two replacing row two. The other entries in row two will also change but this doesn't matter. All we care about at this point is making the first entry in row two zero. We notate this pivot operation by writing "R subscript two" plus three times "R subscript one" followed by an arrow and "R subscript two" indicating that three times row one is added to row two with the sum replacing row two. So let's perform the pivot operation. We start by multiplying row one by three and add the result to row two replacing row two with the sum. Now that the entry below the one is zero the entry below that must also be changed to zero. We can accomplish this by using another pivot operation to add negative two times row one to row three replacing row three. We notate this by writing "R subscript three" minus two times "R subscript one" followed by an arrow and "R subscript three". Multiplying row one by negative two and adding that multiple of row one to row three we replace row three with the result. Now that all the entries below the one in the first column are zero we move on to the second column. The leading entry of row two is now located to the right of the leading entry of row one so we need to change this leading entry to "one". This can be accomplished using a "scale" operation to multiply row two by one-fifth. As we saw in the previous lecture this is notated by writing one-fifth times "R two" followed by an arrow and "R two". Multiplying row two by one-fifth changes the leading entry of the second row to a "one". Now we must change the entry below that leading entry to zero. This can be accomplished with another pivot operation adding negative four times row two to row three replacing row three. We notate this pivot operation by writing "R three" minus four times "R two" followed by an arrow and "R three". Multiplying row two by negative four and adding that multiple of row two to row three we replace row three with the result. Now that the entry below the "one" in the second column is zero we move on to the third column. The matrix is now almost in row echelon form. Each leading entry is located to the right of the leading entry above it. To complete the process, we only need to change row three's leading entry to "one". This can be accomplished by using another "scale" operation to multiply row three by negative one-third. We notate this by writing negative one-third times "R three" followed by an arrow and "R three". Multiplying row three by negative one-third gives us a "one" as the leading entry of the third row. Now that all the leading entries in the matrix are ones and each leading entry is located to the right of the leading entry above it this matrix has been reduced to row echelon form. The process which we just used to transform the augmented matrix into an equivalent matrix in row echelon form is Gaussian elimination. Now, we will see how the system of equations corresponding to this matrix can be solved using the process of back substitution. To solve this system, we start by writing the equations which correspond to this augmented matrix. As we saw in the lecture "An Introduction to Matrices" each row of the augmented matrix is a shorthand representation of one equation in a system of linear equations. The entries in each column to the left of the vertical line are the coefficients of the variables in those equations. Since there are three columns to the left of the vertical line the corresponding system of equations contains three variables which we will call "x" "y" and "z". The entries in the column to the right of the vertical line are the constant terms on the right side of each equation. Using these numbers, we can create the equations which correspond to this augmented matrix. Terms in the equations with zero coefficients can then be eliminated along with coefficients with a value of "one". We can now see why equations which correspond to matrices in row echelon form are generally easier to solve. Since the last equation tells us the value of z that value can be substituted into the second equation, eliminating z in that equation. With z eliminated, the second equation can now be solved for y. Subtracting four from both sides we see that the value of y is negative seven. And now that we know the values of y and z those values can be substituted into the first equation to eliminate y and z. Adding 16 to both sides gives us the value of x. This process, working backwards through the equations to eliminate variables until each equation contains only a single variable is called "back substitution". And once we have obtained the solution it is always a good idea to plug these values back into the original equations to confirm that our answers are in fact a common solution to all three equations. So we have seen that when using Gaussian elimination we work from left to right and top to bottom, changing one column at a time. Although there is typically more than one way to accomplish this the general procedure is to use elementary row operations to insure that each column contains no more than one leading entry. We must also make sure that the leading entries are ones positioned to the right of the leading entries in the rows above and that all the entries below the leading entries are zeros. If a column contains more than one leading entry then we pick one leading entry to keep and if necessary, use a swap operation to move it to the correct position in the column. If that entry is not a one then we can use either a scale or pivot operation to make it a one. The entries below that one are then changed to zeros, using pivot operations. Now let's quickly review the steps we used to transform this matrix into row echelon form. Initially, column one contained three leading entries. Since the leading entry in row three was a "one" we picked it as the leading entry to keep and used a swap operation to move it up to row one. We then needed to make the elements below it zero. We did this using two pivot operations. Once column one was in order we could then move on to column two. Column two contained two leading entries and so we decided to keep the leading entry in row two as the single leading entry in this column. We made this entry a "one" by using a scale operation and then zeroed the element in row three using another pivot operation. With column two in order we could then move to column three. Since this column contained only a single leading entry we only needed to change that entry to a one. Once again, this was accomplished using a scale operation thus completing the transformation of the array to row echelon form. We have seen that once Gaussian elimination has reduced an augmented matrix to row echelon form the system of equations can then be solved by converting the matrix back into equations which are now simpler and easier to solve using back substitution. Or, as we will see in the next lecture we can continue to use elementary row operations following a second row reduction process called "Gauss-Jordan elimination" which simplifies the matrix to the point that the solutions can be easily determined directly from the matrix without converting the matrix back into equations.

Channel: MyWhyU

Views: 194,780

Rating: 4.9209661 out of 5

Keywords: why u, whyu, Professor Von Schmohawk, educational, math, mathematics, Algebra, linear equation, simultaneous equations, systems of equations, systems of linear equations, solving systems of linear equations, matrix, matrices, augmented matrix, augmented matrices, elementary row operation, equivalent system, row reduction, Gaussian elimination, row echelon form, back substitution

Id: 2GKESu5atVQ

Length: 21min 20sec (1280 seconds)

Published: Fri Mar 25 2016