Positive definite matrix

onako · 2010-03-28 23:59:02

Note the following:
A symmetric matrix is positive definite if:

1. all the diagonal entries are positive, and
2. each diagonal entry is greater than the sum of the absolute values of all other entries in the same row.
...........................................................................
However, the following matrix seems to have Cholesky decomposition (therefore, it is positive definite):
5.000 2.000 3.000 2.000
2.000 3.000 1.000 1.000
3.000 1.000 4.000 -1.000
2.000 1.000 -1.000 7.000

Here, the second condition is not satisfied. Any suggestions on the positive definite matrix criteria?
I would need a simple positive definiteness test. (The above seems simple, but might not be correct/complete).
Thanks

onako · 2010-03-29 23:18:31

Anyone?

Ricky · 2010-03-30 08:56:29

Off hand, I know of no easy computable equivalent condition on positive definite matrices. You could use the criteria and if that fails then check the hard way.

onako · 2010-03-30 23:06:55

The problem is that the hard way is computationally expensive. I would need simple strategy to check positive definiteness of symmetric matrices.
The above criteria seems incomplete. Any suggestions on how to check this relatively easily?

Ricky · 2010-03-31 02:47:10

Sylvester's criterion seems to be your best bet.

onako · 2010-03-31 05:37:37

Good choice, but expensive in terms of the computational time/power. Completion of the first criterion would be better.

Ricky · 2010-03-31 08:16:27

Completion of the first criterion would be better.

You're assuming it's possible. Another option is to use the Cholesky decomposition algorithm. A symmetric matrix is positive definite if and only if it has a Cholesky decomposition, and there exists an algorithm for computing this. Use the algorithm, and if it blows up somewhere (i.e. division by zero or a certain condition is not met like A^(n) = I), then the matrix must not be positive definite.

John E. Franklin · 2010-03-31 08:55:00

I spent a few minutes computing the 4x4 determinant by hand.
I obtained minus 281, -281, a negative number. I didn't check my answers though.
All by hand. (Sylvester says should be positive and smaller upper-left ones)

Ricky · 2010-03-31 15:15:33

John, I've verified that the matrix posted is in fact positive definite. I think you have an error.

onako · 2010-04-01 03:08:24

Actually, I should use the checking prior to invoking the Cholesky decomposition. This means the checking is preparation for Cholesky (further used as a preconditioner for Conjugate Gradient). I could, however, start Cholesky and wait until its eventual completion.

Ricky · 2010-04-01 10:06:03

Actually, I should use the checking prior to invoking the Cholesky decomposition. This means the checking is preparation for Cholesky

I've only glanced at the algorithm, but it seems like it will terminate in a finite number of steps whether or not the matrix is positive definite. Assuming this to be true, the algorithm can be used as a check.

Math Is Fun Forum

#1 2010-03-28 23:59:02

Positive definite matrix

#2 2010-03-29 23:18:31

Re: Positive definite matrix

#3 2010-03-30 08:56:29

Re: Positive definite matrix

#4 2010-03-30 23:06:55

Re: Positive definite matrix

#5 2010-03-31 02:47:10

Re: Positive definite matrix

#6 2010-03-31 05:37:37

Re: Positive definite matrix

#7 2010-03-31 08:16:27

Re: Positive definite matrix

#8 2010-03-31 08:55:00

Re: Positive definite matrix

#9 2010-03-31 15:15:33

Re: Positive definite matrix

#10 2010-04-01 03:08:24

Re: Positive definite matrix

#11 2010-04-01 10:06:03

Re: Positive definite matrix

Board footer