# 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$$.