Editing Cholesky decomposition (section)

== LDL decomposition ==

A closely related variant of the classical Cholesky decomposition is the LDL decomposition,

<math display=block>\mathbf{A} = \mathbf{L D L}^*,</math>

where {{math|'''L'''}} is a [[Unitriangular matrix|lower unit triangular (unitriangular)]] matrix, and {{math|'''D'''}} is a [[diagonal matrix|diagonal]] matrix. That is, the diagonal elements of {{math|'''L'''}} are required to be 1 at the cost of introducing an additional diagonal matrix {{math|'''D'''}} in the decomposition. The main advantage is that the LDL decomposition can be computed and used with essentially the same algorithms, but avoids extracting square roots.<ref name="kri">{{cite conference|last=Krishnamoorthy|first=Aravindh|author2=Menon, Deepak|contribution=Matrix Inversion Using Cholesky Decomposition|title=2013 Signal Processing: Algorithms, Architectures, Arrangements, and Applications (SPA)|pages=70–72|publisher=IEEE|arxiv=1111.4144|url=https://ieeexplore.ieee.org/document/6710599}}</ref>

For this reason, the LDL decomposition is often called the ''square-root-free Cholesky'' decomposition. For real matrices, the factorization has the form {{math|1='''A''' = '''LDL'''<sup>T</sup>}} and is often referred to as '''{{math|LDLT}} decomposition''' (or {{math|'''LDL<sup>T</sup>'''}} decomposition, or '''LDL′''').  It is reminiscent of the [[eigendecomposition of a matrix#Real symmetric matrices|eigendecomposition of real symmetric matrices]], {{math|1='''A''' = '''QΛQ'''<sup>T</sup>}}, but is quite different in practice because {{math|'''Λ'''}} and {{math|'''D'''}} are not [[similar matrices]].

The LDL decomposition is related to the classical Cholesky decomposition of the form {{math|'''LL'''*}} as follows:

<math display=block>\mathbf{A} = \mathbf{L D L}^* = \mathbf L \mathbf D^{1/2} \left(\mathbf D^{1/2} \right)^* \mathbf L^* =
\mathbf L \mathbf D^{1/2} \left(\mathbf L \mathbf D^{1/2}\right)^*.</math>

Conversely, given the classical Cholesky decomposition <math display=inline>\mathbf A = \mathbf C \mathbf C^*</math> of a positive definite matrix, if {{math|'''S'''}} is a diagonal matrix that contains the main diagonal of <math display=inline>\mathbf C</math>, then {{math|'''A'''}} can be decomposed as <math display=inline>\mathbf L \mathbf D \mathbf L^*</math> where
<math display=block> \mathbf L  = \mathbf C \mathbf S^{-1} </math> (this rescales each column to make diagonal elements 1),
<math display="block"> \mathbf D  = \mathbf S\mathbf S^*. </math>

If {{math|'''A'''}} is positive definite then the diagonal elements of {{math|'''D'''}} are all positive.
For positive semidefinite {{math|'''A'''}}, an  <math display=inline>\mathbf L \mathbf D \mathbf L^*</math> decomposition exists where the number of non-zero elements on the diagonal {{math|'''D'''}} is exactly the rank of {{math|'''A'''}}.<ref>{{Cite thesis |last=So |first=Anthony Man-Cho |title=A Semidefinite Programming Approach to the Graph Realization Problem: Theory, Applications and Extensions |date=2007 |url=http://www.se.cuhk.edu.hk/~manchoso/papers/thesis.pdf |language=en |type=PhD| at=Theorem 2.2.6}}</ref>
Some indefinite matrices for which no Cholesky decomposition exists have an LDL decomposition with negative entries in {{math|'''D'''}}: it suffices that the first {{math|''n'' − 1}} [[Minor (linear algebra)#Other applications|leading principal minors]] of {{math|'''A'''}} are non-singular.<ref>{{harvtxt|Golub|Van Loan|1996|loc=Theorem 4.1.3}}</ref>