Past exam of the mathematics course of the University of Cambridge / 2021 / ib / Paper 1 / 5B (Numerical Analysis)

Apply symmetric Gaussian elimination without row exchanges. At step $k$, let $d_k$ be the leading diagonal entry of the remaining symmetric Schur complement. If $d_k\le 0$, stop and report that $A$ is not positive definite. If $d_k>0$, use it to eliminate the rest of its row and column. If all steps succeed, this constructs an LDL decompositionwhere $L$ is unit lower triangular and $D=\mathrm{diag}(d_1,\dots ,d_n)$ has positive diagonal.

The test is correct from first principles. If all $d_k>0$, then for every nonzero $x$,because $L$ is invertible. Conversely, if $A$ is positive definite, its first pivot is $a_{11}>0$, and completing the square givesChoosing $s=-b^{T}y/a$ shows that the Schur complement is positive definite. Induction forces every pivot to be positive. This is also Sylvester's criterion.

At step $k$, updating the remaining matrix costs $O((n-k{)}^2)$ arithmetic operations. Hence the total iswhich proves the existence of the required algorithm.