A = LDU Factorization

To solve a dense system $Ax=b$ computationally efficiently one decomposes the matrix $A$ by matrix elimination into the form $A=LU$.

• $L$ is the inverse of the elimination matrices $E=\Pi (E\_ij)$ that were used to turn $A$ into upper triangular form. $L$ is formed by flipping the signs of the factors $\ell \_ij$ that were used to annihilate rows in $A$ with each other. I.e. $E=\left[\begin{array}{ccc}1& 0-2& 1\end{array}\right]\to L=\left[\begin{array}{ccc}1& 02& 1\end{array}\right]$
• $U$ is the upper triangular of the operation, i.e. what is left of $A$ after being acted upon by $E$. Upper triangular means that the underside of the diagonal is empty $U=\left[\begin{array}{ccccccc}1& a& a0& 1& a0& 0& 1\end{array}\right]$

Solving the System

By decomposing $A$ into $LU$ two substitution steps are required to arrive at the solution $x$ to $Ax=b$.

1. Solve $Lc=b$ for $b$ by forward substitution
2. Solve $Ux=c$ by backward substitution

$A=LDU$

This formula arises when we divide each pivot-row of the upper triangular $U$ with its pivot’s value turning the number at the pivot position into a 1. The divisions are kept in the matrix $D=\left[\begin{array}{ccccccc}d\_11& & & d\_22& & & d\_33\end{array}\right]$ such that $A=LU$ becomes $A=LDU$ where all pivots of $U$ are exactly 1. This idea is further extended into $A=LD{L}^T$ for Symmetric Matrices.