[Click here for a PDF of this post with nicer formatting]

To get a better feel for LU factorization before attempting a numeric implementation, let’s look at a numeric example in detail. This will strip some of the abstraction away.

Let’s compute the LU factorization for

\begin{equation}\label{eqn:luExample:20}

M =

\begin{bmatrix}

5 & 1 & 1 \\

2 & 3 & 4 \\

3 & 1 & 2 \\

\end{bmatrix}.

\end{equation}

This matrix was picked to avoid having to think of selecting the right pivot

row. The first two operations are

\begin{equation}\label{eqn:luExample:41}

\begin{aligned}

r_2 &\rightarrow r_2 – \frac{2}{5} r_1 \\

r_3 &\rightarrow r_3 – \frac{3}{5} r_1

\end{aligned},

\end{equation}

and produce

\begin{equation}\label{eqn:luExample:40}

\begin{bmatrix}

5 & 1 & 1 \\

0 &13/5 & 18/5 \\

0 &2/5 & 7/5 \\

\end{bmatrix}

\end{equation}

The row operations (left multiplication) that produce this matrix are

\begin{equation}\label{eqn:luExample:60}

\begin{bmatrix}

1 & 0 & 0 \\

0 & 1 & 0 \\

-3/5 & 0 & 1 \\

\end{bmatrix}

\begin{bmatrix}

1 & 0 & 0 \\

-2/5 & 1 & 0 \\

0 & 0 & 1 \\

\end{bmatrix}

=

\begin{bmatrix}

1 & 0 & 0 \\

-2/5 & 1 & 0 \\

-3/5 & 0 & 1 \\

\end{bmatrix}.

\end{equation}

These operations happen to be commutative and also both invert simply. The inverse operations are

\begin{equation}\label{eqn:luExample:80}

\begin{bmatrix}

1 & 0 & 0 \\

2/5 & 1 & 0 \\

0 & 0 & 1 \\

\end{bmatrix}

\begin{bmatrix}

1 & 0 & 0 \\

0 & 1 & 0 \\

3/5 & 0 & 1 \\

\end{bmatrix}

=

\begin{bmatrix}

1 & 0 & 0 \\

2/5 & 1 & 0 \\

3/5 & 0 & 1 \\

\end{bmatrix}.

\end{equation}

In matrix form the elementary matrix operations that take us to the first stage of the Gaussian reduction are

\begin{equation}\label{eqn:luExample:100}

\begin{bmatrix}

1 & 0 & 0 \\

-2/5 & 1 & 0 \\

-3/5 & 0 & 1 \\

\end{bmatrix}

\begin{bmatrix}

5 & 1 & 1 \\

2 & 3 & 4 \\

3 & 1 & 2 \\

\end{bmatrix}

=

\begin{bmatrix}

5 & 1 & 1 \\

0 &13/5 & 18/5 \\

0 &2/5 & 7/5 \\

\end{bmatrix}.

\end{equation}

Inverted that is

\begin{equation}\label{eqn:luExample:120}

\begin{bmatrix}

5 & 1 & 1 \\

2 & 3 & 4 \\

3 & 1 & 2 \\

\end{bmatrix}

=

\begin{bmatrix}

1 & 0 & 0 \\

2/5 & 1 & 0 \\

3/5 & 0 & 1 \\

\end{bmatrix}

\begin{bmatrix}

5 & 1 & 1 \\

0 &13/5 & 18/5 \\

0 &2/5 & 7/5 \\

\end{bmatrix}.

\end{equation}

This is the first stage of the LU decomposition, although the U matrix is not yet in upper triangular form. Again, with our pivot row in the desired position already, the last row operation to perform is

\begin{equation}\label{eqn:luExample:140}

r_3 \rightarrow r_3 – \frac{2/5}{5/13} r_2 = r_3 – \frac{2}{13} r_2.

\end{equation}

The final stage of this Gaussian reduction is

\begin{equation}\label{eqn:luExample:160}

\begin{bmatrix}

1 & 0 & 0 \\

0 & 1 & 0 \\

0 & -2/13 & 1 \\

\end{bmatrix}

\begin{bmatrix}

5 & 1 & 1 \\

0 &13/5 & 18/5 \\

0 &2/5 & 7/5 \\

\end{bmatrix}

=

\begin{bmatrix}

5 & 1 & 1 \\

0 &13/5 & 18/5 \\

0 & 0 & 11/13 \\

\end{bmatrix}

= U,

\end{equation}

and our desired lower triangular matrix factor is

\begin{equation}\label{eqn:luExample:180}

\begin{bmatrix}

1 & 0 & 0 \\

2/5 & 1 & 0 \\

3/5 & 0 & 1 \\

\end{bmatrix}

\begin{bmatrix}

1 & 0 & 0 \\

0 & 1 & 0 \\

0 & 2/13 & 1 \\

\end{bmatrix}

=

\begin{bmatrix}

1 & 0 & 0 \\

2/5 & 1 & 0 \\

3/5 & 2/13 & 1 \\

\end{bmatrix}

= L.

\end{equation}

A bit of matlab code easily verifies that the above manual computation recovers \( M = L U \)