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$

2 Answers 2

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
    Commented May 9, 2020 at 10:52
  • $\begingroup$ No; moreover Choleski is slightly faster than LU and more stable (when $A$ is ill conditioned). $\endgroup$
    – user91684
    Commented May 9, 2020 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
    Commented May 9, 2020 at 17:20
  • $\begingroup$ Can you think of any counterexample to $A>0 \iff D>0$? $\endgroup$
    – Museful
    Commented May 9, 2020 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
    Commented May 10, 2020 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .