LDL decomposition (source code)

= LDL decomposition
{c}
{title2=$A=LDL^T$}

A diagonal-pivot <LDL decomposition> of a real <symmetric matrix> has the form
$$
A=LDL^T,
$$
where $L$ is a <unit lower triangular matrix> and $D$ is a <diagonal matrix>. When the needed scalar pivots are nonzero, symmetric <Gaussian elimination> computes one <Schur complement> at a time:
$$
d_j=a_{jj}-\sum_{k<j}l_{jk}^2d_k,\qquad
l_{ij}=\frac{a_{ij}-\sum_{k<j}l_{ik}d_kl_{jk}}{d_j}\quad(i>j).
$$
In particular, nonzero leading <principal minors> guarantee this form, and a <symmetric positive-definite matrix> has positive pivots. Conversely, $d_j>0$ for every $j$ gives $x^TAx=(L^Tx)^TD(L^Tx)>0$ for every nonzero <vector> $x$.

For $A=\left(\begin{smallmatrix}4&2\\2&3\end{smallmatrix}\right)$, take $L=\left(\begin{smallmatrix}1&0\\1/2&1\end{smallmatrix}\right)$ and $D=\operatorname{diag}(4,2)$. General <symmetric matrices> need more care: $\left(\begin{smallmatrix}0&1\\1&0\end{smallmatrix}\right)$ has no such unit-lower-triangular/diagonal factorization. Symmetric indefinite numerical factorization can instead use permutations and symmetric diagonal blocks of sizes one or two.<Linear Equations in the LAPACK Users' Guide by LAPACK project>[Computational Routines, Linear Equations: symmetric indefinite diagonal blocks of order one or two]{ref}