# Determining whether a matrix is positive definite from its LU decomposition

Given that $$A=LU$$ where $$L$$ and $$U$$ are (known) lower and upper triangular matrices, is there any simple way to determine whether $$A$$ is positive definite?

### Background

I have been using this algorithm on Wikipedia to compute LU decompositions.

The comment section says:

INPUT: A ... a square matrix having dimension N

OUTPUT: Matrix A is changed, it contains a copy of both matrices L-E and U as A=(L-E)+U such that PA=LU.

I'm not sure what exactly 'E' refers to here, but I understand that 'L' refers to a lower triangular matrix, and 'U' to an upper triangular matrix, and I understand that the algorithm is letting these two cohabit the same square matrix.

I seek to determine whether the original matrix $$A$$ is positive definite. I have a feeling that $$A$$ is positive definite only if $$A$$ is symmetric and (after running the algorithm) all of the diagonal elements are positive. Is this correct? (Or is there some other way to determine whether $$A$$ is positive definite, from its LU decomposition?

### Edit:

If $$A$$ is a symmetric ... positive definite matrix, we can arrange matters so that $$U$$ is the ... transpose of $$L$$. That is, we can write $$A$$ as

$$A = L L^T$$

This decomposition is called the Cholesky decomposition.

Moreover I have read somewhere that a matrix is positive definite if and only if its Cholesky decomposition exists. But I don't know how to put all this together (e.g. what "arrange matters" above means exactly) to determine from the LU decomposition whether the matrix is positive definite.

## 2 Answers

We assume that $$A\in M_n$$ is a real matrix.

There are $$2$$ definitions for $$A>0$$.

i) $$A$$ is symmetric and, for every $$x\not= 0$$, $$x^TAx>0$$.

ii) For every $$x\not= 0$$, $$x^TAx>0$$.

Then ii) is equivalent to i) for the symmetric matrix $$A+A^T$$.

Thus we may assume that $$A$$ is symmetric.

Then the fastest method to see if $$A>0$$ is to use the standard algorithm that calculates the Choleski deomposition of $$A$$.

$$\bullet$$ if the algo. runs completely, then $$A>0$$.

$$\bullet$$ If the algo. stops with an error message, then $$A$$ is not $$>0$$.

• Isn't there a way to go from LU factorization to Cholesky factorization (e.g. via LDU)? I don't know much about it, but it feels like they are tightly related and the conditions for positive definiteness should carry over. – Museful May 9 '20 at 10:52
• No; moreover Choleski is slightly faster than LU and more stable (when $A$ is ill conditioned). – user91684 May 9 '20 at 15:52
• How about $A=LDU=(LD^{1/2})(D^{1/2}U)$ where $L$ and $U$ are unitriangular matrices and $D$ is a diagonal matrix? Isn't that the same result as Cholesky factorization (if $A$ is symmetric)? – Museful May 9 '20 at 17:20
• Can you think of any counterexample to $A>0 \iff D>0$? – Museful May 9 '20 at 17:59
• Ah yes, about the condition $l_{i,i}u_{i,i}>0$, you are right; I forgot this property. I remove my NB. – user91684 May 10 '20 at 6:31

We can determine whether $$A>0$$ by examining the diagonals of $$L$$ and $$U$$.

$$A>0 \iff l_{i,i}u_{i,i}>0 \forall i$$

These products $$l_{i,i}u_{i,i}$$ are the diagonal elements of $$D$$ in the LDU decomposition, and $$A>0\iff D>0$$ as shown here.

(In the algorithm referenced from Wikipedia it is simply a matter of testing whether all diagonal elements in the output are positive.)