Skip to main content

2.5 LU decomposition (2) Properties of L and U

This is a continuation of LU decomposition, if you have no interest about linear algebra, unfortunately this is not for yours.

Last time, we saw the nice property: the result of multiplication of elimination matrices L has sign inverted components of the elimination matrices. I think many of my friends would say: ``so what?'' I think it is convenient if the answer of multiplication of matrices can be found without multiplication.

I would like to have a note first. The last blog, L = (E_{32} E_{31} E_{21})^{-1}' L has inverted signed components of Es. But this is not true for (E_{32} E_{31} E_{21}). Only true if this is inverted. Here, L^{-1} is

E_{31} is not preserved. (In this example, E_{31} has only inverted sign, but, if you solve the Gilbert Strang's book, p. 103, Problem 8, you will find out there is more behind.)

Let's come back to the property.  Intuitively, this is based on the matrix row operation property from the left side. Let's me explain this with 2 by 2 example matrix.  A 2 by 2 Elimination matrix for component 21 (E_{21}) is a lower triangler matrix shown in Equation 6. Equation 7 emphasizes the row operation, A is written in set of the rows.  If you think A is simultaneous linear equations (two equations, a_{r_1}, a_{r_2}), then, we can remove the first term of the a_{r_2} by multiplying l_{21} to the first row (a_{r_1}) and adding it to the second row (a_{r_2}). The Elimination matrix E_{21} performs this.  The inverse matrix of E_{21} is Equation 9. You can find this from the rule of 2 by 2 inverse matrix, but, you can also consider the operation's meaning. The inverse operation of this E_{21} is removing the first row with multiplied by l_{21} (= l_{21} a_{r_1}) from the first row. This is l_{21} a_{r_1} + a_{r_2} - l_{21} a_{r_1} = a_{r_2}. You can get the inverse in this way. This is a better understanding than using the 2 by 2 matrix's inverse rule. Because this idea doesn't depend on the size of matrix, 3 by 3, 4 by 4, ..., n by n, this always works. Moreover, a general problem is n by n.




According to the Elimination's property,  matrices L,U has the following structure, some of the components are always zero.
As you saw, L has non-zero component in Lower triangle part, U has non-zero component in Upper triangle part. When L's lower triangler part has coincidentally zero(s), or U's upper triangler part has coincidentally zero(s), then we have the following interesting property. (p.96 in Gilbert Strang's book)
  1.  When a row of A starts with zeros, so does that row of L.
  2.  When a column of A starts with zeros, so does that column of U.
First, 1.'s zero means the elimination is done. Because the purpose of elimination is to get zero and if it has already been zero, nothing to do, therefore, this component of elimination matrix becomes zero.  Next, 2. is related with the elimination operation performs from top to down. For example, U has one column three zeros from the top, the third row of U is A's row 3 minus a linear combination of A's row 1 and row 2. Then, if row 1 and row 2 component are zero, it's linear combination is also zero (l_{31} 0 + l_{32} 0 + 0 = 0).

At the end, we did here is only elimination. Then why we just do elimination, instead of LU decomposition. As my understand, there are two reasons. Next time finally I would like to explain why we do LU decomposition.

Comments

Popular posts from this blog

Why A^{T}A is invertible? (2) Linear Algebra

Why A^{T}A has the inverse Let me explain why A^{T}A has the inverse, if the columns of A are independent. First, if a matrix is n by n, and all the columns are independent, then this is a square full rank matrix. Therefore, there is the inverse. So, the problem is when A is a m by n, rectangle matrix.  Strang's explanation is based on null space. Null space and column space are the fundamental of the linear algebra. This explanation is simple and clear. However, when I was a University student, I did not recall the explanation of the null space in my linear algebra class. Maybe I was careless. I regret that... Explanation based on null space This explanation is based on Strang's book. Column space and null space are the main characters. Let's start with this explanation. Assume  x  where x is in the null space of A .  The matrices ( A^{T} A ) and A share the null space as the following: This means, if x is in the null space of A , x is also in the null spa

Gauss's quote for positive, negative, and imaginary number

Recently I watched the following great videos about imaginary numbers by Welch Labs. https://youtu.be/T647CGsuOVU?list=PLiaHhY2iBX9g6KIvZ_703G3KJXapKkNaF I like this article about naming of math by Kalid Azad. https://betterexplained.com/articles/learning-tip-idea-name/ Both articles mentioned about Gauss, who suggested to use other names of positive, negative, and imaginary numbers. Gauss wrote these names are wrong and that is one of the reason people didn't get why negative times negative is positive, or, pure positive imaginary times pure positive imaginary is negative real number. I made a few videos about explaining why -1 * -1 = +1, too. Explanation: why -1 * -1 = +1 by pattern https://youtu.be/uD7JRdAzKP8 Explanation: why -1 * -1 = +1 by climbing a mountain https://youtu.be/uD7JRdAzKP8 But actually Gauss's insight is much powerful. The original is in the Gauß, Werke, Bd. 2, S. 178 . Hätte man +1, -1, √-1) nicht positiv, negative, imaginäre (oder gar um

Why parallelogram area is |ad-bc|?

Here is my question. The area of parallelogram is the difference of these two rectangles (red rectangle - blue rectangle). This is not intuitive for me. If you also think it is not so intuitive, you might interested in my slides. I try to explain this for hight school students. Slides:  A bit intuitive (for me) explanation of area of parallelogram  (to my site, external link) .