Completing Squares And LDLᵀ Factorization

Completing Squares Reveals the Matrix

A quadratic form may be written as \(\mathbf{x}^{\top}\mathbf{A}\mathbf{x}\), where \(\mathbf{A}\) is symmetric and \(\mathbf{x}\) is a column vector. If the form is positive definite, its value is positive for every nonzero \(\mathbf{x}\). Completing squares rewrites that expression as a sum of positive multiples of squares of linear combinations of the coordinates. The coefficients of those squares are not arbitrary: they are exactly the successive pivots obtained by eliminating variables in order.

We work over \(\mathbb{R}\). A symmetric matrix \(\mathbf{A}\in\mathbb{R}^{n\times n}\) is positive definite if \(\mathbf{x}^{\top}\mathbf{A}\mathbf{x}>0\) for every \(\mathbf{x}\ne\mathbf{0}\). A matrix \(\mathbf{L}\) is unit lower triangular if it is lower triangular and every diagonal entry is \(1\). A diagonal matrix \(\mathbf{D}\) has zero entries off its main diagonal.

For a \(2\times2\) symmetric matrix, the mechanism is already visible. If \(\mathbf{A}=\begin{bmatrix}a&b\\b&c\end{bmatrix}\) and \(a\ne0\), then

The first square uses the pivot \(a\). The remaining coefficient \(c-b^2/a\) is the next pivot. For a positive definite matrix, both are positive: testing \(\mathbf{x}=(1,0)^{\top}\) gives \(a>0\), and testing \(\mathbf{x}=(-b/a,1)^{\top}\ne\mathbf{0}\) makes the quadratic form equal to \(c-b^2/a>0\).

The Block Step: One Square and a Smaller Form

The same calculation works in any dimension. Write a symmetric matrix in block form, separating its first row and column:

Here \(a\) is a scalar, \(\mathbf{b}\in\mathbb{R}^{n-1}\), \(\mathbf{C}\in\mathbb{R}^{(n-1)\times(n-1)}\) is symmetric, and \(\mathbf{y}\in\mathbb{R}^{n-1}\). When \(a\ne0\), expanding the right-hand side verifies the identity

The smaller symmetric matrix \(\mathbf{C}-\mathbf{b}\mathbf{b}^{\top}/a\) is the Schur complement of the scalar block \(a\) in this partition. The name is useful, but the essential point is its origin: after completing the first square, this matrix gives the remaining quadratic form.

If \(\mathbf{A}\) is positive definite, then \(a>0\), by evaluating the form at \((1,\mathbf{0})^{\top}\). The Schur complement is also positive definite. Indeed, for any \(\mathbf{y}\ne\mathbf{0}\), choose \(x_1=-\mathbf{b}^{\top}\mathbf{y}/a\). The resulting \(\mathbf{x}\) is nonzero, and the completed-square identity gives \(\mathbf{x}^{\top}\mathbf{A}\mathbf{x} =\mathbf{y}^{\top}(\mathbf{C}-\mathbf{b}\mathbf{b}^{\top}/a)\mathbf{y}>0\).

