For more information, please see full course syllabus of Linear Algebra

For more information, please see full course syllabus of Linear Algebra

### Solutions of Linear Systems, Part 1

Lecture Slides are screen-captured images of important points in the lecture. Students can download and print out these lecture slide images to do practice problems as well as take notes while watching the lecture.

- Intro 0:00
- Reduced Row Echelon Form 0:29
- An m x n Matrix is in Reduced Row Echelon Form If:
- Reduced Row Echelon Form 2:58
- Example: Reduced Row Echelon Form
- Theorem 8:30
- Every m x n Matrix is Row-Equivalent to a UNIQUE Matrix in Reduced Row Echelon Form
- Systematic and Careful Example
- Step 1
- Step 2
- Step 3
- Step 4
- Step 5
- Step 6
- Example 30:39
- Find the Reduced Row Echelon Form of a Given m x n Matrix

### Linear Algebra Online Course

### Transcription: Solutions of Linear Systems, Part 1

*Welcome back to educator.com, today we are going to be continuing our study of linear algebra, and we are going to be discussing solutions of linear systems part 1.*0000

*This lesson is going to consist of a couple of very, careful, systematic, slow examples of something called elimination in order to put a matrix into something called reduced row echelon form, so let's get started.*0012

*When we talked about linear systems earlier, we talked about the three things that we can do to a system of linear equations or a matrix, which is of â€˜course just a representation of that linear system.*0033

*We can switch two rows, we can multiply one row by a constant and we can ad multiples of one row to another row, all of these three create an equivalent system, which just is our way of manipulating the linear system to make it easier for us to handle.*0046

*Let's begin today's lesson by defining what we mean by reduced row echelon form, which is going to be the final form that we want to put a augmented matrix into.*0065

*Again an augmented matrix is just the system of linear equations, the coefficients of the linear systems, plus that extra column which is the solutions to that linear system.*0075

*We are going to manipulate that, we are going to put it into reduced row echelon form, so an M by N matrix is in reduced row echelon form.*0085

*We will often refer to it as just RRE, if the following holds, if all rows that are entirely 0, if there are any or at the bottom of the matrix.*0094

*If we, as we read from left to right, the first non-zero entry in a row is a 1, we call that the leading entry, has to be a 1.*0108

*If rows I and I + 1, so for example rows 3 and 4, if they both have leading entries, then the leading entry of the I + 1 row is to the right of the leading entry of row I.*0120

*In other words if I have two leading entries in row three and row four, the one on row four is going to be to the right, it's not going to be right below it or to the left of it.*0135

*All of these will make sense in just a moment when we give some examples of reduced row echelon form.*0143

*Now, if a column actually contains a leading entry of some row, then all of the other entries in the column R is 0, note a matrix in reduced row echelon form may not have any rows consisting of al 0's.*0149

*Reduced row echelon form doesn't mean that we have to have a row that's all 0's, it means that if it does, they need to be at the bottom of the matrix, okay let's look at some examples....*0166

*... So we have the matrix (1, 0, 0, 4, 0, 1, 0, 5, 0, 0, 1, 2), this is in reduced row echelon form.*0192

*Notice, this has a leading entry, it is a 1, everything else is a 0, this column has or this row has a leading entry, but notice it's to the right, that's what we meant by to the right.*0203

*It's to the right of that one, and every other entry in that column is 0, here this row also has a leading entry, it is a 1, it is to the left of these other two, and every other entry in there is a 0, and it doesn't matter what this is.*0217

*(4, 5, 2) this is not a leading entry, this is the leading entry of that row, these numbers are, they are not irrelevant, but as far as the definition of reduced row echelon, they are not important.*0234

*Let's take a look at another matrix (2, 1, 2, 0, 0, 2, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0) same thing.*0247

*We have a leading entry 0's along he column, this one, notice this is a 2 here and there's a (0, 0) here.*0264

*This is the leading entry we haven't run across yet, so itâ€™s okay that the 2 is here, it has nothing to do with the definition, but now we run, yes leading entry is a (1, 0, 0).*0276

*It qualifies, it's to the right of this one, the next row, we have a (1, 0, 0,) and it's to the right of these other two, so this one is in reduced row echelon form.*0286

