# A Brief Understanding of LU factorization.

- What's LU factorization?
- Why do we need LU factorization?
- How to do LU factorization?
- What kind of Matrix can do LU factorization?
- Other special forms of LU factorization

<script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-MML-AM_CHTML'></script>

### 1. What's LU factorization

- Intuitively thinking: For a linear system, \( Ax=b \), if Matrix A can be written as the form $$A=LU$$, where L is a lower trianguler matrix and U is a upper triangular matrix, we have: \(LUx=b\).Then we can calculate Ux using L, assuming that \(Ux=y\), we have: $$Ly=b$$. This equation is easy to solve as L is a triangular matrix. Now we have y, so we can solve x using: $$Ux=y$$, which is also easy to solve as u is a triangular matrix.

### 2. Why do we need LU factorization?

- Easier to calculate the inverse of a matrix.

- Easier to calculate the determinant of a matrix.

### 3. How to do LU factorization?

- 1 Reduce A to its echelon form to get U. The reduced process is called
**Gaussian Elimination**, and is simply a left multiplication of a suitable**Elementary matrix**. An example of a Elementary matrix is:

$$ E1 = begin{bmatrix}

1& 0 \m& 1end{bmatrix}$$

If we invoke E1 to a 2X2 square matrix A, we will scale the first row of A with factor m and then add it to the second row.

- 2 Assume we need an ordered process \(E_{1}, E_{2}, E_{3} \) to get U, which is $$E_{3}E_{2}E_{1}A=U$$

So we have

$$A=E_{1}^{-1}E_{2}^{-1}E_{3}^{-1}U$$

We should note the all elementary matrix are invertible. This is resonable if you look into the process of **Gussian Elimination**. The inverse of an elementary matrix is just an undo action of one Gussian Elimination. More details of how to calculate the inverse of an elementary matrix can be found on wikipedia page.

- 3 Solve L.

Now it's much easy to solve L.

$$A=E_{1}^{-1}E_{2}^{-1}E_{3}^{-1}U$$

$$A=LU$$

So, we have

$$L=E_{1}^{-1}E_{2}^{-1}E_{3}^{-1}$$

The amazing thing is that, by using the above equation, the calculated L is an upper trangular matrix. Now we add another constraint to make all the pivots of L to be 1. This L is also called unitriangular matrix. There are some more properties in L, but we will not go to details here.

### 4. What kind of Matrix can do LU factorization?

**The first requirement**of Matrix A(square matrix) is obvious,**A is invertible**. This is the requirement if we want to get its echelon form, and finally get U. Becuase A is invertible, we have:

$$A^{-1}=U^{-1}L^{-1}$$

This means that L and U are also invertible. As L is calculated by inverse of elementary matrix, so L is always invertible. Now the problem is U, whether U is invertible or not. Actually this comes to our second requirement.

**Second requirement**: not all invertible square matrix A can do LU factorization. When there are zeros in pivot position of Matrix U, U is not invertible. When there are pretty large number and pretty small numbers on pivot positions of Matrix U, U is ill-conditioned. Both cases can not do LU factorization.**How to deal with zero pivots in Matrix U?**

What we should do now is a simply row exchange action on matrix A. And this row exchange action can also be represented as a left multiplication of A using the**Permutation Matrix**P, such as:

$$ P = \begin{bmatrix}0& 1 \\\ 1& 0 \end{bmatrix}$$

This Permutation matrix P means exchange a 2X2 square matrix A's first row and second row.

Applying Permutation Matrix to U several times is equivalent applying P to left multiply Matrix A, which has the form of :

$$PA=LU$$

More details about this kind of LU factorization can be found here.

### 5. Other special forms of LU factorization

- \(A=LDU\):

L: a lower triangular matrix with all the pivots are 1.

D: a diagonal matrix

U: a upper triangular matrix with all the pivots are 1.

**source: Walsh Matrix, Wikipedia

- \( A=LDL^T \):

A special form of A=LDU if A is a symetric matrix such as:

$$ A = begin{bmatrix}

8& 4 & 2 \4& 6 & 0 \

2& 0 & 3

end{bmatrix}$$

- \(PA=LU\):

When doing the regular A=LU, we get an uninvertible U or ill-conditioned U, we need to think about this form. More details about this kind of LU factorization can be found here.