[Linear Algebra] 11. LU decomposition

Published in

jun-devpBlog

3 min readSep 28, 2019

1. Definition of LU decomposition

Let 𝐀 be a square matrix. An 𝐋𝐔 decomposition of 𝐀 refers to the factorization of A, with proper row and/or column orderings or permutations, into two triangular matrices, one lower triangular matrix 𝐋 and one upper triangular matrix 𝐔, such that the product(matrix multiplication) of these two matrices 𝐋𝐔 is identical to the original matrix 𝐀.

Figure 1. Definition of the 𝐋𝐔 decomposition

According to its definition, in the lower triangular matrix, all entries above the diagonal are zero, and in the upper triangular matrix, all the elements below the diagonal are zero.

why permutations(orderings) are required?

Let’s think about the case: 𝑎₁₁ = 𝑙₁₁⨯𝑢₁₁ = 0. Since 𝑎₁₁ is zero, either 𝑙₁₁ or 𝑢₁₁ has to be zero, which implies that one of 𝐋 and 𝐔 is a singular matrix. However, this problem can be solved by reordering the rows(or columns) of 𝐀 so that the first entry of the permuted matrix is nonzero.

2. How does Lu decomposition work

Figure 2. Example of the 𝐋𝐔 decomposition

Above figure is showing the flow of 𝐋𝐔 decomposition of the 2⨯2 square matrix 𝐀. In that example, permutations were not necessary but one restriction was required to find the unique solutions of entries in the matrix 𝐋 and 𝐔, which is setting all the diagonal entries of 𝐋 as one. With the help of the restriction, the unique 𝐋𝐔 decomposition can be found.

Why setting all diagonal elements in 𝐋 is necessary to find the unique solution of 𝐋𝐔 decomposition?

Let’s think about the case 𝑎₁₁ in the example mentioned above. In order to find the solution of 𝑙₁₁ and 𝑢₁₁, we need to solve the following equation.

3. LU decomposition with the Gauss elimination

Recap of the Gauss elimination

[Linear Algebra] 6. Gauss-Jordan Elimination

Elementary Matrix Operations, Echelon Form, Gauss-Jordan Elimination, Inverse Matrix

medium.com

The general steps for finding 𝐔 matrix for 𝐋𝐔 decomposition of 𝐀 is as below in figure 3.

Figure 3. Find 𝐔 of 𝐀 with Gauss elimination

Using Gauss elimination, reduce 𝐀 into the upper triangular matrix then substitute it into 𝐔. Then one thing left for completing the 𝐋𝐔 decomposition is to find 𝐋. With the restriction which sets all diagonal entries to zero for finding the unique solution, we need to calculate some equations as we’ve done in figure2, but this time, with less calculation since we already know all entries in 𝐔 with the help of Gauss elimination.