= Solution
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\leq0$, stop and report that $A$ is not <positive-definite matrix>[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 decomposition>
$$
A=LDL^T,
$$
where $L$ is unit lower triangular and $D=\operatorname{diag}(d_1,\ldots,d_n)$ has positive diagonal.
The test is correct from first principles. If all $d_k>0$, then for every nonzero $x$,
$$
x^TAx=(L^Tx)^TD(L^Tx)>0
$$
because $L$ is invertible. Conversely, if $A$ is positive definite, its first pivot is $a_{11}>0$, and completing the square gives
$$
\begin{pmatrix}s\\y\end{pmatrix}^{T}
\begin{pmatrix}a&b^T\\b&C\end{pmatrix}
\begin{pmatrix}s\\y\end{pmatrix}
=a\left(s+\frac{b^Ty}{a}\right)^2
+y^T\left(C-\frac{bb^T}{a}\right)y.
$$
Choosing $s=-b^Ty/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 is
$$
\sum_{k=1}^nO((n-k)^2)=O(n^3),
$$
which proves the existence of the required algorithm.
Back to article page
