okay hello everyone um today we are going to continue with um um Okay great all right so today we are going to continue with um all factorization so let's start with that um okay so in this section we are going to cover in this video we are going to cover what is LU factorization and how do we get the LU factorization of a matrix and how we can use this factorization to um help us solve system of linear equations so essentially this video is broken down into those three parts so um the L in um LU factorization okay before I talk about that maybe uh to give you a good idea on what this um chapter is about when we talk about numbers we can split them up into factors right like uh 15 can be split up into um 5 * 3 20 can be split up into 5 * 4 so in a similar way um I guess this is not the best analogy because uh this is more analogous to uh matrix multiplication but um for LU factorization we are able to split our matrices into a product a product of lower um triangular matrices and upper triangular matrices so um yeah so let me um explain what this lower and upper triangular matrices are so this is the formal definition of um a upper triangular matrix and you can see that in page 112 but the intuitive idea is um let's see if I okay so the intuitive idea is um we call up a matrix upper triangular if everything above the main diagonal so this is the main diagonal of the matrix if everything below this is zero we call it upper triangular upper triangular matrix if everything below because the only nonzero values live above the above the um main diagonal and this has a triangle shape like this for this values sort of look like a triangle right so it's called a upper triangular matrix so an example for a 2x two matrix which is upper triangular is going to be like 1 2 3 4 5 6 0 0 0 something that's lower triangular would be 4 5 6 0 0 0 because we can look at um this is the main diagonal of a 3x3 matrix because these are entries a11 a 22 and a3 everything below this diagonal is a zero right so only the non the only non-zero values live above E main diagonal so it's called an upper triangular matrix and for this second case over here this is the main diagonal everything above the main diagonal are zeros the only nonzero values live below the main diagonal so this is a lower triangular matrix so this is to give you a good intuition on what upper and lower triangular matrices are and then um let's continue so um yeah so um many of this many of the many matrices I guess can be written in this way as a product of an um lower triangular matrix times an upper triangular matrix and this is a interesting thing because when you can factoriize the matrix as a product LU solving systems of linear equations becomes much simpler and we'll see that later on so this is the reason why we want to study the LU factorization essentially because everything above or below is a zero we only need half as many operations to find um uh compared to finding the reduced row echelon form all right cool so let's look at a intuitive way to uh get the LU factorization and we also want to take note that not all matrices would have this factorization available so let's look at example 2.66 so essentially we want to write a 2x2 matrix here in the LU form right so we want a lower triangular matrix multiplied to an upper triangular matrix to give you this 2x2 matrix and something I want to take note of is both the upper and lower triangular matrices have to be 2x2 that is their dimension and because we have a lower triangular matrix first everything above the main diagonal is a zero so this is going to be my this is going to be my generic representation of my lower matrix lower triangular matrix i guess I should add the triangle right lower triangular time upper triangular matrix and for my upper triangular matrix everything below the main diagonal is a zero and um so this is the generic form of a upper triangular matrix something I want to take note or something I want to address is for simplicity sake sake we let the diagonal values of the lower triangular matrix be one and that is returned um somewhere here this version is discussed here but sometimes the case where L has numbers other than one is other than one the main diagonal essentially What this is saying is when we talk about lower triangular matrices in generality the main diagonal can have any numbers okay it can have 1 2 3 or four or whatever number but for our sake in this uh section we are going to consider lower triangular matrix which has main diagonals consisting exactly of one and that's to make our computations easier okay so um yeah so what we need to do is we want to find values for we want to find values find the numbers x a b c such that this holds this expression here holds because once we do that we are able to write the given matrix in terms of the expression that we need as a product of a lower and upper upper triangular matrix so we get this intermediate expression over here when we perform matrix multiplication matrix matrix multiplication just to be more specific and from here all we have to do is match the pattern right let me clear the screen so it's not that messy so a is equal to zero b is equal to 1 this tells us that X A is equal to 1 but since we establish that A is zero that means X * 0 is 1 this can never happen right so this means that we cannot we can't write any um we we we can't write this given matrix as a product of the of a lower triangular and upper triangular matrix because that would result in something mathematically impossible so this means that there's no LU factorization so that is what we mean by when we say that um the method lacks generality because this does not apply to every um this does not apply to every um matrix we cannot find uh like not every matrix has a LU factorization form right okay so um but this also showcases um direct method like how can you directly find an LU factorization right so um yeah because uh all you have to do is you have the generic form of the lower multip uh lower triangular matrix you have the upper triangular matrix the generic form of that you do your matrix multiplication and you equal to whatever matrix you're given and then essentially you're solving a system of linear equations to find the unknowns so that is the direct method and now we are going to look at two possible methods to um uh find an LU factorization but before that we give you a condition which tells you whether a matrix has LU factorization and that condition is over here it turns out that matrices whose row echelon form that can be achieved without switching rows have an LU factorization so what this means is in other words matrices which only involve using row operations of type two or three that means you can multiply a row by a nonzero scaler or you can add multiple of one row to another these are the only two valid operations that you can use and if you can only use these two I should say if you can only use these two valid uh operations then you can obtain the row echelon form right so that's a this gives you a condition when you can find uh LU factorization This is a al factorization yep all right okay and then um let's look at an example so one so we looked at a 2x2 matrix earlier on now let's look at um 3x4 uh matrix given this matrix um before we want to write it down as a product of um um a lower triangular matrix multiplied to an upper triangular matrix so let's do that um so the idea is we're going to look at it directly um so let's do that okay so yeah um this is a generalization of the method that we used above so we are going to introduce the generic lower triangular matrix the generic upper triangular matrix and then the variables A B CDE E F H I J and XYZ are the ones that we we need to find and um uh second okay I just needed to realign my laptop uh okay so yeah so when we multiply the two matrices here we get this 3x4 matrix with all the unknown variables we are going to equate this matrix here with the given matrix element wise right so you can see for the first row A is equal to 1 D is equal to 2 H is equal to zero J is equal to two so this is by element wise comparison and when we move on to the second row X A is equal to 1 so we have x a equal to 1 which is written over here and because from the first row we know that a is equal to 1 this implies that x is equal to 1 and we can do that uh for each variable right we can do it um as we go down then we can um compute all of the numbers so with that we can find the LU factorization and uh this is a good step to have so this would allow you to see if all the computations that you performed earlier on are valid uh you didn't make any arithmetic error while doing the computations because if you multiply these two matrix because it's supposed to be equal to the given matrix make sure you get back the given matrix so that's a good um sanity check right so now we have discussed so the first method and this is called the method by inspection because um you're essentially brute forcing the um brute forcing and trying to get the value by inspecting the um the matrices element wise now we have a more um um uh um computationally cheaper method because um if you have a matrix that's like 5 by 10 then you would have a ton of variable to simplify right and the method the inspection method becomes very um tedious so this is sort of a shorter method um to uh get the LU factorization but again we need to remember matrices can only be written in this form if you can reduce it to its row echelon form without interchanging rows so this method only applies to matrices which satisfy this condition and if it does satisfy this condition we can do this multiplier method and just so I make it clear this condition must also be satisfied before you use the factorization by inspection method so this condition holds for both of these methods so the idea is um we are going to write um if this is my given matrix A I'm going to write down the following matrix here i * A where I is my identity matrix and A is my given matrix and the methodology is as follows i'm going to convert my A matrix into an upper triangular matrix and we do this by elementary operations and um again remember we we are not allowed to um interchange rows so all we can do is multiply any row by a non-constant zero non-constant K which is yeah non-zero constant K and we can only um add a multiple of one row to the other so um yeah um those are the only two operations that are valid and whenever you perform one of these two operations we are going to do the same operation on the matrix on the left we yeah we are going to perform the same operations on the matrix which is on the left right so uh for example um uh what they want to start with is they want to begin with the uh topmost row for the matrix on the right so this is the matrix on the right we are going to start with the topmost row the first column and we want to zero out all the entries below the first entry here so I want to zero out two andgative -2 here so what they do is um uh they take -2 * the top row and add it to the second row they take two * the top row and add it to the um yeah they take two * the top row and add it to the second row um to the matrix on the left so essentially the step that they here they're describing the step for the matrix on the right and here they are applying the step to the matrix on the left so essentially whatever you do on the right you also do on the left and for the second step they take two times the top row and add it to the bottom row uh bottom row in the matrix on the right and they do the same thing for the matrix on the left so we zero this out but at the same time we introduce these two nonzero constants here so eventually they continue the process until they have a upper triangular matrix on the left so with one more step we notice that we have this is the main diagonal for the matrix on the left and everything below the main diagonal is a zero right so this is an upper triangular matrix and we can stop here and when you stop here we notice something strange right because when we look at the matrix on the left this is the main diagonal everything above the main diagonal is a zero so this is an lower triangular matrix so somehow when we make the matrix on the right upper triangular the matrix on the left becomes lower triangular when we avoid swapping rows so at this point we're actually done so this is like the multiplier method to actually get your L factorization and now what we can do is we can um solve systems using L factorization and uh like I mentioned earlier why do people care about LU factorization it's because it allows quick solutions to systems of equations so let's look at how we can do that all right so um yeah let's say we want to find the solutions to this system of linear equations right linear equation right uh what we have learned so far is to write down the augmented matrix and then do our elementary row operations and then find what's the final answer but um the thing is this is computationally expensive and it turns out that the LU factorization can give us the solution quickly so this is how we do it um what they did was they already gave us the all factorization of our matrix um want to call this I guess yeah all right a okay so a matrix A is equal to this lower triangular matrix and this upper triangular matrix and what happens then so like what I wrote down here um this is what's originally given this is what's originally given but because the given matrix A can be written down as this LU factorization I can replace this matrix with my factorization over here and that would give me my lower triangular matrix times my upper triangular matrix time X vector X which is B so all I'm doing is just substitution i substitute matrix A with its factorization because we know that they are equivalent and once so now I'm going to introduce some notation i'm going to call my lower triangular matrix here L my upper triangular matrix U my vector of unknowns X which is what we want to find and my um constant vector um B right so I have L Ux= to B and now I'm going to let U * X= Y okay so um once we have y that means I can write down this entire expression here as l * y = b so instead of solving for x first let me solve for y okay so when I replace this entire thing with my vector y and because u is a 3x4 matrix and x is a 4x1 vector I get a 3x1 vector here which I'm going to call y and that's going to be represented as this column vector here this is my original L there's no changes to that so now we want to solve for this and if you're not sure where this is leading to you can think of this as a intermediary step and once we find and to give you a preview of what's happening next once we have found the values of y1 y2 y3 I'm going to solve ux equal to y so I'm breaking this down into like two systems of linear equations but the advantage is even though the system of linear equations increase and what I mean by that if I were to solve this directly I'm only solving one system of linear equation here I'm solving two first I'm solving ux = y uh sorry I'm going to solve um l y = b and then once I have found y i'm going to solve ux = to y to get x but even though I'm solving two sets of two systems here each system I'm cutting like half the half the entries in the matrices are zero so the amount of computation is actually halfed and it makes our life easier so let's see where this goes so when I want to solve for this you can see that y1 is just one then 4 * y1 + y2 gives you two so you can quickly get -2 for y2 and similarly you can get 2 for y3 and once you have found y our problem now reduces to ux = y and we know what's u we know what's y so all we have to do is find X Y and Z so breaking down into triangular matrices gives you a way to do back substitution if you remember this word back substitution we learned it in chapter one so if you do not remember it go look at that so it gives us a way to directly do back substitutions which is why it makes computation so easy so yeah and then now all we have to do is just solve this and then we can get our answer i'm going to skip the justification for the multiply uh multiplier method but if you're interested you can go take a look at it but with that uh we have ended our um our chapter 2 with LU factorization and from the next video on we are going to look at um determinance and talk about those stuff again if you have any questions you can email me if anything is unclear we can set up a zoom call um my office hours are flexible which is why I did not state any specific time i I wanted to keep it like more accommodating in a sense so if you you do need office hours just send me an email and we can find a time to meet through Zoom