LDL decomposition Created 2026-09-24 Updated 2026-11-05
A diagonal-pivot LDL decomposition of a real symmetric matrix has the formwhere is a unit lower triangular matrix and is a diagonal matrix. When the needed scalar pivots are nonzero, symmetric Gaussian elimination computes one Schur complement at a time:In particular, nonzero leading principal minors guarantee this form, and a symmetric positive-definite matrix has positive pivots. Conversely, for every gives for every nonzero vector .
For , take and . General symmetric matrices need more care: 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.[ref]
Linear Equations in the LAPACK Users' Guide by LAPACK project. Computational Routines, Linear Equations: symmetric indefinite diagonal blocks of order one or two
Past exam of the mathematics course of the University of Cambridge 2001 iii Paper 57 4 Solution Created 2026-10-03 Updated 2026-10-14
Use the undirected graph of the symmetric off-diagonal sparsity pattern. Reading the original matrix gives the edgesThis connected nine-vertex, eight-edge graph is a tree. A leaf-removal perfect elimination ordering isThe corresponding lists of remaining neighbors are, in order, . Thus simultaneous row and column permutation to this ordering allows Gaussian elimination without fill-in.
Here are the precise facts that justify the procedure. First, eliminating index makes the remaining entriesOnly pairs of remaining neighbors of can acquire a new nonzero entry. Consequently a vertex whose remaining neighbors form a clique can be eliminated without structural fill. Such a vertex is simplicial. An ordering in which each successive vertex is simplicial is a perfect elimination ordering. The graph characterization says that a graph admits such an ordering if and only if it is a chordal graph, meaning every cycle of length at least four has a chord. A tree has no cycles; more concretely, every nontrivial finite tree has a leaf, and removing a leaf leaves a forest. These statements explain why successive leaf removal works here without having to find a general-purpose chordal ordering.
Second, for a symmetric positive-definite matrix, every diagonal pivot and every successive Schur complement is positive definite. For example, if the first pivot is and its coupling column is , then for any nonzero remaining vector ,Thus no zero pivot requires abandoning the proposed ordering. Since each eliminated vertex here has at most one remaining neighbor, its Schur update changes only a diagonal entry. This proves the claimed fill-free LDL decomposition or Cholesky decomposition for every positive-definite matrix with the given pattern, including cases with additional accidental zeros. It is leaf elimination of a tree-pattern positive-definite matrix.
Past exam of the mathematics course of the University of Cambridge 2002 iii Paper 60 6 Solution 2026-10-14
Sparse Gaussian elimination seeks a direct solution while preserving the advantage of a small number of nonzeros. The main issue is that eliminating unknowns creates new interactions between the remaining unknowns. For a symmetric positive-definite system, simultaneous row and column permutation merely changes the elimination order, and Cholesky decomposition or LDL decomposition can proceed without pivoting. Partition one elimination step asThe remaining system has the Schur complement . It is positive-definite because, for any nonzero , minimizing the positive quadratic form of over the first coordinate gives . This both justifies the next positive pivot and identifies exactly where fill can appear.
The matrix graph of a symmetric sparsity pattern has one vertex per unknown and an edge when is structurally nonzero. At pivot , the updatecan change an entry only when both and are current neighbors of . Thus the elimination graph operation removes and makes its remaining neighbors a clique. Edges absent before this update are fill-in. The graph describes structural or generic nonzeros: special cancellations in the numerical values can reduce the actual fill, but cannot justify omitting possible entries in advance.
A useful global description is the fill-path criterion for symmetric elimination. After a set has been eliminated, remaining vertices are adjacent generically exactly when their original graph contains a path from to with all internal vertices in . The assertion starts with the original edges when is empty. Eliminating the next vertex concatenates two earlier such paths through it; conversely, split any allowed path at the newly eliminated vertex to recover the two earlier connections. This induction explains why sparse long-range couplings may eventually become dense.
The order is decisive. For a star with four leaves, eliminating a leaf only changes the diagonal of its sole neighbor and creates no fill. Repeated leaf elimination preserves this property. Eliminating the central vertex first instead connects all four leaves, creating six edges and a dense four-variable trailing system. This occurs, for example, in a positive-definite star matrix with central diagonal , leaf diagonals and edge entries ; no cancellation removes the new leaf couplings.
The same sparse star graph creates no fill with leaf elimination and six fill edges with central elimination
. Details. For an arbitrary graph, an ordering creates no fill precisely when each pivot's later neighbors are already a clique, namely a perfect elimination ordering. Such an ordering exists exactly for a chordal graph. A chordless cycle of length at least four illustrates the obstruction: its first removed vertex connects its two previously nonadjacent neighbors. Eliminating in a chosen order adds chords until the completed graph is chordal. Thus sparsity of the original matrix alone does not guarantee sparse factors; the graph and its ordering matter together.
If pivot has later neighbors, its column contains factor entries and its symmetric outer-product update costs arithmetic. The total storage is governed by and the work by . A band ordering with matrix bandwidth gives the familiar storage and work, but a narrow profile or graph separator can do better than a single global band. The minimum degree algorithm greedily chooses a current low-degree pivot; it often keeps immediate updates small, but it must account for previously created fill and need not minimize total fill.
Nested dissection instead finds a small vertex separator, recursively eliminates disconnected subdomains, and leaves separator variables until last. For a regular two-dimensional grid with unknowns, a separator has vertices. Its dense final work is , and recursive balanced separation givesAt each level the summed separator-square storage is , giving factor storage over the logarithmic number of levels. These estimates assume the usual geometric separator structure; they are not guarantees for every sparse graph. Independent subdomains also expose parallel work.
In a practical solver a symbolic factorization phase uses the pattern and ordering to allocate factor storage and schedule updates. For the lower-triangular factor, the elimination tree takes the parent of column to be its first later row index containing a structural nonzero. Descendant updates flow towards those later pivots, making the tree useful for dependency scheduling and the organization of the factorization. Compressed sparse storage records only entries and indices; the numerical phase then computes the values, followed by forward and backward substitution. The factors can be reused for many right-hand sides.
Finally, structural efficiency must be balanced with numerical stability. For a nonsymmetric system the pattern can be represented by a directed or bipartite graph, and elimination creates edges from incoming to outgoing neighbors. Separate row and column permutations are possible. A fill-reducing column ordering does not ensure a safe pivot: scaling and partial pivoting may be needed to prevent division by a tiny number and large growth. Such row interchanges can change the predicted fill. Positive-definite symmetric problems avoid this conflict; general sparse solvers must manage it explicitly. Graph-based ordering controls factor sparsity, while pivoting controls numerical safety; an effective sparse factorization needs both.
Past exam of the mathematics course of the University of Cambridge 2008 ib Paper 1 6D Solution Created 2026-09-24 Updated 2026-10-14
A unit lower triangular is invertible. For , , so an LDL decomposition with positive diagonal givesAlso is symmetric. Hence is a positive-definite matrix.
For the specified matrix, comparing entries successively gives , , , , andThusThe last pivot is negative, so this particular factorization is outside the positive-diagonal case proved above. Indeed has , and . There is no positive-diagonal LDL factorization for the printed matrix. The unrestricted LDL decomposition above is nevertheless valid.
Past exam of the mathematics course of the University of Cambridge 2017 ib Paper 4 8C Solution Created 2026-09-24 Updated 2026-10-05
The successive differences of the constant entries give a simple LDL decomposition:For example, entry of is the sum of the first entries of , directly verifying every entry of . Because is an invertible matrix, is strictly positive for every nonzero vector exactly when every diagonal entry of is positive. ConsequentlyAt it is a positive semidefinite matrix and singular; for its quadratic form takes both positive and negative values.
Past exam of the mathematics course of the University of Cambridge 2021 ib Paper 1 5B Solution Created 2026-09-24 Updated 2026-09-25
Apply symmetric Gaussian elimination without row exchanges. At step , let be the leading diagonal entry of the remaining symmetric Schur complement. If , stop and report that is not positive definite. If , use it to eliminate the rest of its row and column. If all steps succeed, this constructs an LDL decompositionwhere is unit lower triangular and has positive diagonal.
The test is correct from first principles. If all , then for every nonzero ,because is invertible. Conversely, if is positive definite, its first pivot is , and completing the square givesChoosing shows that the Schur complement is positive definite. Induction forces every pivot to be positive. This is also Sylvester's criterion.
At step , updating the remaining matrix costs arithmetic operations. Hence the total iswhich proves the existence of the required algorithm.
Since every , the diagonal matrix is invertible. SetThe division is by the diagonal entry of row . Thus is an upper triangular matrix with diagonal entries one and .
To use symmetry without assuming the conclusion, multiply by the matrix inverse of and its transpose:The matrix is symmetric because is a symmetric matrix. It is also an upper triangular matrix, since every factor on the right is an upper triangular matrix. A symmetric upper triangular matrix is diagonal. Its diagonal is exactly , because and have diagonal entries one. Hence , givingThis is the LDL decomposition.
Take the positive square roots of the diagonal entries:The matrix is a lower triangular matrix with positive diagonal, andThis is a Cholesky decomposition. For a nonzero vector , the vector is nonzero because is invertible. ThereforeHere is the Euclidean norm. Thus is a positive-definite matrix.
