LU Decomposition

Definition

• LU Decomposition decomposes a matrix into a Lower triangular matrix $(L)$ and an Upper triangular matrix $(U)$.
• It facilitates solving systems of linear equations, matrix inversion, and determinant calculation.

LU Decomposition for a 3x3 Matrix:

Given a matrix $(A)$, LU decomposition is finding $(L)$ and $(U)$ such that $(A=LU)$, where:

• $(L)$ is a lower triangular matrix.
• $(U)$ is an upper triangular matrix.

$$L=\left[\begin{array}{ccc}{l}_{11}& 0& 0\\ l_{21}& l_{22}& 0\\ l_{31}& l_{32}& l_{33}\end{array}\right]$$ $$U=\left[\begin{array}{ccc}{u}_{11}& u_{12}& u_{13}\\ 0& u_{22}& u_{23}\\ 0& 0& u_{33}\end{array}\right]$$

Doolittle Algorithm for LU Decomposition

• The Doolittle algorithm splits a matrix into lower $L$ and upper $U$ triangular matrices, requiring non-zero leading principal minors.
• When this condition isn’t met, a permutation matrix $P$ is introduced, enabling $PLU$ decomposition through row swapping.
• This step ensures decomposition continuity across a wider matrix range.

Step-by-Step Example

Given a matrix $A$:

$$A=\left[\begin{array}{ccc}4& 3& 2\\ 3& 2& 1\\ 2& 1& 3\end{array}\right]$$

We want to find $L$ and $U$ such that $A=LU$.

1. Initialize $L$ and $U$ with zeros and $L$’s diagonal with ones:

$$L=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right],U=\left[\begin{array}{ccc}0& 0& 0\\ 0& 0& 0\\ 0& 0& 0\end{array}\right]$$

2. Fill (U)‘s first row and (L)‘s first column:

   • $U_{1j}=A_{1j}$ for $j=1,2,3$
   • $L_{i1}=\frac{A_{i1}}{U_{11}}$ for $i=2,3$

$$U=\left[\begin{array}{ccc}4& 3& 2\\ 0& 0& 0\\ 0& 0& 0\end{array}\right],L=\left[\begin{array}{ccc}1& 0& 0\\ \frac{3}{4}& 1& 0\\ \frac{1}{2}& 0& 1\end{array}\right]$$

3. Compute (U)‘s second row and (L)‘s second column:

   • Update $U_{2j}=A_{2j}-L_{21}{U}_{1j}$ for $j=2,3$
   • $L_{i2}=\frac{A_{i2}-L_{i1}{U}_{12}}{U_{22}}$ for $i=3$

$$U=\left[\begin{array}{ccc}4& 3& 2\\ 0& \frac{3}{4}& \frac{1}{2}\\ 0& 0& 0\end{array}\right],L=\left[\begin{array}{ccc}1& 0& 0\\ \frac{3}{4}& 1& 0\\ \frac{1}{2}& \frac{1}{3}& 1\end{array}\right]$$

4. Fill (U)‘s third row:

   • Update $U_{3j}=A_{3j}-L_{31}{U}_{1j}-L_{32}{U}_{2j}$ for $j=3$

$$U=\left[\begin{array}{ccc}4& 3& 2\\ 0& \frac{3}{4}& \frac{1}{2}\\ 0& 0& 2\end{array}\right]$$

Now, $A=LU$ where $L$ and $U$ are:

$$L=\left[\begin{array}{ccc}1& 0& 0\\ \frac{3}{4}& 1& 0\\ \frac{1}{2}& \frac{1}{3}& 1\end{array}\right],U=\left[\begin{array}{ccc}4& 3& 2\\ 0& \frac{3}{4}& \frac{1}{2}\\ 0& 0& 2\end{array}\right]$$

PLU: Row Swapping Example:

• Applying a permutation matrix $P$ rearranges $A$’s rows to avoid division by zero: $P=\left[\begin{array}{ccc}0& 0& 1\\ 1& 0& 0\\ 0& 1& 0\end{array}\right],PA=\left[\begin{array}{ccc}4& 5& 6\\ 1& 0& 3\\ 0& 1& 2\end{array}\right]$
• This modification enables the Doolittle algorithm to process $PA$ without encountering mathematical hindrances, demonstrating the critical role of $P$ in $PLU$ decomposition.