*C will take (1, 0, 0, 3, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1) and we have a couple of rows of all 0's.*0301

*We have this nice big, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, , 5 by 5 matrix, let's see we have this 0 entries there at the bottom of the matrix that takes care of part A of the definition.*0319

*We have a leading entry in this row, it is a 1, that's nice, all of the other entries are 0, there's nothing in this column irrelevant.*0332

*There is a leading entry in this row and it is to the right of that one and all of the other entries are 0.*0340

*No leading entry, no leading entry, no leading entry, yes it satisfies the definition for reduced row echelon, so these three matrices are examples of matrices that are in reduced row echelon form.*0349

*Now let's take a look at a prime...*0366

*(1, 2, 0, 4, 0, 0, 0, 0, 0, 0, 1, -3) this matrix, it has a leading entry and other two entries are 0.*0373

*But you notice here, this row is the second row and yet it's on top of the row that's not all 0's, so this one is not in reduced row echelon form because this 0 row needs to be at the bottom.*0389

*let's take B prime, (1, 0, 3, 4, 0, 2, -2, 5, 0, 0, 1, 2) okay, in this particular case we take a look at the 1, it's a 0 entry.*0408

*The 0's are, the rest of the entries in the column are 0, here the leading entry, the first number that's non-zero is a 2, kit's not a 1, it has to be a 1for it to be in reduced row echelon form.*0424

*You can certainly take this entire row and divide it by 2, to get 1, -1, and five halves, and then you will almost be in reduced row echelon form, but as it stands, this is not reduced row echelon form.*0440

*Let's take (1, 0, 3, 4, 0, 1, -2, 5), let's take (0, 1, 2, 2) and let's take all 0's.*0457

*Okay, so we have a leading entry, which is nice, all of the other entries are 0's, very good, we have a leading entry which is a 1, it is to the left of, I'm sorry to the right of this one, it's the other, the one above it is to the left of it, so far so good.*0472

*But this other entry here in this column is a 1, it's not a 0, it needs to be a 0, so as it stands this one is not reduced row echelon form.*0491

*Okay...*0504

*... Very important theorem, every M by N matrix, every M by N matrix is row equivalent to a unique matrix in reduced row echelon form, which means that no matter what M by N matrix I give you, with the three operations of exchanging rows...*0512

*Multiplying a row by a constant, non-zero constant, and multiplying a multiple of, or adding a multiple of one row to another row, with those three operations handled over and over and over again, you can convert it to a reduced row echelon matrix. *0535

*That is unique, that's what's really interesting, later on we will talk about something called Gaussian elimination and it's the slightly, less detailed version of what it is that we are going to be doing today.*0551

*And it usually suffices for most purposes in linear algebra, but the matrices that you end up with are not unique.*0564

*What makes reduced row echelon fantastic is that, even if you and your friend and another friend do a whole bunch of different operations, in the end you'll end up with the same matrix, there is only one matrix that's in reduced row echelon form for any given matrix.*0571

*That's actually kind of extraordinary when you think about it, so now we are going to go through a very systematic and careful example.*0585

*We are not going to prove the uniqueness, but this example will actually show how you come across the, how you transform the particular matrix into reduced row echelon form.*0592

*Okay, so let's start off with our matrix, and again I am not going to be putting the brackets on there, simply because there is a whole bunch iof extra writing that we want to avoid.*0603

*(0, 2, 3, -4 and 1) (0, 0, 2, 3, 4), (0, 0, 2, 3, 4), (2, 2, -5, 2, 4) (2, , 2, -5, 2and 4).*0613

*Excuse me, my 4 sometimes look like 9, and (2, 0, -6, 9 and 7), okay, so this is the matrix we started off with, this is the one that we want to convert to reduced row echelon form, that's what we want, that's our goal.*0633

*And we will check to see that all the properties of RRE are satisfied, okay so step 1...*0651

*... You want to identify...*0662

*... The first column...*0671

*... Which is not all o's, so in this case we go here leading from left to right, this column, right (0, 0, 2, 2,), it's the first column that are not all 0's, okay.*0679

*Again, very systematic step 2, find...*0697

*... The first...*0705

*... Non-zero entry in that column...*0710

*... By the way, this column is called a pivotal column, and the first entry that you find, which is right there...*0719

