# Triangular matrix calculation

1. Jul 12, 2011

### MRTRACKER

The problem is :

Given a lower triangular matrix L, how to calculate a upper triangular matrix U, such that L'*L=U'*U where L' and U' are transpose of matrix L and U respectively?
I am looking for a method which has less computational complexity, i.e., O(n^2) if the dimension of L is n.

2. Jul 12, 2011

### Petr Mugver

L'L is symmetric positive definite, so it can be diagonalized with an orthogonal matrix M
(that is, M'L'LM = D where M^-1 = M' and D is diagonal with positive eigenvalues). So:

L'L = U'U
MDM' = U'U
D = M'U'UM = (UM)'(UM)

so, just put

UM = E
U = EM'

where E is the diagonal matrix whose eigenvalues are the square roots of the corresponding eigenvalues of D.

Hope it's clear :)

3. Jul 12, 2011

### MRTRACKER

Thank u very much.
From your reply, I see the point is to derive M and D by eigendecomposing on L'L. In general , the computational complexity of eigendecompose is O(N^3). Do you have other ideas that could achieve O(N^2)?
The other thing is your method can not make sure U is an upper triangular matrix.

P.S., I knew the QR decomposition can solve this problem, but QR requires O(N^3) in MATLAB, i.e., [Q, U]=qr(L).

Last edited: Jul 12, 2011
4. Jul 13, 2011

### AlephZero

You can do this in a similar way to the standard Cholesky factorization of a matrix, except you start with the last term and work backwards.

Let $A = L' L = U' U$ and multiply out the two products.

The last element $A_{n,n}= U_{n,n}^2$ so you can find $U_{n,n}$ in terms of the elements of $L$.

The element $A_{n-1,n}$ depends only on $U_{n-1,n}$ and $U_{n,n}$, so you can use it to find $U_{n-1,n}$.

You work backwards along the last row to $A_{1,n}$, then work along the next row starting with $A_{n-1,n-1}$, and finish at $A_{1,1}$

If you haven't seen this before, it might help to write out the matrix products for 3x3 or 4x4 matrices in full.

This algorithm suggests very strongly that the fastest algorithm is $O(n^3)$, because if there was a faster algorithm, the same idea could be used for any matrix factorization.

5. Jul 14, 2011

### MRTRACKER

From this point, I might stop to looking for a $O(n^2)$ solution.