Lower Upper Triangle Decomposition of a Symmetric Matrix

Source code mentioned here is available in SourceCodeRepository.

This algorithm shall be an elemantary matrix algebra and can be found in a textbook.

The key is to note that any row operation is equivalent to left-multiplication with a matrix while any column operation is equivalent to right-multiplication with a matrix.

Let L and G be two n by n matrix and G is sysmetric. We use the notation L :: H by meaning that

H=L.G.Transpose[L]

Therefore, let I be the identity matrix, we have

I :: G

because

G=I.G.Transpose[I]

Now we start a row operaion on both matrix I and G, and an additional column operation matrix on G where the column operation matrix is transpose of the row operation matrix. The row operation is to zero the (2,1) entry of G. Because G is sysmetric, the column operation induced by the operation matrix is exactly to zero the (1,2) entry of G. Now we reach, say,

I1 :: G1

where I1 and G1 are the matrix after operation.

Note that G1 is still sysmetric and we go on the row operation to zero the (3,1) entry of G1. Inductively, after all entry in the 1-column is zero except (1,1) entry, we reach a matrix G2 whose (i,1)entry=(1,i)entry=0 for i>1.

We can go on the row operation to zero (i,2)entry for i>2 and the induced column operation shall zero (2,i) entry for i>2

As long as the diagonal of Gi is not zero, the algorithm can work untill G becomes a diagonal matrix. When Gi is diagonal, the Ii is the lower triangle matrix we want and they have the relationship:

Gi=Ii.G.Transpose[Ii]

This algorithm has nothing to do with the positive-definte or negative-definite of G, all it needs is that during the process, the diagonal is not zero.