Matrix Decomposition

Table of contents
  1. LU decomposition
    1. Condition
    2. How to find $L$ and $U$
      1. Using elementary row operations
      2. Doolittle algorithm
    3. Using LU to solve linear equations

LU decomposition

The LU decomposition of any matrix $A$ is a factorization of $A$ into a product of a lower triangular matrix $L$ and an upper triangular matrix $U$.

$$ A = LU $$

$A$ does not have to be a square matrix.

It is conventional to have the principal diagonal of $L$ to be all $1$.

Condition

For a matrix $A$ to have an LU decomposition, it must be possible to rewrite $A$ as an upper triangular matrix with only non-zero row scalings and row additions.

So basically the elementary row operations except row exchange.

If row exchange is needed, then $A$ has a PLU decomposition, where $P$ is a permutation matrix.

How to find $L$ and $U$

Using elementary row operations

As stated above, matrix $A$ must be able to be rewritten as an upper triangular matrix $U$ for it to have an LU decomposition.

The elementary matrix multiplication $E_1 \dots E_k$ that are used to transform $A$ has an inverse of $E_1^{-1} \dots E_k^{-1}$ by its property.

\[E_k \dots E_1 A = U \Rightarrow A = E_1^{-1} \dots E_k^{-1} U\]

therefore:

$$ L = E_1^{-1} \dots E_k^{-1} $$

Doolittle algorithm

The Doolittle algorithm is a method to find the LU decomposition of a matrix $A$.

Assuming the principal diagonal of $L$ is all $1$.

Starting from the top left corner of $A$, where $l_{1k} = [1, 0, \dots, 0]$ is the first row vector of $L$, and $u_{k1} = [u_{11}, 0, \dots, 0]^T$ is the first column vector of $U$:

\[a_{11} = l_{1k} \cdot u_{k1} = u_{11}\]

We iteratively find the following:

$$ \begin{gather*} \forall i > j,\; l_{ij} = \frac{a_{ij} - \sum_{k=1}^{j-1} l_{ik} u_{kj}}{u_{jj}} \\ \forall i \geq j,\; u_{ij} = a_{ij} - \sum_{k=1}^{j-1} l_{ik} u_{kj} \end{gather*} $$

Using LU to solve linear equations

Let $A$ be a matrix that has an LU decomposition $LU$,

Then the linear equation $Ax = b$ can be solved by:

\[Ax = b \Rightarrow LUx = b \Rightarrow Ly = b \land Ux = y\]

where $y$ is a vector that can be found by solving $Ly = b$.

We do this because with triangular matrices in augmented form, Gauss-Jordan elimination becomes much easier.