noc20-ma54-lec13 - Row Reduced Echelon Form (RREF) Continued

Alright, so recall that in the last class we learnt what was called the RREF, we have not yet been able to give an algorithm for that, so in this class we will give an algorithm for that and what we will see is that it has lots and lots of application as per the understanding of system of linear equations is concerned. So let us do what is called, so what we had learnt when solving the system of equation was the Gauss elimination method, we had learnt this Gauss elimination method and what was that Gauss elimination method, we had the matrix, you took the first one entry here which was a non-zero entry, non-zero entry, used it to make every entry here to be 0, so we made everything 0 here, alright that was the thing we did. The next thing we looked at the second entry, so we forgot about the first row and first column then we came to the 2, 2 entry of the new matrix, if this entry was non-zero we took this as a pivot and made everything 0, fine. If it turns out that this entry is 0, we can interchange 2 rows and then get a pivot and then proceed, alright that was the idea of Gauss elimination method but at each stage we just move down from the first row we went to the second row, second row to third row, third to fourth and so on, alright. So we just went down first to the second, second to third, third to fourth and so on till the mth row, this is the way we proceeded, alright and in the process we also looked at second column, third column and so on, fine. Now we would like to know what is called Gauss Jordan method, we want to understand what is called Gauss Jordan method, alright. So Gauss elimination method gave us the Ref row echelon form, alright. Now this method, Gauss Jordan method is going to give us the row reduced echelon form, alright. So therefore we need to be careful, so let me write the actual without doing any mistake the algorithm. So algorithm is, so I have a matrix A which is given to be a matrix which is, which has so may be m cross n with real entries or complex entries what it is, so A is m cross n matrix with real entries, fine. So first thing is our input is A, input A and what will be the output? Output will be Rref of A, so whatever we get final output will be the Rref of A, it will have all the properties of being Rref, alright. So this is the input, the first step that we are going to look or second step whatever you want to say is the A itself, A is itself the reason for us, now what is this reason? Reason means the place where I am going to work on, so for me initially it is a whole matrix which is the reason for me, the whole matrix, alright, whole matrix is the reason, alright. Now second, second, second, second, second, second, second, second, second, second, third, if all entries in the reason or which is same as the A, all entries in A are 0, a stop and this is the Rref, this is the Rref, alright. So we have stop, if all the entries become 0 for us, alright, fine, else, else find the left most non-zero column, so looking at the column, the first column, second column and so on and find its top most non-zero entry, alright. So what we do is that if the matrix has all entries 0, we have stop, we have the Rref, if it is not, else you can find the left most column, alright, which has a non-zero entry, in that column which has a non-zero entry, pick the top most non-zero entry, that entry is our pivot, take the, find its top most non-zero entry, this is our pivot, this is our pivot, alright, make this pivot 1, make it 1 by dividing by the number whatever it is by dividing, by dividing the required number, required number, alright. So what you are doing, we have non-zero entry, this has become a pivot, we have also made it 1, now put it as or interchange this with the first row, so interchange, so make this the first row, so make this row as our first row, use it to make every other entry in that column, column as 0, alright. So what we have done, I had look at this part, may be the first column consist of all 0s, alright, so first column is all 0, so you do not worry about it, it turns out that suppose that the second column, I have a non-zero entry here, all these entries are 0, so what do we do, first this is the pivot that I have, I multiply it by the number, put it back, so what I get now is a matrix which has 0 here, now there is a 1 here and I do not know what they are, some entries are there, I use this 1 to make every other entry 0 now, is that okay. Once I have done that, I forget about this part and this part, alright, the next stage that is at stage 4, alright, step 4, what we are going to have is that this becomes our new region, alright, so here we need to work on it, is that okay, so we go back to step 2 with this as our region and then do the algorithm again and again, fine, that is what the algorithm is about. So, let us take an example to understand it better, so example, so our matrix A is example, A is 0, 2, 3, 7, 1, 1, 1, 1, 1, 3, 4, 8, 0, 0, 0, 1, I have this, fine, so at present what we see here is that this has non-zero entry, so the region is whole of A and the first non-zero entry here for us is this, so this is the pivot that we are going to look at, so what we are supposed to do at the next stage is, so do not write A here because now the matrix is going to change, so it is going to look like 1, 1, 1, 1, 0, 2, 3, 7, 1, 3, 4, 8, 0, 0, 0, 1, fine, so what we have done exactly is we have interchanged the first and second rows, fine, at the next stage I already see that this entry is 0, we make to, need to make this entry 0, so we just look at what do we need to do, we need to replace the third equation by doing something with the first equation and what do we do, fine, this minus this, so minus 1, is that okay, which is same thing as looking at, if I from matrix point of view, if I look at here the matrix was 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, this was the matrix 4 cross 4 matrix on the left, here I need to do first row there is no change, so as it is second row there is no change, third row is minus 1 times the first row, third row is this and this is the fourth row that we are looking at, fine, this gives us the matrix 1, 1, 1, 1, 0, 2, 3, 7, 0, 3 minus 1 is 2, 4 minus 1 is 3, 8 minus 1 is 7, 0, 0, 0, 1, this is the matrix I get. So now at this stage we have taken care of this part, fine, so once you have taken care of this our new region is now only this part and we need to implement our algorithm only to this part, fine, so here what we see is that there is a 2 here, so we need to divide by 2, alright. So now we do the transformation which is the second row is being multiplied by 1 upon 2, so what I get is 1, 1, 1, 1, 0, 1, 3 by 2, 7 by 2, 0, 2, 3, 7, 0, 0, 0, 1, fine. At the next stage, oh I forgot to write the pivots here, this is a pivot for me, this was the pivot, these are the 2 pivots that I have, fine. Now I need to use this one to make this entry 0, the next entry is already 0, so I need to look at the third row is being replaced by, again the third row is being replaced by using the second row which is 1 here, so I have to put minus 2 here, fine. So it is just 1 as a pivot, 1, 1, 1, 0, 1, 3 by 2, 7 by 2, I am multiplying by 2 and subtracting, so I get here 0, 0, 0, 0 and the last one remains as it is which is this, fine. So here the matrix is going to be, there is no change in the first row, there is no change in the second row, the third row is being replaced by using the second row minus 2, 0, 0 and this is what I have, fine. Now what I see is that these 2, the last row is supposed to be the 0 row, so this is 0 row, it has to be the last row and therefore at this stage, this is my region that I am looking at, fine. And here 1 is here, so we need to interchange, so let us do that, so how do I interchange? So interchange is, interchanging the third and fourth row which is nothing but 1, 0, 0, 0, no change, third row there is a change and there is a change in the fourth row, so this is the matrix that I am looking at. And the corresponding entry here is 1, 1, 1, 1, 0, 1, 3 by 2, 7 by 2, 0, 0, 0, 1 and then 0, 0, 0, 0 and this is the pivot that I have, I have interchanged these 2. Now the idea is that I need to make, so this was in some sense our Gauss elimination method in some sense but making once here as such, fine. What we need to do is that we need to make every entry here to be 0 here, 0 here, sorry not here, 0 here and 0 here, 0 entry for non-pivots, this is what we need to do, alright. So what do I do? At this stage, let us use another ink, so I am going to write it at 1 go now, so what I am going to do is that I am going to use this one to make this entry 0 and this entry 0, fine. So I can multiply by, so I want to make this entry 0, the 2nd row, 2nd row is being replaced by 2nd row 3, fine and look at this 7 by 2 here, so I have to look at minus 7 by 2 here because there are 1 here, fine. So this will give me, this part will be 0, fine and I can get this also 0 by looking at E13 of minus 1, fine. I can do it together basically because every entry here is 0, fine. So when I subtract, when I multiply this by 7 by 2 and subtract nothing happens to the other 2 entries, fine. Similarly when I multiply this by 1 and subtract this will become 0 but these 2 entries will remain as it is, fine. So therefore I can do things at 1 go here itself, so I can write here 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 3 by 2, 0, 1, 1, 1, 0, alright and not only that you can also see that if I want to play with this now, I can play and there will not be any change in these 0s now, alright, fine. So at this stage, now I can do this, I want to make this entry 0, so the first row is going to be changed using the second one with a minus sign and I will get it as 1, 0, 1, 0, 0, 1, 3 by 2, 0, 0, 0, 0, 1, 0, 0, 0, 0 and these are the pivots that I have and you can see that these pivots, there are 3 pivots, so I get 1, 0, 0, 1, 0, 0, 0, 1, 0 and then 0, 0, 1 here, so I get I 3 because there were 3 pivots, alright. So please go through it very, very important that the 0 rows are at the bottom, the first non-zero entry are the pivots and they are 1 for us, fine and every other entry in that column is the 0 and because of that we are getting this, so this is very, very important that because of the condition that every other entry in the pivotal column is 0 implies that we get the requisite identity, fine and then we can write it as, so if I write this matrix as R, the final matrix as R, then R is nothing but just apply A was there, on A I applied E 1 2, then after E 1 2, I applied E 3 1 of minus 1, then I applied E 2 of half, then I applied E 3 2 of minus 2, then it was E 3 4, then it was E 3 4, then these 2 you can write it whatever way you want, E 2 3 of minus 7 by 2, E 1 3 of minus 1 and the last one is E 1 T of minus 1, fine. So I have applied so many elementary transformations, alright on A to get R, is that okay? Now if I look at these elementary matrices, they are product of elementary matrices as such they are invertible and we know that product of invertible matrices are invertible, so what we are saying is let me rephrase it in the next thing, what we are saying is that we have got this theorem which says that theorem, right that A is m cross n, let R be equal to R R E F of A, then there exists a sequence of elementary matrices says say E 1, E 2, E k such that R is equal to E 1, E 2, E k times A or we can say here is that either this or this is one, the second thing we can say is that I can take this matrix define P equal to let P is equal to E 1, E 2, E k, alright then R is equal to P times A and what is P? If I look at this matrix P, it is a product of elementary matrices, all of them are invertible, so the product is invertible hence P is also invertible, so nothing but P inverse is nothing but E 1, E 2, E k whole inverse which is E k inverse, E k minus 1 inverse, E 1 inverse, so P is also, so what we are saying is that if R is equal to R R E F of A, then there exists an invertible matrix P such that R is equal to P times A, alright. So I will be using this idea again and again that given a matrix A, if I want to look at the R R E F, then that R R E F is nothing but P times A for some invertible matrix P, I will not be writing it as product of elementary matrices, I will just say that I have an invertible matrix P, so that P times A is the R R E F, is that okay, that is very important for us and this also tells me that as a third remark I can say that if you look at this R R E F is nothing but obtained through elementary matrices, so the matrices A and R are row equivalent, so what was the definition of row equivalent? Go back to the definition it says that A and B are row equivalent if I can obtain one from the other by multiplying by left multiplying, alright or multiplying on the left by elementary matrices. So this is what we have got, we have obtained R through multiplying elementary matrices on the left of A and therefore the matrix A and R are row equivalent and the idea is that whenever you have row equivalence the solution set does not change, I am not proving it but I am just going to write this as a theorem that consider the system A X is equal to B if, so consider system this, it is augmented matrix, matrix is A B, fine. So if C D is row equivalent to A B then the system A X is equal to B and C X is equal to D have the same solution set, alright this is very important for us that whenever I go from one system to another system and the two systems are row equivalent, alright that is important row equivalent that I am applying matrices on the left, I am multiplying on the left by elementary matrices which are invertible matrices the solution set does not change, is that okay, fine. So the as a final thing would like to state here and I will use it again in the next class is what is called that this theorem which I will not be proving it which is also get very important that, so what happens is suppose you have matrix A which is in m which is an m cross n matrix if you just apply Gauss elimination or you just write the corresponding R e f if you compute R e f of A then it may happen that we may get different matrices depending on the pivots chosen. So what we are trying to say here is that if I look at my this matrix A it may happen that I have a pivot in the first row but if I have the pivot in the first row there is a huge number or there is a number which needs to be whose multiplication may result in lot of fractions, alright but there could be a row in which there are all ones as in the previous example if there are all ones if I have to subtract things or add things it becomes a bit much easier. So to do our process we may like to interchange fine different rows at whatever order we want and that will result in different types of matrices that I have, so we may get different row echelon forms for a given matrix A fine it turns out that that is not true as per as the R e f is concerned, so whatever way you compute your R e f of A whatever way you compute alright this matrix is unique alright. So in whatever way you compute whatever you do this matrix will always be unique and this is very very important we will be using this idea again and again that the R e f of a matrix R e f of a matrix is unique alright, so keep track of this is very important we will be using it again and again to understand lot of ideas alright, so please note that we will be using this R e f idea again and again, so keep track of that thank you.