Algebraic and Combinatorial Circuits - Models of Computation: Exploring the Power of Computing - page 257

LDL T Factorization of SPD Matrices
Now that we know that the Schur complement S of M is SPD when M is SPD, we can show
that every SPD matrix M has a factorization as the product LDL T of a unit lower triangular
matrix L (each of its diagonal entries is the multiplicative unit of the field

6.5.4

R

), a diagonal

matrix D , and the transpose of L .

THEOREM 6.5.2 Every n × n SPD matrix M has a factorization as the product M = LDL T ,
where L is a unit lower triangular matrix and D is a diagonal matrix.
Proof The proof is by induction on n .For n = 1 the result is obvious because we can write
[ m 1,1 ]=[ 1 ][ m 1,1 ][ 1 ] . Assume that it holds for n ≤ N −

1. We show that it holds for

n = N .
Form the Schur factorization of the N

× N matrix M .Sincethe k × k submatrix M 1,1

of M as well as the n

k submatrix S of M are SPD, by the inductive hypothesis
they can be factored in the same fashion. Let

− k × n −

M 1,1 = L 1 D 1 L 1 , S = L 2 D 2 L 2

Then the middle matrix on the right-hand side of equation ( 6.8 ) can be represented as
M 1,1 = L 1 D 1 L 1

0 0 0 0

L 2 0 S 0 L 2 0 D 2 0

Substituting the above product for the middle matrix in ( 6.8 ) and multiplying the two left
and two right matrices gives the following representation for M :
M =

D 1 L 1

L 1 M − 1

L 1

0 0

1,1 M 1,2

(6.10)

M 2,1 M − 1

L 2

1,1 L 1

L 2 0 D 2 0

Since M is symmetric, M 1,1 is symmetric, M 1,2 = M 2,1 ,and

L 1 M − 1

1,1 M 1,2 = L 1 ( M − 1 1,1 ) T M 2,1 =( M 2,1 M − 1 1,1 L 1 ) T

Thus, it suffices to compute L 1 , D 1 , L 2 , D 2 ,and M 2,1 M − 1

1,1 L 1 .

When n = 2 r and k = n/ 2, the proof of Theorem 6.5.2 describes a recursive procedure,
LDL T [ n ], defined on n

n SPD matrices that produces their LDL T factorization. Figure 6.6
captures the steps involved. They are also described below.

×

The LDL T

•

factorization of the n/ 2

× n/ 2matrix M 1,1 is computed using the proce-

dure LDL T [ n/ 2] to produce the n/ 2 × n/ 2 triangular and diagonal matrices L 1 and D 1 ,

respectively.

1,1 L 1 = M 2,1 L − 1 T D − 1 which may be computed by inverting the
lower triangular matrix L 1 with the operation TRI INV [ n/ 2 ] , computing the product

The product M 2,1 M − 1

•

M 2,1 L − 1 T using MULT [ n/ 2 ] , and multiplying the result with D − 1 using a procedure
SCALE [ n/ 2 ] that inverts D 1 and multiplies it by a square matrix.