This page is intended to be a part of the Numerical Analysis section of Math Online. Similar topics can also be found in the Linear Algebra section of the site.

The LU Decomposition of a Matrix

Consider the system of $n$ linear equations in $n$ unknowns represented by the equation $Ax = b$. Recall from The Gaussian Elimination Algorithm page that we could reduce our system to the form $Ux = g$ where $U$ is the $n \times n$ matrix from using Gaussian Elimination on $A$, and $g$ is the $n \times n$ matrix from using Gaussian Elimination on $b$. More precisely, we applied Gaussian Elimination on the augmented matrix $[ \: A \: | \: b \: ]$ to produce $[ \: U \: | \: g \: ]$. We will now look at the relevance of the matrix $U = \begin{bmatrix} u_{11} & u_{12} & \cdots & u_{1n}\\ 0 & u_{22} & \cdots & u_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0& \cdots & u_{nn} \end{bmatrix}$.

Let $L$ be the following $n \times n$ lower triangular matrix whose entries are $l_{ij} = \left\{\begin{matrix} 0 \: \mathrm{if} \: i < j\\ 1 \: \mathrm{if} \: i = j\\ m_{ij} \: \mathrm{if} \: i > j \end{matrix}\right.$. Then the matrix $L$ has the following form:

(1)

\begin{align} \quad L = \begin{bmatrix} 1 & 0 & \cdots & 0\\ m_{21} & 1 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ m_{n1} & m_{n2} & \cdots & 1 \end{bmatrix} \end{align}

Recall that the values $m_{ij}$ are the multipliers used in Gaussian Elimination and $m_{ij} = \frac{a_{ij}^{(j)}}{a_{jj}^{(j)}}$ for each $j = 1, 2, ..., n$ and $i = j+1, j+2, ..., n$. The following theorem outlines an important relationship between the matrix $U$ and the matrix $L$.

Theorem 1: If $A$ is an invertible $n \times n$ matrix then $A$ can be factored as the product of a lower triangular matrix $L$ and an upper triangular matrix $U$ (obtained without pivoting) such that $A = LU$ where $L = \begin{bmatrix} 1 & 0 & \cdots & 0\\ m_{21} & 1 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ m_{n1} & m_{n2} & \cdots & 1 \end{bmatrix}$ and $U = \begin{bmatrix} u_{11} & u_{12} & \cdots & u_{1n}\\ 0 & u_{22} & \cdots & u_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0& \cdots & u_{nn} \end{bmatrix}$.

By now you might be asking what's so important about an LU decomposition. Note that the system $Ax = b$ can be rewritten as $LUx = b$. But $Ux = g$, and so we the following equivalent system $Lg = b$:

(2)

\begin{align} \quad \begin{bmatrix} 1 & 0 & \cdots & 0\\ m_{21} & 1 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ m_{n1} & m_{n2} & \cdots & 1 \end{bmatrix} \begin{bmatrix} g_1\\ g_2\\ \vdots\\ g_n \end{bmatrix} = \begin{bmatrix} b_1\\ b_2\\ \vdots\\ b_n \end{bmatrix} \end{align}

As a system of linear equations we also have that:

(3)

\begin{align} \quad \begin{matrix} g_1 & & & & & & & = & b_1\\ m_{21}g_1 & + & g_2 & & & & & = & b_2\\ \vdots & & \vdots & & \ddots & & & \vdots\\ m_{n1}g_{1} & + & m_{n2}g_2 & + & \cdots & + & g_n & = & b_n \end{matrix} \end{align}

From here we see that $g_1 = b_1$, and from this, we can apply the technique of Forward substitution to find the values of $g = \begin{bmatrix}g_1\\ g_2\\ \vdots\\ g_n \end{bmatrix}$ appearing in the system $Ux = g$. Then we can easily solve for $x$ which is the solution to $Ax = b$.

Thus if $A = LU$ then solving the system $Ax = b$ involves solving two systems whose coefficient matrices $L$ and $U$ are upper triangular, and of course, solving systems for which the corresponding coefficient matrices are triangular is relatively simple.