0
$\begingroup$

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:

Elsewhere on the same Wikipedia page it says

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$ – Museful May 9 '20 at 10:52
  • $\begingroup$ No; moreover Choleski is slightly faster than LU and more stable (when $A$ is ill conditioned). $\endgroup$ – user91684 May 9 '20 at 15:52
  • $\begingroup$ 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)? $\endgroup$ – Museful May 9 '20 at 17:20
  • $\begingroup$ Can you think of any counterexample to $A>0 \iff D>0$? $\endgroup$ – Museful May 9 '20 at 17:59
  • 1
    $\begingroup$ Ah yes, about the condition $l_{i,i}u_{i,i}>0$, you are right; I forgot this property. I remove my NB. $\endgroup$ – user91684 May 10 '20 at 6:31
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.