Proof. We prove both directions. First suppose \(\mathbf{A}\) is positive definite. We use induction on \(n\). For \(n=1\), \(\mathbf{A}=[a]\) with \(a>0\), so take \(\mathbf{L}=[1]\) and \(\mathbf{D}=[a]\). Now suppose \(n>1\), and partition \(\mathbf{A}\) as above. We have \(a>0\), and the block calculation shows that \(\mathbf{S}=\mathbf{C}-\mathbf{b}\mathbf{b}^{\top}/a\) is symmetric positive definite. By the induction hypothesis, \(\mathbf{S}=\mathbf{L}_2\mathbf{D}_2\mathbf{L}_2^{\top}\), with \(\mathbf{L}_2\) unit lower triangular and all diagonal entries of \(\mathbf{D}_2\) positive. Set \(\mathbf{L}=\begin{bmatrix}1&\mathbf{0}^{\top}\\\mathbf{b}/a&\mathbf{L}_2\end{bmatrix}\) and \(\mathbf{D}=\begin{bmatrix}a&0\\0&\mathbf{D}_2\end{bmatrix}\). Block multiplication gives \(\mathbf{L}\mathbf{D}\mathbf{L}^{\top} =\begin{bmatrix}a&\mathbf{b}^{\top}\\\mathbf{b}&\mathbf{b}\mathbf{b}^{\top}/a+\mathbf{S}\end{bmatrix} =\mathbf{A}\). The diagonal entries of \(\mathbf{D}\) are positive. This proves existence. Conversely, suppose \(\mathbf{A}=\mathbf{L}\mathbf{D}\mathbf{L}^{\top}\) with \(\mathbf{L}\) unit lower triangular and \(d_k>0\). Such an \(\mathbf{L}\) is invertible: solving \(\mathbf{L}^{\top}\mathbf{u}=\mathbf{0}\) from the last row upwards gives \(\mathbf{u}=\mathbf{0}\). Thus if \(\mathbf{x}\ne\mathbf{0}\), then \(\mathbf{L}^{\top}\mathbf{x}\ne\mathbf{0}\), and \(\mathbf{x}^{\top}\mathbf{A}\mathbf{x} =(\mathbf{L}^{\top}\mathbf{x})^{\top}\mathbf{D}(\mathbf{L}^{\top}\mathbf{x}) =\sum_{k=1}^{n}d_k((\mathbf{L}^{\top}\mathbf{x})_k)^2>0\). So \(\mathbf{A}\) is positive definite. \(\square\)

Elimination Pivots and Leading Principal Minors

The construction in the proof is an algorithm. At each stage, take the first diagonal entry of the current symmetric matrix as a pivot, complete a square using that pivot, then continue with the Schur complement. No row exchanges are needed for a positive definite matrix, because every pivot is positive. The multipliers used to complete the squares become the entries below the diagonal of \(\mathbf{L}\).

The pivots can also be checked using leading principal minors. Let \(\Delta_k\) be the determinant of the upper-left \(k\times k\) block of \(\mathbf{A}\), and set \(\Delta_0=1\). In an \(LDL^{\top}\) factorization, the upper-left \(k\times k\) block factors using the upper-left \(k\times k\) block of \(\mathbf{L}\) and the first \(k\) entries of \(\mathbf{D}\). The triangular factors have diagonal entries \(1\), so their determinants are \(1\). The determinant of the diagonal factor is \(d_1\cdots d_k\). Hence \(\Delta_k=d_1\cdots d_k\), and therefore \(d_k=\Delta_k/\Delta_{k-1}\). This relation uses \(\Delta_{k-1}\ne0\), which holds here because it is a product of positive pivots (and \(\Delta_0=1\)).

When a Pivot Is Not Positive

A positive pivot is essential to the positive-definite conclusion. For a symmetric matrix, the same square-completion calculation can still be performed when a pivot is nonzero, but a zero pivot prevents division and a negative pivot supplies a negative square coefficient. Neither outcome gives the positive diagonal matrix in the theorem.

Common Pitfall: The Pivot Order Matters

Do not assume that every symmetric matrix can be processed by dividing by each diagonal pivot in turn. For example, the symmetric matrix \(\begin{bmatrix}0&1\\1&0\end{bmatrix}\) has first pivot \(0\), so the formula involving division by that pivot cannot be used. Its quadratic form is \(2x_1x_2\), which takes negative values, for instance at \((1,-1)^{\top}\). A zero pivot signals that this no-row-exchange procedure has stopped; it does not justify dividing by zero or claiming the matrix is positive definite.

For a positive definite matrix, the situation is different: the block argument proves that each successive Schur complement remains positive definite, so its first diagonal entry is positive. Consequently every pivot in the chosen order exists and is positive. This is the feature that makes completing squares both a proof of positive definiteness and a reliable way to construct the factorization.