$$\newcommand{\mat}[1]{\begin{bmatrix}#1\end{bmatrix}} \newcommand{\vxy}[2]{\begin{bmatrix}#1 \\ #2\end{bmatrix}} \newcommand{\sm}[1]{\bigl[\begin{smallmatrix}#1\end{smallmatrix}\bigr]} \newcommand{\A}[0]{\mathbf{A}} \newcommand{\L}[0]{\mathbf{L}} \newcommand{\D}[0]{\mathbf{D}} \newcommand{\U}[0]{\mathbf{U}} \newcommand{\I}[0]{\mathbf{I}} \newcommand{\E}[0]{\mathbf{E}} \newcommand{\xx}[0]{\mathbf{x}} \newcommand{\bb}[0]{\mathbf{b}}$$

# Linear Algebra, Part 8: A=LDU Matrix Factorization

posted March 8, 2014

In this post we'll look at how to construct an $$\A=\L\D\U$$ factorization of an invertible matrix.

There are numerous useful factorizations of matrices but $$\A = \L\U$$ (or $$\A=\L\D\U$$) is the first one we come to. We automatically get $$\U$$ as a by-product of the elimination process: once elimination finishes, and before back-substitution is carried out, we have an upper-triangular matrix $$\U$$. See Part 4 of this series for a worked example.

Since elimination yields $$\U$$, we can view elimination as a function which takes a matrix $$\A$$ and produces a new matrix $$\U$$. That function performs the sequence of multiplications of elimination matries $$\E_{ij}$$ mentioned in Part 5 of this series. So we have

$(\E_{ij}\cdots\E_{ij})\A = \U.$

Manipulating that algebraically, we can invert the elimination steps so that $$(\E_{ij}\cdots\E_{ij})^{-1}\U = \A$$. This inverted elimination process can be written $$\L$$, so we have $$\A = \L\U$$. Now we have the matrix factors $$\L$$ and $$\U$$.

In terms of the typical representation $$\A\xx = \bb$$, we instead have

\begin{align*} \A\xx &= \bb \\ \L\U\xx &= \bb \end{align*}

and

\begin{align*} \xx &= \A^{-1}\bb \\ \xx &= \U^{-1}\L^{-1}\bb. \end{align*}

Lastly, we can factor the pivots from $$\U$$ by dividing each row in $$\U$$ by its pivot and then placing the pivots in a separate diagonal matrix $$\D$$. For example:

\begin{align*} \A &= \mat{1 & 2 \\ 3 & 4} \\ \L\U &= \mat{1 & 0 \\ 3 & 1}\mat{1 & 2 \\ 0 & -2} \\ \L\D\U &= \mat{1 & 0 \\ 3 & 1}\mat{1 & 0 \\ 0 & -2}\mat{1 & 2 \\ 0 & 1} \end{align*}

## Afterword

In this post we've looked at how elimination produces matrix factors $$\L$$ and $$\U$$. Next time I'll cover symmetric matrices and transposes.