CHAPTER 04.07: LU DECOMPOSITION: Finding Inverse of a Matrix Using LU Decomposition: Background

In this segment, we're going to look at how LU decomposition method is used to find the inverse of a matrix. So we're going to look at the background of this.  In a separate segment, we will talk about an example. So, if you are trying to find the inverse of a square matrix, let's suppose somebody gives you a square matrix, which is n-by-n square matrix, and you are trying to find the inverse of this particular matrix, what you are basically looking for is some matrix B, let's suppose, which, when you multiply it to A matrix, you're going to get the identity matrix. So that's what you are looking for when you are trying to solve the inverse of a matrix, or some matrix B which is multiplied to A which also gives you the identity matrix, it will be the same thing.  So let's suppose we are trying to look for . . . so what we are looking for is a B matrix when I multiply it to the A matrix that it gives me the identity matrix there. So what this implies is that in order to be able to do this I'll have to solve certain number of equations. 

So if I write down . . . write this down, what I'll have to do is I want to solve A, n-by-n, and what I can do is I can take the first column of the B matrix, which will be simply b11, b21, all they way up to bn1.  So I'm just going to take the first column of this B matrix which I am trying to find, because the B matrix is the inverse of the matrix which I am trying to find.  So that will be equal to, if I follow my matrix multiplication properly, this is an n-by-1 matrix. If I follow the matrix multiplication properly, then if I am taking the first column of this B matrix and multiplying it to A matrix, then that will give me the first column of this identity matrix, and that will be simply 1, 0, 0, all the way up to 0, which is also an n-by-1 matrix. So this is what's going to happen, is that in order to be able to find out the first column of the inverse of a matrix, I'll be solving this set of equations.  So what I'll be doing is that I'll be changing my A into L times U.  I'll be changing my A into L times U, so what I'll be doing is L times U multiplied by this will give me the identity matrix, 1, 0, 0, 0, 0, there.  So let me write this down here, so I'll have L times U times this B matrix which I have, b11 . . . not B matrix, but the first column of the B matrix, bn1, and will be equal to 1, 0, 0, 0, all the way up to 0.  So what this implies is that if I'm going to use LU decomposition method to find out the first column of the inverse of A which is the first column of the B matrix, then what I'll have to do is I'll have to solve L times Z equal to C, which will be 1, 0, 0, all the way up to this, and once I find out Z, I'll have to do U times X, or X is nothing but my first column of the B matrix, which is b11, b21, all the way up to bn1 will be equal to whatever I get for the Z matrix.  So that's how I'm going to find the first column of the inverse of the matrix, that I'm going to first solve the lower triangular matrix times some Z matrix, which I wanted to find, with the right-hand side being the first column of the inverse of the matrix, and then I'm going to put it . . . put that, whatever solution I get here, put that right here, this is the upper triangular matrix, and I'm going to . . . the solution vector will be the first column of the inverse of . . . inverse matrix. So that's how I'll be able to find the first column, so you can very well see that how this is going, that I can find out the second column and so on and so forth, so let me write down how I'm going to find the second column. 

The second column of the . . . of the B matrix, which is the inverse matrix, we found by this, that if I multiply the A matrix by the second column of the B matrix, which is the . . . which is the inverse matrix, it will be first row, second column, second row, second column, all the way up to nth row, second column will be equal to the second column of the identity matrix, which will be now 0 in the first column . . . first row, 1 in the second row, and then 0s throughout.  This will be an n-by-1, this will be an n-by-1, and this will be n-by-n.  So I'll follow the same methodology here, decompose A into L times U, which is already known to me, solve my L times Z equal to this right-hand side, once I have found Z, I'll say U times this matrix will be equal to the Z matrix, and that way I'll be able to find the second column.  So I will continue this . . . continue this process for . . . for all the n columns . . . for all the n columns of the B matrix. And we know that the B matrix is nothing but the inverse of A matrix.  So that's how we use LU decomposition method to find the inverse of a matrix.  In the next segment, in a separate segment, we will take an example to show how we find out the inverse of a matrix by using the LU decomposition method.  And that's the end of this segment.