PSDdecomposition -- factorization of a positive semidefinite matrix

Synopsis

Usage:

(L,D,P) = PSDdecomposition A
Inputs:
- A, a matrix,
Outputs:
- L, a matrix, nonsingular
- D, a matrix, diagonal
- P, a matrix, permutation matrix

Description

Given a positive semidefinite matrix $A$, this method factorizes it in the form $P' A P = L D L'$, where $P$ is a permutation matrix, $L$ is nonsingular, $D$ is diagonal. If $A$ is a real matrix, this factorization is obtained from its eigenvalue decomposition. For rational matrices we use the LDL decomposition [Golub-vanLoan'89]. The method returns null if $A$ is not positive semidefinite.

i1 : A = matrix(QQ, {{5,3,5},{3,2,4},{5,4,10}})

o1 = | 5 3 5  |
     | 3 2 4  |
     | 5 4 10 |

              3       3
o1 : Matrix QQ  <-- QQ

i2 : (L,D,P) = PSDdecomposition(A)

o2 = (| 1   0   0 |, | 10 0   0 |, | 0 1 0 |)
      | 1/2 1   0 |  | 0  5/2 0 |  | 0 0 1 |
      | 2/5 2/5 1 |  | 0  0   0 |  | 1 0 0 |

o2 : Sequence

i3 : L*D*transpose(L) == transpose(P)*A*P

o3 = true

References: Matrix Computations, Gene Golub and Charles van Loan. Johns Hopkins series in the Mathematical Science (1989), 2 ed., pp. 133-148.

For the programmer

The object PSDdecomposition is a function closure.