# How to Derive U from L in O(n^2) Complexity?

• MRTRACKER
In summary, the conversation discusses finding a method to calculate an upper triangular matrix U from a lower triangular matrix L such that L'*L=U'*U. The method involves using eigendecomposition on L'L to derive an orthogonal matrix M and a diagonal matrix D. The computational complexity of this method is O(n^3). The conversation also mentions the possibility of using a Cholesky factorization method, but it is likely that the fastest algorithm for this problem will still have a complexity of O(n^3).
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.

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 :)

Petr Mugver said:
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 :)

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:
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.

AlephZero said:
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.

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

## 1. What is a triangular matrix?

A triangular matrix is a special type of matrix where all the elements above or below the main diagonal are equal to zero. Based on the position of the zeros, triangular matrices can be classified as upper triangular (zeros below the main diagonal) or lower triangular (zeros above the main diagonal).

## 2. How is a triangular matrix calculated?

To calculate a triangular matrix, we can use various methods such as Gaussian elimination, LU decomposition, or Cholesky decomposition. These methods involve performing row or column operations on the original matrix to transform it into a triangular form.

## 3. What are the applications of triangular matrix calculation?

Triangular matrices are commonly used in linear algebra and have various applications in fields such as engineering, computer science, and physics. They are used to solve systems of linear equations, perform matrix inversion, and represent data in a compressed form.

## 4. Can a non-square matrix be triangular?

No, a non-square matrix cannot be triangular as it does not have a main diagonal. Triangular matrices are only defined for square matrices where the number of rows and columns are equal.

## 5. What is the significance of triangular matrix calculation in machine learning?

In machine learning, triangular matrix calculation is used in algorithms such as Cholesky decomposition and QR decomposition to solve optimization problems and perform matrix factorization. This helps in reducing computational complexity and improving the efficiency of machine learning algorithms.

Replies
4
Views
2K
Replies
5
Views
3K
Replies
16
Views
890
Replies
2
Views
3K
Replies
3
Views
2K
Replies
2
Views
885
Replies
9
Views
2K
Replies
1
Views
2K
Replies
0
Views
391
Replies
1
Views
1K