*... First column is the first entry going down, that's non-zero, that's actually called the pivot, so in our first series of steps, 2 is our pivot.*0734

*Okay...*0748

*... What we are going to do here is we are going to take this row, this row and we are goign to interchange it with the first row, so we want the row that has the pivot in it to be on top.*0754

*Okay, so I'll write out step 3, before I write the, step 3...*0770

*... Interchange if necessary, you don't necessarily have to do this, in this case we do have to, if necessary...*0785

*... The first row...*0799

*... With the row containing the pivot...*0804

*... When we do that, we end up with the following matrix (2, 2, -5, 2, 4, 0, 0, 2, 3, 4, 0, 2, 3, -4, 1, 2, 0, -6, 9 and 7.*0810

*All we have done is we have exchanged the first and the third rows, that was the one with the pivot, we put it on top, okay.*0832

*Now we are going to divide this first row, so let's make step 4...*0840

*... Divide the first row, what is now the first row, not the original first row, so these steps refer to the matrix that I just completed, so divide the first row, by its first entry.*0849

*In other words I am just trying to make this first entry a 1, so I am going to divide everything in this row by 2, so I end up with (1, 1, -5halves, 1, 2) and then I copy the other, (0, 0, 2, 3, 4, 0, 2, 3, -4, 1).*0865

*And (2, 0, -6, 9 and 7), so this is what I end up with, okay.*0890

*Next, I am going to, actually let me rewrite what I had before (1, 1, -5halves, 1, 2, 0, 0, 2, 3, 4, 0, 2, 3, -4, 1, 2, 0, -6, 9 and 7).*0903

*Okay....*0933

*.. We are going to take our fifth step, and that is we are going to do is we are going to, remember what we wanted to do, we just draw echelon form we wanted to get all of these 0, so we are going to add a multiple of this to this, to make it, to make this thing 0.*0936

*In other words we are going to multiply the first line by -2 added to the fourth row and see what we get, so step 5...*0950

*... Add -2 times first row...*0963

*... The fourth row, and then when we do that, so -2 times 1 is -2 + 2, so I'll leave everything else the same, nothing changes in the other rows.*0972

*(2, 3, 4, 0, 2, 3, -4, 1), this becomes 0, -2 times 1 is -2 + 0, we end up with -2...*0987

*... -2 times -5 halves is 5, 5 - 6, 5 - 6 is -1, -2 times 1 is -2, -2 + 9 is 7.*1005

*_2 times 2 is -4, -4 + 7 is 3.*1022

*Look what we have done, we have created a row with a leading entry of 1, everything else is 0, now I am going to put a little bracket here...*1029

*... My first row is done, now I am going to think about this matrix, I completely ignore this one, I never have to worry about the first row again.*1041

*Now step 6, well, this is the nice thing about it , we just repeat everything we just did, repeat steps 1 to 5 for this particular matrix here.*1049

*Okay, so what is it that we did, we found the first column that had the, that was not all 0's, this is all 0's so we go to this column, and in this column, we find the first entry that is non-zero, which is 2.*1064

*That's going to be our new pivot, okay, we take that pivot and we move it up to the top, and again we don't touch this one, we leave it alone so we exchange this row right here with this row.*1080

*Now we are talking about 1, 2, 3, so we are going to exchange rows 1 and 2, so now let's go ahead and write down that matrix.*1095

*Let me actually do a little arrow here, and I am going to say...*1104

*... Switch 2 and 3, I am sorry, so we are still talking about the entire matrix, so we are going to call this row 2, we are going to call this row 3, so we are going to switch 2 and 3.*1112

*And when we do that, the matrix we end up with is the following, we get of â€˜course the original (1, 1, -5 halves, 1, 2), we get (0, 2, 3 and -4, 1).*1124

*We get (0, 0, 2, 3, 4) we get (0, -2, -1, 7 and 3), okay.*1140

*Now, we want to take, remember what we did before, the next step, once we have this pivotal, the row with the pivot, I'll go ahead and circle the pivot, so we know what we did to it.*1151

*Now we want to go ahead and divide that by that number, everything in that row by that number to turn this into a 1.*1162

*We will divide...*1170

*... Row 2 by 2, which is the pivot, matrix we get is (1, 1, -5 halves, 1, 2) nothing changes, (0, 1, 3halves, -2 and 1 half)...*1176

*...Alright ...*1198

*... And we get the (0, 0, 2, 3, 4, 0, -2, -1, 7 and 3).*1202

*Now we have a leading entry of 1, and now we need to do is we need to get rid of...*1216

*... Did we make a mistake here?..*1230

*... See here, let us multiply...*1234

*... Two times the second row, added to this row to get rid of this and make it a 0...*1242

*... Let me see if I can squeeze this in here, (1, 1, -5 halves, 1 and 2, 0, 1, 3 halves, -2, 1 half, 0, 0, 2, 3, 4).*1254

*Half...*1275

*... Okay...*1278

*1...*1283

*... Let me see here...*1288

*... And let me go, so we will do negative, yes we will do +2 times this row + this row, so we will end up with 0 here.*1294

*+2 times 1 is 2 - 2 is 0, +2 tim3s 3 halves is 3, 3 - 1 will end up giving me a 2, + 2 times -2 is 4.*1303

*-4, -4 + should be +3 and +2 times 1 half is 1, 1 + 3 is 4.*1320

*Okay, so I am going to go ahead and copy this onto the next page here...*1331

*(2, 3, 4, 2, 3, 4), so we have something to continue with, alright, so we have got (1, 1, -5 halves, 1, 2, 0, 1, 3 halves, -2, 1 half, 0, 0, 2, 3, 4).*1337

*We have (0, 0, 2, 3, 4), okay, let's see what is the best way to handle this one next.*1362

*Let's go ahead and continue with our process, so now we are dealing with, well...*1375

*... The couple of things that we can do here, you notice, so we have a leading entry, we have all 0's in this column, we have a leading entry here, 0's down here, not a 0 up here.*1388

*We have a choice, we can go ahead and take care of this 0, and 0 this out now and then deal with what's left over, the ones that don't have leading entries or we can go ahead and continue the process and get leading entries all the way down and then go back and take care of all the other 0's.*1398

*I think I am going to go ahead and do that, it's more little bit more consistent with the process that we had done, so now this stays, this stays.*1417

*We will leave those two alone, now we are just dealing with this one, so again we repeat those steps that we did before, (0, 0) this is the first column non-zero entries.*1425

*And the first entry is here, so now our pivot is here, and notice we don't have to do anything, we don't have to switch anything, it's already at the top, so since the pivot is there, we can go ahead and divide by 2...*1436

*... We will divide row 3 by 2 to make it a 1, which turns everything into (1, 1, -5 halves, 1 and 2, 0, 1, 3 halves, -2, 1 half, 0, 0, 1, 3, halves)*1462

*And...*1485

*... 4 divided by 2 is 2, and then we have (0, 0, 2, 3, 4), okay so now I am going to go...*1490

*... I am going to go this way just to create a little bit more room, what I am going to do here is I am going to take -2 times this row added to this row, in order to turn this into a 0, so we wil do...*1509

*... -2 times the third row + the fourth row.*1527

*And what I end up with is (1, 1, -5 halves, 1, 2, 0, 1, 3 halves, -2, 1 half, 0, 0, 1, 3 halves, 2, 0).*1537

*When you multiply this out so, -2 times that + that is 0, -2 times that + that, you end up with -3 + 3 is 0, -2 times that is -4 + 4, you end up with this matrix right here.*1558

*Again we are getting down to where we want it, we have the all 0's down to the bottom, we have leading entries, now we just have to take care of these other 0's to make sure everything else is 0 in the entries that have, in the columns that have leading entries as 1.*1575

*Okay, so let's see, let's do...*1588

*... Let's get rid of...*1598

*... Let's get rid of this 3 halves first, which means I am going to take 3 halves, -3 halves times this row to this row, so let me write own what it is that I am doing.*1602

*We have -3 half times the third row + the second and when I do that, I end up with...*1611

*... (1, 1, -5 halves, 1, 2, 0, 1, 0, -17 fourths, -5 halves, 0, 0, 1, 3 halves 2) and of â€˜course the bottom one is all 0's.*1626

*Now I am going to get rid of...*1648

*... This 5 halves, so I am going to multiply 5 halves times the third row...*1652

*... + the first row, that will give me (1, 1, 0, 19 fourth, 7, 0, 1, 0, -17 fourths, -5 halves 0, 0)*1662

*(3 halves, 2) and of â€˜course the final 0's...*1687

*... Now, let's see what we have got, I am going to create a little bit more space here, this time, I'm going to, so I have taken care of this and this are fine, now I just have this one to take care of, so I am going to multiply...*1695

*-1, oops, -1 times the second row...*1713

*... + the first row and when I do that I get (1, 0,), let me do this one actually specifically -1 times 1 is -1 + 1 is 0.*1720

*-1 times 0, 0 + 0, 0, -1 times -17 fourths + 19 fourths, you end up with 19 fourths + 17 fourths, 36 fourths, which is 9.*1739

*And then the same thing here, -1 times 5 halves is 5 halves + 7, you end up with 19 halves, 0, 1, 0, -17 fourth, -5 halves.*1754

*Here you get (0, 0, 1, 3 halves and 2, 0, 0, 0, 0, 0).*1772

*This, my friends is our final...*1783

*... Reduced row echelon, my apologies for these little marks with the pen here, so the matrix that we started off with through series of operations was converted to this unique reduced row echelon matrix, okay this is unique.*1788

*It's the only matrix that you'll end up with, notice we have adding entry 1, all 0's leading entry 1 is to the right of this one, all 0's, leading entry 1, it's to the right, all 0's.*1804

*No leading entry, so it doesnâ€™t matter what these are...*1818

*... Okay...*1825

*... Let's go ahead and do one more example, we will move a little but more quickly this time, again we are just doing the same operations that you are accustomed to....*1828

*... Let's take as our matrix (1, 2, 3, 9, 2, -1, 1, 8, 3, 0, -1, 3) okay.*1841

*Look for the first column, not all 0's, that's this one, the first non-zero entry here, our pivot is 1, we don't have to do anything to it, it's already at the top.*1860

*And we don't have to divide by it, it's already a 1, so all we have to do is turn this into a 0, and this into a 0, so I am going to do this in two steps, okay.*1868

*I'll go ahead and let you do the, what we are going to be dealing is multiplying -2 times the first row + the second, -2 times that, plus that to turn this and do with 0.*1879

*And the second step we are going to do is -3 times the second row...*1892

*...-3 times the first row, of â€˜course the first row...*1900

*... Times the first row + the third, so -3 times that + that, so I am going to do it in two steps, I'm going to combine it and just give the final matrix that we get.*1908

*We should end up with (1, 2, 3, 9, 0, -5, -5, -10, 0, -6, -10, -24), so we have taken care of this one.*1918

*This is done, now we want to deal with that, so our pivot here, we look for the first column that's non-zero entry, that's here.*1936

*We will look for the first entry from top to bottom, so our new pivot is -5, so what we want to do is we want to divide everything in here by that number to turn this into a 1.*1949

*We will go ahead and...*1961

*We have (1, 2, 3, 9), we have 0, 1, -5 divided by -5, 1, -5 divided by 2, and we have 0, -6, -10, -24.*1969

*Okay, so now let me move up...*1989

*... Here, I want to get rid of this, make it a 0, I want to make 0's, everything underneath, so I am going to multiply 6 times...*1995

*... The second row + the third, so I end up with the matrix 1, oops...*2013

*... We don't want these, too many of these stray marks to confuse is, my apologies.*2023

*(1, 2, 3, 9) and the we are going to have (0, 1, 1, 2) and we are going to have (0, 0, -4, -12) okay.*2030

*We find a new pivot, so in this particular case, we have taken care of that, our new pivot is now -4, because this were always done, this were always done.*2051

*We have leading entries of 1 and 1, we can take care of the other's layer, who want to work our way down from the top-left to the bottom right.*2061

*We go ahead and divide this by -4, the whole thing by -4, so let me move on to the next page...*2069

*... And rewrite this...*2079

*... We started off with (1, 2, 3, 9, 0, 1, 1, 2, 0, 0, -4, -12) okay.*2083

*We divide the third by -4, to get (1, 2, 3, 9, 0, 1, 1, 2, 0, 0, 1 and 3).*2099

*Now we have that and now we just, now we have our 1, we have our 1, we have our 1, we need to convert this to (0, 0) and we need to convert this to 0.*2118

*Lets go ahead and take...*2129

*Lets do this in a couple of steps, let's go...*2135

*â€¦ -1 times the third row + the second...*2139

*... And we will do -3 times the third row, -3 times the third row + the first...*2149

*... And when we do that we end up with (1, 2, 0, 0, 0, 1, 0, -1, 0, 0, 1, 3).*2161

*And now what we want to do is we want to get rid of this 2, so we are going to take -2, times the second.*2182

*We are going to add it to the first, and what we are going to end up with is (1, 0, 0, 2, 0, 1, 0, -1, 0, 0, 1, 3).*2195

*Now we check the leading entry, leading entry, right goes to the right, these are all 0's, these are 0's, these are 0's no leaving entry problems here, this is irrelevant.*2212

*Our final...*2225

*... Reduced row echelon matrix is this matrix (1, 0, 0, 2, 0, 1, 0, -1, 0, 0, 1, -3), let's start it from our initial ones with series of those operations.*2229

*Find your pivotal column, find your pivot, move it to the top, divide by the pivot to make it a 1, eliminate all the 0's underneath that one.*2243

*Leave that row alone; move down to the next into the same thing.*2254

*Find the column that's not all 0's, find the first entry that's not a 0, that's your pivot, move it to the top, divide by it to turn it into alone.*2257

*Remove all the zeros, do that all the way down in a stereo step fashion, echelon is a Greek word for stereo step, which is why it's like that.*2267

*It moves in a stereo step from top-left to bottom right, and then once you get down to where you can't really go further, then you go back and you eliminate all the zero's above the ones, to get a unique matrix and reduced row echelon form.*2274

*Thank you for joining us today at educator.com, look forward to seeing you next time.*2290

1 answer

Last reply by: Professor Hovasapian

Sat Nov 15, 2014 10:28 PM

Post by Imran Malik on November 12, 2014

When you divided row 2 by 2 around 20 minutes in, could you not have just added that row with the 4th row to make turn the leading entry 2 of row 2 into a 0?

1 answer

Last reply by: Professor Hovasapian

Thu Nov 7, 2013 2:48 PM

Post by Eddie Chan on November 7, 2013

is there a lecture about smith normal form?

1 answer

Last reply by: Professor Hovasapian

Tue Nov 5, 2013 2:16 PM

Post by jawhara oukhija on November 5, 2013

Hi is RRE the same as Gauss Jordan? Thanks for clearing.

0 answers

Post by hajar maazia on July 5, 2013

does *

1 answer

Last reply by: Professor Hovasapian

Sat Jul 6, 2013 5:47 AM

Post by hajar maazia on July 5, 2013

i would like to ask you .. Dores RRE mean elementary matrices, because my professor didint talk at all about RRE instead he talked about elementary matrices. Thank you

1 answer

Last reply by: Professor Hovasapian

Mon Jun 3, 2013 2:33 AM

Post by Manfred Berger on June 2, 2013

Am I missing something essential here or is RRE the Upper Triangular Form with the leading entries normalized to one?

1 answer

Last reply by: Professor Hovasapian

Mon Feb 4, 2013 11:09 PM

Post by Cecilia Azurdia on February 4, 2013

CAN THE 1'S BE NEGATIVE?

1 answer

Last reply by: Professor Hovasapian

Fri Oct 5, 2012 3:45 AM

Post by Suhaib Hasan on October 5, 2012

So do all Matrices have an RRE form? If not, how do you find which ones have one and others that don't?

1 answer

Last reply by: Professor Hovasapian

Mon Jul 23, 2012 5:54 PM

Post by Winnie So on July 22, 2012

Hi Raffi, Is the 1 in the 5th column, 3rd row a leading entry? I thought it will be but am not too certain?

0 answers

Post by Mohammed Altannak on March 5, 2012

Looking Forowrd to see you next time =)

0 answers

Post by Jason Mannion on October 10, 2011

The only point of criticism I can give here is that there are no practice problems available for each lecture. That would be really nice. Besides that, these lessons are worthy of some of the highest praise.