Matrix Decomposition: LU & Cholesky

Matrix decomposition (or factorization) is a foundational tool in numerical linear algebra. It decomposes a given matrix into simpler matrices, allowing for easier computation of the determinant, matrix inverse, or a linear system. Here, we will discuss LU decomposition and its application in linear systems.

LU decomposition uses a lower triangular matrix and a lower triangular matrix. There are two methods to solve for the triangular matrices. The Doolittle method requires the diagonal elements of the lower triangular matrix while the Crout method enforces the same rule on the upper triangular matrix. L and U elements are solved using

$u_{ij} = a_{ij} - \sum_{k=1}^{i-1}u_{ij}l_{ik}$
$u_{ij} = \left(a_{ij} - \sum_{k=1}^{i-1}u_{ij}l_{ik} \right) u_{ii}^{-1}$

Assuming no pivoting is required, L and U can be substituted into any square linear system,

$\textbf{A}x=b$
$\textbf{LU}x=b$ ,

where $x,b\in \mathbb{R}^{n\times 1}$ and $\textbf{A} \in\mathbb{R}^{n\times n}$ is a non-singular coefficient matrix. Solving for $\textbf{U}x=y$ , yields $\textbf{L}x=y$ .

The triangular form of L and U allows forward and backward substitution, producing for a straightforward solution to the linear system. The inverse of A is calculated by substitution the identity matrix for b. A special case of LU decomposition is the Cholesky factorization, which assumes that the matrix is symmetric positive definite. This property allows the factorization to be reduced into an even simpler form, giving

$\textbf{A} = \textbf{L}\textbf{L}^T$
$\textbf{A} = \textbf{U}^T\textbf{U}$

The decomposition consists of the lower triangular matrix and its transpose or the upper matrix and its
matrix (reversed matrix multiplication). Linear systems and the inverse are solved using the same
substitution method.

$\begin{bmatrix} 8& 1 & 6 \\ 3& 5 & 7 \\ 4& 9 & 2 \end{bmatrix}$ = $\begin{bmatrix} 1 & 0 & 0 \\ l_{21} & 1 & 0 \\ l_{31} & l_{32} & 1 \end{bmatrix} \begin{bmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23}\\ 0 & 0 & u_{33} \end{bmatrix}$

Figure 1. Example of LU factorization of a 3×3 matrix using
the Doolittle method.

Complete Communications Engineering