# Cholesky decompostion: upper triangular or lower triangular?

Can I find and use $U$ such that

$$A = U U^{T}$$

where $U$ is an upper triangular matrix, to find a solution instead of finding $L$ such that $A = L L^{T}$ (where $L$ is a lower triangular matrix) to solve $Ax=b$ using Cholesky factorization? If not, what is the correct way of using Cholesky factorization?

• Maybe I'm missing something, but I'm wondering who gave this a +1? – suvrit Dec 1 '16 at 17:46
• Reverse the order of rows and columns, and you turn a lower triangular factorization to an upper... – Robert Israel Dec 1 '16 at 19:08

You can use $A=UU^T$ to solve linear equations. However it is not what people call Cholesky decomposition. Also the algorithm is less intuitive.
Note: Both decompositions are equivalent. Let $P$ the permutation which reverses the order, which is symmetric. Then, $\tilde A = PAP$ is symmetric and positive definite iff $A$ is. In particular we have the cholesky decomposition $$\tilde A = PAP = (PUP)(PUP)^T.$$
• Is it possible to apply proposed approach in order to find a matrix $B$ such that: $A=BB^T$? where $B$ is the positive definite matrix? – Nick Dec 6 '16 at 8:25
• @Nick I don't think so. Is $B$ supposed to symmetric? For the symmetric root, you could consider the eigen value decomposition of $A$. – user251257 Dec 6 '16 at 8:36
• I have only one assumption on $B$, it's should be the positive definite matrix. – Nick Dec 6 '16 at 8:40
• How do you get the Cholesky factorization from $A=UU^T$? – Ion Sme Jun 11 '18 at 4:15
We can modify the original Cholesky algorithm to obtain an upper-triangular version. According to https://en.wikipedia.org/wiki/Cholesky_decomposition#The_Cholesky_algorithm, the original method starts at the top left and goes down to the bottom right by using this recursion step $$A_i = L_i A_{i+1} L_i^T$$, where $$L_i$$ is a lower-triangular matrix. The $$A_i$$ in the original version is created in a top-down fashion.
The upper-triangular version of the algorithm starts at the bottom right and goes up to the top left using a similar recursion $$A_i = U_i A_{i+1} U_i^T$$, where $$U_i$$ is an upper-triangular matrix. The $$A_i$$ matrix is created in a bottom-up fashion as $$A_{i}=\begin{bmatrix} B & b & 0 \\ b^T & a & 0 \\ 0 & 0 & I_{i-1} \end{bmatrix}.$$ The $$A_{i+1}$$ matrix is defined as $$A_{i+1}=\begin{bmatrix} B-\frac{1}{a}bb^T & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & I_{i-1} \end{bmatrix}.$$ The $$U_i$$ matrix is defined as $$U_{i}=\begin{bmatrix} I_{n-i} & \frac{1}{\sqrt{a}}b & 0 \\ 0 & \sqrt{a} & 0 \\ 0 & 0 & I_{i-1} \end{bmatrix}.$$ We can check that this expression $$A_i = U_i A_{i+1} U_i^T$$ holds, which gives an upper-triangular version of the Cholesky algorithm ($$A=UU^T$$, where $$U=U_1U_2\dots U_n$$ is an upper-triangular matrix).