LU Decomposition

The key problem of Linear Algebra is solving the equation \(Ax=b\). We know that with Gaussian elimination, we can decompose \(A = LU\), where \(L\) is a lower-triangular matrix and \(U\) is an upper triangular matrix. An example speaks a thousand words:

\begin{equation} A x=\left[\begin{array}{ccc}{2} & {1} & {1} \ {4} & {-6} & {0} \ {-2} & {7} & {2}\end{array}\right]\left[\begin{array}{l}{u} \ {v} \ {w}\end{array}\right]=\left[\begin{array}{c}{5} \ {-2} \ {9}\end{array}\right]=b \end{equation}

We have that:

\begin{equation} U x=\left[\begin{array}{ccc}{2} & {1} & {1} \ {0} & {-8} & {-2} \ {0} & {0} & {1}\end{array}\right]\left[\begin{array}{l}{u} \ {v} \ {w}\end{array}\right]=\left[\begin{array}{c}{5} \ {-12} \ {2}\end{array}\right]=c \end{equation}

And the process from getting from A to U is \(GFEA = U\):

\begin{equation} G F E=\left[\begin{array}{ccc} {1} & {} & {} \\\
{} & {1} & {} \\\
{} & {1}& {1} \end{array}\right] \left[\begin{array}{ccc} {1} & {} & {} \\\
{} & {1} & {} \\\
{1} & {} & {1} \end{array}\right] \left[\begin{array}{ccc} {1} & {} & {1} \\\
{-2} & {1} & {} \\\
{} & {} & {1}\end{array}\right] =\left[\begin{array}{ccc} {1} & {} & {} \\\
{-2} & {1} & {} \\\
{-1} & {1} & {1} \end{array}\right] \end{equation}

We have that \(E^{-1} F^{-1} G^{-1} U= LU = A\):

\begin{equation} E^{-1} F^{-1} G^{-1}=\left[ \begin{array}{ccc} {1} & {} & {}\\\
{2} & {1} & {} \\\
{} & {} & {1} \end{array}\right] \left[\begin{array}{ccc} {1} & {} & {} \ {} & {1} & {} \ {-1} & {} & {1} \end{array}\right] \left[\begin{array}{ccc} {1} & {} & {} \\\
{} & {1} & {} \\\
{} & {-1} & {1}\end{array}\right]= \left[\begin{array}{ccc}{1} & {} & {} \ {2} & {1} & {} \ {-1} & {-1} & {1}\end{array}\right]=L \end{equation}

The \(A = LU\) decomposition is exactly the matrix that solves \(Ax=b\). Each triangular system requires \(\frac{n^2}{2}\) steps each, compared to the \(O(n^3)\) system of factoring \(A\).

The triangular factorization can be written \(A = LDU\) where \(L\) and \(U\) have 1s on the diagonal, and \(D\) is the diagonal matrix of pivots:

\begin{equation} A=\left[\begin{array}{ll}{1} & {2} \ {3} & {4}\end{array}\right]=\left[\begin{array}{ll}{1} & {1} \ {3} & {1}\end{array}\right]\left[\begin{array}{rr}{1} & {2} \ {} & {-2}\end{array}\right]=\left[\begin{array}{ll}{1} \ {3} & {1}\end{array}\right]\left[\begin{array}{ll}{1} & {} \ {} & {-2}\end{array}\right]\left[\begin{array}{ll}{1} & {2} \ {} & {1}\end{array}\right]=L D U \end{equation}

This factorization is uniquely determined by \(A\).