Welcome to a lesson Matric LU
Decomposition Using Elementary Matrices.
The goal of LU Decomposition,
is to write matrix A, which is a square matrix,
as a product of matrix L and matrix U,
where matrix L is a lower triangular matrix
and matrix U is an upper triangular matrix.
Notice a lower triangular matrix
has zeros above the main diagonal.
And an upper triangular matrix
has zeros below the main diagonal.
All the other elements can be zero or non-zero.
In order for this product to be possible,
A must be able to be reduced to row-echelon form,
which is matrix U, without interchanging any rows,
and we should also note that L and U are not unique.
Let's develop the idea of how we're going to do this
based upon what we've already learned
about elementary matrices.
Our first goal is to start with matrix A
and then determine which elementary matrices
we would multiply by in order to
write matrix A as an upper triangular matrix.
So the product of a certain number
of elementary matrices and matrix A
is going to equal the upper triangular matrix.
And then if we solve this equation for A,
we know we'd have to multiply both
sides of the equation by the inverses
of these elementary matrices.
So that would give us this equation here,
where matrix A is equal to the product of
the inverse of these elementary matrices
and matrix U, but the product of
these inverse elementary matrices
will always be a lower triangular matrix
so we can let L equal the product of these inverses.
And this is what we need, to find
the LU decomposition of matrix A.
A is going to be equal to L times U,
where L, our lower triangular matrix
is a product of these inverse elementary matrices
and U is our upper triangular matrix.
I should mention that in the next video,
we will discuss a shorter method for determining
L and U without using elementary matrices.
Let's take a look at two examples, in this video,
using elementary matrices.
Let's start with the basic two by two matrix
to determine the LU decomposition.
To get this started, we know the product
of the two by two identity matrix and matrix A
is equal to the given matrix.
Now I want to write the given matrix
in upper triangular form.
Because we only have a two by two matrix,
that means we want this element here, to be zero.
Now, I'll determine what row operation we can perform
to have a zero in this position here.
And we'll perform that same row operation on
the two by two identity matrix
to determine our first elementary matrix.
Since the least common multiple of four and three is 12,
Let's replace row two with negative three times row one
plus four times row two.
So, if the first row would stay the same,
four and then negative 16
then we'll have negative three times four
plus four times three, that's zero.
And then, we'll have negative three times negative 16,
that's positive 48 plus four times negative eight,
or plus negative 32, that's going to be positive 16.
Now to determine the elementary matrix on the left
for this product we performed the same row operation,
we're going to perform this row operation
on this identity matrix.
So the first row's going to stay the same.
Second row is going to be
negative three times one plus zero, that negative three.
Here we'd have negative three times zero
plus four times one, that's four.
And since this matrix here is already
in upper triangular form,
we're actually done for this example.
This should be E sub one
times matrix A
is equal to matrix U, our upper triangular matrix.
But we still do have a little work
to determine the LU decomposition.
So again, this line here's
what we found on the previous slide.
Here's E sub one and here's our
upper triangular matrix U.
If we solve this for matrix A,
we would multiply both sides
by the inverse of E sub one, which we have here.
Now, I didn't show it, but this matrix here
is the inverse of E sub one.
And this is our upper triangular matrix again.
But notice the inverse of E sub one
is a lower triangular matrix,
so we can let L equal the inverse of E sub one
and therefore, we have our LU decomposition.
A is equal to L times U,
where here is matrix L and here is matrix U.
Let's take a look at a second example
where A is a three by three matrix,
which will require a little more work.
We want to find the LU decomposition
of the given three by three matrix.
So again, we're going to start with
the identity matrix times matrix A
is equal to the given matrix.
And now I'll perform row operations
in order to write this matrix here
as an upper triangular matrix.
Let's go ahead and do this on the next slide,
where we have more room.
Let's start by obtaining a zero in this position here.
So let's replace row two
with negative three times row one plus row two.
And then after we do this,
we'll perform the same row operation
on our identity matrix to find
our first elementary matrix.
So first row stays the same,
and we'll have negative three times
one plus three, that's zero.
Negative three times two, that's negative six,
Plus negative four, that's negative 10.
Negative three times zero plus one is one.
Third row stays the same.
Now I'll perform the same row operation
on our identity matrix.
So the first row stays the same,
second row is going to be
negative three times one plus zero, that's negative three.
Negative three times zero plus one is one
and negative three times zero plus zero,
of course, is still zero.
So this is our first elementary matrix E sub one.
Now let's obtain a zero in this position here.
So we'll replace row three
with two times row one plus row three.
First two rows stay the same.
For the third row we have two times one, that's two
plus negative two, that's zero.
Two times two plus four, that's eight,
and then we have two times zero
plus negative three, that's negative three.
Notice on the left, we already have E sub one here,
now we'll perform the same row operation
on the identity matrix again to find E sub two.
So the first two rows stay the same.
The third row is going to be
two times one plus zero, that's two.
Two times zero plus zero is zero.
And two times zero plus one is one.
We'll call this E sub two,
our second elementary matrix.
Now for the last step, we want to have a zero
in this position here, in order
for this to be an upper triangular matrix.
And since the least common multiple
of 10 and eight is 40, we're going
to replace row three with four times row two
plus five times row three.
First two rows stay the same
and then here we'll have four times zero plus
five times zero, that's zero.
Four times negative 10, that's negative 40
plus five times eight, that's positive 40.
So that sum would be zero
and then here we'll have four times one, that's four
plus five times negative three,
that's going to be negative 11.
And now to find our third elementary matrix,
Again, the first two rows stay the same.
The third row, we're going to perform
the same row operation.
So four times row two plus five times row three.
So four times zero plus zero is zero.
Four times one plus five times zero is four.
And four times zero plus five times one is five.
This is E sub 3.
So notice that E sub 3 times E sub 2 times E sub 1
times A is equal to the upper triangular matrix,
which we have here.
Let's go ahead and put
all the pieces together on the next slide.
This is what we found on the previous slide,
so again, here's matrix A, here's E sub one,
E sub two and E sub three.
So if we want to solve this equation for matrix A,
we have to multiply both sides by the inverses of
these elementary matrices, which we have done here.
And then the product of the inverse
of the elementary matrices is our lower triangular matrix.
And what I didn't have time to show is
finding the inverses of these elementary matrices.
So here's the inverse of E sub one, inverse of E sub two,
and the inverse of E sub three.
Again, notice how the product is a lower triangular matrix.
So here's our matrix L, therefore
the LU decomposition, where A is equal to L times U,
Here's the given matrix, matrix A.
Here's our lower triangular matrix
and here's our upper triangular matrix.
So this is how you perform LU decomposition
using elementary matrices.
The next video will look at a shortcut
for determining matrix L and matrix U.
I hope you found this helpful.