The purpose of this note is to clarify questions and statements in class, and a step-by-step way to find an LU decomposition by hand.

We start with notations. Let $A$ be an $n$-by-$n$ non-singular matrix, $b$ is a vector in $\mathbb{R}^n$. The goal is to solve the linear system $Ax=b$, where $x$ is the unique solution of the system.

Define $L_{ij}:=\mathbb{I}+l_{ij}E_{ij}$ be the matrix associate to the row operation between $i$-th and $j$-th row when performing Gauss elimination. Here, $E_{ij}$ is an $n$-by-$n$ matrix whose entries are all zeros except the $(i,j)$-entry is 1. The Gauss elimination procedure (without pivoting) can be described as

\[U=L_{n,(n-1)}\cdots L_{32}L_{31}L_{21}A,\]

where $U$ is an upper triangular matrix. The system is equivalent to

\[Ux=L_{n,(n-1)}\cdots L_{32}L_{31}L_{21}b,\]

and can be solved easily.

The corresponding LU decomposition of $A$ is given by

\[A=LU,\quad\text{where}~~L=L_{21}^{-1}L_{31}^{-1}L_{32}^{-1}\cdots L_{n,(n-1)}^{-1}.\]

We get $U$ and $L_{ij}$ directly from the Gauss elimination procedure. Here, we derive a way to calculate $L$ by hand.

First, we compute the inverse of $L_{ij}$.

Proposition 1. For $i>j$, $L_{ij}^{-1}=\mathbb{I}-l_{ij}E_{ij}$.

Proof. We check the following identity

\[L_{ij}L_{ij}^{-1}=(\mathbb{I}-l_{ij}E_{ij})(\mathbb{I}-l_{ij}E_{ij})=\mathbb{I}-l_{ij}^2E_{ij}^2=\mathbb{I}.\]

Here, we use the fact that $E_{ij}^2=0$ if $i\neq j$, which is a direct consequence of proposition 2.

Example 1. For  $L_{32}=\begin{pmatrix}1&0&0\\0&1&0\\0&5&1\end{pmatrix}$, its inverse $L_{32}^{-1}=\begin{pmatrix}1&0&0\\0&1&0\\0&-5&1\end{pmatrix}$.

Proposition 2. The matrix $E_{ij}$ satisfies the following identity.

\[E_{i_1j_1}E_{i_2j_2}=\begin{cases}0&\text{if~} j_1\neq i_2\\E_{i_1j_2}&\text{if~} j_1=i_2 \end{cases}\]

This in particular implies $L_{i_1j_1}$ and $L_{i_2j_2}$ are commutable if $i_2\neq j_1$ and $i_1\neq j_2$. {\it Note: they do not always commute.}

Next, we compute the product of $L_{ij}^{-1}$.

Proposition 3. If $j_1\neq i_2$, then $L_{i_1j_1}^{-1}L_{i_2j_2}^{-1}=I-l_{i_1j_1}E_{i_1j_1}-l_{i_2j_2}E_{i_2j_2}$.

Example 2. If $L_{21}^{-1}=\begin{pmatrix}1&0&0\\-1&1&0\\0&0&1\end{pmatrix}$ and $L_{31}^{-1}=\begin{pmatrix}1&0&0\\0&1&0\\2&0&1\end{pmatrix}$, then $L_{21}^{-1}L_{31}^{-1}=\begin{pmatrix}1&0&0\\-1&1&0\\2&0&1\end{pmatrix}$.

As $L=L_{21}^{-1}L_{31}^{-1}L_{32}^{-1}\cdots L_{n,(n-1)}^{-1}$, we are always in the case that $j_1<i_2$. Hence, we can simply assemble each term together to obtain $L$.

Example 3 (Complete procedure of LU decomposition (without pivoting)) Find the LU decomposition of the following matrix  $A=\begin{pmatrix}20&30&-10\\6&49&-13\\4&26&3\end{pmatrix}$.

Solution. We proceed with Gauss elimination.

\begin{align*}\begin{matrix}\textbf{1}\\ \textbf{2}\\ \textbf{3}\end{matrix}\begin{pmatrix}20&30&-10\\6&49&-13\\4&26&3\end{pmatrix}\longrightarrow\begin{matrix}\textbf{1}\\ \textbf{2}+(-\frac{6}{20})\times\textbf{1}\\ \textbf{3}\end{matrix}\begin{pmatrix}20&30&-10\\0&40&-10\\4&26&3\end{pmatrix}&\qquad L_{21}=\begin{pmatrix}1&0&0\\-.3&1&0\\0&0&1\end{pmatrix}\\ \longrightarrow\begin{matrix}\textbf{1}\\ \textbf{2}+(-\frac{6}{20})\times\textbf{1}\\ \textbf{3}+(-\frac{4}{20})\times\textbf{1}\end{matrix}\begin{pmatrix}20&30&-10\\0&40&-10\\0&20&5\end{pmatrix}&\qquad L_{31}=\begin{pmatrix}1&0&0\\0&1&0\\-.2&0&1\end{pmatrix}\\ \begin{matrix}\textbf{1}\\ \textbf{2}\\ \textbf{3}\end{matrix}\begin{pmatrix}20&30&-10\\0&40&-10\\0&20&5\end{pmatrix}\longrightarrow\begin{matrix}\textbf{1}\\ \textbf{2}\\ \textbf{3}+(-\frac{20}{40})\times\textbf{2}\end{matrix}\begin{pmatrix}20&30&-10\\0&40&-10\\0&0&10\end{pmatrix}&\qquad L_{32}=\begin{pmatrix}1&0&0\\0&1&0\\0&-.5&1\end{pmatrix}\end{align*}

Therefore, we conclude $U=\begin{pmatrix}20&30&-10\\0&40&-10\\0&0&10\end{pmatrix}$, and

\[L=L_{21}^{-1}L_{31}^{-1}L_{32}^{-1}=\begin{pmatrix}1&0&0\\.3&1&0\\0&0&1\end{pmatrix} \begin{pmatrix}1&0&0\\0&1&0\\.2&0&1\end{pmatrix}\begin{pmatrix}1&0&0\\0&1&0\\0&.5&1\end{pmatrix} =\begin{pmatrix}1&0&0\\.3&1&0\\.2&.5&1\end{pmatrix}.\]